计算机科学
作业车间调度
分布式计算
动态优先级调度
有向无环图
公平份额计划
调度(生产过程)
两级调度
单调速率调度
最早截止时间优先安排
云计算
并行计算
算法
数学优化
地铁列车时刻表
数学
操作系统
作者
Mirsaeid Hosseini Shirvani,Reza Noorian Talouki
标识
DOI:10.1016/j.parco.2021.102828
摘要
An efficient workflow scheduling can potentially exploit heterogeneity of resources in heterogeneous cloud computing (HCC) platform commensurate with variable requirement of dependent tasks in a given workflow. Minimizing the total scheduling length, makespan, is essential for application performance in heterogeneous computing systems especially in cloud computing environment. The problem of scheduling a set of different dependent tasks onto a set of heterogeneous computational resources is a well-known NP-Hard problem. Therefore, no polynomial scheduling algorithm for computing the optimal solution exists. For approximating a solution to this problem many algorithms have been proposed, but majority of them have low efficiency. In this paper, a novel hybrid heuristic-based list scheduling (HH-LiSch) algorithm is presented for solving the dependent task scheduling in HCC systems in a bounded number of the fully connected virtual machines (VMs). The novelty of the current paper is to present the new task priority strategy, find appropriate VM's slot time, and utilize task duplication technique. Two novel task priority strategies are applied to prioritize tasks in an efficient ordered list. Then, during the scheduling process an insertion-based procedure is called to find an appropriate potential slot time for performing task duplication technique. If it works, the task duplication is added to rudimentary scheduling scheme. In this way, the final scheduling is gradually generated. To validate the work, the experiments are based on six real-world scientific workflows and a random task graph (RTG); then, the performance is evaluated in terms of makespan, Schedule Length Ratio (SLR), speedup and efficiency. The simulation results prove a significant improvement against other counterparts in literature.
科研通智能强力驱动
Strongly Powered by AbleSci AI