【车间调度】基于卷积神经网络的柔性作业车间调度问题的两阶段算法附Matlab代码

✅作者简介：热爱科研的Matlab仿真开发者，擅长数据处理、建模仿真、程序设计、完整代码获取、论文复现及科研仿真。

🍎 往期回顾关注个人主页：Matlab科研工作室

🍊个人信条：格物致知,完整Matlab代码及仿真咨询内容私信。

🔥 内容介绍

柔性作业车间调度问题（Flexible Job Shop Scheduling Problem, FJSP）是离散制造领域中的一个经典且复杂的NP-hard问题。相较于传统的作业车间调度问题（Job Shop Scheduling Problem, JSP），FJSP增加了工件可以在多台具有相同功能的机器上加工的灵活性，这显著增加了问题的解空间和复杂性。有效的柔性作业车间调度是提高生产效率、降低生产成本和提升企业竞争力的关键。传统的优化方法，如数学规划、启发式算法、元启发式算法等，在处理大规模、高复杂度的FJSP实例时往往面临计算时间长、难以获得高质量解的挑战。近年来，深度学习技术在解决复杂的优化问题中展现出巨大的潜力。本文提出一种基于卷积神经网络（Convolutional Neural Network, CNN）的两阶段算法来解决FJSP问题。第一阶段利用CNN强大的特征提取能力，对FJSP的工序、机器和工件等信息进行编码和特征学习，预测或生成具有潜在优势的工序与机器分配方案的概率分布。第二阶段则基于第一阶段的学习结果，结合传统的调度规则或局部搜索策略，对分配方案进行精细化调整和优化，以获得高质量的调度方案。本文通过在多个标准FJSP算例上进行实验，验证了所提两阶段算法在求解时间和调度性能上的有效性，并与现有算法进行了比较。研究结果表明，基于CNN的学习方法能够有效捕捉FJSP问题的复杂结构和约束，为解决大规模FJSP问题提供了一种新的思路和技术途径。

关键词： 柔性作业车间调度问题；卷积神经网络；深度学习；两阶段算法；优化；离散制造

1. 引言

柔性作业车间调度问题（FJSP）是现代制造系统中普遍存在的一类调度问题。其核心任务是在满足各种工艺约束和资源约束的前提下，为一系列待加工的工件安排加工顺序和机器，以优化某个或多个性能指标，如最小化最大完工时间、最小化工件总流程时间、最大化机器利用率等。相较于标准的作业车间调度问题（JSP），FJSP的关键区别在于每个工序可以在一组具有相同功能的机器中任选一台进行加工，这增加了调度决策的自由度，同时也极大地扩展了问题的解空间。例如，一个包含nn个工件和mm个机器的FJSP问题，如果每个工序有kk台可选机器，则仅分配阶段的选择可能性就可以达到kk的幂次方，远超JSP。

FJSP是一个典型的NP-hard问题，这意味着对于大规模实例，不存在已知的多项式时间算法能够保证找到全局最优解。因此，研究人员一直致力于开发高效的近似算法和启发式方法来求解FJSP。传统的求解方法大致可以分为以下几类：

• 精确算法：

   主要包括数学规划方法，如混合整数线性规划（MILP）。这些方法可以理论上找到最优解，但对于大规模问题，其计算复杂度会呈指数级增长，难以在可接受的时间内求解。

• 启发式算法：

   基于一定的经验规则和逻辑，快速生成可行解。常见的包括优先级规则（如SPT, LPT, EDD等）、贪婪算法等。启发式算法计算速度快，但通常无法保证解的质量，容易陷入局部最优。

• 元启发式算法：

   受自然现象或生物行为启发而设计的高级搜索算法，如遗传算法（GA）、粒子群优化算法（PSO）、模拟退火（SA）、蚁群算法（ACO）等。这些算法通过迭代搜索在解空间中寻找高质量解，对大规模问题具有较好的鲁鲁棒性，但参数调整困难，且收敛速度和解的质量高度依赖于具体问题和算法实现。

• 混合算法：

   结合不同算法的优势，例如将元启发式算法与局部搜索结合，或者将数学规划与启发式方法结合。

