Scheduling for Optimal Response Times in Queues of Stochastic Workflows

Abstract

We investigate the problem of scheduling tasks of structured workflows, given a stochastic arrival of workflow instances, which gives rise to a queue. Each workflow conforms to a known structure expressed by a directed acyclic graph. However, within this model, the precise execution time of each atomic task and the delay of each communication edge are non-deterministic. Unlike in most scheduling approaches that minimize the schedule length, we additionally aim at minimizing the total time spent by a workflow instance in the system, as perceived by the end user on whose behalf the workflow is executed, i.e., the expected response time. Moreover, we do not make any restrictive assumptions on the nature of the involved distributions. We propose a novel risk-gain local trade-off mechanism to determine priorities at runtime that optionally can be made even more accurate by employing of conditional means for running activities instead of marginal mean execution times. Finally, the tasks that are unlikely to affect the makespan of an instance are delayed with a local look-ahead to allow incoming new instances to start earlier. We show that adding these features leads to a significant improvement in response time, particularly in situations of scarce processing resources.