基于MapReduce模型带准备时间的平行机调度优化
|
摘要
研究了一类基于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.
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.
引文
[1] Chen F, Kodialam M S, Lakshman T V, et al. Joint scheduling of processing and Shuffle phases in MapReduce systems[J]. International Conference on Computer Communications, 2012:1143-1151.
[2] Li X, Jiang T, Ruiz R, et al. Heuristics for periodical batch job scheduling in a MapReduce computing framework[J]. Information Sciences, 2016, 326:119-133.
[3] Tang S J, Busung L, Bingsheng H. Dynamic job ordering and slot configurations for MapReduce workloads[J].IEEE Transactions on Services Computing,2016, 9(1):4-17.
[4] Tian W, Luo G, Tian L, et al. On dynamic job ordering and slot configurations for minimizing the makespan of multiple MapReduce jobs[J]. arXiv:Data Structures and Algorithms, 2016.
[5] Verma A, Cherkasova L, Campbell R H, et al. Two sides of a coin:Optimizing the schedule of MapReduce jobs to minimize their makespan and improve cluster performance[J]. Modeling, Analysis, and Simulation on Computer and Telecommunication Systems, 2012:11-18.
[6] Verma A, Cherkasova L, Campbell R H, et al. Orchestrating an ensemble of MapReduce jobs for minimizing their makespan[J]. IEEE Transactions on Dependable and Secure Computing, 2013, 10(5):314-327.
[7] Wang C, Liu C, Zhang Z H, et al. Minimizing the total completion time for parallel machine scheduling with job splitting and learning[J]. Computers&Industrial Engineering, 2016, 97(C):170-182.
[8] Wang W L, Wang H Y, Zhao Y W, et al. Parallel machine scheduling with splitting jobs by a hybrid differential evolution algorithm[J]. Computers&Operations Research, 2013, 40:1196-1206.
[9] Luo T, Zhu Y, Wu W, et al. Online makespan minimization in MapReduce-like systems with complex reduce tasks[J]. Optimization Letters, 2017, 11(2):271-277.
[10] Huang J D, Zheng F F, Xu Y F, et al. Online MapReduce processing on two identical parallel machines[J].Journal of Combinatorial Optimization, 2018, 35(1):216-223.
[11]李坤,唐立新,陈树发.多集装箱堆场空间分配与车辆调度集成问题的建模与优化[J].系统工程理论与实践,2014, 34(1):115-121.Li K, Tang L X, Chen S F. Modeling and optimizing for the integrated problem with container storage allocation and truck scheduling[J]. Systems Engineering—Theory&Practice,2014, 34(1):115-121.
[12] Afzalirad M, Rezaeian J. Resource-constrained unrelated parallel machine scheduling problem with sequence dependent setup times, precedence constraints and machine eligibility restrictions[J]. Computers&Industrial Engineering, 2016:40-52.
[13]黄霞,叶春明,曹磊.多目标置换流水车间调度的混沌杂草优化算法[J].系统工程理论与实践,2017,37(1):253-262.Huang X, Ye C M, Cao L. Chaos invasive weed optimization algorithm for multi-objective permutation flow shop scheduling problem[J]. Systems Engineering—Theory&Practice, 2017, 37(1):253-262.
[14] Mirjalili S. SCA:A sine cosine algorithm for solving optimization problems[J]. Knowledge-Based Systems, 2016,96:120-133.
[15]徐松金,龙文.求解高维优化问题的改进正弦余弦算法[J].计算机应用研究,2018, 35(9):821-828.Xu S J, Long W. Improved sine cosine algorithm for solving high-dimensional optimization problems[J]. Application Research of Computers, 2018, 35(9):821-828.
[16] Mohamed A E, Diego O, Shengwu X. An improved opposition-based sine cosine algorithm for global optimization[J]. Expert Systems With Applications, 2017(90):484-500.
[17] Storn R, Price K. Differential evolution—A simple and efficient adaptive scheme for global optimization over continuous spaces[R]. International Computer Science Institute, Berkeley, CA, Tech Rep TR-95-012, 1995.
[18] Liu X, Fu M. Cuckoo search algorithm based on frog leaping local search and chaos theory[J]. Applied Mathematics and Computation, 2015:1083-1092.
[19] Jose E C, Arroyo, Joseph Y T. An effective iterated greedy algorithm for scheduling unrelated parallel batch machines with non-identical capacities and unequal ready times[J]. Computers&Industrial Engineering, 2017,105:84-100.
[2] Li X, Jiang T, Ruiz R, et al. Heuristics for periodical batch job scheduling in a MapReduce computing framework[J]. Information Sciences, 2016, 326:119-133.
[3] Tang S J, Busung L, Bingsheng H. Dynamic job ordering and slot configurations for MapReduce workloads[J].IEEE Transactions on Services Computing,2016, 9(1):4-17.
[4] Tian W, Luo G, Tian L, et al. On dynamic job ordering and slot configurations for minimizing the makespan of multiple MapReduce jobs[J]. arXiv:Data Structures and Algorithms, 2016.
[5] Verma A, Cherkasova L, Campbell R H, et al. Two sides of a coin:Optimizing the schedule of MapReduce jobs to minimize their makespan and improve cluster performance[J]. Modeling, Analysis, and Simulation on Computer and Telecommunication Systems, 2012:11-18.
[6] Verma A, Cherkasova L, Campbell R H, et al. Orchestrating an ensemble of MapReduce jobs for minimizing their makespan[J]. IEEE Transactions on Dependable and Secure Computing, 2013, 10(5):314-327.
[7] Wang C, Liu C, Zhang Z H, et al. Minimizing the total completion time for parallel machine scheduling with job splitting and learning[J]. Computers&Industrial Engineering, 2016, 97(C):170-182.
[8] Wang W L, Wang H Y, Zhao Y W, et al. Parallel machine scheduling with splitting jobs by a hybrid differential evolution algorithm[J]. Computers&Operations Research, 2013, 40:1196-1206.
[9] Luo T, Zhu Y, Wu W, et al. Online makespan minimization in MapReduce-like systems with complex reduce tasks[J]. Optimization Letters, 2017, 11(2):271-277.
[10] Huang J D, Zheng F F, Xu Y F, et al. Online MapReduce processing on two identical parallel machines[J].Journal of Combinatorial Optimization, 2018, 35(1):216-223.
[11]李坤,唐立新,陈树发.多集装箱堆场空间分配与车辆调度集成问题的建模与优化[J].系统工程理论与实践,2014, 34(1):115-121.Li K, Tang L X, Chen S F. Modeling and optimizing for the integrated problem with container storage allocation and truck scheduling[J]. Systems Engineering—Theory&Practice,2014, 34(1):115-121.
[12] Afzalirad M, Rezaeian J. Resource-constrained unrelated parallel machine scheduling problem with sequence dependent setup times, precedence constraints and machine eligibility restrictions[J]. Computers&Industrial Engineering, 2016:40-52.
[13]黄霞,叶春明,曹磊.多目标置换流水车间调度的混沌杂草优化算法[J].系统工程理论与实践,2017,37(1):253-262.Huang X, Ye C M, Cao L. Chaos invasive weed optimization algorithm for multi-objective permutation flow shop scheduling problem[J]. Systems Engineering—Theory&Practice, 2017, 37(1):253-262.
[14] Mirjalili S. SCA:A sine cosine algorithm for solving optimization problems[J]. Knowledge-Based Systems, 2016,96:120-133.
[15]徐松金,龙文.求解高维优化问题的改进正弦余弦算法[J].计算机应用研究,2018, 35(9):821-828.Xu S J, Long W. Improved sine cosine algorithm for solving high-dimensional optimization problems[J]. Application Research of Computers, 2018, 35(9):821-828.
[16] Mohamed A E, Diego O, Shengwu X. An improved opposition-based sine cosine algorithm for global optimization[J]. Expert Systems With Applications, 2017(90):484-500.
[17] Storn R, Price K. Differential evolution—A simple and efficient adaptive scheme for global optimization over continuous spaces[R]. International Computer Science Institute, Berkeley, CA, Tech Rep TR-95-012, 1995.
[18] Liu X, Fu M. Cuckoo search algorithm based on frog leaping local search and chaos theory[J]. Applied Mathematics and Computation, 2015:1083-1092.
[19] Jose E C, Arroyo, Joseph Y T. An effective iterated greedy algorithm for scheduling unrelated parallel batch machines with non-identical capacities and unequal ready times[J]. Computers&Industrial Engineering, 2017,105:84-100.