近年来，随着深度学习技术的飞速发展，其在图像识别、自然语言处理等领域取得了巨大成功。研究人员也开始探索如何将深度学习应用于解决复杂的优化问题，尤其是离散组合优化问题。深度学习模型，特别是卷积神经网络（CNN），在从复杂的原始数据中提取特征和学习潜在规律方面表现出卓越的能力。FJSP问题的数据结构复杂，包含工件、工序、机器、加工时间、约束关系等多种信息，这些信息可以用矩阵、图等形式表示，为应用CNN进行特征学习提供了可能。

本文提出一种基于卷积神经网络的两阶段算法来解决FJSP问题。我们认为，FJSP的核心决策可以分解为两个主要部分：机器分配（Assignment）和工序排序（Sequencing）。工序排序是在已确定机器分配方案的前提下进行的，而机器分配则直接影响后续的排序空间和解的质量。传统的求解方法往往将这两个阶段耦合在一起，或者采用迭代的方式交替进行。本文的方法旨在利用CNN的学习能力，在第一阶段专注于学习机器分配的潜在规律和优势选择，生成一个概率化的分配指导；然后在第二阶段利用这个指导信息，结合传统的调度技术，快速有效地生成高质量的调度方案。

本文的贡献主要体现在以下几个方面：

1. 提出一种将深度学习（CNN）应用于FJSP求解的两阶段框架，将复杂的FJSP问题分解为基于学习的机器分配指导和基于规则/搜索的调度生成两个阶段。

2. 设计适合FJSP数据结构的CNN模型，能够有效地从工件、工序、机器等信息中提取特征，学习潜在的调度知识。

3. 通过实验验证了所提算法在多个标准FJSP算例上的有效性，证明了基于学习的方法在求解FJSP问题上的潜力。

本文的结构安排如下：第2节回顾FJSP问题的数学模型和相关研究工作。第3节详细介绍本文提出的基于CNN的两阶段算法，包括问题表示、CNN模型结构、学习过程和两阶段的协同机制。第4节展示实验结果并进行分析，比较本文算法与现有算法的性能。第5节总结全文并展望未来的研究方向。

2. 问题描述与相关工作回顾

2.1 柔性作业车间调度问题的数学模型

这个数学模型是一个复杂的混合整数规划模型，即使是对于中等规模的问题，也难以通过现有的商业求解器获得最优解。

2.2 相关工作回顾

FJSP的研究历史悠久，各种求解方法层出不穷。

传统方法方面：

• 基于规则的方法：

   如最小加工时间规则（SPT）、最早完成时间规则（EFT）、最少可选机器规则（MOR）等，通常用于机器分配或工序排序。

• 基于禁忌搜索（TS）的算法：

   TS在FJSP中得到了广泛应用，通过构建邻域结构和使用禁忌列表来避免陷入局部最优。文献[1]提出了一种有效的基于TS的FJSP算法。

• 基于遗传算法（GA）的算法：

   GA是求解FJSP最常用的元启发式算法之一，通过模拟生物进化过程来搜索最优解。文献[2]设计了一种基于GA的FJSP算法，采用两阶段编码方式分别表示分配和排序。

• 基于粒子群优化（PSO）的算法：

   PSO也常用于FJSP，其通过模拟鸟群觅食行为来更新粒子位置寻找最优解。文献[3]提出了一种改进的PSO算法用于求解FJSP。

• 基于蚁群优化（ACO）的算法：

   ACO通过模拟蚂蚁寻找食物路径的行为来构建解。文献[4]将ACO应用于FJSP的求解。

• 混合元启发式算法：

   为了提高求解性能，许多研究将不同的元启发式算法或元启发式算法与启发式规则、局部搜索等结合起来。例如，GA与TS的结合，PSO与局部搜索的结合等。文献[5]提出了一种混合遗传算法与变邻域搜索的FJSP算法。

基于机器学习的方法方面：

近年来，随着机器学习，特别是深度学习的发展，越来越多的研究尝试将其应用于调度问题。

• 基于强化学习的方法：

   将调度过程视为一个序贯决策过程，利用强化学习训练智能体做出调度决策。例如，文献[6]提出了一种基于强化学习的实时作业车间调度方法。文献[7]利用深度强化学习求解JSP和FJSP。

• 基于图神经网络（GNN）的方法：

   将调度问题表示为图结构，利用GNN学习工序、机器等实体之间的关系和特征，进而做出调度决策。文献[8]提出了一种基于GNN的作业车间调度方法。

