摘要
针对异构分布式系统下处理机具有时间窗口约束的可分任务调度问题,通过寻找最优的任务分配方案和最优的处理机调度顺序,可以使得任务的完成时间最短。首先,在已有模型上引入处理机时间窗口的概念,使得所建模型更加贴切实际;然后,建立了一个新的考虑处理机时间窗口可分任务调度的非阻塞优化模型,同时设计了一种基于全局优化的遗传算法来求解模型;最后,为了快速、高效地求解模型,所提算法同时对处理任务量和调度顺序进行编码,利用不同的交叉算子来优化调度顺序和任务分配量,设计了合理的修正算子来修正不满足处理机时间窗口的任务分配方案,并且设计了高效的局部搜索算子来加快算法的收敛速度。仿真实验结果表明,在处理机时间窗口约束下,与已有算法相比,所提算法至少提升了20%以上的性能,从而证明了所提算法的正确性和有效性。
A divisible-load scheduling problem under the constraint of processor time-window for heterogeneous distributed systems is presented, and the make-span is minimized by finding the optimal load partition strategy and the optimal distribution sequence of processors. On the basis of existing research, the concept of time-window is introduced first, which makes the model more practical. Then a novel divisible-load scheduling non-blocking model is proposed considering the time-window. Meanwhile, a genetic algorithm is designed for the proposed model. In order to solve the model quickly and efficiently, the load partition and the distribution sequence of processors are encoded at the same time. Different crossover operators are designed to optimize the load partition and the distribution sequence of processors, and a modification operator is designed to modify the load partition scheme which does not satisfy the constraint of processors＇ time-window. Moreover, An efficient local search operator to is also designed speed up the convergence rate of the algorithm. Finally, simulation experiments are carried out, and the results show that under the constraint of the processor time-window, the proposed algorithm can improve the performance of the existing algorithms by at least 20 %, which proves the correctness and effectiveness of the proposed algorithm.
出处
《西安交通大学学报》
EI
CAS
CSCD
北大核心
2017年第9期118-124,共7页
Journal of Xi'an Jiaotong University
基金
国家自然科学基金资助项目(61472297
U1404622)
关键词
处理机
可分任务调度
时间窗口
遗传算法
processor
divisible-load scheduling
time-window
genetic algorithm
