基于组合缓冲的分布式置换流水车间调度优化*

doi:10.16731/j.cnki.1671-3133.2025.01.001

现代制造工程 ›› 2025, Vol. 532 ›› Issue (1): 1-14.doi: 10.16731/j.cnki.1671-3133.2025.01.001

• 先进制造系统管理运作 • 下一篇

基于组合缓冲的分布式置换流水车间调度优化^*

轩华, 吕琳

郑州大学管理学院,郑州 450001

收稿日期:2023-12-04 出版日期:2025-01-18 发布日期:2025-02-10
通讯作者: 轩华,博士,教授,主要研究方向为生产计划与调度、物流优化与控制。
作者简介:吕琳,硕士研究生,主要研究方向为物流优化与控制。E-mail:hxuan@zzu.edu.cn
基金资助:
* 国家自然科学基金资助项目(U1804151);河南省科技攻关计划项目(232102321093,232102321026);河南省哲学社会科学规划项目(2023BJJ085)

Distributed permutation flow shop scheduling optimisation with combined-buffer

XUAN Hua, LÜ Lin

School of Management,Zhengzhou University,Zhengzhou 450001,China

Received:2023-12-04 Online:2025-01-18 Published:2025-02-10

摘要/Abstract

摘要： 针对制造行业中机器间有两种缓冲条件(即有限缓冲、零等待)的分布式置换流水车间调度问题,以最小化最大完工时间作为目标建立数学规划模型,提出了一种结合改进两分段Tent混沌映射、自适应柯西变异和贪婪算法的混合人工蜂群算法。首先,通过改进两分段Tent混沌映射产生初始工件序列群;然后,在雇佣蜂阶段采用基于自适应柯西变异的邻域搜索产生新工件序列,在跟随蜂阶段设计适应度选择策略和基于自适应柯西变异的逆序反转操作对工件序列进行优化,在侦察蜂阶段利用贪婪算法基于关键/非关键工厂更新未改善的工件序列;最后,通过大量算例仿真与多种算法对比,表明所提算法在合理的计算时间内可以得到较好的近优解。

关键词: 分布式置换流水车间调度, 有限缓冲和零等待, 混合人工蜂群算法, 改进两分段Tent混沌映射, 自适应柯西变异

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

中图分类号:

TB49

轩华, 吕琳. 基于组合缓冲的分布式置换流水车间调度优化^*[J]. 现代制造工程, 2025, 532(1): 1-14.

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

参考文献

[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.

基于组合缓冲的分布式置换流水车间调度优化^*

Distributed permutation flow shop scheduling optimisation with combined-buffer

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 9

编辑推荐

Metrics

[1]	杨逢海, 杨晓英, 裴志杰, 武亚琪, 张志伟. 基于深度强化学习的风电拉挤板生产智能排程^*[J]. 现代制造工程, 2025, 532(1): 23-32.
[2]	张家骅. 不确定需求下的单向环形设备动态布局方法[J]. 现代制造工程, 2023, 518(11): 12-18.
[3]	张思奇，于登辉，郑一明，李冠洋. 基于多目标候鸟算法的车间布局研究[J]. 现代制造工程, 2022, 497(2): 16-23.
[4]	刘菲，郑参，刘正，张立涛. 基于IE及整数规划理论的生产线平衡研究[J]. 现代制造工程, 2021, 489(6): 101-115.
[5]	张凯，郭永博，张聃，王志国，王冰川. 微激振多余物清理方案设计及仿真分析[J]. 现代制造工程, 2020, 478(7): 60-65.
[6]	包贤哲，丁稳房，宋阿妮. 混沌压缩非线性粒子群算法求解车间调度问题[J]. 现代制造工程, 2020, 480(9): 15-22.
[7]	刘约翰，韩忠华，林硕，史海波，常大亮，孙亮亮. 可重入工序柔性流水车间有限缓冲区排产研究[J]. 现代制造工程, 2020, 482(11): 21-32.
[8]	琚晶晶, 林锦国. 基于改进的GA-SLP生产车间布局规划研究[J]. 现代制造工程, 2017, 446(11): 120-124.
[9]	葛晓梅，李世豪. 基于改进遗传算法的多目标车间布局优化问题研究[J]. 现代制造工程, 2021, 486(3): 10-14.