作业车间调度的替代评估指标的自动构建方法

《Systems》：Automatic Construction Method of Surrogate Evaluation Measures for Job Shop Scheduling

　　

作业车间调度因其对各类工业及制造系统的相关性和影响而具有重要意义。针对考虑随机机器故障的作业车间调度问题，研究人员建立了一个同时考虑制造周期（makespan）和期望制造周期延迟（expected makespan delay）的多目标优化模型。考虑到期望制造周期延迟无法解析计算，本文提出了一种基于符号回归（symbolic regression, SR）的构建方法，该方法能够自动学习一个替代评估指标（surrogate evaluation measure）。随后，研究人员提出了一种基于该替代评估指标的多目标进化算法（multi-objective evolutionary algorithm, MOEA）来求解该模型，其中用构建的替代评估指标替代期望制造周期延迟进行适应度评估，以实现快速评估和高效优化。最后，在40个作业车间调度基准问题上进行了广泛的仿真实验，验证了所提方法的有效性及其在计算效率上的优势。

论文解读文章

**研究背景与问题**

作业车间调度问题（job shop scheduling problem, JSSP）是经典的NP-hard问题，广泛应用于生产制造、交通运输、航空航天及网络通信等领域。传统的确定性调度研究假设问题参数静态已知，但实际生产中随机机器故障等不确定性事件不可避免，会干扰原有生产计划，导致制造周期（makespan）增加等性能恶化风险。确定性调度无法适应这些动态变化，因此亟需在调度中充分考虑不确定性事件的影响，开展不确定作业车间调度研究。

**现有挑战**

现有研究主要采用性能指标的期望值或期望偏差来评估不确定性下的调度方案，例如期望制造周期或期望偏差。然而，由于不确定调度问题的复杂性，此类期望形式的目标通常无法直接解析计算。最常用的蒙特卡洛（Monte Carlo, MC）模拟虽能获得较高精度的近似值，但需要大量采样，计算成本极高，会显著降低优化算法效率。另一种思路是设计替代评估指标作为原始目标的函数逼近，例如基于松弛时间的手工设计指标。但这些方法严重依赖对问题的深入分析和经验试错，且传统松弛指标仅能反映调度结构特性而忽略不确定性影响。因此，如何高效构建高性能替代评估指标成为有价值且紧迫的问题。

**研究目标与方案**

本文针对考虑随机机器故障的作业车间调度问题，同时优化制造周期（makespan）和期望制造周期延迟（expected makespan delay）。为提升优化算法计算效率，提出一种基于机器学习思想的近似方法，旨在设计一个既能准确评估又能快速计算的替代评估指标，以取代耗时的蒙特卡洛模拟。首先，基于对问题特征的深入分析，提出基于符号回归（symbolic regression, SR）的替代评估指标自动构建方法；然后，提出基于替代评估指标的多目标进化算法（surrogate measure-based multi-objective evolutionary algorithm, SM-MOEA），以实现制造周期和期望制造周期延迟的快速评估与优化。论文发表在《Systems》。

**主要关键技术方法**

研究人员采用以下关键技术：1）基于符号回归的构建方法，利用遗传编程（genetic programming, GP）框架自动学习解析表达式，以近似期望制造周期延迟；2）问题特征集（F）的提取，包括关键操作与非关键操作的聚合统计特征（如机器故障率、期望停机时间、加工时间、空闲时间等）；3）算术运算符集（A）的选取（加、减、乘、除、幂、指数）；4）通过蒙特卡洛模拟生成训练数据集，为每个数据实例提供特征向量与标签值（期望制造周期延迟近似值）；5）基于非支配排序遗传算法（NSGA-II）框架的多目标进化算法（SM-MOEA），采用优先级列表编码与替代指标进行适应度评估。样本队列来源为经典LA基准问题集，扩展了随机机器故障属性，构成LA-MB问题集（训练集La01–La20，测试集La21–La40）。

**研究结果**

* **5.1 自动构建方法性能评估**
* **5.1.1 构建的替代评估指标**：通过多次运行自动构建方法，得到最优替代评估指标（式9），该指标是关键操作与非关键操作上期望停机时间之和的函数，与平均总空闲时间负相关，与关键操作总加工时间正相关。平均绝对相对偏差在训练集和测试集上均为0.05–0.06，标准偏差0.04–0.05，表明评估精度高且稳定，未出现过拟合。
* **5.1.2 评估精度分析**：在40个基准问题上，构建的替代指标与蒙特卡洛模拟值的平均绝对相对偏差范围窄（0.05–0.06），整体平均值仅0.06，标准偏差低至0.04。箱线图显示中位数误差低于0.05，75%实例误差小于0.10。在未见过的测试集上表现一致，验证了良好的泛化能力。
* **5.1.3 相关性分析**：采用单因素方差分析进行线性回归，决定系数R²在训练集上为0.97–0.98，测试集上为0.98–0.99，显著性p值均小于0.01，表明替代指标与期望制造周期延迟之间存在强线性相关，能有效区分不同调度的延迟水平。
* **5.2 多目标进化算法性能分析**
* **5.2.1 对比实验设置**：将SM-MOEA与基于蒙特卡洛的多目标进化算法（MC-MOEA）和基于传统鲁棒性指标（加权总空闲时间）的多目标进化算法（RM-MOEA）进行对比，采用平均距离（AD）和集合覆盖（SC）指标。
* **5.2.2 优化性能分析**：SM-MOEA的AD值在训练集上平均0.02，测试集上平均0.01，与MC-MOEA（平均0.01）接近，且显著优于RM-MOEA（平均0.03–0.04）。SC结果显示，SM-MOEA与MC-MOEA互有胜负但整体相当（训练集平均SC(SM,MC)=0.31，SC(MC,SM)=0.53；测试集分别为0.34和0.56），而SM-MOEA在训练集中平均支配RM-MOEA的50%解（SC(SM,RM)=0.50），在测试集上高达87%（SC(SM,RM)=0.87），RM-MOEA支配SM-MOEA的比例极低。帕累托前沿可视化也证实SM-MOEA与MC-MOEA前沿几乎重叠，远优于RM-MOEA。
* **计算效率对比**：SM-MOEA的平均计算时间仅66秒，为MC-MOEA（1932秒）的3.42%，且随问题规模增长缓慢；RM-MOEA耗时43秒（2.23%），但以牺牲解质量为代价。SM-MOEA在保持与MC-MOEA相近解质量的同时，大幅提升了效率。

**总结讨论与研究结论**

本文建立了一个考虑随机机器故障的作业车间调度多目标优化模型，同时优化制造周期和期望制造周期延迟。基于符号回归方法提出替代评估指标的自动构建方法，降低了设计复杂度。进而提出基于替代指标的多目标进化算法，显著提升了求解效率。广泛实验验证了所构建替代指标在评估精度上接近蒙特卡洛模拟，且大幅缩短计算时间，充分证明了方法的有效性和计算效率优势。论文指出，当前方法仅考虑随机机器故障，未来将扩展至更复杂的不确定调度场景（如随机加工时间、动态工件到达），并尝试将符号回归与深度学习结合以增强逼近能力与泛化性能。