收稿日期: 2022-06-27
修回日期: 2022-07-24
录用日期: 2022-07-27
网络出版日期: 2022-11-25
基金资助
国家自然科学基金(61973120);国家自然科学基金(61973209);资助项目,河南省科技攻关(202102110282);资助项目,河南省科技攻关(222102110095)
An Improved Multi-Swarm Migrating Birds Optimization Algorithm for Hybrid Flow Shop Scheduling
Received date: 2022-06-27
Revised date: 2022-07-24
Accepted date: 2022-07-27
Online published: 2022-11-25
针对带顺序依赖准备时间的混合流水车间调度(HFS-SDST)问题,以最小化总最大作业完成时间为调度目标,提出一种改进多种群候鸟迁徙优化(IMMBO)算法.算法中个体基于工件加工顺序进行编码,用改进的NEH(MNEH)算法产生初始种群,并按照适应度值分配到各子种群.子种群中领飞鸟和跟飞鸟分别利用串行和并行邻域策略产生邻域个体,如果跟飞鸟优于领飞鸟,二者互换,完成种群内部个体的信息交互;在IMMBO算法中嵌入离散鲸鱼优化策略对各子种群的领飞鸟进行优化,实现子种群之间信息交互;为提高算法的局部搜索(LS)能力,对种群中最优个体执行LS,同时,为了避免算法早熟收敛,针对每个种群的领飞鸟设计了种群多样化控制策略.最后,在实验法调整算法参数的基础上,对IMMBO的4个变体进行了仿真实验,通过测试Ta自适应算例验证IMMBO算法各部分的作用;将IMMBO算法与现有3个算法测试Ta自适应算例,进行实验结果比较,证明了IMMBO算法求解混合车间调度问题的有效性.
关键词： 混合流水车间调度; 改进多种群候鸟迁徙优化; 子种群信息交互; 串行邻域; 并行邻域
张素君, 杨文强, 顾幸生 . 基于改进多种群候鸟迁徙算法的混合流水车间调度[J]. 上海交通大学学报, 2023 , 57(10) : 1378 -1388 . DOI: 10.16183/j.cnki.jsjtu.2022.242
An improved multi-swarm migrating birds optimization (IMMBO) algorithm is proposed for hybrid flow shop scheduling with sequence-dependent setup times (HFS-SDST), to minimize the total maximum completion time (i.e., makespan). Permutation-based encoding is adopted to substitute the individual. The modified Nawaz-Enscore-Ham (MNEH) algorithm is employed to generate initial population which are assigned to each sub-swarm according to the makespan. For each sub-swarm, the neighborhood individuals of the leader and followers are generated respectively by performing serial and parallel neighborhood strategies. If the follower is better than the leader according to their makespan, they are exchanged to ensure the information interaction of individuals within the sub-swarm. Moreover, the discrete whale optimization strategy is embedded in IMMBO to optimize the leaders of all sub-swarms to enhance the interaction among them. Furthermore, the local search is designed for the optimal individual to further improve the local search ability of the algorithm. Meanwhile, to avoid algorithm premature convergence, the control strategy for population diversification is designed to the leader of each sub-swarm. Finally, based on adjusting the algorithm parameters experimentally, simulation experiments are conducted on four variants of IMMBO to verify the function of each part by testing an adaptation dataset of Ta. Moreover, the IMMBO is compared with three existing algorithms by testing an adaptation dataset of Ta, and the experimental results demonstrate the effectiveness of the IMMBO algorithm to solve the hybrid flow shop scheduling problem.
| [1] | ZANDIEH M, FATEMI GHOMI S M T, MOATTAR HUSSEINI S M. An immune algorithm approach to hybrid flow shops scheduling with sequence-dependent setup times[J]. Applied Mathematics and Computation, 2006, 180(1): 111-127. |
| [2] | 李颖俐, 李新宇, 高亮. 混合流水车间调度问题研究综述[J]. 中国机械工程, 2020, 31(23): 2798-2813. |
| [2] | LI Yingli, LI Xinyu, GAO Liang. Review on hybrid flow shop scheduling problems[J]. China Mechanical Engineering, 2020, 31(23): 2798-2813. |
| [3] | SIOUD A, GAGNé C. Enhanced migrating birds optimization algorithm for the permutation flow shop problem with sequence dependent setup times[J]. European Journal of Operational Research, 2018, 264(1): 66-73. |
| [4] | 李俊青, 李文涵, 陶昕瑞, 等. 时间约束混合流水车间调度问题综述[J]. 控制理论与应用, 2020, 37(11): 2273-2290. |
| [4] | LI Junqing, LI Wenhan, TAO Xinrui, et al. A survey on time constrained hybrid flow shop scheduling problems[J]. Control Theory & Applications, 2020, 37(11): 2273-2290. |
| [5] | NADERI B, ZANDIEH M, ROSHANAEI V. Scheduling hybrid flowshops with sequence dependent setup times to minimize makespan and maximum tardiness[J]. The International Journal of Advanced Manufacturing Technology, 2009, 41(11/12): 1186-1198. |
| [6] | MOCCELLIN J V, NAGANO M S, PITOMBEIRA NETO A R, et al. Heuristic algorithms for scheduling hybrid flow shops with machine blocking and setup times[J]. Journal of the Brazilian Society of Mechanical Sciences and Engineering, 2018, 40(2): 1-11. |
| [7] | BURCIN OZSOYDAN F, SA?IR M. Iterated greedy algorithms enhanced by hyper-heuristic based learning for hybrid flexible flowshop scheduling problem with sequence dependent setup times: A case study at a manufacturing plant[J]. Computers & Operations Research, 2021, 125: 105044. |
| [8] | 周炳海, 刘文龙. 考虑能耗和准时的混合流水线多目标调度[J]. 上海交通大学学报, 2019, 53(7): 773-779. |
| [8] | 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. |
| [9] | GóMEZ-GASQUET P, ANDRéS C, LARIO F C. An agent-based genetic algorithm for hybrid flowshops with sequence dependent setup times to minimise makespan[J]. Expert Systems With Applications, 2012, 39(9): 8095-8107. |
| [10] | PAN Q K, GAO L, LI X Y, et al. Effective metaheuristics for scheduling a hybrid flowshop with sequence-dependent setup times[J]. Applied Mathematics and Computation, 2017, 303: 89-112. |
| [11] | TIAN H X, LI K, LIU W. A Pareto-based adaptive variable neighborhood search for biobjective hybrid flow shop scheduling problem with sequence-dependent setup time[J]. Mathematical Problems in Engineering, 2016, 2016: 1257060. |
| [12] | KHARE A, AGRAWAL S. Scheduling hybrid flowshop with sequence-dependent setup times and due windows to minimize total weighted earliness and tardiness[J]. Computers & Industrial Engineering, 2019, 135: 780-792. |
| [13] | DUMAN E, UVSAL M, ALKAVA A F. Migrating birds optimization: a new metaheuristic approach and its performance on quadratic assignment problem[J]. Information Sciences, 2012, 217(24): 65-77. |
| [14] | PAN Q K, DONG Y. An improved migrating birds optimisation for a hybrid flowshop scheduling with total flowtime minimisation[J]. Information Sciences, 2014, 277: 643-655. |
| [15] | HAN D Y, TANG Q H, ZHANG Z K, et al. An improved migrating birds optimization algorithm for a hybrid flow shop scheduling within steel plants[J]. Mathematics, 2020, 8(10): 1661. |
| [16] | 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. |
| [17] | 汤洪涛, 王丹南, 邵益平, 等. 基于改进候鸟迁徙优化的多目标批量流混合流水车间调度[J]. 上海交通大学学报, 2022, 56(2): 201-213. |
| [17] | TANG Hongtao, WANG Dannan, SHAO Yiping, et al. A modified migrating birds optimization for multi-objective lot streaming hybrid flowshop scheduling[J]. Journal of Shanghai Jiao Tong University, 2022, 56(2): 201-213. |
| [18] | BáEZ S, ANGEL-BELLO F, ALVAREZ A, et al. A hybrid metaheuristic algorithm for a parallel machine scheduling problem with dependent setup times[J]. Computers & Industrial Engineering, 2019, 131: 295-305. |
| [19] | HAN Y X, GU X S. Improved multipopulation discrete differential evolution algorithm for the scheduling of multipurpose batch plants[J]. Industrial & Engineering Chemistry Research, 2021, 60(15): 5530-5547. |
| [20] | GAO L, PAN Q K. A shuffled multi-swarm micro-migrating birds optimizer for a multi-resource-constrained flexible job shop scheduling problem[J]. Information Sciences, 2016, 372: 655-676. |
| [21] | TONGUR V, üLKER E. PSO-based improved multi-flocks migrating birds optimization (IMFMBO) algorithm for solution of discrete problems[J]. Soft Computing, 2019, 23(14): 5469-5484. |
| [22] | RUIZ R, STüTZLE T. A simple and effective iterated greedy algorithm for the permutation flowshop scheduling problem[J]. European Journal of Operational Research, 2007, 177(3): 2033-2049. |
| [23] | MIRJALILI S, LEWIS A. The whale optimization algorithm[J]. Advances in Engineering Software, 2016, 95: 51-67. |
| [24] | VALLADA E, RUIZ R, MAROTO C. Synthetic and real benchmarks for complex flow-shops problems[R]. Valencia, Spain:Universitat Politécnica de València, 2003. |
/
| 〈 |
|
〉 |
