基于发布时间预测的灵活作业车间两阶段鲁棒调度方法，采用基于Q学习的超启发式进化算法

《Engineering Applications of Artificial Intelligence》：A two-stage robust rescheduling for flexible job shop based on release time prediction using a Q-learning-based hyper-heuristic evolutionary algorithm

针对动态柔性车间调度中频繁调整导致资源浪费的问题，提出考虑紧急任务预测发布时间的两阶段鲁棒调度模型TRR-FJS-RTP，并设计Q-learning结合的高阶策略与混合调度策略，通过六种低阶策略动态优化搜索路径，实验验证其优于现有方法。

　　

张文宇|杨思涵|王婉茹|丁欣怡|杨玉书

浙江财经大学信息技术与人工智能学院，中国杭州，310018

摘要

对于动态灵活的作业车间调度问题，不稳定的重新调度方案可能导致频繁的机器调整、资源浪费、生产中断等问题。此外，现实中经常需要随机插入紧急任务，但很少考虑紧急任务的预测发布时间，以实现最优和稳健的重新调度方案，并减少与初始调度方案的差异。因此，本文提出了一种基于发布时间预测的灵活作业车间两阶段稳健重新调度问题（TRR-FJS-RTP），并构建了相应的模型来优化综合稳健性。特别是在重新调度时考虑预测发布时间，以优化调度方案，并提出了一种混合重新调度策略来应对紧急任务的插入。为了获得高质量的TRR-FJS-RTP解决方案，提出了一种新的基于Q学习的超启发式进化算法，该算法结合了初始化策略、低级启发式和基于Q学习的高级策略。实验结果表明，所提出的方法比其他现有方法具有更好的性能。

引言

在当代市场环境中，优化作业车间的调度效率和生产适应性对于制造企业保持竞争优势至关重要（Fontes等人，2023年）。灵活作业车间调度问题（FJSP）是对经典作业车间调度问题的扩展，它允许每个操作由多台替代机器处理，从而提高系统的生产力和灵活性（Destouet等人，2023年；Echeverria等人，2025年）。因此，FJSP已成为近年来制造业研究的热点之一。然而，在实际应用中经常遇到动态干扰，如紧急任务的插入、机器故障、供应链中断和质量引起的返工，这些都会降低生产效率（An等人，2022年）。因此，需要高效和实时的重新调度方法来应对动态FJSP面临的挑战。

目前大多数关于动态FJSP的研究集中在重新调度方案的最大完成时间、延迟等方面，而对它们的稳健性关注较少（Caldeira等人，2020年；Tliba等人，2023年）。在调度文献中，稳健性的概念主要包括：（1）在面对干扰时提高调度方案的性能稳定性（Zhang等人，2023a）；（2）在面对干扰时减少初始调度方案与重新调度方案之间的偏差（Xiong等人，2013年）；（3）通过预防措施提高调度方案的缓冲能力以应对未来的干扰（Luo，2020年）。本研究中的稳健性具体指的是最小化初始调度方案与重新调度方案之间的偏差，从而减少频繁的机器调整、资源浪费和生产中断等问题。鉴于理论调度模型与现实生产约束之间的这种对立，有必要关注重新调度方案的稳健性，以便开发出能够适应现实变化的稳健优化模型。

值得注意的是，紧急任务的插入是现实生产过程中最常见的干扰之一，这会导致生产方案的频繁重新调度、资源分配冲突的增加，最终降低生产效率（Hasan等人，2011年；Cevikcan和Durmusoglu，2014年；Lu等人，2024年）。在现实中的作业车间调度系统中，一些紧急任务的发布时间通常是可预测的，这可以减少紧急任务随机插入的负面影响并提高生产效率（Xiong等人，2024年）。然而，据我们所知，很少有研究考虑在动态FJSP中利用紧急任务的预测发布时间来进行重新调度，以实现稳健的调度方案。因此，将紧急任务的预测发布时间作为影响动态FJSP调度方案稳健性的新因素是必要的。

近年来，许多进化算法被用于解决FJSP问题（Baykaso?lu等人，2020年；Chen等人，2024b）。然而，影响进化算法性能的搜索策略很大程度上依赖于人类经验，且常常表现出短视行为（Ji等人，2021年）。对于动态FJSP，调度方案需要动态调整，这需要有效的搜索策略来选择合适的进化操作符，以便在最短时间内获得良好的结果。因此，一些研究在进化算法中使用了基于Q学习的高级策略（HLS），在问题的不同阶段寻找合适的低级启发式（LLH）（Liu等人，2022年；Chen等人，2024a）。然而，现有的基于Q学习的进化算法研究往往忽略了在解决调度问题时对调度方案稳健性的优化。

