Workflow Scheduling With Guaranteed Responsiveness and Minimal Cost

卷:16

Article

关键词: SCIENTIFIC WORKFLOWS;    EXECUTING WORKFLOW;    INFRASTRUCTURE;    ALGORITHMS;    DEADLINE;   

DOI  :  10.1109/TSC.2022.3222098

来源: SCIE

【 摘 要 】

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 article, 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), ?), of workflow paths where T-exe(P) is the set of path execution times. Based on (T-exe(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.

【 授权许可】

Free