上海交通大学学报

上海交通大学学报 >

2022 , Vol. 56 >Issue 2: 201 - 213

DOI: https://doi.org/10.16183/j.cnki.jsjtu.2020.435

基于改进候鸟迁徙优化的多目标批量流混合流水车间调度

展开
  • 浙江工业大学 机械工程学院, 杭州 310023
汤洪涛(1976-),男,湖北省十堰市人,副教授,研究方向为生产与物流系统建模与优化、智能工厂规划.

收稿日期: 2020-12-28

  网络出版日期: 2022-03-03

基金资助

国家重点研发计划(2018YFB1308100);浙江省自然科学基金资助项目(LY19G020010)

收起

A Modified Migrating Birds Optimization for Multi-Objective Lot Streaming Hybrid Flowshop Scheduling

Expand
  • College of Mechanical Engineering, Zhejiang University of Technology, Hangzhou 310023, China

Received date: 2020-12-28

  Online published: 2022-03-03

Fold

摘要

针对2+1+1型混合流水车间,研究了多目标不相等批量流混合流水车间调度问题,提出一种基于变邻域搜索的自适应候鸟迁徙优化(AMBO)算法,实现了最小化完工时间与最小平均在制品数量的多目标优化.相比原始候鸟迁徙算法,AMBO算法引入变邻域搜索策略,实现每个算子的权重随迭代次数自适应调整,并提出了时间窗算子,以提升交换算子搜索性能和收敛速度.对随机生成不同规模的订单进行算例研究,结果表明AMBO算法比候鸟迁徙优化算法、遗传算法具有更高的求解质量和收敛性能,从而验证了AMBO算法的有效性.

关键词： 批量流问题; 混合流水车间调度问题; 变邻域搜索; 自适应候鸟迁徙优化; 时间窗算子

本文引用格式

汤洪涛, 王丹南, 邵益平, 赵文彬, 江伟光, 陈青丰 . 基于改进候鸟迁徙优化的多目标批量流混合流水车间调度[J]. 上海交通大学学报, 2022 , 56(2) : 201 -213 . DOI: 10.16183/j.cnki.jsjtu.2020.435

Abstract

This paper proposes an adaptive migrating birds optimization (AMBO) method based on variable neighborhood search to solve the inequal lot streaming hybrid flowshop scheduling problem (ILS-HFSP) for a 2+1+1 hybrid flowshop, which realizes multi-objective optimization of minimizing makespan and minimum average work in process. Compared with the original migrating birds optimization, the AMBO algorithm adopts the variable neighborhood search strategy with an adaptive selection probability of neighborhood operator that is adaptively adjusted with the number of iterations. Besides, a time-window operator is adopted to improve the search performance of exchange operators and convergence rate. Several orders of different scales generated randomly are studied, and the results show that the AMBO algorithm has a higher solution quality and a better convergence performance than the migrating birds optimization algorithm and the genetic algorithm, thereby verifying the effectiveness of the AMBO algorithm.

Key words： lot streaming problem; hybrid flowshop scheduling problem; variable neighborhood search; adaptive migrating birds optimization (AMBO); time window operation

参考文献

