|
|
|
In the beginning of the new millennium, enterprises distributed over space, time, and capability will closely interact to deliver products and services. The Internet and the Web may work as the primary communication platform, but sophisticated workflow systems, perhaps integrated in ERP software, are needed for the success of that business model. These systems must include time management capabilities in order to satisfy time constraints among the different activities involved in the processes.
This paper provides a good overview of the issues involved in time modeling in production workflows, and a useful comparison with similar problems in project management, job-shop scheduling, and constraint reasoning in Artificial Intelligence. I also see two main contributions, the first being a quite general classification and formal modeling of temporal constraints in workflows, and the second is a polynomial algorithm to compute longest/shortest workflow instances. Time constraints are divided into "duration constraints", which limit the duration of specific tasks to a range of values ([min,max]), "limited duration constraints" which restrict the overall duration of a process in the model, "interdependent constraints" which limit the time distance between two tasks in the workflow, and "deadline constraints" which limit the start or end of a task to certain instants in time. All, except this last type of constraints, express "relative" values in time, essentially independent on the time the workflow is instantiated. "Duration constraints" are given a first class citizenship in the workflow model, since any other constraint may be added to the model only if it can be satisfied considering any combination of values in the range admitted by duration constraints, and considering the structure of the workflow. This is essentially what characterizes the notion of consistency in a workflow, as defined by the authors, with respect to the same notion in different contexts. Despite the fact that there is no universally accepted standard to represent workflows, the formalism adopted in this paper is quite expressive, allowing so called "AND/OR split" and "joins" to describe the flow of information.
The algorithm to compute the shortest/longest workflow instances can also be used to compute the time distance among a pair of specific tasks, and it is derived from standard graph algorithms (shortest-path partitioning) by taking into account the workflow structure (e.g., the distance may have to take into account parallel paths, conditional branches, etc., which can appear in workflow instances) and distance constraints. The computed distances are then used to determine the consistency of other types of constraints with respect to duration ones.
Among interesting open problems, I see: (i) Relaxing the current limitation on interdependent constraints, so that they can be considered for consistency also when defined between parallel or adjacent tasks; (ii) When inconsistency is detected, how can we find a minor tightening of some duration constraints that would lead to a consistent workflow? (iii) Introduce constraints in terms of different time granularities. About related work, see my review of [2];[3] is not specifically workflow related but may help with respect to point (iii) above, and [4] is a collection of papers giving a good overview of current issues in workflow management.
Copyright © 2000 by the author(s). Review published with permission.