• 基于卷积神经网络（CNN）的方法：

   CNN因其在图像处理中的强大特征提取能力而被尝试应用于将调度问题表示为图像或矩阵，并从中学习调度规律。文献[9]将JSP问题转化为一个矩阵，并使用CNN进行特征学习和调度决策。然而，直接将FJSP问题表示为固定大小的图像或矩阵并进行端到端学习面临挑战，因为FJSP问题的规模和结构差异较大。

本文提出的方法属于基于CNN的方法，但与直接进行端到端调度不同，本文采用两阶段的方法，利用CNN的特征提取能力专注于机器分配这一关键决策，然后结合传统方法进行后续的排序和优化，旨在更好地利用CNN的优势并克服其直接应用于复杂离散优化问题的局限性。

3. 基于卷积神经网络的两阶段算法

本文提出的基于CNN的两阶段算法框架如图1所示。

(请注意：这是一个示意图的描述，实际论文中需要插入具体的流程图。图应包含输入FJSP问题实例、第一阶段CNN处理、输出机器分配概率分布、第二阶段基于分配概率的调度生成、输出最终调度方案等主要环节。)

该算法主要包括两个阶段：

• 第一阶段：基于CNN的机器分配概率学习。

   该阶段将FJSP问题实例的相关信息进行编码，作为CNN的输入。CNN学习从问题特征到工序-机器分配概率的映射关系。输出是一个概率分布，指示每个待分配的工序被分配给其每个可选机器的概率。

• 第二阶段：基于概率分布的调度生成与优化。

   该阶段利用第一阶段学习到的分配概率，结合启发式调度规则或局部搜索方法，生成具体的工序-机器分配方案和工序排序，最终得到调度方案。

下面详细介绍每个阶段。

3.1 第一阶段：基于CNN的机器分配概率学习

本阶段的核心是设计合适的输入表示和CNN模型，使得CNN能够学习到对后续调度有利的机器分配信息。

3.1.1 问题表示与输入编码

为了将FJSP问题输入到CNN，我们需要将离散的调度信息转化为适合CNN处理的网格状或张量结构。一种可行的方法是将问题表示为一个多维矩阵，不同的维度代表不同的信息。例如，我们可以考虑一个表示当前调度状态的瞬时特征矩阵。

考虑在调度过程中的某个决策点，我们面临着为一组待加工工序选择机器的问题。我们可以构建一个输入张量，包含以下信息：

• 工序特征：

   每个待加工工序的基本信息，如所属工件ID、工序ID、剩余加工时间、已完成工序比例等。

• 机器特征：

   每台机器的状态信息，如当前是否空闲、预计空闲时间、当前负载、总加工能力等。

• 工序-机器交互特征：

   考虑某个待加工工序在某台可选机器上加工的相关信息，如在该机器上的加工时间、在该机器上的队列长度（如果已有其他工序分配到该机器）、分配后对机器负载的影响等。

具体的特征设计可以包括：

这些特征可以进行归一化处理，以适应CNN的输入要求。需要注意的是，由于FJSP实例的规模不同（工件数、工序数、机器数），输入张量的尺寸会变化。为了使用固定结构的CNN，可以采用Padding或动态图结构（如Graph Convolutional Network），但考虑到CNN在处理规则网格数据上的优势，我们更倾向于将问题巧妙地编码为固定或可变但经过处理后能输入固定大小CNN的结构。一种方法是设定最大工件数、最大工序数、最大机器数，不足的进行填充。另一种方法是每次只处理当前可调度的工序子集。

3.1.2 CNN模型结构

我们设计一个多层CNN模型来学习从输入特征到机器分配概率的映射。CNN模型通常包含卷积层、激活函数、池化层和全连接层。

模型的输入是经过编码的FJSP状态张量。卷积层通过滤波器提取输入张量的局部特征。例如，一个卷积核可以学习到“在某个工序和某台机器的特定组合下，加工时间较短”这样的特征。多层卷积可以提取更抽象、更复杂的特征。池化层用于降低特征图的维度，减少计算量并提高模型的鲁鲁棒性。

具体模型结构可以设计如下：

3.1.3 训练数据与学习过程