为了解决上述问题，本研究提出了一种基于发布时间预测的灵活作业车间两阶段稳健重新调度问题（TRR-FJS-RTP），并提出了一种新的基于Q学习的超启发式进化算法（QLHHEA）来解决TRR-FJS-RTP。本研究主要有四个贡献：

(1)

提出了一种新的TRR-FJS-RTP，并构建了相应的模型来优化综合稳健性。特别是在重新调度时考虑预测发布时间，以优化调度方案，并提出了一种结合三种调度方法的混合重新调度策略来应对紧急任务的插入。

(2)

为了更高效地生成高质量的初始调度方案，提出了一种初始化策略，该策略通过重用历史最佳调度方案来初始化有希望的调度方案，从而提高算法的收敛性。

(3)

使用六种启发式来构建LLH池，以丰富QLHHEA的搜索行为，从而获得更优的解决方案。

(4)

提出了一种改进的基于Q学习的HLS，其中提出了一种新的状态定义方法来优化搜索方向，设计了一种奖励函数来提高探索能力，并在Q值更新过程中使用衰减因子来适应动态环境中的经验效应。

本研究的其余部分安排如下。第2节提供了相关文献的概述。第3节详细描述了TRR-FJS-RTP的数学模型和提出的调度策略。第4节提出了新的QLHHEA算法。第5节展示了数值实验的结果。第6节得出了结论并为未来的研究提供了方向。

部分摘录

重新调度问题

传统的重新调度研究侧重于优化性能指标，如完成时间和总延迟时间。例如，Mihoubi等人（2021年）提出了一种基于调度规则的FJSP重新调度方法，以最小化完成时间。Zhang等人（2021年）研究了一种包含作业车间干扰因素的重新调度场景，优化目标包括生产周期时间、最大机器工作负载和总延迟时间。然而，不稳定的重新调度

问题描述

TRR-FJS-RTP可以定义如下。该问题涉及$I$个任务和$H$台机器，每个任务$B_i$包含$J_i$个操作，其中$O_j$是任务$B_i$的$O_j$操作。每个操作$O_{ij}$可以由一组可用机器中的任意一台执行，且操作的处理时间随所选机器的不同而变化。每个任务的操作顺序是确定的。

所有任务分为两种类型：普通任务（NJ）和紧急插入任务（UIJ）。

•

预测的发布时间，

提出的QLHHEA算法用于TRR-FJS-RTP

本研究提出的TRR-FJS-RTP需要优化调度方案的综合稳健性。因此，提出了一种新的QLHHEA，该算法采用基于Q学习的HLS来动态识别最合适的LLH，如算法1所示。QLHHEA的新颖之处在于以下三个方面：1）提出了一种初始化策略，以更高效地生成高质量的初始调度方案；2）使用六种启发式来构建LLH

实验

为了验证所提出方法的有效性，进行了比较实验、消融实验、敏感性分析、统计分析和案例研究。这些实验是在配备Intel(R) Core处理器（1.60 GHz）和8 GB内存的Windows 10个人计算机上使用Python 3.7实现的。

结论

本研究提出了一种新的TRR-FJS-RTP，并构建了相应的模型来优化综合稳健性。特别是在重新调度时考虑预测发布时间，以优化调度方案，并提出了一种混合重新调度策略来应对紧急任务的插入。为了获得高质量的TRR-FJS-RTP解决方案，提出了一种新的QLHHEA。在该算法中，提出了一种初始化策略来生成高质量的初始调度

CRediT作者贡献声明

张文宇：撰写 – 审稿与编辑、监督、资源管理、项目管理、资金获取、形式分析、概念化。杨思涵：撰写 – 原始草稿、验证、软件开发、方法论、调查、形式分析、数据整理、概念化。王婉茹：撰写 – 审稿与编辑、资源管理、项目管理、调查、概念化。丁欣怡：可视化、验证、软件开发、调查。杨玉书：调查，

伦理标准

作者声明本研究符合伦理标准。本研究不涉及人类参与者或动物。

利益冲突声明

作者声明他们没有已知的财务利益或个人关系可能影响本文报告的工作。

致谢

本工作得到了浙江省“建冰”重点研发项目（编号：2025C01010）、浙江省重点科技创新人才计划项目（编号：2023R5213）和杭州市重点研究项目（编号：2024SZD1A18）的支持。