计算机科学 ›› 2025, Vol. 52 ›› Issue (4): 271-279.doi: 10.11896/jsjkx.240600049
王思彤, 林荣恒
WANG Sitong, LIN Rongheng
摘要： 相比于传统流水线,混合流水车间具有更高的灵活性,能适应多变的生产场景,但其排产方案的求解复杂度更高,是现代实际制造系统中的常见问题。针对群智能进化算法在解决该问题时计算难度大且搜索效率不高的问题,以最小化总完工时间为优化目标,提出了一种混合禁忌搜索遗传优化算法。该算法根据排产问题中所有工件具有相同生产工艺、工件数量多、各阶段并行机不同速的特点,采用了基于首阶段工件顺序的单层编码、考虑机器选择三层优先级的解码方法、多种遗传算子和禁忌搜索算子,具有更加优秀的搜索性能,在保证解质量的基础上提高了算法的收敛速度。最后,通过40个算例和实际应用案例评估算法性能,并将其与其他算法进行比较。实验结果表明,所提出的算法在求解中规模算例、大规模算例和加工车间案例时表现优秀,排产结果的完工时间平均缩短了10.71%,算法达到最优解所需的迭代次数减少了25.72%,运行时间缩短了10.79%。
中图分类号:
| [1]LI Y L,LI X T,GAO L.A survey of hybrid flow shop scheduling problems [J].China Mechanical Engineering,2020,31(23):2798-2813,2828. [2]RAUF M,GUAN Z,SARFRAZ S,et al.A smart algorithm for multi-criteria optimization of model sequencing problem in assembly lines[J].Robotics and Computer-Integrated Manufacturing,2020,61:101844. [3]MOSADEGH H,GHOMI S M T F,SÜER G A.Stochasticmixed-model assembly line sequencing problem:Mathematical modeling and Q-learning based simulated annealing hyper-heuristics[J].European Journal of Operational Research,2020,282(2):530-544. [4]ZHOU Q Y,XIAO M S,ZHANG L X,et al.Intelligent optimization technology for production scheduling under multiple constraints [J].Computer Science,2021,48(3):239-245. [5]LV Y Y,FAN K,QU H,et al.Multi-objective particle swarm optimization for hybrid multiprocessor task shop scheduling problem [J].Microcomputer System,2022,43(1):218-224. [6]LI Y,LI X,GAO L,et al.A discrete artificial bee colony algorithm for distributed hybrid flowshop scheduling problem with sequence-dependent setup times[J].International Journal of Production Research,2021,59(13):3880-3899. [7]LU C,GAOL,PAN Q,et al.A multi-objective cellular grey wolf optimizer for hybrid flowshop scheduling problem considering noise pollution[J].Applied Soft Computing,2019,75:728-749. [8]DONG J,YE C M.Interval number reentrant hybrid flow shop scheduling and pre-maintenance collaborative optimization [J].Control and Decision-making,2021,36(11):2599-2608. [9]ZHOUE Y Q,WANG C Y,LI Y L,et al.Improved fruit fly algorithm for hybrid flow shop scheduling problem [J].Control Theory and Application,2023,40(4):597-606. [10]ZHANG B,XU L,ZHANG J.A multi-objective cellular genetic algorithm for energy-oriented balancing and sequencing problem of mixed-model assembly line[J].Journal of Cleaner Production,2020,244:118845. [11]DEFERSHA F M,MOHEBALIZADEHGASHTI F.Simultaneous balancing,sequencing,and workstation planning for a mixed model manual assembly line using hybrid genetic algorithm[J].Computers & Industrial Engineering,2018,119:370-387. [12]YUAN S,LI T K,WANG B L.Improved migratory bird optimization algorithm for group scheduling problem of hybrid flow shop with unrelated parallel machines [J].Computer Integrated Manufacturing System,2022,28(12):3912-3922. [13]LOPES T C,SIKORA C G S,MICHELS A S,et al.An iterative decomposition for asynchronous mixed-model assembly lines:combining balancing,sequencing,and buffer allocation[J].International Journal of Production Research,2020,58(2):615-630. [14]ABREU L R,PRATA B A.A hybrid genetic algorithm for solving the unrelated parallel machine scheduling problem with sequence dependent setup times[J].IEEE Latin America Transactions,2018,16(6):1715-1722. [15]XUAN H,ZHENG Q,LI B,et al.A novel genetic simulated annealing algorithm for no-wait hybrid flowshop problem with unrelated parallel machines[J].ISIJ International,2021,61(1):258-268. [16]OMARA F A,ARAFA M M.Genetic algorithms for task sche-duling problem[J].Journal of Parallel and Distributed computing,2010,70(1):13-22. [17]ZHANG C Y,LI P G,GUAN Z L,et al.A tabu search algorithm with a new neighborhood structure for the job shop scheduling problem[J].Computers & Operations Research,2007,34(11):3229-3242. [18]MASTROLILLI M,GAMBARDELLA L M.Effective neigh-bourhood functions for the flexible job shop problem[J].Journal of scheduling,2000,3(1):3-20. [19]ZHOU H,LIU H,LV C,et al.A Path Relinking with Tabu Search Algorithm for Solving Hybrid Flow Shop Scheduling Problem Considering Multiple Critical Paths[J].Computer &Operations Research,2024,170:106783. [20]CARLIER J,NERON E.An exact method for solving the multi-processor flow-shop[J].RAIRO-Operations Research-Recherche Opérationnelle,2000,34(1):1-25. [21]LIAO C J,TJANDRADJAJA E,CHUNG T P.An approachusing particle swarm optimization and bottleneck heuristic to solve hybrid flow shop scheduling problem[J].Applied Soft Computing,2012,12(6):1755-1764. [22]LIU C.Application of genetic algorithm in parallel multi-locomotive scheduling problem of enterprise A [D].Shanghai:Dong-hua University,2022. [23]YU C,SEMERARO Q,MATTA A.A genetic algorithm for the hybrid flow shop scheduling with unrelated machines and machine eligibility[J].Computers & Operations Research,2018,100:211-229. [24]SUN L,SHI W,WANG J,et al.Research on production scheduling technology in knitting workshop based on improved genetic algorithm[J].Applied Sciences,2023,13(9):5701. [25]FAN J,LI Y,XIE J,et al.A hybrid evolutionary algorithm using two solution representations for hybrid flow-shop scheduling problem[J].IEEE Transactions on Cybernetics,2021,53(3):1752-1764. |
|
||
首页