Jochen Kuster, Hagen Volzer, et al.
Software and Systems Modeling
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.
Jochen Kuster, Hagen Volzer, et al.
Software and Systems Modeling
Karl Aberer, Saket Sathe, et al.
SIGSPATIAL GIS 2010
Mirela Botezatu, Ioana Giurgiu, et al.
KDD 2016
Jochen Kuster, Niklaus Meyer, et al.
EDOC 2019