|
چکیده
|
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, (Texe(P),≼) , of workflow paths where Texe(P) is the set of path execution times. Based on (Texe(P),≼), 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.
|