[1] 周炳海, 刘文龙. 考虑能耗和准时的混合流水线多目标调度[J]. 上海交通大学学报, 2019, 53(7):773-779.
[1] ZHOU Binghai, LIU Wenlong. Multi-objective hybrid flow-shop scheduling problem considering energy consumption and on-time delivery[J]. Journal of Shanghai Jiao Tong University, 2019, 53(7):773-779.
[2] ZHOU X J, YU M Q. Semi-dynamic maintenance scheduling for multi-station series systems in multi-specification and small-batch production[J]. Reliability Engineering & System Safety, 2020, 195:106753.
[3] 陶辛阳, 夏唐斌, 奚立峰. 基于健康指数的预防性维护与多目标生产调度联合优化建模[J]. 上海交通大学学报, 2014, 48(8):1170-1174.
[3] TAO Xinyang, XIA Tangbin, XI Lifeng. Health-index-based joint optimization of preventive maintenance and multi-attribute production scheduling[J]. Journal of Shanghai Jiao Tong University, 2014, 48(8):1170-1174.
[4] 李颖俐, 李新宇, 高亮. 混合流水车间调度问题研究综述[J]. 中国机械工程, 2020, 31(23):2798-2813.
[4] LI Yingli, LI Xinyu, GAO Liang. Review on hybrid flow shop scheduling problems[J]. China Mechanical Engineering, 2020, 31(23):2798-2813.
[5] ZHANG B, PAN Q K, GAO L, et al. An effective modified migrating birds optimization for hybrid flowshop scheduling problem with lot streaming[J]. Applied Soft Computing, 2017, 52:14-27.
[6] MENG T, PAN Q K, LI J Q, et al. An improved migrating birds optimization for an integrated lot-streaming flow shop scheduling problem[J]. Swarm and Evolutionary Computation, 2018, 38:64-78.
[7] ZHANG M, TAN Y T, ZHU J H, et al. A competitive and cooperative migrating birds optimization algorithm for vary-sized batch splitting scheduling problem of flexible job-shop with setup time[J]. Simulation Modelling Practice and Theory, 2020, 100:102065.
[8] NADERI B, YAZDANI M. A model and imperialist competitive algorithm for hybrid flow shops with sublots and setup times[J]. Journal of Manufacturing Systems, 2014, 33(4):647-653.
[9] LALITHA J L, MOHAN N R, PILLAI V M. Lot streaming in [N-1](1)+N(m) hybrid flow shop[J]. Journal of Manufacturing Systems, 2017, 44:12-21.
[10] 李航, 章旸, 叶鸿庆, 等. 考虑批量流与换模时间的柔性生产线调度方法研究[J]. 工业工程与管理, 2020, 25(3):179-187.
[10] LI Hang, ZHANG Yang, YE Hongqing, et al. Research on flexible production line scheduling with lot streaming and setup times[J]. Industrial Engineering and Management, 2020, 25(3):179-187.
[11] ZHANG B, PAN Q K, GAO L, et al. A multi-objective migrating birds optimization algorithm for the hybrid flowshop rescheduling problem[J]. Soft Computing, 2019, 23(17):8101-8129.
[12] LI J Q, TAO X R, JIA B X, et al. Efficient multi-objective algorithm for the lot-streaming hybrid flowshop with variable sub-lots[J]. Swarm and Evolutionary Computation, 2020, 52:100600.
[13] GONG D W, HAN Y Y, SUN J Y. A novel hybrid multi-objective artificial bee colony algorithm for blocking lot-streaming flow shop scheduling problems[J]. Knowledge-Based Systems, 2018, 148:115-130.
[14] 沈倩, 管在林, 张正敏, 等. 面向卷烟生产调度的集成产能过滤算法与仿真技术的优化框架[DB/OL].(2020 -10-26)[2021-02-07]. https://kns.cnki.net/kcms/detail/11.5946.TP.20201026.1016.012.html.
[14] SHEN Qian, GUAN Zailin, ZHANG Zhengmin,, et al. An optimization framework based on simulation integrated capacity filtering algorithm for cigarette production scheduling[DB/OL].(2020 -10-26)[2021-02-07]. https://kns.cnki.net/kcms/detail/11.5946.TP.20201026.1016.012.html.
[15] 吕洁, 郭婷芳, 韩文民. 虚拟制造单元瓶颈缓冲区容量优化[J]. 组合机床与自动化加工技术, 2016(12):121-124.
[15] LV Jie, GUO Tingfang, HAN Wenmin. Bottleneck buffer allocation optimization of the virtual manufacturing[J]. Modular Machine Tool & Automatic Manufacturing Technique, 2016(12):121-124.
[16] ENGEHAUSEN F, LÖDDING H. Managing sequence-dependent setup times—The target conflict between output rate, WIP and fluctuating throughput times for setup cycles[J]. Production Planning & Control, 2020: 1-17.
[17] DUMAN E, UYSAL M, ALKAYA A F. Migrating birds optimization: A new metaheuristic approach and its performance on quadratic assignment problem[J]. Information Sciences, 2012, 217:65-77.
[18] DINDAR O Z. An improvement on the migrating birds optimization with a problem-specific neighboring function for the multi-objective task allocation problem[J]. Expert Systems With Applications, 2017, 67:304-311.
[19] EXPOSITO IZQUIERDO C, DE ARMAS J, LALLA RUIZ E. Multi-leader migrating birds optimization: A novel nature-inspired metaheuristic for combinatorial problems[J]. International Journal of Bio-Inspired Computation, 2017, 10(4):1.
[20] ALMONACID B, SOTO R, CRAWFORD B. Comparing three simple ways of generating neighboring solutions when solving the cell formation problem using two versions of migrating birds optimization [C]//2017 17th International Conference on Computational Science and Its Applications (ICCSA) . Piscataway, NJ, USA: IEEE, 2017: 1-9.
[21] TONGUR V, ÜLKER E. The analysis of migrating birds optimization algorithm with neighborhood operator on traveling salesman problem[C]//The 19th Asia Pacific Symposium. Bangkok, Thailand: Springer, 2015: 1-11.
[22] ROPKE S, PISINGER D. An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows[J]. Transportation Science, 2006, 40(4):455-472.
[23] 姚妮. 混合候鸟迁徙优化算法求解柔性作业车间调度问题[J]. 华中师范大学学报(自然科学版), 2016, 50(1):38-42.
[23] YAO Ni. Hybrid migrating brids optimization algorithm for the flexible job shop scheduling problem[J]. Journal of Central China Normal University (Natural Sciences), 2016, 50(1):38-42.
[24] 唐立力. 求解低碳调度问题的改进型候鸟优化算法[J]. 计算机工程与应用, 2016, 52(17):166-171.
[24] TANG Lili. Improved migrating birds optimization algorithm to solve low-carbon scheduling problem[J]. Computer Engineering and Applications, 2016, 52(17):166-171.
Options
文章导航

/

〈 〉