针对大型零部件的柔性作业车间，改进了基于遗传算法（GA）的调度方法，同时考虑了多台起重机之间的干扰因素

《JOURNAL OF MANUFACTURING SYSTEMS》：Improved GA-based scheduling of a flexible job shop for large components considering the interference between multiple cranes

柔性车间调度与起重机运输协同优化问题，提出改进遗传算法通过三重染色体编码和起重机动作解码机制，解决时空耦合约束，案例验证使最大完成时间降低18.7%。

　　

潘家宇|王东|王丽萍|李学坤

清华大学机械工程系制造工程研究所，北京100084，中国

摘要

随着现代制造业的快速发展，灵活作业车间调度问题（FJSP）引起了全球的关注。在涉及多个工件、工艺、机器和起重机的大型组件车间中，必须同时考虑作业调度和起重机调度。然而，很少有研究同时解决这两个紧密耦合的问题。本文提出了一种改进的遗传算法（IGA），以实现具有起重机运输功能的灵活作业车间的高效智能调度（FJSP-CT）。通过四个关键方面——染色体编码、选择、交叉和变异——对遗传算法（GA）进行了改进，以确保生成可行的解决方案，并增强全局优化能力。在解码阶段，开发了一组基于起重机动作的操作符，将运输任务分解为可执行的起重机动作，从而确保起重机调度的非干扰性。这些组件构成了一个基于IGA的调度框架，明确考虑了作业、机器和起重机之间的时空耦合约束。以滚磨生产线为例，这是一个典型的FJSP-CT场景。以所有工件的最大完成时间（makespan）作为性能指标，通过算法计算和场景验证，将提出的IGA与企业的当前调度方法和一般的改进遗传算法（GIGA）进行了比较。结果表明，IGA在调度性能上更优，为实际的大型组件制造环境提供了有效且实用的解决方案。

引言

作业车间调度问题（JSP）是运筹学中的一个经典NP难题，其中一组具有预定义工艺顺序的作业必须在资源有限的专用机器上进行处理[1]。为了反映现代制造业中路由灵活性的提高，灵活作业车间调度问题（FJSP）允许每个作业在几台可选机器之一上进行处理[2]。尽管这种灵活性提高了生产的适应性，但它显著扩大了解决方案的空间并增加了调度问题的计算复杂性[3]。

在大型组件车间中——例如重型滚磨、航空航天结构制造和大规模焊接装配——内部物料运输不可忽视[4]。起重机是主要的处理设备，其移动受到严格的安全距离约束。由于起重机共享导轨且移动性有限，如果起重机调度协调不当，可能会发生干扰和潜在的碰撞[5]。这些特性引入了额外的时间和空间依赖性，直接影响作业处理时间和机器可用性。

尽管在FJSP研究方面取得了实质性进展，但大多数现有研究假设运输过程是瞬时的或由容量无限的车辆处理的，这对于大型和重型组件来说是不现实的。相反，起重机调度研究通常仅关注纯运输任务，常常忽略与作业处理和机器约束的交互。然而，在实际车间执行中，作业处理、机器容量和起重机移动形成了一个强耦合的系统：

（1）在起重机完成交付任务之前，机器无法开始处理。

（2）起重机的移动受到干扰和安全距离约束的限制。

（3）任何起重机的延迟都会传播到下游作业，影响整体调度。

这种强烈的时空耦合导致了具有起重机运输功能的灵活作业车间调度问题（FJSP-CT），其复杂性远高于单独解决FJSP或起重机调度。传统的基于GA的方法在纯FJSP上表现良好，但在这种设置中往往遇到困难，因为传统的解码机制无法明确模拟起重机移动和干扰，导致在考虑起重机约束时产生不可行的调度或收敛效果不佳。