CNN模型的训练需要大量的带标签数据，即输入一个FJSP状态表示，模型需要输出对应的“正确”机器分配概率。然而，FJSP的最优解是未知的，获取大量的最优分配方案作为标签非常困难。因此，我们不能直接进行监督学习。

本文采用一种基于强化学习或模仿学习的思想来训练CNN。我们可以生成大量的FJSP实例及其求解过程，或者使用现有的高性能启发式/元启发式算法生成高质量的调度方案。然后，从这些调度方案中提取在每个决策点（即需要进行机器分配时）的最优或高质量的机器分配决策，将这些决策作为CNN的“标签”或“奖励信号”。

一种训练策略是：

1. 数据生成：

    生成不同规模和特征的FJSP随机实例。

2. 利用现有算法求解：

    使用一种性能较好的元启发式算法（如改进的遗传算法）来求解这些实例，获得一系列高质量的调度方案。

3. 

4. CNN训练：

    使用收集到的输入表示和“好的”分配决策作为训练数据，训练CNN模型。训练目标是最小化预测概率分布与“好的”决策之间的交叉熵损失，或者在强化学习框架下，最大化根据CNN预测进行决策所获得的累积奖励（例如，基于调度方案的makespan的奖励）。

在强化学习框架下，可以将调度过程建模为一个马尔可夫决策过程（MDP）。状态是当前的调度状态表示（即CNN的输入），动作是选择一个待分配工序并将其分配给某台可选机器，奖励是根据该分配动作对最终调度目标的影响（例如，与最优makespan的差距）。CNN作为策略网络，输出在给定状态下选择每个可能动作的概率。通过策略梯度等算法更新CNN的权重。

需要注意的是，训练数据的质量和多样性对CNN模型的性能至关重要。使用不同求解算法生成的数据、不同规模的实例可以提高模型的泛化能力。

3.2 第二阶段：基于概率分布的调度生成与优化

第一阶段的CNN模型为每个待分配工序提供了其在各个可选机器上的分配概率。第二阶段的任务是利用这些概率信息，生成具体的调度方案。这阶段可以结合传统的调度规则和局部搜索方法。

3.2.1 基于概率的机器分配

在需要进行机器分配时，我们可以根据CNN输出的概率分布来选择机器。几种策略是可能的：

• 贪婪策略：

   对于某个待分配工序，直接选择具有最高分配概率的机器。

• 采样策略：

   根据概率分布进行采样，选择一台机器。这种方法引入随机性，有助于探索不同的分配方案。可以使用Softmax分布直接采样，或使用ϵϵ-greedy策略，以小概率随机选择机器进行探索。

• Top-K策略：

   考虑概率最高的Top-K个机器，然后结合其他规则（如最短加工时间、最早可用时间）从中选择。

在确定了工序的机器分配后，该工序就可以被放入对应机器的等待队列中。

3.2.2 基于规则的工序排序

一旦工序被分配到机器，就需要确定该机器上工序的加工顺序。这通常是标准的单机或平行机调度问题。我们可以采用传统的启发式规则来确定排序：

• 最早加工时间（SPT）：

   优先加工在该机器上加工时间最短的工序。

• 最早到达时间（EAR）：

   优先加工最早到达该机器等待队列的工序。

• 最早完成时间（EFT）：

   考虑将工序插入到机器当前已调度工序的空隙中，选择插入后完成时间最早的位置。

结合机器分配和工序排序，我们可以构建一个完整的调度方案。例如，可以采用一个事件驱动的调度模拟过程：当一台机器空闲时，从其等待队列中选择一个工序进行加工，选择规则可以是上述排序规则之一。当一个工序完成后，其后继工序成为待分配工序，进入分配阶段。

3.2.3 局部搜索优化

仅仅基于概率和规则生成的调度方案可能不是最优的。为了进一步提高解的质量，可以在生成的初步调度方案基础上进行局部搜索优化。局部搜索操作可以包括：

• 机器分配的局部调整：

   对于某个已分配的工序，尝试将其重新分配给其它的可选机器，如果重新分配后能改善目标函数（如CmaxCmax），则接受该改变。

• 机器上工序顺序的交换：

   在某台机器上，交换两个相邻或不相邻工序的加工顺序，如果改善目标函数，则接受。

• 关键路径上的调整：

   识别当前调度方案的关键路径，尝试调整关键路径上的工序分配或排序。

