随着人工智能的快速发展，图神经网络（Graph Neural Networks，GNN）作为一种强大的机器学习工具，正逐渐在各个领域展现出惊人的应用潜力。在制造业领域，柔性作业车间调度问题（FJSP）一直是一个重要的挑战。本文将介绍如何将图神经网络与FJSP相结合，探讨这种创新融合在优化调度问题上的应用前景。

Part1图的基本定义

图的构成：顶点（Vertex）和边（Edge），其中顶点表示研究的对象，边用于连接顶点，表示两个对象之间特定的关系。

数学上，将图记为，其中是顶点集合，是边集合，并设图的顶点数为，边数为。

一条连接顶点的边记为或者。

如下图所示，

图的定义

1.1图的基本类型

有向图和无向图

如果图中的边存在方向性，则称这样的边为有向边<>;

如果图中的边不存在方向性，则称这样的边为无向边或双向边，即<>=<>=。

图 有向图

非加权图与加权图

如果图里的每条边都有一个实数与之对应，我们称这样的图为加权图，如下图示，该实数称为对应边上的权重。在实际场景中，权重可以代表两地之间的路程或运输成本。一般情况下，我们习惯把权重抽象成两个顶点之间的连接强度。与之相反的是非加权图，我们可以认为非加权图各边上的权重是一样的。

图 加权图

连通图与非连通图

如果图中存在孤立的顶点，没有任何边与之相连，这样的图被称为非连通图，如下图所示。相反，不存在孤立顶点的图称为连通图。

图 非连通图

二部图

二部图是一类特殊的图。我们将中的顶点集合拆分成两个子集和，如果对于图中的任意一条边均有或者，则称图G为二部图，如下图所示。二部图是一种十分常见的图数据对象，描述了两类对象之间的交互关系， 比如：用户与商品、作者与论文。

图 二部图

1.2邻居和度

如果存在一条边连接顶点和， 则称是的邻居， 反之亦然。我们记的所有邻居为集合 ， 即：

以为端点的边的数目称为的度(Degree)，记为 ：

在图中，所有节点的度之和与边数存在如下关系：

在有向图中，我们同时定义出度(Outdegree) 和入度(Indegree) ，顶点的度数等于该顶点的出度与入度之和。 其中，顶点的出度是以为起点的有向边的数目， 顶点的入度是以为终点的有向边的数目。

1.3图的存储与遍历

邻接矩阵与关联矩阵

邻接矩阵（Adjacency matrix） 和关联矩阵（Incidence matrix） 是常见的两种图的存储表示方法。

设图，在这里我们对边重新进行了编号， 如下图所示。我们用邻接矩阵描述图中顶点之间的关联， ， 其定义为：

图 图示例

用邻接矩阵存储图的时候，我们需要一个一维数组表示顶点集合，需要一个二维数组表示邻接矩阵，如下图所示。

图 邻接矩阵

也可用关联矩阵来描述节点与边之间的关联， 定义如下：

与相连

用关联矩阵存储图的时候，我们需要两个一维数组分别表示顶点集合和边集合，需要一个二维数组表示关联矩阵，如下图所示。

图 关联矩阵

Part2FJSP描述及析取图模型

2.1描述

柔性作业车间调度问题是一个经典的制造业调度问题，涉及多个作业（jobs）需要在多个机器（machines）上完成加工。每个作业都有一定的处理时间，且可以在不同的机器上进行加工（柔性体现在这里），但每个作业只能在一个机器上加工一次。问题的目标是找到一个作业在各个机器上的加工顺序，以最小化总的完成时间（makespan），即所有作业完成所需要的时间。

问题的形式化描述：

• 给定作业集合 {J1, J2, …, Jn} 和机器集合 {M1, M2, …, Mm}。
• 每个作业 Ji 需要在某些机器上进行加工，用一个机器序列表示。
• 每个作业 Ji 在机器序列上的加工时间也不同。
• 每个机器 Mi 一次只能加工一个作业，而且每个作业只能在一个机器上加工一次。
• 目标是找到一个机器序列的安排，以最小化所有作业完成的时间。

