A Hybrid Algorithm Based on Comprehensive Search Mechanisms for Job Shop Scheduling Problem  

作　　者：Lin Huang Shikui Zhao Yingjie Xiong 

机构地区：[1]School of Mechanical Engineering,University of Jinan,Jinan 250022,China

出　　处：《Complex System Modeling and Simulation》2024年第1期50-66,共17页复杂系统建模与仿真（英文）

基　　金：supported by the National Natural Science Foundation of China(NSFC)(Nos.52275490 and 51775240).

摘　　要：The research on complex workshop scheduling methods has important academic significance and has wide applications in industrial manufacturing.Aiming at the job shop scheduling problem,a hybrid algorithm based on comprehensive search mechanisms(HACSM)is proposed to optimize the maximum completion time.HACSM combines three search methods with different optimization scales,including fireworks algorithm(FW),extended Akers graphical method(LS1+_AKERS_EXT),and tabu search algorithm(TS).FW realizes global search through information interaction and resource allocation,ensuring the diversity of the population.LS1+_AKERS_EXT realizes compound movement with Akers graphical method,so it has advanced global and local search capabilities.In LS1+_AKERS_EXT,the shortest path is the core of the algorithm,which directly affects the encoding and decoding of scheduling.In order to find the shortest path,an effective node expansion method is designed to improve the node expansion efficiency.In the part of centralized search,TS based on the neighborhood structure is used.Finally,the effectiveness and superiority of HACSM are verified by testing the relevant instances in the literature.

关 键 词：job shop scheduling fireworks algorithm tabu search Akers graphical hybrid scheduling algorithms 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]