Solving the permutation flow shop scheduling problem with sequence-dependent setup time via iterative greedy algorithm and imitation learning

Zhao-sheng Du, Jun-qing Li, Hao-nan Song, Kai-zhou Gao, Ying Xu, Jia-ke Li and Zhi-xin Zheng

Mathematics and Computers in Simulation (MATCOM), 2025, vol. 234, issue C, 169-193

Abstract: In recent years, the application of learning-based methods in flow shop scheduling problem has gained considerable attention. However, there are gaps in the quality of their solution due to the difficulty of fully exploring the huge search space faced by learning-based methods and the difficulty of reward function design. In this paper, a hybrid approach of meta-heuristic algorithm and imitation learning (IL) is proposed to solve the permutation flow shop scheduling problem with sequence-dependent setup times (PFSP-SDST). Firstly, jobs are treated as nodes, and the processing time and setup times of PFSP-SDST are considered as features of the nodes, respectively. Secondly, a graph neural network based on an attention feature fusion (AFF) mechanism is designed as an encoder to embed the feature information of the problem. Finally, an iterative greedy algorithm based on critical path is proposed to provide high-quality expert solutions for the IL algorithm. The running results on randomly generated datasets and benchmark datasets demonstrate the effectiveness of the proposed method.

Keywords: Graph neural network (GNN); Imitation learning (IL); Permutation flow shop scheduling; Attentional feature fusion (AFF); Iterative greedy algorithm (IGA) (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0378475425000692
Full text for ScienceDirect subscribers only

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:eee:matcom:v:234:y:2025:i:c:p:169-193

DOI: 10.1016/j.matcom.2025.02.026

Access Statistics for this article

Mathematics and Computers in Simulation (MATCOM) is currently edited by Robert Beauwens

More articles in Mathematics and Computers in Simulation (MATCOM) from Elsevier
Bibliographic data for series maintained by Catherine Liu ().