求解模糊分布式调度的竞争人工蜂群算法

doi:10.11896/jsjkx.250400001

摘要/Abstract

摘要： 分布式调度是分布式制造的重要环节,也是目前调度研究的焦点,而不确定性是分布式制造的本质特性。针对考虑工厂适用性和附加资源的模糊分布式两阶段混合流水车间调度问题,提出一种竞争人工蜂群(CABC)算法以最小化最大完成时间和总一致指标。为了获得高质量优化结果,将种群划分为两个蜂群,构建了两个蜂群间的竞争过程。该过程定义取胜蜂群为雇佣蜂群,失败蜂群为跟随蜂群,整个过程由雇佣蜂阶段和额外搜索、自适应跟随蜂阶段组成。给出了5种搜索策略并实现了蜂群间的差异化搜索,设计了一种自适应种群重构方法以避免蜂群间的过度竞争。进行了大量计算实验,实验结果验证了CABC新策略的有效性和它在求解模糊分布式调度方面的较强搜索优势。

关键词: 模糊, 分布式调度, 混合流水车间, 人工蜂群算法, 智能优化

Abstract: Distributed scheduling is important part of distributed manufacturing and the focus of the scheduling research.Uncertainty is the basic feature of distributed maufacturing.To solve fuzzy distributed two-stage hybrid flow shop scheduling problem with factory eligibility and additional resources,a competition artificial bee colony(CABC) algorithm is proposed to minimize makespan and total agreement index.To obtain high quality solutions,the whole population is divided into two bee swarms and competition process between them is constructed.In the competition process,the winning swarm is used as employed bee swarm and another one acts as onlooker bee swarm.The competition process is composed of employed bee phase and extra search,and adaptive onlooker bee phase.Five search strategies are given and the diversified search is implemented.An adaptive population reconstruction is applied to avoid excessive competition between swarms.Experiments are conducted and the computational results reveal that new strategies of CABC are effective and CABC has the promising search advantages on solving the considered pro-blem.

Key words: Fuzzy, Distributed scheduling, Hybrid flow shop, Artificial bee colony, Intelligent optimization

中图分类号:

TP273

郑友莲. 求解模糊分布式调度的竞争人工蜂群算法[J]. 计算机科学, 2026, 53(7): 178-185. https://doi.org/10.11896/jsjkx.250400001

ZHENG Youlian. Competitive Artificial Bee Colony Algorithm for Fuzzy Distributed Scheduling[J]. Computer Science, 2026, 53(7): 178-185. https://doi.org/10.11896/jsjkx.250400001

参考文献

