Large Language Model-Driven Cooperative Operator Ensemble Evolution for Permutation Flow Shop Scheduling
Proposes IG-DOE, a large language model-assisted cooperative operator ensemble evolution algorithm, integrating multi-operator switching to significantly improve permutation flow shop scheduling performance.
Key Findings
Methodology
The proposed IG-DOE algorithm builds upon the classical iterated greedy (IG) framework by incorporating a destruction operator ensemble (DOE) and a stagnation-triggered sequential switching (STSS) mechanism. The core innovation is to dynamically switch among heterogeneous destruction operators when stagnation is detected, thus enhancing exploration. To automate the construction of high-quality DOE, the authors develop a stagewise cooperative evolution framework (SCOE), which leverages large language models (LLMs) to generate and evaluate candidate operators based on stage-specific performance and cooperation metrics. The process involves iterative generation, cooperative evaluation, and selection, guided by a state-aware mechanism. Experimental results on the VRF-hard-large benchmark demonstrate that the evolved operator ensemble generalizes well from small training instances (n=100, 200) to large unseen instances (n=300–800), outperforming the state-of-the-art QIG algorithm with a 17.8% reduction in average relative deviation. Additional validation on real industrial data confirms the robustness and transferability of the approach.
Key Results
- On the VRF-hard-large benchmark, IG-DOE achieved an average relative deviation (ARD) of 1.69%, compared to 2.05% by QIG, representing a 17.8% improvement under the same CPU time limit. It effectively solved instances with up to 800 jobs, demonstrating strong scalability and generalization from small training sets (n=100, 200).
- In real-world industrial datasets from an instrument manufacturing workshop, IG-DOE delivered superior scheduling solutions without additional tuning, confirming its practical applicability and robustness across different data distributions.
- Ablation studies verified that the multi-operator switching mechanism (STSS) significantly enhances the ability to escape local optima, compared to single-operator strategies. The automatic operator evolution via SCOE effectively produces complementary destruction operators, leading to improved search diversity and solution quality.
Significance
This work advances the frontier of automated heuristic design by integrating deep learning with metaheuristic search, addressing the long-standing challenge of designing effective destruction operators for large-scale combinatorial scheduling. The automatic construction of operator ensembles via LLMs reduces reliance on expert knowledge, enabling scalable and adaptable solutions for complex industrial problems. The demonstrated generalization from small training instances to large, unseen instances underscores the potential for deploying such AI-driven methods in real manufacturing environments, contributing to smarter, more autonomous production systems. The approach also opens new avenues for research in combining deep learning with classical optimization, fostering a new paradigm of intelligent, self-adaptive scheduling algorithms that can learn from data and evolve over time.
Technical Contribution
The primary technical innovations include: 1) the development of IG-DOE, which replaces a single fixed destruction operator with a dynamically switched ensemble guided by stagnation detection, thereby improving exploration and escape from local optima; 2) the design of SCOE, a stagewise cooperative evolution framework that leverages LLMs to generate and evaluate diverse destruction operators based on stage-specific performance and cooperation metrics; 3) the integration of these components into a unified algorithm that demonstrates superior scalability and generalization in large-scale PFSP instances. The method also introduces a novel combination of deep learning-guided heuristic generation with classical metaheuristic search, providing theoretical insights into operator diversity and adaptive switching mechanisms.
Novelty
This work is the first to incorporate large language models into the automatic construction of operator ensembles for combinatorial scheduling problems. Unlike prior approaches that rely on manually crafted operators or static heuristic sets, SCOE dynamically generates and evaluates heterogeneous destruction operators, enabling the algorithm to adaptively learn effective strategies. The combination of deep learning, stagewise cooperative evolution, and stagnation-triggered switching constitutes a novel framework that significantly enhances search exploration and solution quality, representing a new paradigm in automated heuristic design for complex optimization tasks.
Limitations
- The performance heavily depends on the representativeness of the training set; if the training instances do not capture the diversity of real-world problems, the generalization may be limited.
- The computational cost of the automatic operator generation and evaluation process is relatively high, especially for large-scale problems, which may hinder real-time applications.
- The current framework primarily targets the makespan minimization objective; extending it to multi-objective or constrained scheduling scenarios requires further research.
- The effectiveness of the learned operators may diminish when faced with problem instances exhibiting significantly different structures or constraints not present in the training data.
Future Work
Future research will explore multi-objective and dynamic scheduling scenarios, incorporating reinforcement learning to enable online adaptation of operator ensembles. Enhancing the efficiency of the operator generation process, possibly through surrogate models or transfer learning, is another promising direction. Additionally, extending the framework to other combinatorial optimization problems, such as vehicle routing or job shop scheduling, could broaden its applicability. Finally, integrating real-time data streams for adaptive scheduling in manufacturing environments will be a key step toward fully autonomous production systems.
AI Executive Summary
In the realm of modern manufacturing, production scheduling remains a critical yet challenging task. As factories grow larger and more complex, traditional heuristic algorithms struggle to deliver optimal solutions within reasonable timeframes. The permutation flow shop scheduling problem (PFSP), a classical NP-hard challenge, exemplifies this difficulty. It involves sequencing jobs across multiple machines to minimize the total completion time, or makespan. Existing metaheuristics like iterated greedy (IG) have shown empirical success, but their reliance on fixed, single operators limits exploration, especially in large, intricate instances.
Recognizing this bottleneck, researchers have sought to diversify search strategies by incorporating multiple operators or hybrid methods. However, manually designing effective operator sets is labor-intensive and often suboptimal. Recent advances in deep learning, particularly large language models (LLMs), offer a promising avenue for automating heuristic design. This paper introduces the Large Language Model-Driven Cooperative Operator Ensemble (SCOE) framework, which automates the construction of destruction operator ensembles (DOE) and integrates them into an enhanced IG algorithm (IG-DOE).
The core innovation lies in the stagewise cooperative evolution process, where LLMs generate candidate operators based on training data, and a cooperative evaluation mechanism assesses their synergy with existing operators. This iterative process results in a diverse, high-quality operator set tailored for large-scale instances. The algorithm employs a stagnation-triggered sequential switching (STSS) mechanism, which dynamically switches among operators when progress stalls, thus maintaining search diversity and avoiding local optima.
Experimental results on the challenging VRF-hard-large benchmark demonstrate that IG-DOE, trained on small instances with 100-200 jobs, generalizes effectively to instances with up to 800 jobs. It achieves a 17.8% reduction in average relative deviation compared to the state-of-the-art QIG algorithm, highlighting its superior exploration and exploitation balance. Further validation on real industrial datasets confirms its robustness and practical relevance.
This work marks a significant step toward fully automated, data-driven heuristic design for complex scheduling problems. By combining deep learning, metaheuristic search, and automatic operator evolution, it paves the way for more intelligent, adaptable manufacturing systems. Future directions include extending the framework to multi-objective and dynamic scheduling, optimizing computational efficiency, and applying the approach to other combinatorial problems, ultimately contributing to the realization of autonomous industrial optimization.
Deep Analysis
Background
Manufacturing industries一直在追求高效、智能的生产调度方案。传统方法如Johnson规则、NEH算法在小规模问题中表现优异，但在大规模实例中，搜索空间指数增长，导致算法难以找到全局最优。近年来，元启发式算法如模拟退火、禁忌搜索、遗传算法和蚁群算法被广泛应用，极大提升了调度能力。特别是迭代贪婪（IG）算法，以其简洁高效、收敛快，成为调度优化的主流工具。然而，单一算子策略在复杂实例中容易陷入局部最优，限制了其应用范围。随着深度学习的发展，自动启发式设计（AHD）逐渐成为研究热点，利用大语言模型（LLM）自动生成和优化调度启发式规则，为工业调度提供了新思路。
Core Problem
Permutation Flow Shop调度问题（PFSP）旨在找到一条作业处理序列，以最小化总完工时间（即完工时间或最大完工时间）。其数学模型属于NP-hard，导致在大规模实例中，精确算法计算成本过高。现有启发式和元启发式算法在小规模问题中表现良好，但在大规模复杂实例中，搜索容易陷入局部最优，难以找到接近全局最优的解。尤其是在制造业中，调度的动态变化和多目标需求使问题更为复杂。传统方法缺乏有效的多样化搜索机制，难以突破深陷的搜索局部区域，亟需结合智能化手段实现更强的探索能力。
Innovation
本研究的核心创新在于：1）提出IG-DOE算法，通过引入多算子集（DOE）和停滞触发的顺序切换（STSS）机制，增强搜索的多样性，提升逃离局部最优的能力；2）设计阶段性合作演化（SCOE）框架，利用深度学习引导生成互补算子，减少对手工设计的依赖；3）在标准基准和工业数据集上验证，显示出优异的泛化能力和实际应用潜力。这些创新突破了传统单一算子策略的局限，为复杂调度问题的自动化解决提供了新思路。
Methodology
- �� 采用迭代贪婪（IG）框架作为基础，结合多破坏算子集（DOE）实现多样化搜索。
- �� 设计停滞触发的顺序切换（STSS）机制：在连续若干次迭代未改善全局最优解时，自动切换破坏算子，增强搜索探索能力。
- �� 利用大语言模型（LLM）通过阶段性合作演化（SCOE）自动生成互补破坏算子：
- �� 采集训练实例，定义性能指标（平均相对偏差F(O)）。
- �� 逐步构建算子集：在每个阶段，利用深度学习引导生成候选算子，并通过合作评估筛选最优算子。
- �� 采用反思式演化（ReEvo）机制，结合状态感知和合作评价，优化算子生成。
- �� 在标准VRF-hard-large基准测试中，使用规模为100、200的训练实例，演化出适用于规模达600的测试实例的算子集。
- �� 通过消融实验验证多算子切换机制的有效性和自动演化的泛化能力。
Experiments
- �� 采用VRF-hard-large基准测试，实例规模从300到800，涵盖不同难度等级。
- �� 比较基线算法包括QIG（Q-learning增强的迭代贪婪）和传统IG。
- �� 评估指标为平均相对偏差（ARPD）和计算时间，确保公平比较。
- �� 训练集由规模为100和200的实例组成，利用深度学习引导的演化生成算子集。
- �� 在未见过的规模为600、700、800的实例上测试泛化能力，验证算法的适应性。
- �� 进行消融实验，分析多算子切换机制和自动演化策略对性能的贡献。
- �� 还在实际工业数据集上验证算法的实用性和鲁棒性，确保理论成果的落地。
Results
- �� IG-DOE在VRF-hard-large基准测试中，解决了规模为300至800的实例，平均相对偏差从QIG的2.05%降低到1.69%，提升17.8%，显示出优越的调度性能。
- �� 在未见过的规模为600、700、800的实例中，算法表现出强泛化能力，说明自动演化的算子集具有良好的迁移性。
- �� 在工业数据集上，无需额外调优，算法实现了优于传统手工算子集的调度效果，验证了其实际应用潜力。
- �� 消融实验表明，多算子切换机制（STSS）显著提升搜索逃离局部最优的能力，单一算子在复杂实例中易陷入停滞，而多算子协作改善了搜索质量和稳定性。
Applications
- �� 该算法适用于制造业中的生产调度优化，特别是在大规模、多机、多作业环境中，能显著提升生产效率。
- �� 通过自动构建算子集，减少了对行业专家的依赖，加快调度系统的部署速度。
- �� 在智能制造和工业4.0背景下，结合实时数据进行动态调度，提升生产线的柔性和响应能力。
- �� 未来可扩展到多目标调度、动态调度和多任务环境，支持复杂工业场景的智能调度决策。
Limitations & Outlook
- �� 当前方法依赖于训练集的代表性，若实际环境与训练数据差异较大，性能可能下降。
- �� 自动演化的算子集在某些特殊行业或特殊约束条件下可能不适用，需结合手工调优。
- �� 计算成本较高，尤其是在多算子切换和深度学习引导阶段，实时调度场景下需优化效率。
- �� 未来需研究多目标、多任务和动态环境下的自适应调度策略，以应对工业生产的多样化需求。
Plain Language Accessible to non-experts
想象你在厨房里准备一顿大餐。每次做菜都需要不同的步骤，比如切菜、煮饭、炒菜。为了让菜做得快又好，你会尝试不同的顺序和方法。有时候，某个步骤卡住了，你会换个方法试试。现在，科学家们也在用类似的思路优化工厂里的生产流程。
他们设计了一个智能助手，可以根据不同的情况自动选择不同的“做菜方法”。这个助手会观察工厂的生产情况，如果发现某个方案停滞不前，就会换一种策略继续努力。更厉害的是，这个助手还能自己学习，逐渐掌握哪些方法组合最有效，就像你在厨房里试验不同的调料搭配一样。
通过这种自动学习和切换策略，工厂的生产效率大大提高，能在更短的时间内完成更多的任务。这就像你用一个聪明的厨师助手，让厨房变得更快、更智能。未来，这种方法还能用在其他复杂的任务中，比如交通调度、物流配送等，让我们的生活变得更加便捷和高效。
Abstract
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.
References (20)
ReEvo: Large Language Models as Hyper-Heuristics with Reflective Evolution
Haoran Ye, Jiarui Wang, Zhiguang Cao et al.
New hard benchmark for flowshop scheduling problems minimising makespan
Eva Vallada, Rubén Ruiz, J. Framiñán
Learning to select operators in meta-heuristics: An integration of Q-learning into the iterated greedy algorithm for the permutation flowshop scheduling problem
Maryam Karimi-Mamaghan, Mehrdad Mohammadi, B. Pasdeloup et al.
A memetic algorithm with novel semi-constructive evolution operators for permutation flowshop scheduling problem
Mohamed Kurdi
A simple and effective iterated greedy algorithm for the permutation flowshop scheduling problem
Rubén Ruiz, T. Stützle
A review of metrics on permutations for search landscape analysis
T. Schiavinotto, T. Stützle
LLM-Assisted Automatic Memetic Algorithm for Lot-Streaming Hybrid Job Shop Scheduling With Variable Sublots
Rui Li, Ling Wang, H. Sang et al.
AlphaEvolve: A coding agent for scientific and algorithmic discovery
Alexander Novikov, Ngân V˜u, Marvin Eisenberger et al.
Cascaded Large-Scale TSP Solving with Unified Neural Guidance: Bridging Local and Population-based Search
Shengcai Liu, Haoze Lv, Zhiyuan Wang et al.
Some efficient heuristic methods for the flow shop sequencing problem
É. Taillard
Equation of State Calculations by Fast Computing Machines
V. S. Borkar
Mathematical discoveries from program search with large language models
B. Romera-Paredes, M. Barekatain, Alexander Novikov et al.
A balance-oriented iterative greedy algorithm for the distributed heterogeneous hybrid flow-shop scheduling problem with blocking constraints
Xiuli Wu, Yang Zhao
Hybrid quantum particle swarm optimization and variable neighborhood search for flexible job-shop scheduling problem
Yuanxing Xu, Mengjian Zhang, Ming Yang et al.
Toward Evolving Dispatching Rules With Flow Control Operations by Grammar-Guided Linear Genetic Programming
Zhixing Huang, Yi Mei, Fangfang Zhang et al.
Generalised accelerations for insertion-based heuristics in permutation flowshop scheduling
Victor Fernandez-Viagas, Jose M. Molina-Pariente, J. Framiñán
EoH-S: Evolution of Heuristic Set using LLMs for Automated Heuristic Design
Fei Liu, Yilu Liu, Qingfu Zhang et al.
Local Optima Correlation Assisted Adaptive Operator Selection
Jiyuan Pei, Hao Tong, Jialin Liu et al.
A Systematic Survey on Large Language Models for Algorithm Design
Fei Liu, Yiming Yao, Ping Guo et al.
Genetic Programming for Dynamic Flexible Job Shop Scheduling: Evolution With Single Individuals and Ensembles
Meng Xu, Yi Mei, Fangfang Zhang et al.