随着人工智能的快速发展，图神经网络（GraphNeuralNetworks，GNN）作为一种强大的机器学习工具，正逐渐在各个领域展现出惊人的应用潜力。在制造业领域，柔性作业车间调度问题（FJSP）一直是一个重要的挑战。本文将介绍如何将图神经网络与FJSP相结合，探讨这种创新融合在优化调度问题上的应用前景。
图的构成：顶点（Vertex）和边（Edge），其中顶点表示研究的对象，边用于连接顶点，表示两个对象之间特定的关系。
如果图里的每条边都有一个实数与之对应，我们称这样的图为加权图，如下图示，该实数称为对应边上的权重。在实际场景中，权重可以代表两地之间的路程或运输成本。一般情况下，我们习惯把权重抽象成两个顶点之间的连接强度。与之相反的是非加权图，我们可以认为非加权图各边上的权重是一样的。
如果图中存在孤立的顶点，没有任何边与之相连，这样的图被称为非连通图，如下图所示。相反，不存在孤立顶点的图称为连通图。
在图中，所有节点的度之和与边数存在如下关系：
邻接矩阵（Adjacencymatrix）和关联矩阵（Incidencematrix）是常见的两种图的存储表示方法。
与相连用关联矩阵存储图的时候，我们需要两个一维数组分别表示顶点集合和边集合，需要一个二维数组表示关联矩阵，如下图所示。
问题的形式化描述：
图7所示的析取图为尚未求解时候的状态，在进行求解时，需要确定同一机床上工序的先后顺序，即析取弧的方向，如果形成的图形是一个有向无环图，那么这个有向无环图将是一个具体可行的调度解。图8为对图7中析取图进行一次实例化后所形成的可行解的有向无环图：
在得到了可行解的有向无环图之后，需要通过拓扑排序将有向无环图G中的所有顶点排成一个具有明确的先后顺序的线性序列。当然拓扑排序不是唯一的，但是对一个有向无环图的所有拓扑排序对应的最后调度结果将是唯一的，图9为对图8进行一次拓扑排序后的结果。
而在FJSP问题中，每道工序可以有多台机器选择，因此此时的析取图不再是二维图形，而是Z轴表示可选机器的三维图形，其求解过程如下动画所示。
GNN是一类用于处理图数据的机器学习模型。与传统的神经网络专注于处理向量和矩阵数据不同，GNN能够捕捉图数据中节点和边之间的复杂关系，使其在社交网络分析、推荐系统、生物信息学以及化学等领域展现出强大的应用潜力。GNN的基本思想是通过在节点上聚合局部信息来更新节点的表示，然后将这些更新传递到相邻节点，从而逐步融合全局信息。
根据前面的分析可知，FJSP中既存在工序节点，又存在机器节点，而由于描述工序和机器节点的信息不同，因此FJSP的析取图本质上为异构图，存在工序与工序以及工序与机器的关系。
同样在图结构中，各个节点之间的相互影响也是不同的，通常用注意力系数（AttentionCoefficient）来量化影响程度，然后再通过Softmax函数进行归一化，并作为权重对邻居节点特征进行加权求和，即可得到节点的新特征，这整个过程就是嵌入（Embedding）。
而FJSP析取图为异构图，其工序节点和机器节点的特征维度和范围不同，此时需要在网络结构上进行一些改进，此时的嵌入过程可以分为两个阶段：
然后，通过图神经网络的多层堆叠，增强特征提取能力，从而提升泛化性能，并通过平均池化构建最终的图特征，此时任意大小的调度问题都可转换成固定维度的嵌入。
总体的流程大致如下：
人才库：加入运筹精英人才库，获得独家职位推荐
电子书：免费获取平台小编独家创作的优化理论、运筹实践和数据科学电子书，持续更新中ing...
加入我们：加入「运筹OR帷幄」，参与内容创作平台运营
知识星球：加入「运筹OR帷幄」数据算法社区，免费参与每周「领读计划」、「行业inTalk」、「OR会客厅」等直播活动，与数百位签约大V进行在线交流