%0 Journal Article
%T 分布式计算系统下可分任务的周期性多趟调度<br>A Periodical Multi？？Installment Scheduling Model and Algorithm for Divisible Loads in Distributed Computing Systems
%A 朱海
%A 王晓丽
%A 马海明
%J 西安交通大学学报
%D 2018
%R 10.7652/xjtuxb201808013
%X 针对已有单趟任务调度模型因无法充分利用分布式平台的并行特性导致系统利用率和任务完成效率较低的问题,提出了一种新的周期性多趟任务调度优化模型。在给定处理机调度顺序的情况下,推导得到了分布式系统最优任务分配方案的解析解;通过分析任务完成时间关于调度趟数和服务器数的变化曲线,设计了一种启发式算法寻求最优的调度趟数和参与计算的服务器数;为了获得最优的服务器调度顺序,提出了一种高效的全局优化进化算法。实验结果表明:与已有调度算法相比,所提算法能够在分布式平台下最小化任务的完成时间,对于小规模和大规模任务,任务完成时间分别降低了至少25％和43％。<br>A new periodical multi？？installment task？？scheduling model is proposed to solve the problem that the existing single？？installment task？？scheduling models could not take full advantage of the parallel characteristics of distributed platforms, which results in low system utilization and inefficiency of task computation. A closed？？form of the solution for an optimal load distribution strategy is firstly derived for a given scheduling sequence of servers. Then, a heuristic algorithm to find optimal numbers of installments and servers involved in workload computation is designed by analyzing the function of finish time with respect to the numbers of installments and servers. An efficient global optimization evolutionary algorithm is proposed to obtain an optimal scheduling sequence of servers. Experiment results and comparisons with existing scheduling algorithms show that the proposed algorithms obtain a minimum finish time of tasks under distributed computing systems. As for relatively small workloads, the proposed algorithm can reduce the finish time of workloads by at least 25％ and 43％ for relatively small workloads and large？？scale workloads, respectively
%K 多趟调度
%K 可分任务
%K 全局优化
%K 进化算法&lt
%K br&gt
%K multi？？installment scheduling
%K divisible load
%K global optimization
%K evolutionary algorithm
%U http://zkxb.xjtu.edu.cn/oa/DArticle.aspx?type=view&id=201808013