Workflow Scheduling with Guaranteed Responsiveness and Minimal Cost

Abstract

Workflow scheduling is the process of optimally assigning virtual machines to workflow tasks subject to response time and cost consideration. Since such an optimization problem is NP-compete, providing an effective heuristic approach is essential. In this paper, we consider the workflow scheduling problem with the least cost subject to a bound on the response time. We show that existing solutions fundamentally care for the longest execution path within the workflow without appropriately handling non-critical paths. To overcome such a shortcoming, we propose a novel heuristic algorithm based on discrete mathematics. We first demonstrate that a workflow has a bijective relation with a partially ordered set and then introduce two operations on the workflow to show that it is an algebraic structure. We then form a totally ordered set, (T exe(P), 4), of workflow paths where T exe(P) is the set of path execution times. Based on (T exe(P), 4), we identify the path with the maximum cumulative execution time and allocate a virtual machine to each task of the path based on the workflow deadline. We then delete the scheduled path and run our algorithm for each resulting sub-workflow in parallel. The results indicate that the proposed algorithm outperforms the best-known approaches in the literature.