为了解决这些挑战，本文提出了一种专为强耦合的FJSP-CT设计的改进遗传算法（IGA）。与仅基于抽象调度决策的标准GA框架不同，所提出的IGA将作业-机器-起重机分配直接集成到染色体表示中。更重要的是，开发了一种基于起重机动作的解码机制，在解码过程中明确重建起重机位置和移动轨迹，从而实时解决起重机干扰和安全约束问题。因此，进化搜索由真实反映物理系统行为的可执行调度指导。

本文的主要贡献总结如下：

（1）制定了FJSP-CT的全面数学模型，捕捉了作业优先级、机器容量、起重机动态和安全距离约束之间的时空耦合。

（2）开发了一个集成的IGA框架，具有三层染色体结构和改进的遗传操作，以在强耦合条件下保持可行性并提高全局搜索性能。

（3）提出了一种基于起重机动作的解码机制，明确模拟起重机移动和干扰行为，使GA能够将染色体评估为可执行的调度。

本文的其余部分组织如下。第2节回顾了FJSP、起重机调度及其集成方面的相关工作。第3节介绍了问题描述和数学建模。第4节详细介绍了提出的IGA和解码机制。第5节提供了计算实验和场景验证。第6节讨论了实验结果。第7节总结了研究并概述了未来方向。

节选

灵活作业车间调度问题（FJSP）

自从Brucker和Schlie首次提出FJSP以来，由于其能够表示现代制造业中的路由灵活性，它已成为一个基本的研究课题。FJSP的研究已经从单一算法优化发展到混合元启发式算法，最近又发展到数据驱动和动态调度方法。

由于强大的全局搜索能力和鲁棒性，遗传算法（GA）已成为FJSP最普遍的基线方法。早期研究主要集中在改进GA的结构上

问题描述

具有起重机运输功能的灵活作业车间调度模型的符号定义如下：

术语
n	工件总数
m	机器总数
q	起重机总数
i	工件编号索引，i = 1,2,…,n
j	工艺编号索引，j = 1,2,…,
k	机器编号索引，k = 1,2,…,$mi$
l	起重机编号索引，l = 1,2,…,$q$
Oij	工件i的第j个工艺
Ci	工件i的完成时间
Sij	Oij的开始时间
Cij	Oij在机器k上的完成时间
tijk	Oij

IGA的总体框架

本研究提出的改进遗传算法（IGA）将整个FJSP-CT调度逻辑嵌入到进化优化过程中。标准GA无法直接解决FJSP-CT，因为它缺乏（1）表示工件、机器和起重机之间的时空耦合，以及（2）重建缺失信息（如起重机位置和时间）的能力。为了克服这些限制，IGA在四个关键组成部分——编码、选择、交叉和变异——进行了改进

案例研究

我们以典型的FJSP-CT——滚磨生产线——为例，使用所提出的算法解决了一个实际问题。

讨论

在本节中，围绕提出的IGA算法进行了一系列必要的讨论。

（1）FJSP和起重机调度之间的强耦合

现有的FJSP和起重机调度研究主要将这两个问题视为可分离的或弱耦合的。在大多数基于GA的FJSP研究中，起重机运输被简化为一个固定或瞬时的辅助过程，而起重机调度研究通常假设预定义的工艺顺序。这样的建模无法捕捉到强

结论和未来工作

本研究解决了具有起重机运输功能的灵活作业车间调度问题（FJSP-CT），这是一个由工件、机器和起重机之间的强时空耦合特征的复杂制造问题。开发了一种改进的遗传算法（IGA），将调度逻辑直接集成到进化过程中。与标准GA相比，提出的IGA引入了三层染色体结构、增强的选择-交叉-变异操作以及解码机制

CRediT作者贡献声明

王丽萍：监督、资金获取、概念化。王东：撰写 – 审稿与编辑、方法论、调查、资金获取、数据整理。李学坤：撰写 – 审稿与编辑、监督、资金获取、形式分析。潘家宇：撰写 – 审稿与编辑、撰写 – 原稿、可视化、验证、概念化。

利益冲突声明

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

致谢

本研究得到了国家自然科学基金（编号：52575582, 52275440）的财政支持。