考虑运输时间的MapReduce模型下的同类机调度研究

Uniform Machine Scheduling with Transportation Time in the MapReduce System

MapReduce模型在大数据处理及机器调度方面日趋重要.针对MapReduce模型中的每个工件由Map和Reduce两道加工工序组成,其中Map工序允许分割成若干个子任务,并在多台同类机上并行加工,而Reduce工序只能在该工件的Map工序里的子任务全部加工完后才能启动加工,且Reduce工序不能分割,即只能在一台机器上连续加工.在实际生产中,重型工件的两个相邻工序若分配给不同机器,则工件在机器之间需要一定的运输时间.结合工件的到达时间约束,以最小化最大完工时间为目标,构建了混合整数规划模型,设计了采用单纯形差分变异策略的改进磷虾算法来求解模型.利用数值仿真实验,与基本磷虾算法、遗传算法及CPLEX计算结果进行对比.测试结果说明了所提出的改进磷虾算法在解的质量和运行时间方面均优于基本磷虾算法、遗传算法,验证了模型与算法改进的有效性.

The MapReduce model has become increasingly important in machine scheduling and big data processing.Each job 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.The processing of reduce task can’t be interrupted.In actual production,if the heavy workpiece is in different machines in two processes,heavy workpiece are transported between different machines and take a certain amount of time.Combined with the arrival time of the job,the goal is to minimize the total completion time.In this paper,we formulate the MapReduce problem as a mixed integer linear programming(MILP)model and develop an improved Krill Herd algorithm(IKH),using simple differential perturbation to obtain a near-optimal solution.The numerical simulation experiment is compared with the krill herd algorithm,genetic algorithm and CPLEX calculation results.The effectiveness of the model and the improved krill herd algorithm is evaluated by computational experiments on a series of randomly generated instances.The numerical results indicate that the improved Krill Herd algorithm outperforms GA and KH for the problem.