一种基于任务执行时间的启发式独立任务调度算法  

A heuristic independent task scheduling algorithm based on task execution time

作　　者：乔保军[1] 张稼祥 左宪禹[1] Qiao Baojun;Zhang Jiaxiang;Zuo Xianyu(Henan Key Laboratory of Big Data Analysis and Processing,School of Computer and Information Engineering,Henan University,Kaifeng 475004,China)

机构地区：[1]河南大学河南省大数据分析与处理重点实验室,计算机与信息工程学院,河南开封475004

出　　处：《河南师范大学学报（自然科学版）》2022年第5期19-28,共10页Journal of Henan Normal University(Natural Science Edition)

基　　金：国家自然科学基金(62176087);河南省重大科技专项(201400210300);河南省科技厅重点计划项目(212102210393,202102110121).

摘　　要：近年来,为了处理大量的数据,分布式、云计算技术已成为主流技术.在各种分布式计算中,任务调度一直是一个关键的问题.一个理想的调度算法针对各种不同的任务可以充分利用已有资源,节约任务的完成时间.在任务调度中,常见的独立任务调度算法有MIN-MIN算法,MAX-MIN算法.由于任务与资源的异构性,会导致上述算法在一些情况下调度结果不理想,同时上述算法在执行过程中需要经过三重迭代,导致算法时间复杂度过高.针对上述问题,提出一种基于任务执行时间的启发式独立任务调度算法,通过对任务执行时间矩阵的预处理、分解、预调度、调整等4个阶段将任务分配至不同的资源上.实验结果表明,所提算法在时间复杂度低的同时,多数条件下整体任务的完成时间优于上述算法.In recent years, distributed and cloud computing technologies have become the mainstream for processing a large amount of data. In all kinds of distributed computing, task scheduling is always a key problem. An ideal scheduling algorithm for different tasks can make full use of existing resources and save task completion time. In task scheduling, MIN-MIN algorithm and MAX-MIN algorithm are common independent task scheduling algorithms. Due to the heterogeneity of tasks and resources, the scheduling results of the above algorithms are not ideal in some cases. At the same time, three iterations are needed in the execution process of the above algorithm, resulting in high time complexity of the algorithm. To solve the above problems, a heuristic independent task scheduling algorithm based on task execution time is proposed in the paper, and the tasks are allocated to different resources through four stages: preprocessing, decomposition, pre-scheduling and adjustment of the task execution time matrix. Experimental results show that the proposed algorithm has low time complexity and the overall task completion time is better than that of the above algorithms under most conditions.

关 键 词：MIN-MIN算法 分布式计算 独立任务 调度算法 四阶段调度 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]