Automatic construction of simple artifact-based business processes

Almost all medium- and large-scale businesses rely on electronic workflow systems to manage their business processes. A key challenge is to enable the easy re-use and modification of these workflow schemas and their piece-parts, so that they can be adapted to new business situations. This paper describes an approach for automatic construction (and thus, evolution) of a workflow schema that satisfies a specified condition (or "goal"), starting from a set of basic building block services (or "tasks"). We use a workflow model based on "business artifacts", which represent key (real or conceptual) business entities, and include both the business-relevant data about them and a specification of their lifecycle, that is, how they can evolve over time as they move through the workflow as the result of services being applied to them. This paper uses a declarative form of artifact-centric workflow. The services are non-deterministic, which corresponds to the intuition that humans performing the services may rely on information that is not modeled within the framework. We study the problem of, given a goal to be achieved, automatically finding the "maximal" workflow schema that has the following property: every execution is either complete or can be completed, and every complete execution satisfies the goal. We also study a complimentary problem, in which exception-handling is used to deal with executions that would otherwise not complete successfully. These problems are non-trivial because the workflow services are non-deterministic. This paper provides a general framework for studying these problems, and shows a tight relationship between workflow systems specified using logics that permit quantifier elimination and the ability to construct maximal schemas with the desired properties. The paper then studies a restricted setting to provide insights into complexity issues. Even in the restricted setting, the problem of testing properties of maximal workflows is PSPACE-complete. Copyright 2009 ACM.