The Complexity of Deadline Analysis for Workflow Graphs with Multiple Resources

We study whether the executions of a time-annotated sound workflow graph (WFG) meet a given deadline when an unbounded number of resources (i.e., executing agents) is available. We present polynomial-time algorithms and NP-hardness results for dierent cases. In particular, we show that it can be decided in polynomial time whether some executions of a sound workflow graph meet the deadline. For acyclic sound workflow graphs, it can be decided in linear time whether some or all executions meet the deadline. Furthermore, we show that it is NP-hard to compute the expected duration of a sound workflow graph for unbounded resources, which is contrasting the earlier result that the expected duration of a workflow graph executed by a single resource can be computed in cubic time. We also propose an algorithm for computing the maximum concurrency of the workflow graph, which helps to determine the optimal number of resources needed to execute the workflow graph.

A shorter version of this paper has been published in: Business Process Management, Conference Proceedings 14th International Conference on Business Process Management (BPM 2016), Lecture Notes in Computer Science vol. 9850 (Springer, 2016)

Keyword: Voelzer, Volzer