融合障碍图模型的柔性作业车间调度混合算法

打开文本图片集

中图分类号：TP301文献标志码：A

Abstract：Aimingattheflexiblejob shopscheduling problem，anobstacle graph model wasconstructedanda hybrid residual scheduling strategy incorporating left-shiftandright-shiftoperations ofremainingjobswasdesignedtoenhance the utilization eficiencyof machineidle time for subsequent operations.During thepath search process of the obstacle graph model，twolocalpathproactivedelaymethodswere introduced tofullutilizejob-levelinsertionneighborhoodmovesand avoid redundant movement operation cycles.Amobilejobselection search algorithmwas used to guide theoveraliterative process ofthe obstacle graph model，soas to deeply search thesolution spaceand generate more discriminative neighborhood solutionsets.Withthe makespan as theoptimizationobjective，a hybridalgorithm integrating theobstacle graph model for flexible job shop scheduling was proposed based on the existing algorithm forflexible job shop scheduling including genetic algorithmand two-level neighborhoodsearch.The proposedalgorithmwasdevelopedand implemented by using MATLAB software.Its performance was tested and evaluated on 31 benchmark instances，and compared with classical algorithms intheliterature.Theresultsshow thatthecomputation speedacross all31benchmark instances is improvedafter integrating theobstacle graph model intothe proposed algorithm.Theoptimal values of the makespanfor 5 benchmark instances are improved，and the means ofrelative deviations for BRdata and BCdata benchmark instance sets are optimized to14.98and22.45，respectively.The effectivenessof the proposed algorithm is verifiedbycomparing the means of relative deviations of its solutions and those of classical algorithms from the literature.

Keywords：flexible job shop scheduling problem；obstacle graph model；two-level neighborhood；makespan

柔性作业车间调度问题（flexiblejob shop sched-ulingproblem，FJSP）是一种广泛应用于工业生产的离散资源优化问题，同时也是典型的非确定性多项式时间（NP）困难问题。（剩余12029字）