Intelligent Workflow - State of the Art in Workflow

This summary of our literature search in the area of workflow is intended as an introduction to the basic concepts and a statement about exisiting achievements and challenges within the field.

The first section gives the overview of the problems addressed by the workflow community and the basic concepts behind the workflow solution. The summary then divides the technical state of the art discussions into 2 broad fields:

Process modeling techniques and tools including process specification languages
Workflow management systems often referred to as workflow engines

Overview of Workflow Domain

Workflow is a domain that has evolved from several fields, business management, modeling, simulation and, to a lesser extent, planning and control. It has primarily evolved from the need to understand, to organise and, often ultimately, to automate the processes on which a business is based. However, it can also be characterized by the analysis and automation of processes of any kind involving combinations of humans and machine-based activities, particularly information intensive activities. Workflow, in general, is defined by the Workflow Management Coalition (WfMC) as

"The automation of a business process, in whole or part, during which documents, information or tasks are passed from one participant to another for action, according to a set of procedural rules." (WfMC '96)

We have emphasised the work business in the above definition because we see workflow as being applicable to many types of process not only business processes and therefore the techniques of workflow management as applicable to a wide variety of coordination and control problems. However, this summary will concentrate on the evolution of workflow within the business management domain as it dominates the literature.

In a final section we will explore the implications of policy and technologies being developed to allow effective statement of policy and integration with the emerging workflow tools and techniques. Figure 1 below is adapted from one by the WfMC in its Reference Model (WfMC '94)

Figure 1: Architecture for Current Workflow Management System Technology

Process Modeling Tools and Techniques

Abstract or graphical representations of an organization's processes are called "process model". Process models are an excellent tool for both the analysis and reengineering. However, they also form the basis of most automated workflow management systems. The purpose of process modeling is to ``produce an abstraction of a process (model) that serves as a basis for the workflow specification'' [Cichocki etal. 98]. Process models can be used for improved human understanding of operations within a domain, or to assist with analysis or re-engineering. Additionally, they can serve as the basis for automated workflow control. Modeling as a discipline had been around for some time and there are three basic approaches to modeling a process:

communication-based models
artifact-based models
activity-based models

Communication-based methodologies are based on "The Winograd/Flores Conversation for Action Model" (Winograd and Flores '87). An action in a workflow is represented by the communication between customer and performer. In artifact-based methodologies objects, or artifacts, are created, modified and used during the process and thus the model is based on work products and their paths through a series of workflow activities. An increasingly comkmonly used methodology in the workflow management domain is activity-based modeling. Here the overall process is decomposed into tasks that are ordered based on the dependencies among them. This model can most easily be transfered into a workflow specification. However, many technicians use a combination of these methodologies producing a set of models for an organizational process based on an information flow model (communication-based) a capabilities model (artifact-based) and a process-model (activity-based).

A process specification basically an activity-based model of a process. The WfMC has constructed a glossary of terms, (WfMC '96), from which Figure 2 the following diagram indicates the relationship between terminology.

Figure 2: WfMC Glossary of Workflow Terms There have been several specification languages used to construct process models. Here is a list of a few:

The Process Interchange Format (PIF)

PIF is built on top of the Knowledge interchange Format (KIF), a product of the ARPA-sponsored Knowledge Sharing Effort. Pif adds constructs specifically tailored for capturing typical process information. For example, it allows a complex process to comprise a number of distinct activities linked together by successorrelations. PIF is designed as a "least common denominator" among process modeling languages and as such has many shortcomings.
The Enhanced Process Interchange Format (EPIF)

EPIF was developed at Knowledge Based Systems Inc, as a "beefed up" version of PIF. Thus, it distinguishes between an activity and the roles it can play in distinct processes and it also provides explicit representation of activity and process instances.
The Process Specification Language (PSL)

PSL is under development by a National Institute of Standards and Technology (NIST) project
IDEF3 Process Modeling and Simulation

The name IDEF originates from the Air Force program for Integrated Computer-Aided Manufacturing (ICAM) which developed the first ICAM Definition, or IDEF, methods. The IDEF3 Process Description Capture Method was created specifically to capture descriptions of sequences of activities. The primary goal of IDEF3 is to provide a structured method by which a domain expert can express knowledge about the operation of a particular system or organization. It is probably the most commonaly used formalism for the modeling of military processes.
Verb/Noun Phrase/Qualifier Phrase (VNQ) Methodology (Drabble '98)

Developed to capture the capabilities of agents within the process. Each agent is capable of a variety of activities which can be described using a verb to classify the type of activity, a Noun Phrase to identify the artifacts (or information products) on which the activity is performed and a Qualifier phrase to indicate how the activity is performed on this artifact.

Other examples of representations or process modeling schema include CIMOSA(Kosanke'93), Petri Nets(Murata '89) and Finite State Automata(Peluso et al.'94). These like IDEF3 are based on the input-process-output paradigm in contrast to speech-act or communication paradigm.

There have also been significant development in recent years in the availablity of tools to aid in the creation and definition of "business" processes. These tools allow the user to describe a process usually using a mixture of graphical and textual building blocks. Thee resulting representation can then be easily translated into a process specification language. Examples of such systems include :

ProCap/ProSim

ProCap and ProSim are process modeling products that enableusers to capture, document, and analyze processes. Both ProSim and ProCap are based on IDEF3, a government-endorsed, standard process modeling method. These products are from KBSI.
ActionWorkflow Analyst

A Business Process mapping tool for modeling and analyzing business processes from Action Technologies Inc.,. This tool is based on the communication-based methodology of(Winograd and Flores '87).
METEOR Designer

The METEOR Designer is a process modeling tool from LSDIS and can be used in conjunction with the WEBWORK enactment system. It is an activity-based system.

Workflow Management Systems (Workflow Engines)

The role of a workflow management system is to provide the services required for automating workflow processes. WFM systems can be characterized by the following functional components:

modeling and representation of workflow processes and their constituent activities
selection and instantiation of processes for activation in response to a user request or key events
scheduling of activities to agents and resulting tasking of the agents
monitoring and adaptation of executing processes

At the heart of a WFM system lies a library of templates that encode explicit process models for the relevant problem domain. Templates can be represented as explicit sets of tasks or activities to be undertaken, or more abstractly as collections of constraints on allowed activity. Activities can encompass a broad array of operations, including transmission of data, tasking of software agents, or communication with human operators. As reflected in Figure 1, process modeling and representation are typically limited to build time within current WFM technology. However, process creation and adaptation will inevitably migrate from build time to runtime as application domains demand flexible adaptation to environment dynamics.

Templates are selected for activation based on current tasking and environmental conditions. Selected templates can be tailored to a range of situations through appropriate instantiation of template variables. Typically, activation results in the addition of the constituent activities of the instantiated template to an activity list, which contains information about all current and pending tasks. As part of activation, resource allocation is performed for new activities based on current and projected resource availability. These activities are then scheduled in accordance with temporal sequencing constraints specified within the process template

The term enactment is used generally to refer to the execution and ongoing management of activated processes. For many domains, process execution will occur within highly unpredictable and dynamic operating environments. For this reason, enacted processes must evolve and adapt over time in response to a number of factors, including changes in the environment, the addition of new tasks, and partial execution results. Monitoring plays a critical role during enactment, to detect key events that may necessitate adaptations to current processes, or enactment of new or different processes. Similarly, process templates should evolve over time, to reflect improved models of the domain obtained by analyzing information gathered from previous enactment episodes.

The Workflow Engine

A workflow engine provides the runtime environment for activating, managing, and executing workflow processes. Different models for workflow engines can be employed. The WfMC focuses on a paradigm in which the engine instantiates a workflow specification, decomposes it into taskable activities, and then allocates activities to processing entities for execution. This approach distinguishes between the process definition, which describes the processes which may be executed, and the process instance, which is the actual enactment (execution) of the process. This paradigm is referred to as the scheduler-based paradigm [Cichocki etal. 98].

The implementation and deployment of the scheduler-based approach to workflow can be described in terms of a state transition machine. Individual process or activity instances change state in response to workflow engine decisions or external events, such as the completion of an activity. Thus, to give a few example states, a process instance may be initiated once selected for enactment, active after at least one of its activities has been started, suspended (perhaps waiting for some event), or completed. Similarly, an activity may be inactive, active, suspended, or completed. It is the role of the workflow engine to manage this state transition machine, selecting processes to be instantiated, initiating activities by scheduling them to processing components, and controlling and monitoring the resulting state transitions. The workflow engine must also implement the rules that govern the transitions between tasks, updating the processes as tasks complete or fail, and taking appropriate actions in response.

The scheduler-based paradigm is the most common, and as such will be the focus within this report. However, two alternative paradigms for enactment are worth mentioning, namely data-flow and information pull [Cichocki etal. 98].

The data-flow paradigm views the workflow as a repository for data that is passed between processing components according to sets of rules, current situation, and history. Thus, decision-making is inherently decentralized. The data-flow paradigm is well-suited for domains where the workflows tend to be partially specified, dynamic, and goal oriented. Examples of these types of domains include some database management systems or some administrative domains. While not a heavily explored paradigm, there has been interesting recent work (for examples, INCAs [Barbera et al '96]).
The information pull paradigm originated with the network and information management fields, where the requirement for information drives the creation and enactment of processes. This is a relatively new area of research in the workflow domain [Hackathorn '97].

Process Selection

One key responsibility of the workflow engine is to manage the selection and instantiation of process templates. The engine will respond to some stimulus (i.e., a triggering event) by selecting a suitable process from the library of templates. Examples of possible triggering events include arrival of a new user request, generation of a product by an already active process, or even the passage of time. The workflow engine manages the instantiation of the relevant process. There may be alternative applicable processes that must be compared to the triggering conditions and selected appropriately. In many existing WFM systems this task is trivial, as there is no or little choice among processes given the predefined stimulus for enactment. But there are domains where there may be many, or even no, directly applicable and valid processes for a given stimulus, thus requiring process selection, adaptation, or even dynamic process creation.

Task Allocation

Once a process is instantiated, the workflow manager forwards activities to an activity list manager to control the tasking of processing entities for the activities. An activity is assigned to a processing entity according to the capability and availability of the entity and temporal and sequencing constraints of the activity. This allocation task can be viewed as a scheduling problem. Thus, the workflow engine takes a centralized role in coordinating the operation of processing entities. The activity list manager can be implemented as a simple in-tray of work items or a complex set of agenda-based load balancing and interrelated work assignments with complex supervisory roles.

Scheduling techniques within workflow management systems have employed straightforward enumerative or heuristic-based algorithms to date. As the complexity of WFM domains increases, more sophisticated approaches that provide robust reactive scheduling will be critical to accommodate processing entities that require some autonomy, can be tasked by other workflow managers, may break down, or have variable capabilities. For example, there has been some work on exploiting the dependencies between activities within the workflow task allocation problem [Attie et al.'96].

Enactment Control, Execution Monitoring, and Failure Recovery

The workflow engine must maintain all the knowledge and internal control data to identify the states of each of the individually instantiated activities, transition conditions, connections among processes (for example, parent/child relationships), and performance metrics. The WfMC defines two types of data relevant to the control and monitoring of workflow processes:

Workflow Control Data: encompasses state information about processes, activities, and possibly performance criteria. It is internal information managed directly by the workflow engine.
Workflow Relevant Data: is external information used by the WFM system to determine when to enact new processes and when to transition among states within enacted processes.

There has been a significant amount of work on control within workflow enactment systems, based primarily on state transition mechanisms (as described above) and transaction processing. However, current-generation WFM systems have limited abilities to recover from failures, with many simply assuming that operations will complete successfully. Workflow failures may result from a processing entity not completing a task correctly or on time, or by an unexpected event in the environment. WFM systems should provide a variety of recovery mechanisms, from the clean termination of a process to the adaptation of the process to the failure.

Work in this area to date has focused on the use of transactional methods to ensure data integrity, especially when concurrent activities must share data. For example, most WFM systems offer only basic locking mechanisms to protect data, although there has been some work on longer-lived transactions [Garcia-Molina et al `90], [Reuter '89], [Mohan et al `95]. These approaches focus on returning the state of execution to a previously known safe state. Two popular techniques are checkpointing and roll-back.

Checkpointing schemes rely on the use of log files that store safe states; when problems occur, the system can be reset to the most recently available safe state and processing restarted.
Roll-back schemes [Eder and Liebhart `95] rely on the availability of invertible actions. When a problem occurs, the effects of actions are undone by employing their inverses in reverse order.

These approaches, while suitable for certain forms of data-driven workflow, are inadequate for more general domains that involve highly dynamic environments in which the world changes continuously and unpredictably, and in which actions may not be undoable. More powerful and flexible methods for failure recovery are required in order for workflow technology to be effective in a broader range of application domains. Specific requirements include the ability to adapt processes at runtime in response to failures or changes in situation, and to accommodate open-ended activities.

Representative Workflow Management Systems

A diverse set of commercial and academic WFM products is currently available. Here, we describe several key systems that span a range of approaches and capabilities.

MENTOR [Wodtke et al. `96], [Wodtke and Weikum '97]

is a WFM system aimed at large-scale applications. It adopts a typical WfMC approach with workflow being defined in a specification formalism and transformed into distributed runtime executable workflow. An interesting contribution is that the transformation involves a semantic partitioning of a state chart to produce components that can be executed on different processing entities. This system has demonstrated that state and activity charts are suitable as a workflow specification formalism. As yet, MENTOR cannot support dynamic modification of workflow specifications.

WIDE [Ceri et al.`97]

is a distributed architecture for workflow management. WIDE uses enhanced database technology as the basis for its workflow management system and focuses on extended transaction management. It provides reactivity through the use of a decoupled rule execution model. Rule execution is divided into scheduling and interpretation of rules. Triggers inserted into the database management system cause events to be noticed. The scheduler inspects the event database and matches the event to the rules, which are then recorded in a to-execute list and interpreted for execution. WIDE is distinguished by its exploration of distributed WFM, and its sophisticated transactional capabilities. It adopts a two-layered transactional model: the upper layer provides global transactions with loose semantics and the lower provides strict, more conventional, transactional semantics. The two layers are orthogonal, providing one possible approach to long-lived transactions.

MIGRATING WORKFLOWS [Cichocki etal. 98]

As mentioned earlier, some researchers have been exploring a data-flow paradigm as an alternative to scheduler-based workflow. Influenced by INCAs [Barbera et al '96], the Migrating Workflows system has been implemented based on

a migrating workflow containing a business process specifying services required and desired sites using event-condition-action rules
sites that offer services to workflows that visit them, each with its own set of policies and rules
history, recovery information, and accountability logs for each workflow

This effort is distinguished by its emphasis on reactivity and robust handling of failure.

METEOR [Miller et al '98], [Sheth '97], [Sheth and Kochut '97]

METEOR (Managing End To End OpeRations) provides a range of products, including the METEOR Designer, the WEBWORK enactment system, and ORBWork, all grounded in the activity-based paradigm. It addresses the problem of compound transactions through a two-phase commitment coordinator, and provides a platform for experimentation with algorithms related to workflow, particularly tasking algorithms.

The Role of Policy

References

Workflow Management Coalition (1994) "Workflow Management Coalition: Reference Model", Document Number WFMC-TC-1011, Document Status - Issue 2.0, WfMC, Avenue Marcel Thiry 204, 1200 Brussels, Belgium.
Workflow Management Coalition (1996) "Workflow Management Coalition: Terminology and Glossary", Document Number WFMC-TC00-1003, Document Status - Issue 1.1, WfMC, Avenue Marcel Thiry 204, 1200 Brussels, Belgium.
Brian Drabble, Terri Lydiard, and Austin Tate (1998) "Workflow Support in the the Air Campaign Planning Process" in the proceedings of the Fourth International Conference on Artificial Intelligence Planning Systems (AIPS '98) workshop on Collaborative Planning, Pittsburgh.
Terry Winograd and Fernando Flores. (1987). Understanding Computers and Cognition, Addison-Wesley.
K. Kosanke (1993) "CIMOSA: Open System Architecture for CIM", Springer Verlag
T. Murata, (1989) "Petri Nets: Properties, Analysis and Applications" Proceedings of the IEEE 77,4, April, 541-580.
E.Peluso, J.Goldstine, S. Phoha, S.Sircar, M. Yukish, J.Licari and I.Mayk. (1994) "Hierarchical Supervision for the Command and Control of Interacting Automata" In Proceedings of the Symposium on Command and Control Research.
A. Cichocki, A. S. Helal, M. Rusinkiewicz, and D. Woelk. Workflow and Process Automation: Concepts and Technology. Kluwer, 1998.
D. Barbera, S. Mehrotra, and M. Rusinkiewicz. INCAs: Managing dynamic workflows in distributed environments. Journal of Database Management, 7(1), 1996.
R. Hackathorn. Publish or perish. Byte, September:65-72, 1997.
P. Attie, M. Singh, E. Emerson, A. Sheth, and M. Rusinkiewicz. Scheduling workflows by enforcing intertask dependencies. Distributed Systems Engineering Journal, 3, 1996.
H. Garcia-Molina, J. K. D. Gawlick, K. Kleissner, and K. Salem. Coordinating multi-transaction activities. Technical Report CS-TR-247-90, Princeton University, 1990.
C. Mohan, D. Agrawal, G. Alonso, A. E. Abbadi, R. Gunthor, and M. Kamath. Exotica: A project on advanced transaction management and workflow systems.
A. Reuter. Contracts: A means for extending control beyond transaction boundaries. In In Proceedings of Third International Workshop on High Performance Systems, 1989.
J. Eder and W. Liebhart. The workflow activity model WAMO. In Proceedings of Third International Conference on Cooperative Information Systems, Vienna, Austria, 1995.
D. Wodtke and G. Weikum. A formal foundation for distributed workflow execution based on state charts. In Proceedings of the IEEE International Conference on Data Engineering, 1997.
D. Wodtke, J. Weissenfels, G. Weikum, and A. Dittrich. The Mentor project: Steps towards enterprise-wide workflow management. In Proceedings of the IEEE International Conference on Data Engineering, New Orleans, LA, 1996.
S. Ceri, P. Grefen, and G. Sanchez. WIDE - a distributed architecture for workflow management. In Proceedings of the Seventh International Workshop on Research Issues in Data Engineering, Birmingham, England, 1997.
J. Miller, D. Palaniswami, A. Sheth, K. Kochut, and H. Singh. Webwork: Meteor's web-based workflow management system. Journal of Intelligent Information Systems, 10(2):1-30, 1998.
A. Sheth. From contemporary workflow process automation to adaptive and dynamic work activity coordination and collaboration. In Proceedings of the Workshop on Workflow Management in Scientific and Engineering Applications, Toulouse, France, 1997. (keynote talk).
A. Sheth and K. Kochut. Workflow applications to research agenda: Scalable and dynamic work coordination and collaboration systems. In Proceedings of the NATO ASI on Workflow Management Systems and Interoperability, Istanbul, Turkey, 1997.

Bibliography

T. White and L. Fischer, Eds. (1994) "The Workflow Paradign. Future Strategies, Book Division, 909 Marina Village Parkway, Alameda, CA 94501.
Kathy Center and Suzanne Henry. (1993) "A New Paradigm for Business Processes." Proceedings of the Workflow Conference on Business Process Technology. (August). 167-185.
Mark Klein (1996) "Challenges and Directions for Coordination Science", Proceedings of the 2nd Int. Conf. on the Design of Cooperative Systems.
P.T. Harker and L.H. Ungar (1996) "A Market-Based Approach to Workflow Automation", Proceedings of NSF Workshop on Workflow and Process Automation in Information Systems: State-of-the-Art and Future Directions