Graph Knowledge-Enhanced Iterated Greedy Algorithm for Hybrid Flowshop Scheduling Problem

Yingli Li, Biao Zhang (), Kaipu Wang, Liping Zhang, Zikai Zhang and Yong Wang
Additional contact information
Yingli Li: School of Management, Wuhan University of Science and Technology, Wuhan 430081, China
Biao Zhang: School of Computer Science, Liaocheng University, Liaocheng 252000, China
Kaipu Wang: Hubei Digital Manufacturing Key Laboratory, School of Mechanical and Electronic Engineering, Wuhan University of Technology, Wuhan 430062, China
Liping Zhang: Key Laboratory of Metallurgical Equipment and Control Technology, Wuhan University of Science and Technology, Wuhan 430081, China
Zikai Zhang: Key Laboratory of Metallurgical Equipment and Control Technology, Wuhan University of Science and Technology, Wuhan 430081, China
Yong Wang: School of Management, Wuhan University of Science and Technology, Wuhan 430081, China

Mathematics, 2025, vol. 13, issue 15, 1-22

Abstract: This study presents a graph knowledge-enhanced iterated greedy algorithm that incorporates dual directional decoding strategies, disjunctive graphs, neighborhood structures, and a rapid evaluation method to demonstrate its superior performance for the hybrid flowshop scheduling problem (HFSP). The proposed algorithm addresses the trade-off between the finite solution space corresponding to solution representation and the search space for the optimal solution, as well as constructs a decision mechanism to determine which search operator should be used in different search stages to minimize the occurrence of futile searching and the low computational efficiency caused by individuals conducting unordered neighborhood searches. The algorithm employs dual decoding with a novel disturbance operation to generate initial solutions and expand the search space. The derivation of the critical path and the design of neighborhood structures based on it provide a clear direction for identifying and prioritizing operations that have a significant impact on the objective. The use of a disjunctive graph provides a clear depiction of the detailed changes in the job sequence both before and after the neighborhood searches, providing a comprehensive view of the operational sequence transformations. By integrating the rapid evaluation technique, it becomes feasible to identify promising regions within a constrained timeframe. The numerical evaluation with well-known benchmarks verifies that the performance of the graph knowledge-enhanced algorithm is superior to that of a prior algorithm, and seeks new best solutions for 183 hard instances.

Keywords: hybrid flow-shop scheduling problem; iterated greedy algorithm; critical paths; neighborhood structure; rapid evaluation method (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/13/15/2401/pdf (application/pdf)
https://www.mdpi.com/2227-7390/13/15/2401/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:13:y:2025:i:15:p:2401-:d:1710296

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().