The Complexity of Deadline Analysis for Workflow Graphs with a Single Resource

Abstract

Workflow graphs (WFGs) are control-flow graphs extended by parallel fork and join. They are used to represent the main control-flow of e.g. business process models modeled in languages such as BPMN or UML activity diagrams. A WFG is said to be sound if it is free of deadlocks and exhibits no lack of synchronization. We study the question whether the executions of a time-annotated sound WFG meet a given deadline. We present polynomial-time algorithms and NP-hardness results for different cases. In particular, we show that it can be decided in polynomial time whether some executions of a sound WFG meet the deadline. Furthermore we show that for general probabilistic WFGs, it is NP-hard to determine whether the probability of an execution meeting the deadline is higher than a given threshold, whereas the expected duration of an execution can be computed in polynomial time.