Distributed permutation flow shop scheduling optimisation with combined-buffer

doi:10.16731/j.cnki.1671-3133.2025.01.001

Abstract

Abstract: The permutation flow shop problem with two inter-machine buffer conditions (i.e.limited buffer,zero-wait) is studied arising from manufacturing industry,and a mathematical programming model is established with the objective of minimizing maximum completion time.A mixed artificial bee colony algorithm is then proposed combined with improved two-segment Tent chaotic mapping,adaptive Cauchy mutation and greedy algorithm. Firstly,the initial job sequence population is generated by improving two-segment Tent chaotic mapping. Then,in the employed bee phase,the neighborhood search based on adaptive Cauchy mutation is applied to generate new job sequences. In the onlooker bee stage,a selection fitness strategy and the inverse-order reversal operation based on adaptive Cauchy mutation are designed to optimize the job sequences.In the scout bee phase,unimproved job sequence is updated based on key/non-key factories by greedy algorithm. Finally,a large number of simulations and comparisons with various algorithms show that the proposed algorithm can obtain a good near-optimal solution in a reasonable computational time.

Key words: distributed permutation flow shop schedule problem, limited buffer and zero-wait, mixed artificial bee colony algorithm, improved two-segment Tent chaotic mapping, adaptive Cauchy mutation

CLC Number:

TB49

XUAN Hua, LÜ Lin. Distributed permutation flow shop scheduling optimisation with combined-buffer[J]. Modern Manufacturing Engineering, 2025, 532(1): 1-14.

References

[1] 王海群,费斐,陈凯玲.基于能源区块链的虚拟电厂分布式调度策略[J].系统管理学报,2022,31(2):406-411.
[2] WANG Y,LI X,RUIZ R,et al.An iterated greedy heuristic for mixed no-wait flowshop problems[J].IEEE Transactions on Cybernetics,2018,48(5):1553-1566.
[3] NADERI B,RUIZ R.The distributed permutation flowshop scheduling problem[J].Computers & Operations Research,2010,37(4):754-768.
[4] YANG S,WANG J,XU Z.Real-time scheduling for distributed permutation flowshops with dynamic job arrivals using deep reinforcement learning[J].Advanced Engineering Informatics,2022,54:101776.
[5] YU Y,ZHANG F Q,YANG G D,et al.A discrete artificial bee colony method based on variable neighborhood structures for the distributed permutation flowshop problem with sequence-dependent setup times[J].Swarm and Evolutionary Computation,2022,75:101179.
[6] MAO J Y,PAN Q K,MIAO Z H,et al.A hash map-based memetic algorithm for the distributed permutation flowshop scheduling problem with preventive maintenance to minimize total flowtime[J].Knowledge-Based Systems,2022,242:108413.
[7] GUO H,SANG H,ZHANG B,et al.An effective metaheuristic with a differential flight strategy for the distributed permutation flowshop scheduling problem with sequence-dependent setup times[J].Knowledge-Based Systems,2022,242:108328.
[8] KARABULUT K,ÖZTOP H,KIZILAY D,et al.An evolution strategy approach for the distributed permutation flowshop scheduling problem with sequence-dependent setup times[J].Computers & Operations Research,2022,142:105733.
[9] JING X L,PAN Q K,GAO L,et al.An effective iterated greedy algorithm for a robust distributed permutation flowshop problemwithcarryover sequence-dependent setup time[J].IEEE Transactions on Systems,Man,and Cybernetics:Systems,2021,52(9):5783-5794.
[10] SCHULZ S,SCHöNHEIT M,NEUFELD J S.Multi-objective carbon-efficient scheduling in distributed permutation flow shops under consideration of transportation efforts[J].Journal of Cleaner Production,2022,365(10):132551.
[11] AVCI M,AVCI M G,HAMZADAYI A.A branch-and-cut approach for the distributed no-wait flowshop scheduling problem[J].Computers & Operations Research,2022,148:106009.
[12] ZHAO F,JIANG T,WANG L.A reinforcement learning driven cooperative meta-heuristic algorithm for energy-efficient distributed no-wait flow-shop scheduling with sequence-dependent setup time[J].IEEE Transactions on Industrial Informatics,2022,19(7):8427-8440.
[13] ALLALI K,AQIL S,BELABID J.Distributed no-wait flow shop problem with sequence dependent setup time:Optimization of makespan and maximum tardiness[J].Simulation Modelling Practice and Theory,2022,116:102455.
[14] ZENG Q,LI J,LI R,et al.Improved NSGA-II for energy-efficient distributed no-wait flow-shop with sequence-dependent setup time[J].Complex & Intelligent Systems,2023,9(1):825-849.
[15] 徐震浩,王程,顾幸生.基于DICA的存储受限流水车间调度[J].华东理工大学学报(自然科学版),2018,44(4):563-572.
[16] ZHANG G,XING K.Differential evolution metaheuristics for distributed limited-buffer flowshop scheduling with makespan criterion[J].Computers & Operations Research,2019,108:33-43.
[17] 王垒,摆亮,钱斌,等.分布式有限缓冲区流水车间混合EDA调度[J].控制工程,2020,27(4):593-598.
[18] LU C,HUANG Y,MENG L,et al.A Pareto-based collaborative multi-objective optimization algorithm for energy-efficient scheduling of distributed permutation flow-shop with limited buffers[J].Robotics and Computer-Integrated Manufacturing,2022,74:102277.
[19] CHENG C Y,LIN S W,POURHEJAZY P,et al.Minimizing total completion time in mixed-blocking permutation flowshops[J].IEEE Access,2020,8:142065-142075.
[20] SHAO Z,SHAO W,PI D.Effective constructive heuristic and iterated greedy algorithm for distributed mixed blocking permutation flow-shop scheduling problem[J].Knowledge-Based Systems,2021,221:106959.
[21] LIU S Q,KOZAN E.Scheduling a flow shop with combined buffer conditions[J].International Journal of Production Economics,2009,117(2):371-380.
[22] 王万良,宋璐,徐新黎,等.含有混合中间存储策略的模糊流水车间调度方法[J].计算机集成制造系统,2006,12(12):2067-2073.
[23] LIU S Q,KOZAN E.Parallel-identical-machine job-shop scheduling with different stage-dependent buffering requirements[J].Computers & Operations Research,2016,74:31-41.
[24] LIU S Q,KOZAN E,MASOUD M,et al.Job shop scheduling with a combination of four buffering constraints[J].International Journal of Production Research,2018,56(9):3274-3293.
[25] 孙厚权,张其亮.人工蜂群算法求解混合约束流水车间调度问题[J].计算机技术与发展,2019,29(3):144-148,153.
[26] 刘金梅,张卫,丘水生.一种改善Tent混沌序列随机性的方法[J].计算机工程,2012,38(6):10-12.
[27] ALGHAMDI A S.A new self-adaptive teaching-learning-based optimization with different distributions for optimal reactive power control in power networks[J].Energies,2022,15(8):2759.
[28] 轩华,李文婷,李冰.混合离散人工蜂群算法求解含不相关并行机的分布式柔性流水线调度[J].控制与决策,2023,38(3):779-789.
[29] 轩华,付鑫博,李冰.基于混合离散人工蜂群算法的混合零等待柔性流水车间优化研究[J].工业工程与管理,2023,28(1):170-180.