考虑处理机时间窗口的可分任务调度优化模型

发布时间：2018-03-14 12:27

本文选题：处理机　切入点：可分任务调度　出处：《西安交通大学学报》2017年09期 　论文类型：期刊论文

【摘要】：针对异构分布式系统下处理机具有时间窗口约束的可分任务调度问题,通过寻找最优的任务分配方案和最优的处理机调度顺序,可以使得任务的完成时间最短。首先,在已有模型上引入处理机时间窗口的概念,使得所建模型更加贴切实际;然后,建立了一个新的考虑处理机时间窗口可分任务调度的非阻塞优化模型,同时设计了一种基于全局优化的遗传算法来求解模型;最后,为了快速、高效地求解模型,所提算法同时对处理任务量和调度顺序进行编码,利用不同的交叉算子来优化调度顺序和任务分配量,设计了合理的修正算子来修正不满足处理机时间窗口的任务分配方案,并且设计了高效的局部搜索算子来加快算法的收敛速度。仿真实验结果表明,在处理机时间窗口约束下,与已有算法相比,所提算法至少提升了20%以上的性能,从而证明了所提算法的正确性和有效性。
[Abstract]:For the divisible task scheduling problem with time window constraints in heterogeneous distributed systems, the task completion time is shortest by searching for the optimal task allocation scheme and the optimal processor scheduling order. The concept of processor time window is introduced to the existing model, which makes the model more practical. Then, a new non-blocking optimization model considering processor time window divisible task scheduling is established. At the same time, a genetic algorithm based on global optimization is designed to solve the model. Finally, in order to solve the model quickly and efficiently, the proposed algorithm encodes the processing task and scheduling order simultaneously. Using different crossover operators to optimize the scheduling order and task allocation, a reasonable modified operator is designed to modify the task allocation scheme which does not satisfy the processor time window. An efficient local search operator is designed to speed up the convergence of the algorithm. The simulation results show that the proposed algorithm improves the performance of the proposed algorithm by more than 20% compared with the existing algorithms under the constraint of the processor time window. Thus, the correctness and validity of the proposed algorithm are proved.
【作者单位】：西安电子科技大学计算机学院;
【基金】：国家自然科学基金资助项目(61472297,U1404622)
【分类号】：TP18

【相似文献】