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

Title:
A Hybrid Algorithm Based on Comprehensive Search Mechanisms for Job Shop Scheduling Problem
Authors:
Lin Huang, Shikui Zhao, Yingjie Xiong
Source:
Complex System Modeling and Simulation, Vol 4, Iss 1, Pp 50-66 (2024)
Publisher Information:
Institute of Electrical and Electronics Engineers (IEEE), 2024.
Publication Year:
2024
Subject Terms:
TA168, fireworks algorithm, akers graphical, Electronic computers. Computer science, job shop scheduling, tabu search, 0211 other engineering and technologies, 0202 electrical engineering, electronic engineering, information engineering, QA75.5-76.95, 02 engineering and technology, hybrid scheduling algorithms, Systems engineering
Document Type:
Fachzeitschrift Article
ISSN:
2097-3705
2096-9929
DOI:
10.23919/csms.2024.0001
Access URL:
https://doaj.org/article/c6ce9cf348bd461ea64c49eb14d010af
Accession Number:
edsair.doi.dedup.....b6e2394568089b3782d7ca19da99a76d
Database:
OpenAIRE

Weitere Informationen

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.