2.2析取图模型

在经典的作业车间调度问题的研究中，通常用析取图模型来表达问题的解，析取图模型可由三元组G（N，C，E）进行表示：其中N为所有工序节点集合（包括了虚拟的起始节点Start和终止节点End），C为同一零件下由工艺决定的相邻工序之间关系的有向连接弧集合，用实线表示；E表示在可在同一机床上加工的工序间的析取弧集，用虚线表示。图7为一个简单的析取图模型，其中圆圈表示工序节点，节点内容表示工序名称，数字代表第几个零件的第几道工序，例如O11表示第1个零件的第1道工序。具有相同颜色的工序节点说明该类工序需要相同的机床。弧上的权重表示工序的加工时间。

图 析取图

图7所示的析取图为尚未求解时候的状态，在进行求解时，需要确定同一机床上工序的先后顺序，即析取弧的方向，如果形成的图形是一个有向无环图，那么这个有向无环图将是一个具体可行的调度解。图8为对图7中析取图进行一次实例化后所形成的可行解的有向无环图：

图  析取图实例化

在得到了可行解的有向无环图之后，需要通过拓扑排序将有向无环图G中的所有顶点排成一个具有明确的先后顺序的线性序列。当然拓扑排序不是唯一的，但是对一个有向无环图的所有拓扑排序对应的最后调度结果将是唯一的，图9为对图8进行一次拓扑排序后的结果。

图  拓扑排序

而在FJSP问题中，每道工序可以有多台机器选择，因此此时的析取图不再是二维图形，而是Z轴表示可选机器的三维图形，其求解过程如下动画所示。

表示调度问题的析取图本质上是图结构的一种，顶点就是工序，边就是工序之间的工艺顺序关系；因为存在工艺路线约束，因此顶点之间是有顺序约束的，即为有向图；工序往往需要一定的准备时间、加工时间、运输时间、静置时间等，因此每条边也是加权的。

Part3图神经网络

GNN是一类用于处理图数据的机器学习模型。与传统的神经网络专注于处理向量和矩阵数据不同，GNN 能够捕捉图数据中节点和边之间的复杂关系，使其在社交网络分析、推荐系统、生物信息学以及化学等领域展现出强大的应用潜力。GNN的基本思想是通过在节点上聚合局部信息来更新节点的表示，然后将这些更新传递到相邻节点，从而逐步融合全局信息。

      图神经网络大致经历了以下几个关键阶段：

• 早期模型：最早的图神经网络模型可以追溯到2004年，当时Gori等人提出了Graph Neural Network（GNN）的概念。这些早期模型主要关注节点的聚合和更新，但缺乏可扩展性和泛化能力。

• 图卷积网络（GCN）的兴起：2017年，Thomas Kipf和Max Welling提出了图卷积网络（GCN），引领了GNN的新一波发展。GCN将传统的卷积操作引入图数据领域，通过聚合邻居节点信息来更新每个节点的表示，大大提高了模型的性能。
• 注意力机制的引入：之后，图注意力网络（GAT）于2018年被Thomas Kipf等人提出。GAT引入注意力机制，使得节点在聚合邻居特征时能够赋予不同的权重，从而能够更好地捕捉节点之间的关系。
• 大规模图数据处理：为了处理大规模图数据，一些模型如GraphSAGE和Graph Isomorphism Network（GIN）在2018年逐渐受到关注。这些模型使用随机采样或池化操作来聚合邻居节点信息，以降低计算复杂度。
• 深度图神经网络：随着研究的深入，越来越多的深度图神经网络被提出，如多层GCN、GAT等。这些深度模型能够逐层地传播节点信息，从而更好地捕捉图数据中的复杂关系。
• 时空图神经网络：近年来，针对时序图数据的研究逐渐兴起，时空图神经网络应运而生。这些模型能够处理图数据中的时序变化，例如社交媒体数据、交通数据等。

Part4图神经网络用于FJSP的可行方案

