Predicting Temporal Exceptions in Concurrent Workflows Figure 19. Prediction accuracy on short duration "long-task" scenario RELATED WORK Critical paths are widely used in predicting as well as in handling exceptions. For detecting artifact anomalies in temporal structured workflows, Hsu and Wang (2011) unfold loops into a decision structure with three branches. The first branch represents the case when there is no iteration. The second branch represents the case when there is a single iteration. The last branch represents the case for maximal iterations. The resulting decision structure is then used for the analysis of struc- ture and temporal relationships between artifact operations to reveal any anomalies buried in the workflow. In the algorithm for handling temporal exception (Xie, Yu, & Kuang, 2009), the longest and shortest time to complete is used to detect potential exceptions at the process instantiation or during run time. When a potential exception is detected, the slack time of remaining activities is reduced so that the process can complete before the overall deadline. Son and Kim (2001) also propose a method for determining the minimum number of servers for the activities within the critical path of a given workflow specification. Their approach maximizes the number of work- flow instances that satisfy the deadline and hence improve the performance of time-constrained workflow processing. The M/M/1 queuing network based approach for identifying the critical path of a workflow model is detailed by Son et al. (2005). In their approach, loops are transformed into sequence control constructs for finding the longest execu- tion paths. The main difference between their approach and ours is that in their approach, each activity is considered as an independent M/M/1 queuing system and the average execution time of a workflow instance in an activity is derived from the sum of the average servicing time and the average waiting time of the activity, whereas in our approach, an exhaustive search (breadth- first search) is used to identify the critical path based on the maximum allowable execution time of activities. In addition, the waiting time at the queue of the activity is implicitly taken into ac- count when the conflict-free execution trace is derived from the resulting critical paths. For preventing temporal violations in scientific workflows, Liu et al. (2010a) proposed an estima- 215