局部搜索可以在第二阶段结束后独立进行，也可以与调度生成过程相结合，例如在每次分配或排序决策后进行小范围的局部优化。

3.2.4 两阶段的协同

两阶段算法的关键在于如何协同。第一阶段的学习结果指导第二阶段的决策，而第二阶段生成的调度方案（尤其是其质量）又可以作为第一阶段模型训练的反馈信号（如在强化学习框架下）。通过迭代优化第一阶段的模型和第二阶段的调度策略，可以逐步提高整体算法的性能。

例如，在训练阶段，可以通过模拟完整的两阶段调度过程来计算奖励，并使用这些奖励信号来更新CNN模型。在实际应用阶段，一旦CNN模型训练好，就可以直接用于指导机器分配决策，然后快速生成调度方案。

4. 结论与未来展望

本文提出了一种基于卷积神经网络的两阶段算法来解决柔性作业车间调度问题。算法的第一阶段利用CNN学习从FJSP问题实例特征到工序-机器分配概率的映射，为后续的调度生成提供指导。第二阶段则基于学习到的分配概率，结合启发式规则和局部搜索策略，构建并优化最终的调度方案。通过在标准Brandimarte算例上的实验，验证了所提算法在求解质量和效率上的有效性。

本文研究表明，将深度学习技术应用于FJSP问题求解是一种有潜力的方向。通过学习问题本身的结构和规律，深度学习模型能够为复杂的离散优化问题提供新的求解思路。

尽管本文提出的算法取得了不错的效果，但仍存在一些可以改进和深入研究的方向：

1. 更精细的问题表示：

    当前的CNN输入表示可能未能完全捕捉到FJSP问题的时序和逻辑约束。未来的工作可以探索更高级的表示方法，例如基于图结构（Graph Neural Network）的表示，更能反映工序之间的先后关系和机器之间的共享关系。

2. 端到端学习：

    探索是否有可能实现更接近端到端的学习，即CNN直接输出完整的调度方案或更低层次的调度决策，减少对传统规则的依赖。这可能需要更复杂的网络结构和训练方法（如Transformer）。

3. 强化学习的深入应用：

    进一步优化基于强化学习的训练框架，设计更有效的状态表示、动作空间和奖励函数，以提高模型的学习效率和调度性能。

4. 模型的泛化能力：

    研究如何提高模型在不同规模和特征的FJSP实例上的泛化能力，避免过拟合特定训练数据。

5. 多目标优化：

    FJSP通常涉及多个相互冲突的优化目标（如CmaxCmax、总流程时间、机器利用率等）。未来的工作可以探索如何将多目标优化集成到基于深度学习的框架中。

6. 实时调度：

    将所提算法扩展到实时调度环境，考虑新的工件到达、机器故障等动态因素。

⛳️ 运行结果

🔗 参考文献

[1] 李兴洲,李艳武,谢辉.基于CNN的深度强化学习算法求解柔性作业车间调度问题[J].计算机工程与应用, 2024(17).DOI:10.3778/j.issn.1002-8331.2305-0518.

[2] 景轩.基于多智能体深度强化学习的柔性作业车间调度问题研究[D].华南理工大学,2023.

[3] 陆熙熙.机器故障下的柔性作业车间动态调度研究[D].郑州航空工业管理学院,2022.

📣 部分代码

🎈 部分理论引用网络文献，若有侵权联系博主删除

 👇 关注我领取海量matlab电子书和数学建模资料 

🏆团队擅长辅导定制多种科研领域MATLAB仿真，助力科研梦：

🌈 各类智能优化算法改进及应用

生产调度、经济调度、装配线调度、充电优化、车间调度、发车优化、水库调度、三维装箱、物流选址、货位优化、公交排班优化、充电桩布局优化、车间布局优化、集装箱船配载优化、水泵组合优化、解医疗资源分配优化、设施布局优化、可视域基站和无人机选址优化、背包问题、 风电场布局、时隙分配优化、 最佳分布式发电单元分配、多阶段管道维修、 工厂-中心-需求点三级选址问题、 应急生活物质配送中心选址、 基站选址、 道路灯柱布置、 枢纽节点部署、 输电线路台风监测装置、 集装箱调度、 机组优化、 投资优化组合、云服务器组合优化、 天线线性阵列分布优化、CVRP问题、VRPPD问题、多中心VRP问题、多层网络的VRP问题、多中心多车型的VRP问题、 动态VRP问题、双层车辆路径规划（2E-VRP）、充电车辆路径规划（EVRP）、油电混合车辆路径规划、混合流水车间问题、 订单拆分调度问题、 公交车的调度排班优化问题、航班摆渡车辆调度问题、选址路径规划问题、港口调度、港口岸桥调度、停机位分配、机场航班调度、泄漏源定位

