Large Language Model-Driven Cooperative Operator Ensemble Evolution for Permutation Flow Shop Scheduling
For researchers and practitioners in combinatorial optimization and intelligent manufacturing, this work addresses the search stagnation issue in classical IG algorithms for large and complex PFSP instances.
The paper tackles the permutation flow shop scheduling problem (PFSP) by proposing a multi-operator iterated greedy algorithm (IG-DOE) that uses a stagnation-triggered sequential switching mechanism to switch among destruction operators, and an LLM-assisted framework (SCOE) to automatically evolve a high-quality operator ensemble. On the VRF-hard-large benchmark, IG-DOE achieved much better average performance than the state-of-the-art QIG algorithm under the same CPU-time limit.
The permutation flow shop scheduling problem (PFSP) is a classical NP-hard combinatorial optimization problem in intelligent manufacturing. In practice, PFSP is commonly addressed using metaheuristic algorithms, among which the iterated greedy (IG) algorithm is widely adopted due to its simplicity and strong empirical performance. However, classical IG relies on a single fixed destruction operator, which often limits exploration and leads to search stagnation on large and complex problem instances. To address this issue, this work proposes a multi-operator IG algorithm, termed IG-DOE, which enhances exploration by switching among heterogeneous destruction operators along a single search trajectory. The core mechanism, called stagnation-triggered sequential switching, activates the next destruction operator in an ordered destruction operator ensemble (DOE) when stagnation is detected, thereby enriching the perturbation behavior of classical IG. Moreover, to reduce reliance on expert-crafted operators, a large language model (LLM)-assisted framework, termed SCOE, is introduced to automatically construct a high-quality DOE through stagewise evolution, state-awareness, and cooperative evaluation. Experiments on the challenging \textit{VRF-hard-large} benchmark show that the DOE evolved from smaller problem instances generalizes well to larger unseen instances. Under the same CPU-time limit, IG-DOE obtained much better average performance than QIG, a state-of-the-art IG algorithm. Additional experiments on real-world industrial-data-derived instances further show that the evolved DOE can generalize effectively to different data distributions without additional adaptation.