根据前面的分析可知，FJSP中既存在工序节点，又存在机器节点，而由于描述工序和机器节点的信息不同，因此FJSP的析取图本质上为异构图，存在工序与工序以及工序与机器的关系。

处理同构图常用的机制就是图注意力机制（Graph Attention Mechanism），其核心思想就是人们在识别一幅图时往往只需要抓住某些关键要素就能准确判断，因此图像中各个像素、区域、特征具有不同的权重，这给我们的启发就是，我们并不需要处理所有的细节，从而可以利用更短的时间实现目标。

同样在图结构中，各个节点之间的相互影响也是不同的，通常用注意力系数（Attention Coefficient）来量化影响程度，然后再通过Softmax函数进行归一化，并作为权重对邻居节点特征进行加权求和，即可得到节点的新特征，这整个过程就是嵌入（Embedding）。

而FJSP析取图为异构图，其工序节点和机器节点的特征维度和范围不同，此时需要在网络结构上进行一些改进，此时的嵌入过程可以分为两个阶段：

1. 机器嵌入阶段。该阶段用于汇总可加工工序的信息到机器上。由于此时处理的是不同节点，在计算机器与可加工工序之间的注意力时，需要对不同节点的特征进行不同的线性变换，类似地再进行归一化和加权求和，最终得到新的机器特征。

1. 工序嵌入阶段。该阶段用于汇总前后置工序信息到工序上。同样利用注意力机制获取新的工序特征。

然后，通过图神经网络的多层堆叠，增强特征提取能力，从而提升泛化性能，并通过平均池化构建最终的图特征，此时任意大小的调度问题都可转换成固定维度的嵌入。

总体的流程大致如下：

最后就是网络的训练过程了，可以采用强化学习或是无梯度方法（最新力作|基于进化策略和图强化学习的动态作业车间调度问题研究）1来对参数进行更新。

Part5结语

图神经网络作为一种新兴的技术手段，为解决FJSP等复杂调度问题带来了全新的可能性，目前也有一些相关的研究成果（论文+源码解读|基于图神经网络和深度强化学习的柔性作业车间调度问题研究2、论文解读（源码）：求解柔性作业车间调度问题（FJSP）的多动作（multi-action）深度强化学习框架3）。通过将图神经网络与FJSP相结合，可以大大提升调度模型的泛化性和求解效率，从而更好地优化生产调度，提高制造业的效率和竞争力。然而，这一领域仍然需要更多的研究和实践，如多目标、并行工序场景等。

参考文献

• [1] Su C, Zhang C, Xia D, et al. Evolution strategies-based optimized graph reinforcement learning for solving dynamic job shop scheduling problem[J]. Applied Soft Computing, 2023, 145: 110596.
• [2] Song W, Chen X Y, Li Q Q, et al. Flexible Job-Shop Scheduling via Graph Neural Network and Deep Reinforcement Learning[J]. Ieee Transactions on Industrial Informatics, 2023, 19(2): 1600-1610.
• [3] Lei K, Guo P, Zhao W, et al. A multi-action deep reinforcement learning framework for flexible Job-shop scheduling problem[J]. Expert Systems with Applications, 2022, 205: 117796.

微信公众号后台回复

加群：加入全球华人OR|AI|DS社区硕博微信学术群

资料：免费获得大量运筹学相关学习资料

人才库：加入运筹精英人才库，获得独家职位推荐

电子书：免费获取平台小编独家创作的优化理论、运筹实践和数据科学电子书，持续更新中ing…

加入我们：加入「运筹OR帷幄」，参与内容创作平台运营

知识星球：加入「运筹OR帷幄」数据算法社区，免费参与每周「领读计划」、「行业inTalk」、「OR会客厅」等直播活动，与数百位签约大V进行在线交流

文章须知

文章作者：韩宝安

责任编辑：张琪 马玺渊

微信编辑：疑疑

文章由『运筹OR帷幄』转载发布

如需转载请在公众号后台获取转载须知

关注我们 

       FOLLOW US