A basic step towards flexibility in workflow systems is the consistent and effective management of workflow evolution, i.e. of changing existing workflows while they are operational. One of the most challenging issue is the handling of running instances when their schemata are modified: simple solutions can be devised, but they often imply losing all the work done or failing in capturing the advantages offered by workflow modifications; this is unacceptable for many applications. In this paper we address the problem of workflow evolution, from both a static and a dynamic point of view. We define a complete, minimal, and consistent set of modification primitives that allow modifications of workflow schemata and we introduce a taxonomy of policies to manage evolution of running instances when the corresponding workflow schema is modified. Formal criteria are introduced, based on a simple workflow conceptual model, in order to determine which running instances can be transparently migrated to the new version. A case study, relating the assembling of a desktop computer, will exemplify the introduced concepts.
