考虑恶化效应的MapReduce模型下的同类机调度

Uniform machines scheduling with deteriorating effects in the MapReduce system

中文关键词  恶化效应  同类机调度  蝙蝠优化算法  MapReduce  正余弦扰动

英文关键词  deteriorating effect  uniform machines scheduling  bat algorithm  MapReduce  sine-cosine perturbation

中文摘要

      本文研究了MapReduce模型中考虑恶化效应的同类机调度问题. 在MapReduce模型中每个工件加工必须经 过两道工序. 其中在第1道工序中每个工件加工任务可分割成若干个子任务且能并行加工, 当某个工件中的所有子 任务全部完成后, 才允许启动第2道工序, 且第2道工序只能在一台机器上连续加工. 本文考虑了工件实际加工时间 与其开工前的等待时间呈线性函数关系的恶化效应, 构建了以最小化所有工件的逗留时间和为目标函数的混合整 数规划模型, 同时给出了问题的一个下界, 最后设计了采用正余弦差分扰动机制的改进蝙蝠优化算法来求解模型. 通过数值仿真对蝙蝠优化算法、遗传算法、CPLEX结果与下界进行对比, 验证了模型的正确性和改进算法的有效 性.

英文摘要

      This paper considers a class of uniform machine scheduling with deteriorating effects in the MapReduce system. There are two stage for each job in the MapReduce model. A job can be split several subtasks and processed on several machines simultaneously in the first stage. The second stage can only start processing after all subtasks in the first stage of the job are completed, and can only be processed continuously on a single machine. The deteriorating effect considered in this paper refers to the fact that the processing time of a job is a linear function of its starting time and the waiting time. A mixed integer programming model (MILP) was constructed to minimize total flow time of all jobs as the objective function, at the same time, a lower bound of the problem is given and an improved bat algorithm using sinecosine difference disturbance mechanism is designed to solve the model. The effectiveness of the MILP and bat algorithm improvement is verified by comparing the bat algorithm, genetic algorithm numerical simulation experiment and CPLEX calculation result with the lower bound.