The parallel machine scheduling problem in the MapReduce system with deteriorating effect of installation time and step deteriorating effect of processing time is considered. 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. We consider the workpiece installation with linear deteriorating effect and processing time with step deteriorating effect on parallel identical machines in the MapReduce system, aiming at minimizing the makespan. We formulate the problem as a mixed integer linear programming model, and give a lower bound of the problem. An improved grey wolf algorithm which uses the simplex difference disturbance mechanism, are proposed to solve the model. Numerical experiments are carried out to demonstrate the efficiency of the MILP and the proposed algorithms, comparing the results of the improved grey wolf algorithm, greedy algorithm and genetic algorithm with the lower bounds of the problem.
HUANG Jidan, ZHENG Feifeng, XU Yingfeng, LIU Ming
. Parallel machine scheduling with deteriorating installation times in the MapReduce system[J]. Operations Research Transactions, 2020
, 24(4)
: 93
-106
.
DOI: 10.15960/j.cnki.issn.1007-6093.2020.04.008
[1] 王磊, 张玉忠, 邢伟, 等. 具有可变配送费用和固定配送时刻的单机排序问题[J]. 运筹学学报, 2017, 21(3):14-22.
[2] 王成飞, 张玉忠, 柏庆国. 具有线性恶化效应的在线分批排序问题[J]. 运筹学学报, 2011, 15(3):107-114.
[3] Wang T, Roberto B, Lim A, et al. A branch-and-price algorithm for scheduling of deteriorating jobs and flexible periodic maintenance on a single machine[J]. European Journal of Operational Research, 2018, 271(2):826-838.
[4] Woo Y B, Jung S, Kim B S. A rule-based genetic algorithm with an improvement heuristic for unrelated parallel machine scheduling problem with time-dependent deterioration and multiple rate-modifying activities[J]. Computers & Industrial Engineering, 2017, 109(1):179-190.
[5] Woo Y B, Kim B S. Matheuristic approaches for parallel machine scheduling problem with timedependent deterioration and multiple rate-modifying activities[J]. Computers & Operations Research, 2018, 95(2):97-112.
[6] Eduardo L R, Voß S. Modeling the parallel machine scheduling problem with step deteriorating jobs[J]. European Journal of Operational Research, 2016, 255(1):21-33.
[7] Jafari A A, Lotfi M M. Single machine scheduling to minimize the maximum tardiness under piecewise linear deteriorating jobs[J]. Scientia Iranica E, 2018, 25(1), 370-385.
[8] 马卫民, 孙丽, 宁磊, 等. 加工时间带恶化和指数学习效应的成组排序[J]. 系统工程理论与实践, 2017, 37(1):205-211.
[9] 范静, 鲁习文. 机器带不可用时间限制的简单线性恶化供应链排序问题[J]. 运筹学学报, 2016, 20(4):69-76.
[10] 苗翠霞, 邹娟. 带有退化效应和序列相关运输时间的排序问题[J]. 运筹学学报, 2016, 20(4):61-68.
[11] 苗翠霞, 孟凡晓. 基于退化效应的两台机器流水作业可拒绝排序[J]. 运筹学学报, 2017, 21(2):66-72.
[12] Luo T B, Zhu Y, Wu W L, Xu Y F, et al. Online makespan minimization in MapReduce-like systems with complex reduce tasks[J]. Optimization Letters, 2017, 11(2):271-277.
[13] 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.
[14] 黄基诞, 郑斐峰, 徐寅峰, 等. 基于MapReduce模型带准备时间的平行机调度优化[J]. 系统工程理论与实践, 2019, 39(1):174-182.
[15] Ling X, Yuan Y, Wang Dan, et al. Joint scheduling of MapReduce jobs with servers:Performance bounds and experiments[J]. Journal of Parallel and Distributed Computing, 2016, 90(1):52-66.
[16] Li X, Jiang T, Ruiz R, et al. Heuristics for periodical batch job scheduling in a MapReduce computing framework[J]. Information Sciences, 2016, 326(1):119-133.
[17] Tang S J, Busung L, Bingsheng H. Dynamic job ordering and slot configurations for MapReduce wrkloads[J]. IEEE Transactions on Services Computing, 2016, 9(1):4-17.
[18] Shao Y L, Li C L, Gu J G, et al. Efficient jobs scheduling approach for big data applications[J]. Computers & Industrial Engineering, 2018, 117(2):249-261.
[19] Shi V Y, Zhang K H, Cui L Z, et al. MapReduce short jobs optimization based on resource reuse[J]. Microprocessors and Microsystems, 2016, 47(1):178-187.
[20] Mirjalili S, Mirjalili S M, Lewis A. Grey wolf optimizer[J]. Advances in Engineering Software, 2014, 69(1):46-61.
[21] 姜天华. 混合灰狼优化算法求解柔性作业车间调度问题[J]. 控制与决策, 2018, 33(3):503-508.
[22] 姚远远, 叶春明. 求解作业车间调度问题的改进混合灰狼优化算法[J]. 计算机应用研究, 2018, 35(5):1310-1314.
[23] Long W, Jiao J, Liang X, et al. Inspired grey wolf optimizer for solving large-scale function optimization problems[J]. Applied Mathematical Modelling, 2018, 60(1):112-126.
