带恶化工件的不相关并行机调度优化

doi:10.16182/j.issn1004731x.joss.17-0150

系统仿真学报 ›› 2019, Vol. 31 ›› Issue (5): 919-924.doi: 10.16182/j.issn1004731x.joss.17-0150

带恶化工件的不相关并行机调度优化

轩华¹, 秦莹莹¹, 王薛苑¹, 张百林²

1.郑州大学管理工程学院,河南郑州 450001;
2.浪潮电子信息产业股份有限公司,山东济南 250101

收稿日期:2017-04-10 修回日期:2017-07-09 出版日期:2019-05-08 发布日期:2019-11-20
作者简介:轩华(1979-),女,河南睢县,博士,教授,研究方向为物流优化与控制等。
基金资助:
国家自然科学基金(U1604150, U1804151),教育部人文社会科学研究(15YJC630148),郑州大学优秀青年教师发展基金(1421326092),河南省高等学校重点项目(17A520058)

Optimization for Unrelated Parallel Machine Scheduling with Deteriorating Jobs

Xuan Hua¹, Qin Yingying¹, Wang Xueyuan¹, Zhang Bailin²

1.School of Management Engineering, Zhengzhou University, Zhengzhou 450001, China;
2.Inspur Electronic Information Industry Co., Ltd, Ji’nan 250101, China;

Received:2017-04-10 Revised:2017-07-09 Online:2019-05-08 Published:2019-11-20

摘要/Abstract

摘要： 研究了以最小化最大完工时间为目标的不相关并行机环境下带恶化工件的车间调度问题,工件的加工时间随着开始时间的不同而改变,将其表示为开始时间的增函数,假设每个工件在不同机器上有各自的恶化系数。针对该NP-hard问题,建立数学规划模型,设计基于两段式编码和遗传参数自适应调节策略的改进遗传算法以合理地进行工件排序及机器分配。通过测试不同规模问题的仿真实验,对比结果表明所设计的算法在求解时间和求解质量上均具有较大优势。

Abstract: Unrelated parallel machine scheduling problem with deteriorating jobs is studied with the objective of minimizing the maximum completion time. The processing time of a job varies with its beginning time which is denoted as an increasing function of its starting time. It is assumed that each job has its own different deterioration rate on each machine. A mathematical programming model is formulated for the NP-hard problem. An improved genetic algorithm based on two segment coding and self-adaptive adjustment of genetic parameters is then designed to make job scheduling and machine allocation more reasonable. Through the simulation experiments of different sized problems, the results show that the proposed algorithm has more advantages in both resolution time and solution quality.

Key words: maximum completion time, unrelated parallel machines scheduling, deteriorating jobs, two segment coding, self-adaptive strategy

中图分类号:

轩华, 秦莹莹, 王薛苑, 张百林. 带恶化工件的不相关并行机调度优化[J]. 系统仿真学报, 2019, 31(5): 919-924.

Xuan Hua, Qin Yingying, Wang Xueyuan, Zhang Bailin. Optimization for Unrelated Parallel Machine Scheduling with Deteriorating Jobs[J]. Journal of System Simulation, 2019, 31(5): 919-924.

参考文献

[1] Ji M, Cheng T C E. Parallel-machine scheduling of simple linear deteriorating jobs[J]. Theoretical Computer Science(S0304-3975), 2009, 410: 3761-3768.
[2] 胡大勇, 姚振强. 调整时间与顺序相关的等同并行机调度[J]. 机械工程学报, 2011, 47(16): 160-165.
Hu Dayong, Yao Zhenqiang.Identical parallel machines scheduling with sequence-dependent setup times[J]. Journal of Mechanical Engineering, 2011, 47(16): 160-165.
[3] Beezão A C, Cordeau J F, Laporte G, et al.Scheduling identical parallel machines with tooling constraints[J]. European Journal of Operational Research (S0377-2217), 2017, 257(3): 834-844.
[4] 吴楚格, 王凌, 郑晓龙. 求解不相关并行机调度的一种自适应分布估计算法[J]. 控制与决策, 2016, 31(12): 2177-2182.
Wu Chuge, Wang Ling, Zheng Xiaolong.An adaptive estimation of distribution algorithm for solving the unrelated parallel machine scheduling[J]. Control and Decision, 2016, 31(12): 2177-2182.
[5] 许晓晴, 崔文田, 林军, 等. 基于最小最大遗憾的同型并行机鲁棒调度模型[J]. 系统工程学报, 2013, 28(6): 729-737.
Xu Xiaoqing, Cui Wentian, Lin Jun, et al.Robust identical parallel machines scheduling model based on min-max regret criterion[J]. Journal of Systems Engineering, 2013, 28(6): 729-737.
[6] Eduardo L R, Stefan V.Modeling the parallel machine scheduling problem with step deteriorating jobs[J]. European Journal of Operational Research (S0377-2217), 2016, 255(1): 21-33.
[7] Wang X Y, Zhou Z L, Ji P, et al.Parallel machines scheduling with simple linear job deterioration and non-simultaneous machine available times[J]. Computers and Industrial Engineering (S0360-8352), 2014, 74: 88-91.
[8] Zhang Q, Luo C X. Uniform parallel-machine scheduling with deteriorating jobs and rejection[J]. Applied Mechanics and Materials, 2014, 644/650: 2030-2033.
[9] Rostami M, Pilerood A E, Mazdeh M M.Multi-objective parallel machine scheduling problem with job deterioration and learning effect under fuzzy environment[J]. Computers and Industrial Engineering(S0360-8352), 2015, 85: 206-215.
[10] 于莹莹, 陈燕, 李桃迎. 改进的遗传算法求解旅行商问题[J]. 控制与决策, 2014, 29(8): 1483-1488.
Yu Yingying, Chen Yan, Li Taoying.Improved genetic algorithm for solving TSP[J]. Control and Decision, 2014, 29(8): 1483-1488.
[11] Liu M H, Peng X F. Improved adaptive genetic algorithms for job shop scheduling problems[J]. Advanced Materials Research(S0363-7425), 2010, 97/101: 2473-2476.
[12] 李玲, 唐秋华, 张利平. 文化基因算法求解多工艺路线炼钢-连铸生产调度问题[J]. 武汉科技大学学报, 2017, 40(1): 17-22.
Li Ling, Tang Qiuhua, Zhang Liping.Memetic algorithm for steelmaking-continuous casting production scheduling with multiple process routes[J]. Journal of Wuhan University of Science and Technology, 2017, 40(1): 17-22.

带恶化工件的不相关并行机调度优化

Optimization for Unrelated Parallel Machine Scheduling with Deteriorating Jobs

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 2

编辑推荐

Metrics

本文评价

[1]	李冰, 王星, 轩华, 王薛苑. 嵌入备件库存的设备运维闭环控制系统仿真研究[J]. 系统仿真学报, 2018, 30(10): 3817-3825.
[2]	李慧, 杨少刚, 刘凤英. GSHP机组数学建模及仿真应用[J]. 系统仿真学报, 2018, 30(3): 914-921.