On verification of nested workflows with extra constraints: From theory to practice

R Barták, V Rovenský - Expert systems with applications, 2014 - Elsevier
R Barták, V Rovenský
Expert systems with applications, 2014Elsevier
Workflows are used to formally describe processes of various types such as business and
manufacturing processes. One of the critical tasks of workflow management is automated
discovery of possible flaws in the workflow–workflow verification. In this paper, we formalize
the problem of workflow verification as the problem of verifying that there exists a feasible
process for each task in the workflow. This problem is tractable for nested workflows that are
the workflows with a hierarchical structure similar to hierarchical task networks in planning …
Abstract
Workflows are used to formally describe processes of various types such as business and manufacturing processes. One of the critical tasks of workflow management is automated discovery of possible flaws in the workflow – workflow verification. In this paper, we formalize the problem of workflow verification as the problem of verifying that there exists a feasible process for each task in the workflow. This problem is tractable for nested workflows that are the workflows with a hierarchical structure similar to hierarchical task networks in planning. However, we show that if extra synchronization, precedence, or causal constraints are added to the nested structure, the workflow verification problem becomes NP-complete. We present a workflow verification algorithm for nested workflows with extra constraints that is based on constraint satisfaction techniques and exploits an incremental temporal reasoning algorithm. We then experimentally demonstrate efficiency of the proposed techniques on randomly generated workflows with various structures and sizes. The paper is concluded by notes on exploiting the presented techniques in the application FlowOpt for modeling, optimizing, visualizing, and analyzing production workflows.
Elsevier
Showing the best result for this search. See all results