Existing learning-based methods for solving job shop scheduling problem
(JSSP) usually use off-the-shelf GNN models tailored to undirected graphs and
neglect the rich and meaningful topological structures of disjunctive graphs
(DGs). This paper proposes the topology-aware bidirectional graph attention
network (TBGAT), a novel GNN architecture based on the attention mechanism, to
embed the DG for solving JSSP in a local search framework. Specifically, TBGAT
embeds the DG from a forward and a backward view, respectively, where the
messages are propagated by following the different topologies of the views and
aggregated via graph attention. Then, we propose a novel operator based on the
message-passing mechanism to calculate the forward and backward topological
sorts of the DG, which are the features for characterizing the topological
structures and exploited by our model. In addition, we theoretically and
experimentally show that TBGAT has linear computational complexity to the
number of jobs and machines, respectively, which strengthens the practical
value of our method. Besides, extensive experiments on five synthetic datasets
and seven classic benchmarks show that TBGAT achieves new SOTA results by
outperforming a wide range of neural methods by a large margin.

本文提出了一种基于注意机制的拓扑感知双向图注意网络（TBGAT），用于解决作业车间调度问题，通过嵌入要解决的不相交图（DG），并利用消息传递机制计算 DG 的正向和反向拓扑排序，从而实现并行计算且取得了新的研究前沿结果。