安装具有退化效应的MapReduce模型下的平行机调度

运筹学学报

• 运筹学 •

安装具有退化效应的MapReduce模型下的平行机调度

黄基诞¹,郑斐峰²,徐寅峰¹,刘明³

1. 东华大学旭日工商管理学院
2. 东华大学
3. 同济大学经济与管理学院

收稿日期:2018-12-17 修回日期:2019-03-16 发布日期:2019-05-13
通讯作者: 黄基诞
基金资助:
教育部高职高专计算机类专业指导委员会立项课题;混合型联合分析方法及其应用;消费者视角的品牌联盟战略及其应用

Parallel machines scheduling with deteriorating installing times in the MapReduce system

Received:2018-12-17 Revised:2019-03-16 Published:2019-05-13
Contact: Ji-dan HUANG

摘要/Abstract

摘要： 考虑了平行机环境下安装时间具有退化效应且加工时间具有分步恶化效应的MapReduce模型调度优化问题. 在MapReduce模型中，每个工件包含Map和Reduce两道工序。其中，Map工序可以分割成若干个子任务并在多台平行机上同时加工，而 Reduce工序只有在该工件Map工序的所有子任务完成后才能启动加工,而且只能在一台机器上连续加工. 本文研究Reduce工序的启动安装时间具有线性恶化效应、两个工序的加工时间具有分步恶化效应的平行机调度问题，构建了以最小化最大完成时间为优化目标的混合整数规划模型. 给出了问题解的一个下界；同时，设计了采用单纯形差分扰动机制的改进灰狼算法以及贪婪算法进行模型求解. 最后，利用数值仿真实验，将灰狼优化算法、贪婪算法、遗传算法的解与问题的下界进行对比，验证了模型与所设计算法的有效性.

关键词: 分步恶化, 退化效应, 平行机调度, MapReduce模型, 灰狼优化算法(GWO)

Abstract: 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.

Key words: step deteriorating, deteriorating effects, parallel machine scheduling, MapReduce, grey wolf algorithm(GWO)

黄基诞郑斐峰徐寅峰刘明. 安装具有退化效应的MapReduce模型下的平行机调度[J]. 运筹学学报.

参考文献

[1]范静, 鲁习文.机器带不可用时间限制的简单线性恶化供应链排序问题[J].运筹学学报, 2016, 20(4):69- [2]付亚平, 王洪峰, 黄敏等.设备具有恶化特性的多目标流水车间调度模型与算法[J].系统工程理论与实践, 2016, 36(11):2941- [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- [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]., 2017, 109:179--190., 109(1):179-190 [5]Woo Y B, Kim B S.Matheuristic approaches for parallel machine scheduling problem with time-dependent deterioration and multiple rate-modifying activities[J].[J]., 2018, 95(2):97-112 [6]. [7] Eduardo L R, VoBS.Modeling the parallel machine scheduling problem with step deteriorating jobs[J]., 2016, 255(1):21-33 [8]. [9]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. [10]马卫民, 孙丽, 宁磊等.加工时间带恶化和指数学习效应的成组排序[J].系统工程理论与实践, 2017, 37(1):205- [11] 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].[J]., 2017, 2(11):271-277 [12]. [13]. [14]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 [15] Ling X, Yuan Y, Wang Dan, et al.Joint scheduling of MapReduce jobs with servers: Performance bounds and experiments[J]. [16]Journal of Parallel and Distributed Computing, 2016, 90(1):52-66. [17]Li X, Jiang T, Ruiz R, et al.Heuristics for periodical batch job scheduling in a MapReduce computing framework[J]. [18]Information Sciences, 2016, 326(1): 119-133. [19]Tang S J, Busung L, Bingsheng H.Dynamic Job Ordering and Slot Configurations for MapReduce Workloads[J]. [20]IEEE Transactions on Services Computing, 2016, 9(1){: 4-17. [21]Shao Y L, Li C L, Gu J G, et al.Efficient jobs scheduling approach for big data applications[J]., 2018, 117(2):249-261 [22]. [23]Shi V Y, Zhang K H, Cui L Z, et al.MapReduce short jobs optimization based on resource reuse[J]. [24]Microprocessors and Microsystems, 2016, 47(1):178-187. [25]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 [26]Mirjalili S, Mirjalili S M, Lewis A.Grey wolf optimizer[J]., 2014, 69(1):46-61 [27]姜天华.混合灰狼优化算法求解柔性作业车间调度问题[J].控制与决策, 2018, 33(3):503-508 [28]姚远远, 叶春明.求解作业车间调度问题的改进混合灰狼优化算法[J].计算机应用研究, 2018, 35(5):1310- [29]Long W, Jiao J, Liang X, et al.Inspired grey wolf optimizer for solving large-scale function optimization problems[J][J]., 2018, 60:112-126

安装具有退化效应的MapReduce模型下的平行机调度

Parallel machines scheduling with deteriorating installing times in the MapReduce system

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 3

编辑推荐

Metrics

本文评价

[1]	黄基诞, 郑斐峰, 徐寅峰, 刘明. 安装时间具有退化效应的MapReduce模型下的平行机调度[J]. 运筹学学报, 2020, 24(4): 93-106.
[2]	苗翠霞, 孟凡晓. 基于退化效应的两台机器流水作业可拒绝排序[J]. 运筹学学报, 2017, 21(2): 66-72.
[3]	苗翠霞, 邹娟. 带有退化效应和序列相关运输时间的排序问题[J]. 运筹学学报, 2016, 20(4): 61-68.