On verification of nested workflows with extra constraints: From theory to practice |
| |
| Affiliation: | 1. Research Program of Applied Mathematics and Computations, Mexican Petroleum Institute;2. Graduate Programs on Computer Sciences Tecnologico de Monterrey, Campus Estado de México;1. College of Biomedical Engineering and Instrument Science, Zhejiang University, 310008 Zhou Yiqing Building 510, Zheda road 38#, Hangzhou, Zhejiang, China;2. Department of Information and Communication Engineering, University of Murcia, Spain;1. Control Engineering and Intelligent Systems Group eXiT, University of Girona, Campus Montilivi Building PIV, 17071 Girona, Spain;2. Division of Cardiology, Pontchaillou University Hospital, Rennes F-35000, France;3. Université de Rennes 1, LTSI, Rennes F-35000, France;4. INSERM, U1099, Rennes F-35000, France;1. Innovative Information Industry Research Center, School of Computer Science and Technology, Shenzhen Graduate School, Harbin Institute of Technology, Shenzhen, China;2. Information and Communications Research Laboratories, ITRI, Hsinchu, Taiwan, ROC;3. CyLab, Carnegie Mellon University, Pittsburgh, USA;4. Department of Computer Science, National Tsing Hua University, Hsinchu, Taiwan, ROC |
| |
| 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. |
| |
| Keywords: | Workflow Verification Complexity Constraint satisfaction Temporal consistency |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
