基于MapReduce模型带准备时间的平行机调度优化

Parallel machine scheduling with setup time in the MapReduce system

研究了一类基于MapReduce模型的平行机调度问题.每个工件包含Map和Reduce两道加工工序,Map工序可以分割为若干个子任务,并且在多台平行机上同时并行加工,Reduce工序只有在该工件的所有Map工序的子任务加工完成后才能进行,而且Reduce只能在一台机器上加工且不可中断.结合工件具有释放时间和加工准备时间等约束,以最小化最大完工时间为目标,构建了混合整数规划模型,并设计了采用差分变异策略和逐维Levy扰动机制的改进正弦余弦算法来求解该模型.最后,利用数值仿真实验与标准正弦余弦算法及遗传算法进行对比,实验结果表明,运用改进正弦余弦算法求解的结果与下界值的平均相对偏差GAP为3.02%,较标准正弦余弦算法以及遗传算法的效果提升显著,显示了该改进算法的有效性.

This work studies MapReduce model-based parallel machine scheduling.Each job with arbitrary release time and setup time consists of one map task and one reduce task.The map task can be split and processed on several machines simultaneously,while the reduce task has to be processed on a single machine and it cannot be started unless the map task has been completed,and the processing for any task cannot be interrupted.In this paper,we consider the MapReduce scheduling on parallel identical machines,aiming at minimizing the makespan.We formulate the problem as a mixed integer linear programming model,and develop an improved sine cosine algorithm(ISCA)using differential perturbation and dimension-bydimension Levy perturbation to obtain a near-optimal solution.Computational comparisons between ISCA and genetic algorithm together with the classical SCA algorithm show that the proposed ISCA algorithm outperforms the other two algorithms.Besides,the ISCA is of an average relative deviation of 3.02%from the lower bound of the problem.Numerical computation verifies the effectiveness of the proposed algorithm.