[1]YAN Q,WU N Q,HE Y F,et al.Adaptive genetic algorithm for two-stage hybrid flow-shop scheduling with sequence-dependent setup time and no-interruption requirement[J].Expert Systems with Applications,2022,208:118068.
[2]WANG M,ZHANG J,ZHANG P,et al.Independent double DQN-based multi-agent reinforcement learning approach for online two-stage hybrid flow shop scheduling with batch machines[J].Journal of Manufacturing Systems,2022,65:694-708.
[3]HIDRI L,ELSHERBEENY A M.Optimal solution to the two-stage hybrid flow shop scheduling problem with removal and transportation times[J].Symmetry,2022,14(7):1424.
[4]LIU H,ZHAO F Q,WANG L,et al.An estimation of distribution algorithm with multiple intensification strategies for two-stage hybrid flow-shop scheduling problem with sequence-dependent setup time[J].Applied Intelligence,2022,53:5160-5178.
[5]ZHANG S,HE Z W,YANG Z,et al.Effective upper and lower bounds for a two-stage reentrant flexible flow shop scheduling problem[J].Computers and Operations Research,2023,153:106183.
[6]KOMAKI G M,TEYMOURIAN E,KAYVANFAR V.Mini-mising makespan in the two-stage assembly hybrid flow shop scheduling problem using artificial immune systems[J].International Journal of Production Research,2016,54:963-983.
[7]LANG S,REGGELIN T,SCHMIDT J,et al.Neuro Evolution of augmenting topologies for solving a two-stage hybrid flow shop scheduling problem:a comparison of different solution strategies[J].Expert Systems with Applications,2021,172:114666.
[8]FIGIELSKA E.A heuristic for scheduling in a two-stage hybridflow shop with renewable resources shared among the stages[J].European Journal of Operational Research,2014,236(2):433-444.
[9]WANG S,LIU M.Two-stage hybrid flow shop scheduling with preventive maintenance using multi-objective tabu search method[J].International Journal of Production Research,2014,52(5):1495-1508.
[10]WANG S J,WANG X D,CHU F,et al.An energy-efficient two-stage hybrid flow shop scheduling problem in a glass production[J].International Journal of Production Research,2020,58(8):2283-2314.
[11]WANG Y M,LEI D M.A feedback-based artificial bee colony algorithm for solving distributed two-stage hybrid flow shop scheduling[J].Control Theory and Applications,2024,41(6):1137-1146.
[12]CAI J C,ZHOU R,LEI D M.Fuzzy distributed two-stage hybrid flow shop scheduling problem with setup time:collaborative variable search[J].Journal of Intelligent and Fuzzy Systems,2020,38(3):3189-3199.
[13]XI B J,LEI D M.Q-learning teaching-learning optimization for distributed two-stage hybrid flow shop scheduling with fuzzy processing time[J].Complex System Modeling and Simulation,2022,2(2):113-129.
[14]DONG J,YE C M.Green scheduling of distributed two-stagereentrant hybrid flow shop considering distributed energy resources and energy storage system[J].Computers and Industrial Engineering,2022,169:108146.
[15]LEI D M,WANG T.An improved shuffled frog leaping algorithm for the distributed two-stage hybrid flow shop scheduling[J].Control and Decision,2021,36(1):241-248.
[16]CEI JC,LEI D M.Distributed two-stage flow shop scheduling with setup time[J] Computers Integrated Manufacturing Systems,2020,25(8):2170- 2179.
[17]XU T P,ZHAO F Q,ZHANG J L,et al.Distributed flexible flow-shop scheduling problem with time-of-use electricity tariffs constraint and its solving algorithm[J].Computers Integrated Manufacturing Systems,2025,31(4):1299-1313.
[18]MRAIHI T,DRISS Q B,El-HAOUZI H B.Distributed permutation flow shop scheduling problem with worker flexibility:review,trends and model proposition[J].Expert Systems with Applications,2024,238:121947.
[19]ZHANG Z P,FU Y P,GAO K Z,et al.A learning-driven multi-objective cooperative artificial bee colony algorithm for distributed flexible job shop scheduling problems with preventive maintenance and transportation operations[J].Computers and Industrial Engineering,2024,196:110484.
[20]LI R.WANG L,GONG W Y,et al.An evolutionary multitasking memetic algorithm for multi-objective distributed heterogeneous welding flow shop scheduling[J].IEEE Transactions on Evolutionary Computation,2025,29(6):2287-2298.
[21]SHAO Z S,SHAO W S,CHEN J R,et al.A feedback learning-based selection hyper-heuristic for distributed heterogeneous hybrid blocking flow-shop flexible scheduling problem with flexible assembly and setup time[J].Engineering Applications of Artificial Intelligence,2024,131:107818.
[22]QIN H,LI T,TENG Y,et al.Integrated production and distribution scheduling in distributed hybrid flow shops[J].Memetic Computing,2021,13(2):185-202.
[23]EDIS E B,OGUZ C,OZKARAHAN I.Parallel machine scheduling with additional resources:Notation,classification,models and solution methods[J].European Journal of Operational Research,2013,230:449-463.
[24]GENG K,LIU L,WU Z.Energy-efficient distributed heterogeneous re-entrant hybrid flow shop scheduling problem with sequence dependent setup times considering factory eligibility constraints[J].Scientific Reports,2022,12(1):18741.
[25]LI Y L,LI X Y,GAO L,et al.A discrete artificial bee colony algorithm for distributed hybrid flow shop scheduling problem with sequence-dependent setup Times[J].International Journal of Production Research,2020,59(13):3880-3899.
[26]LI YL,LI X Y,GAO L,et al.An improved artificial bee colony algorithm for distributed heterogeneous hybrid flow shop sche-duling problem with sequence-dependent setup times[J].Computers & Industrial Engineering,2020,147:106638.
[27]LEI D M.Solving fuzzy job shop scheduling problems using random key genetic algorithm[J].International Journal of Advanced Manufacturing Technology,2010,49:253-262.
[28]DEB K,PRATAP A,AGARWAL S,et al.A fast and elitist multiobjective genetic algorithm:NSGA-II [J].IEEE Transactions on Evolutionary Computation,2002,6(2):182-197.
[29]DENG J,WANG L.A competitive memetic algorithm for multi-objective distributed permutation flow shop scheduling problem[J].Swarm and Evolutionary Computation,2017,32:121-131.
[30]SHAO W S,SHAO Z S,PI D C.A Pareto-Based Estimation of Distribution Algorithm for Solving Multiobjective Distributed No-Wait Flow-Shop Scheduling Problem With Sequence-Depen-dent Setup Time[J].IEEE Transactions on Automation Science and Engineering,2019,16(3):1344-1360.
[31]BOSMAN P,THIERENS D.The balance between proximity and diversity in multiobjective evolutionary algorithms[J].IEEE Transactions on Evolutionary Computation,2003,7(2):174-188.
[32]ZITZLER E,THIELE L.Multi-objective evolutionary algorithms:a comparative case study and the strength Pareto approach[J].IEEE Transactions on Evolutionary Computation,1999,3(4):257-271.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed