双目标可重入混合流水车间调度问题的离散灰狼优化算法

doi:10.12005/orms.2019.0191

运筹与管理 ›› 2019, Vol. 28 ›› Issue (8): 190-199.DOI: 10.12005/orms.2019.0191

• 管理科学 • 上一篇

双目标可重入混合流水车间调度问题的离散灰狼优化算法

姚远远, 叶春明, 杨枫

上海理工大学管理学院,上海 200093

收稿日期:2018-01-28 出版日期:2019-08-25
作者简介:姚远远(1989-),女,河南灵宝人,博士研究生,研究方向为复杂车间调度、智能优化算法;叶春明(1964-),男,安徽宣城人,教授,博导,研究方向为工业工程、生产调度和智能优化等;杨枫(1978-),男,河南新县人,副教授,博士,研究方向为智能优化、人工智能等。
基金资助:
国家自然科学基金资助项目(71840003);上海理工大学科技发展资助项目(2018KJFZ043)

Solving Bi-objective Reentrant Hybrid Flow Shop Scheduling Problemsby a Hybrid Discrete Grey Wolf Optimizer

YAO Yuan-yuan, YE Chun-ming, YANG Feng

Business School, University of Shanghai for Science and Technology, Shanghai 200093, China

Received:2018-01-28 Online:2019-08-25

摘要/Abstract

摘要： 可重入混合流水车间调度问题普遍存在于许多高科技制造产业中,如半导体晶圆制造和TFT-LCD面板生产过程等,但目前关于可重入调度问题的相关研究还比较少。本文设计了一种改进多目标灰狼优化算法(IMOGWO)解决最小化最大完工时间和总拖期时间最小的可重入混合流水车间调度问题,针对该问题特点对基本灰狼优化算法进行了一系列改进操作。通过对小规模测试问题基准算例的数值实验,验证了所设计的IMOGWO算法求解该调度问题的有效性。实验结果表明IMOGWO算法在非劣解的收敛性和支配性方面显著优于已有的NSGA-II和MOGWO算法,在解的分布性指标方面IMOGWO稍微优于其他两种算法。

关键词: 可重入混合流水车间调度, 改进多目标灰狼优化算法, 双目标优化, 解码机制

Abstract: Reentrant hybrid flow shop (RHFS) scheduling problems have extensive applications in high-tech manufacturing industries such as semiconductor wafers and thin film transistor-liquid crystal display (TFT-LCD) panels, but appear under-studied in the literature. Firstly, a bi-objective mixed-integer programming model for the RHFS scheduling problems with the makespan and total tardiness criteria is formulated. Then an improved multi-objective grey wolf optimizer (IMOGWO) that hybridize with the fast nondominated sorting strategy, crowding distance technique and elitism is proposed to solve this problem. To evaluate the effectiveness of the proposed IMOGWO, which is compared with two existing evolutionary multi-objective algorithms such as NSGA-II and MOGWO based on some small-sized benchmarking instances. The results have shown the validity of this approach. The numerical test results indicate that the proposed IMOGWO algorithm is significantly superior to the NSGA-II and MOGWO in terms of the convergence to optimal solutions and the dominance of solutions, but the spread of the nondominated solutions explored by the three algorithms are almost at the same level.

Key words: reentrant hybrid flow shop scheduling, improved multi-objective grey wolf optimizer, bi-objective optimization, decoding scheme

中图分类号:

TP18

姚远远, 叶春明, 杨枫. 双目标可重入混合流水车间调度问题的离散灰狼优化算法[J]. 运筹与管理, 2019, 28(8): 190-199.

YAO Yuan-yuan, YE Chun-ming, YANG Feng. Solving Bi-objective Reentrant Hybrid Flow Shop Scheduling Problemsby a Hybrid Discrete Grey Wolf Optimizer[J]. Operations Research and Management Science, 2019, 28(8): 190-199.

参考文献

[1] 周炳海,钟臻怡.可重入混合流水车间调度的拉格朗日松弛算法[J].控制理论与应用,2015,32(7):881-886.
[2] Wang M Y, Sethi S P, Vandevelde S L. Minimizing makespan in a class of reentrant shops[J]. Operations Research, 1997, 45(5): 702-712.
[3] Graves Stephen C, Meal Harlan C, Stefek Daniel et al. Scheduling of re-entrant flow shops[J]. Journal of Operations Management, 1983, 3(4): 197-207.
[4] Lin Danping, Lee Carman K.M. A review of the research methodology for the re-entrant scheduling problem[J]. International Journal of Production Research, 2011, 49(8): 2221-2242.
[5] 韩忠华,董晓婷,史海波.可重入混合流水车间负荷平衡排产优化问题研究[J].高技术通讯,2015,25(1):70-81.
[6] Bertel S, Billaut J C. A genetic algorithm for an industrial multiprocessor flow shop scheduling problem with recirculation[J]. European Journal of Operational Research, 2004, 159(3): 651-662.
[7] Choi Hyun Seon, Kim Hyung Won, Lee Dong Ho et al. Scheduling algorithms for two-stage reentrant hybrid flow shops: minimizing makespan under the maximum allowable due dates[J]. International Journal of Advanced Manufacturing Technology, 2009, 42(9-10): 963-973.
[8] Yalaoui Naim, Amodeo Lionel, Yalaoui Farouk et al. Efficient methods to schedule reentrant flowshop system[J]. Journal of Intelligent and Fuzzy Systems, 2014, 26(3): 1113-1121.
[9] Kim H W, Lee D H. Heuristic algorithms for re-entrant hybrid flow shop scheduling with unrelated parallel machines[J]. Proceedings of the Institution of Mechanical Engineers, Part B: Journal of Engineering Manufacture, 2009, 223(4): 433-442.
[10] Dugardin Frédéric, Yalaoui Farouk, Amodeo Lionel. New multi-objective method to solve reentrant hybrid flow shop scheduling problem[J]. European Journal of Operational Research, 2010, 203(1): 22-31.
[11] Choi Hyun-Seon, Kim Ji-Su, Lee Dong-Ho. Real-time scheduling for reentrant hybrid flow shops: a decision tree based mechanism and its application to a TFT-LCD line[J]. Expert Systems with Applications, 2011, 38(4): 3514-3521.
[12] Cho Hang-Min, Bae Suk-Joo, Kim Jungwuk et al. Bi-objective scheduling for reentrant hybrid flow shop using Pareto genetic algorithm[J]. Computers and Industrial Engineering, 2011, 61(3): 529-541.
[13] Ying Kuo-Ching, Lin Shih-Wei, Wan Shu-Yen. Bi-objective reentrant hybrid flowshop scheduling: an iterated Pareto greedy algorithm[J]. International Journal of Production Research, 2014, 52(19): 5735-5747.
[14] Shen Jing-nan, Wang Ling, Zheng Huan-yu. A modified teaching-learning-based optimisation algorithm for bi-objective re-entrant hybrid flowshop scheduling[J]. International Journal of Production Research, 2016, 54(12): 3622-3639.
[15] Shen Jingnan, Wang Ling, Deng Jin et al. A Pareto-Based Discrete Harmony Search Algorithm for Bi-objective Reentrant Hybrid Flowshop Scheduling Problem[C]. Proceedings of the 2nd International Conference on Harmony Search Algorithm(ICHSA2015). Berlin: Springer, 2016: 435-445.
[16] Cho Hang-Min, Jeong In-Jae. A two-level method of production planning and scheduling for bi-objective reentrant hybrid flow shops[J]. Computers and Industrial Engineering, 2017, 106: 174-181.
[17] Pan Jason Chao-Hsien, Chen Jen-Shiang. Mixed binary integer programming formulations for the reentrant job shop scheduling problem[J]. Computers and Operations Research, 2005, 32(5): 1197-1212.
[18] Pinedo Michael L. Scheduling: theory, algorithms, and systems[M]. Fourth Edition. New York: Springer, 2012. 13-19.
[19] Seyedali Mirjalili, Seyed Mohammad Mirjalili, Andrew Lewis. Grey wolf optimizer[J]. Advances in Engineering Software, 2014, 69: 46-61.
[20] Lu Chao, Gao Liang, Li Xinyu et al. A hybrid multi-objective grey wolf optimizer for dynamic scheduling in a real-world welding industry[J]. Engineering Applications of Artificial Intelligence, 2017, 57: 61-79.
[21] Deb Kalyanmoy, Pratap Amrit, Agarwal Sameer et al. A fast and elitist multiobjective genetic algorithm: NSGA-II[J]. IEEE Transactions on Evolutionary Computation, 2002, 6(2): 182-197.
[22] Croce Federico Della, Tadei Roberto, Volta Giuseppe. A genetic algorithm for the job shop problem[J]. Computers and Operations Research, 1995, 22(1): 15-24.
[23] Seyedali Mirjalili, Shahrzad Saremi, Seyed Mohammad Mirjalili et al. Multi-objective grey wolf optimizer: a novel algorithm for multi-criterion optimization[J]. Expert Systems with Applications, 2016, 47: 106-119.
[24] Coello Carlos A. Coello, Pulido Gregorio Toscano, Lechuga Maximino Salazar. Handling multiple objectives with particle swarm optimization[J]. IEEE Transactions on Evolutionary Computation, 2004, 8(3): 256-279.

双目标可重入混合流水车间调度问题的离散灰狼优化算法

Solving Bi-objective Reentrant Hybrid Flow Shop Scheduling Problemsby a Hybrid Discrete Grey Wolf Optimizer

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 4

编辑推荐

Metrics

[1]	张俊光, 刘念. 基于工期-成本综合效用最大的关键链项目缓冲确定[J]. 运筹与管理, 2021, 30(10): 87-94.
[2]	于冬梅, 高雷阜, 赵世杰. 考虑应急设施中断风险与防御的可靠性选址模型研究[J]. 运筹与管理, 2020, 29(9): 53-61.
[3]	滕尚儒, 何成铭, 丛彬. 装备维修器材生产路径双目标问题优化决策方法研究[J]. 运筹与管理, 2020, 29(6): 1-9.
[4]	俞武扬, 方俊俊. 制造单元布局问题的双目标模型与算法研究[J]. 运筹与管理, 2018, 27(6): 100-106.