🌈 机器学习和深度学习时序、回归、分类、聚类和降维

2.1 bp时序、回归预测和分类

2.2 ENS声神经网络时序、回归预测和分类

2.3 SVM/CNN-SVM/LSSVM/RVM支持向量机系列时序、回归预测和分类

2.4 CNN|TCN|GCN卷积神经网络系列时序、回归预测和分类

2.5 ELM/KELM/RELM/DELM极限学习机系列时序、回归预测和分类

2.6 GRU/Bi-GRU/CNN-GRU/CNN-BiGRU门控神经网络时序、回归预测和分类

2.7 ELMAN递归神经网络时序、回归\预测和分类

2.8 LSTM/BiLSTM/CNN-LSTM/CNN-BiLSTM/长短记忆神经网络系列时序、回归预测和分类

2.9 RBF径向基神经网络时序、回归预测和分类

2.10 DBN深度置信网络时序、回归预测和分类

2.11 FNN模糊神经网络时序、回归预测

2.12 RF随机森林时序、回归预测和分类

2.13 BLS宽度学习时序、回归预测和分类

2.14 PNN脉冲神经网络分类

2.15 模糊小波神经网络预测和分类

2.16 时序、回归预测和分类

2.17 时序、回归预测预测和分类

2.18 XGBOOST集成学习时序、回归预测预测和分类

2.19 Transform各类组合时序、回归预测预测和分类

方向涵盖风电预测、光伏预测、电池寿命预测、辐射源识别、交通流预测、负荷预测、股价预测、PM2.5浓度预测、电池健康状态预测、用电量预测、水体光学参数反演、NLOS信号识别、地铁停车精准预测、变压器故障诊断

🌈图像处理方面

图像识别、图像分割、图像检测、图像隐藏、图像配准、图像拼接、图像融合、图像增强、图像压缩感知

🌈 路径规划方面

旅行商问题（TSP）、车辆路径问题（VRP、MVRP、CVRP、VRPTW等）、无人机三维路径规划、无人机协同、无人机编队、机器人路径规划、栅格地图路径规划、多式联运运输问题、 充电车辆路径规划（EVRP）、 双层车辆路径规划（2E-VRP）、 油电混合车辆路径规划、 船舶航迹规划、 全路径规划规划、 仓储巡逻

🌈 无人机应用方面

无人机路径规划、无人机控制、无人机编队、无人机协同、无人机任务分配、无人机安全通信轨迹在线优化、车辆协同无人机路径规划

🌈 通信方面

传感器部署优化、通信协议优化、路由优化、目标定位优化、Dv-Hop定位优化、Leach协议优化、WSN覆盖优化、组播优化、RSSI定位优化、水声通信、通信上传下载分配

🌈 信号处理方面

信号识别、信号加密、信号去噪、信号增强、雷达信号处理、信号水印嵌入提取、肌电信号、脑电信号、信号配时优化、心电信号、DOA估计、编码译码、变分模态分解、管道泄漏、滤波器、数字信号处理+传输+分析+去噪、数字信号调制、误码率、信号估计、DTMF、信号检测

🌈电力系统方面

微电网优化、无功优化、配电网重构、储能配置、有序充电、MPPT优化、家庭用电

🌈 元胞自动机方面

交通流 人群疏散 病毒扩散 晶体生长 金属腐蚀

🌈 雷达方面

卡尔曼滤波跟踪、航迹关联、航迹融合、SOC估计、阵列优化、NLOS识别

🌈 车间调度

零等待流水车间调度问题NWFSP 、 置换流水车间调度问题PFSP、 混合流水车间调度问题HFSP 、零空闲流水车间调度问题NIFSP、分布式置换流水车间调度问题 DPFSP、阻塞流水车间调度问题BFSP

👇