4.1.3 作业调度问题
作业调度问题（JSSP）是计算机科学和运筹学中广泛研究的组合优化问题，在制造业和交通运输等行业中有着广泛的应用。在 JSSP中，许多具有预定义约束的作业被分配给一组异构机器，该问题的求解目标为最小化完工时间、流动时间或延迟。优先级调度方法（PDR）是在实际中被广泛应用的一种高效启发式算法。PDR 计算快速、直观且易于实现。然而，设计一个有效的 PDR 需要大量的领域知识和试错，特别是对于复杂的调度问题。机器学习可以很好的发掘实例的共同特征，且通过大量实例训练得到的模型表现往往相对稳定。因此，
人们越来越关注调度问题的机器学习求解方法。
调度问题通常基于端到端的图学习方法进行求解。例如，Wang 等人[24] 提出了一种基于图深度学习的动态调度方法，采用近端策略优化来寻找调度的最优策略，以应对由于问题规模增加而导致的状态和行动空间维度灾难。Zhang 等人[25] 通过端到端图深度学习获得调度的公共模式，并应用训练得到的模型来自动学习分配优先级。Zhang等人[25] 使用离散图表示调度问题，提出了一种基于图神经网络求解调度过程中的状态，有效的提高了泛化性能。然而，上述学习方法没有考虑到作业车间调度问题中决策顺序对整体求解的影响，影响了求解的质量。为了克服决策顺序对问题求解质量的影响，Park 等人[26]提出了使用图神经网络来学习作业车间调度问题的框架。将 JSSP 的调度过程建模为一个具有图表示的序列决策问题，随后使用 GNN 来学习节点特征，通过节点特征学习最佳调度。Jeon 等人[27] 提出了一种基于机器学习的序列调度器，该调度器使用 one-shot 图神经网络编码器对节点序列优先级进行采样，通过列表调度将节点序列优先级转换为最终调度。Park 等人[28] 提出了一种基于图深度学习的实时调度器 ScheduleNet。具体的，ScheduleNet 首先将多代理调度问题建模为具有连续奖励的 semi-MDP，用智能体（Agent）任务图表示调度问题的状态，利用类型感知图注意力提取智能体和任务节点的节点嵌入，最终用计算出的节点嵌入计算调度分配概率。