Deep Reinforcement Learning Guided Improvement Heuristic for Job Shop Scheduling
Authors: Cong Zhang
Zhiguang Cao
Wen Song
Yaoxin Wu
Jie Zhang
Venue: ICLR 2024 poster (2024)
Keywords: Deep Reinforcement Learning
Graph Neural Network
Job Shop Scheduling
Combinatorial Optimization
Primary area: optimization

Abstract: Recent studies in using deep reinforcement learning (DRL) to solve Job-shop scheduling problems (JSSP) focus on construction heuristics. However, their performance is still far from optimality, mainly because the underlying graph representation scheme is unsuitable for modelling partial solutions at each construction step. This paper proposes a novel DRL-guided improvement heuristic for solving JSSP, where graph representation is employed to encode complete solutions. We design a Graph-Neural-Network-based representation scheme, consisting of two modules to effectively capture the information of dynamic topology and different types of nodes in graphs encountered during the improvement process. To speed up solution evaluation during improvement, we present a novel message-passing mechanism that can evaluate multiple solutions simultaneously. We prove that the computational complexity of our method scales linearly with problem size. Experiments on classic benchmarks show that the improvement policy learned by our method outperforms state-of-the-art DRL-based methods by a large margin.

Published as a conference paper at ICLR 2024
DEEP REINFORCEMENT LEARNING GUIDED IM- PROVEMENT HEURISTIC FOR JOB SHOP SCHEDULING
Cong Zhang', Zhiguang Cao², Wen Song Yaoxin Wu² & Jie Zhang'
Nanyang Technological University, Singapore "Sngaapore Management University, Singapore
Institute of Marine Science and Technology. Shandong University, China
'Department of Industrial Engineering & Innovation Sciences, Eindhoven University of Technology cong0300e .nt.uu.uu edu, sg, y2gcao smu. edu. sg, wensongeemail sdu, edu. on y mu2@tueen.) izhang@ntan eddu.sd
ABSTRACT
Recent studies in using deep reinforcement learning (DRL) to solve Job-shop scheduling problems (JSSP) focus on construction heuristics. However, their per- formance is still far from optimality, mainly because the underlying graph repre- sentation scheme is unsuitable for modelling partial solutions at each construction step. This paper proposes novel DRL- DRL-guided improvement heuristic for solving JSSP, where graph representation is employed to encode complete solutions. We design
representation scheme, consisting of two modules to effectively capture the information of dynamic topology and different types of nodes in graphs encountered during the improvement process. To speed up solution evaluation during improvement, we present novel message-passing mechanism that can evaluate multiple solutions simultaneously. We prove that the computational complexity of our method scales linearly with problem size. Ex- periments on classic benchmarks show that the improvement policy learned by our method outperforms state-of-ther -f-th-r-the-art DRL-based methods by a large margin.
Neuph--Nuurll-etwwrkk
INTRODUCTION
Recently, there has been a growing trend towards applying deep (reinforcement) learning (DRL) to solve combinatorial optimization problems (Bengio et al., 2020). Unlike routing problems that are vastly studied (Kool al., 2018; Xin al., 2021a; Hottung al., 2022; Kwon al., 2020; Ma et al., 2023; Zhou et al., 2023; Xin et al., 2021b), the Job-shop scheduling problem (ISSP), a well-known problem in operations research ubiquitous many industries such as manufacturing and transportation, received relatively less attention.
Compared to routing problems, the performance of existing learning-based solvers for scheduling problems is still quite far from optimality due to the lack of an effective learning framework and neu- ral representation scheme. For JSSP, most existing learning- bbaedd approaches follow a dispatching procedure that constructs schedules by extending partial solutions to complete ones. To represent the constructive states, i.e. partial solutions, they usually employ disjunctive graph (Zhang et al., 2020; Park al., 2021b) augment the graph with artificial machine nodes (Park al., 2021a). Then, a Graph Neural Network (GNN) based agent learns a latent embedding of the graphs and outputs construction actions. However, such representation may not be suitable for learning construction heuristics. Specifically, while the agent requires proper solution during each construction step (c.g. the current machine load and job status), it is hard to incorporate them into disjunctive graph, given that the topological relationships could be more naturally modelled among operations' (Balas, 1969). Consequently, with the important components being ignored due to the solution incompleteness, such as the disjunctive ares among undispatched operations (Zhang et al., 2020) and the orientations of disjunctive ares among operations within machine clique (Park et al., 2021b), the partial solution representation by disjunctive graphs in
information of the partial
corresponding author
Please refer to Appendix K for detailed discussion

---

Published as a conference paper at ICLR 2024
current works may suffer from severe biases. Therefore, one question that comes to mind is: Can we transform the learning-to Searning-to-schedie to-schedule problem into a learning-to- teattt--erch-grapee graph-structures problem to circumvent the issue of partial solution representation and significantly improve performance?
Compared to construction ones, improvement heuristics perform iterative search in the neighbour- hood for better solutions. For JSSP, neighbour is complete solution, which is naturally repre- sented as a disjunctive graph with all the necessary information. Since searching over the space of disjunctive graphs is more effective and efficient, it motivates a series of breakthroughs in tra- ditional heuristic methods (Nowicki & Smutnicki, 2005; Zhang et al., 2007). In traditional JSSP improvement heuristies, local moves in the neighbourhood are guided by hand-crafted rules, e.g. picking the one with the largest improvement. This inevitably brings two major limitations. Firstly, at each improvement step, solutions in the whole neighhourhood need to be evaluated, which is com- putationally heavy, especially for large-scale problems. Secondly, the hand-crafted rules are often short-sighted and may not take future effects into account, therefore could limit the improvement performance.
In this paper, we propose a novel DRL-based improvement heuristic for JSSP that addresses the above limitations, based on simple yet effective improvement framework. The local moves are generated by a deep policy network. which circumvents the need to evaluate the entire neighbour- hood. More importantly, through reinforcement learning, the agent is able to automatically learn search policies that are longer-sighted, leading to superior performance. While a similar paradigm has been explored for routing problems (Chen & Tian, 2019; Lu et al., 2019; Wu et al., 2021), it is rarely touched in the scheduling domain. Based on the properties of JSSP, we propose novel GNN-based representation scheme capture the complex dynamics of disjunctive graphs in the improvement process, which is equipped with two embedding modules. One module is responsible for extracting topological information of disjunctive graph, while the other extracts embeddings by incorporating the heterogeneity of nodes' neighbours in the graph. The resulting policy has linear computational complexity with respect to the number of jobs and machines when embedding dis- junctive graphs. To further speed up solution evaluation, especially for batch processing, we design a novel message-passing mechanism that can evaluate multiple solutions simultancously.
We verify our method on seven classic benchmarks. Extensive results show that our method gen- erally outperforms state-of-the-art DRL-based methods by a large margin while maintaining a low computational cost. On large-scate scale instances, method even outperforms Or-tools CP-SAT, highly efficient constraint programming solver Our aim is to showcase the effectiveness of Deep Reinforcement Learning (DRL.) in learning superior search control policies compared to traditional methods. Our computationally efficient DRL-baased heuristic narrows the performance gap with ex- isting techniques and outperforms tabu search algorithm in experiments. Furthermore, our method can potentially be combined with more complicated improvement frameworks, however it is out of the scope of this paper and will be investigated in the future.
2 RELATED WORK
Most existing DRL-basedd methods for JSSP focus on learning dispatching rules, or construction heuristics. Among them, L2D (Zhang et al., 2020) encodes partial solutions as disjunctive graphs and GNN-based agent is trained via DRL to dispatch jobs to machines to construct tight schedules. Despite the superiority to traditional dispatching rules, its graph representation can only capture rela- tions among dispatched operations, resulting in relatively large optimality gaps. A similar approach is proposed in (Park et al., 2021b). By incorporating heterogeneity of neighbours (e.g. predecessor or successor) in disjunctive graphs, a GNN model extracts separate embeddings and then aggregates them accordingly. While delivering better solutions than L2D, this method suffers from static graph representation, as the operations in each machine clique are always fully connected. Therefore, fails to capture structural differences among solutions, which we notice to be critical. For exam- ple, given a JSSP instance, the processing order of jobs on each machine could be distinct for each solution, which cannot be reflected correctly in the respective representation scheme. ScheduleNet (Park et al., 202 introduces artificial machine nodes and edges in the disjunctive graph to encode machine-job relations. The new graph enriches the expressiveness but is still static. A Markov de- cision process formulation with a matrix state representation is proposed in (Tassel et al., 2021). Though the performance is ameliorated, it is online method that learns for each instance sepa- rately, hence requiring much longer solving time. Moreover, unlike the aforementioned graph-based ones, the matrix representation in this method is not size-agnostic, which cannot be generalised
2

---

Published as a conference paper at ICLR 2024
across different problem sizes. RASCL (Iklassov al., 2022) learns generalized dispatching rules for solving JSSP, where the solving process is modelled as MDPs. Tassel et al. (2023a) propose to leverage existing Constraint Programming (CP) solvers to train DRL-agent learning a Priority Dis- patching Rule (PDR) that generalizes well to large instances. Despite substantial improvement, the performance of these works is still far from optimality compared with our method. Other learning- based construction heuristics for solving variants of ISSP include FFSP (Choo et al., 2022; Kwon al., 2021) and scheduling problems in semiconductor manufacturing (Tassel al., 2023b). How- ever, these methods are incompatible with JSSP due to their underlying assumption of independent machine sets for each processing stage, which contradicts the shared machine configuration inherent in JSSP.
work similar to ours is MGRO (Ni et al., 2021), which learns a policy to aid Iterated Greedy (IG), an improvement heuristic, to solve the hybrid flow shop scheduling problem. Our method differs from it in two aspects. Firstly, unlike MGRO which learns to pick local operators from a pool of manually designed ones, our policy does not require such manual work and directly outputs local moves. Secondly, MGRO encodes the current solution as multiple independent subgraphs, which is not applicable to JSSP since cannot model precedence constraints.
3 PRELIMINARIES
Job-shop Scheduling. A JSSP instance of size |J] x |M consists of [J] jobs and |M] machines. Each job j E J required to processed by each machine m E M in a predefined order Of""" - *Om mas ja
M with Jj denoting the ith operation of job j. which should be processed by the machine mys with processing time Pys E N. Let Oj be the collections of all operations for job j. Only can the operation Oj be processed when all its precedent operations 10 < i} C O2 are processed, which is the so-called precedence constraint. The objective is to find a schedule v 10 Th5 [Vj, + N. i.e. the starting time for each operation, such that the makespan CIaxx max(n(O))."
j]M]
Pya) is minimum without violating the precedence constraints. To enhance succinctness, the notation myj indicating the machine allocation for operation Oj will be disregarded as machine assignments for operations remain constant throughout any given JSSP instance. This notation will be reinstated only if its specification is critical.
Disjunctive Graph. The disjunctive graph (Balas, 1969) is a directed graph
(O,C D),
where O = (O i) (j, U {Os, Or} } is the set of all operations, with O5 and Or being the dummy ones denoting the beginning and end of processing. consists of directed ares (conjunctions) rep- resenting the precedence constraints connecting every two consecutive operations of the same job. Undirected ares (disjunctions) in set D connect operations requiring the same machine, forming clique for each machine. Each are is labelled with weight, which is the processing time of the operation that the are points from (two opposite-directed arcs can represent a disjunctive arc). Consequently, finding a solution disjunction, such that the resulting graph G(s) is DAG (Balas, 1969). The longest path from Os to Or in a solution is called the critical path (CP), whose length is the makespan of the solution. An example of disjunctive graph for JSSP instance and its solution are depicted in Figure 1.
JSSP instance is equivalent
fixing the direction of each
The Ns neighbourhood Structure. Various neighbourhood structures have been proposed for JSSP (Zhang et al., 2007). Here we employ the well-known N₂ designed based on the con- cept of critical block (CB), i.e. a group of con- secutive operations processed by the same ma- chine on the critical path (refer to Figure 1 for an example). Given solution s, Nss constructs the neighbourhood Ns(s) as follows. First, it finds the critical path CP(s) of G(s) (randomly selects one if more than one exist). Then for each C.B,, = T + O + ... + 0T + 00-1 ОT with m; and 1 < 1 L denoting the processing machine and the index of operation O along the critical path CP(s), at
Critical
blocks
Figure 1: Disjunctive graph representation. Left: a x JSSP instance. Black arrows are con- junctions. Dotted lines of different colors are dis- junctions, grouping operations on each machine into machine cliques. Right: a complete solution, where a critical path and critical block are high- lighted. Are weights are omitted for clarity.
3

---

Published as a conference paper at ICLR 2024
(0m,
Best
Son
Grapa Representation
Operation
Changes
Criterion
A) mar(f -0me(t)))
(a) The overall framework of method.
(b) State transition example.
Figure 2: Our local search framework and an example of state transition. In Figure (b), the state 8, is transited to $141 by swapping operation O22 and O31 A new critical path with its two critical blocks is generated and highlighted in S++1-
most two neighbours are obtained by swapping the first (OTh), ,0Th) or last pair (Oh-1', Or,)) of operations. Only one neighbour exists if CB has only two operations. For the first and last CB, only the last and first operation pair are swapped. Consequently, the neighbourhood size [Ns(s) is most (N( 2 with (s) being the number of CBs in G(s).
METHODOLOGY
The overall framework of our improvement method is shown in Figure 2(a). The initial solution is generated by basic dispatching rules. During the improvement process, solutions are proxied by their graphical counterpart, i.c disjunctive graphs. Different from traditional improvement heuristics which need to evaluate all neighbours at each step, our method directly outputs an operation pair, which is used to update the current solution according Nç- The process terminates if certain condition met. Here we set it as reaching a searching horizon of steps.
Below present our DRL-based method for learning the pair picking policy. We first formulate the learning task as Markov decision process (MDP). Then we show how to parameterize the policy based GNN, and design a customized REINFORCE (Williams, 1992) algorithm to train the policy network. Finally, we design message- message-passing mechanism to quickly calculate the schedule, which significantly improves efficiency especially for batch training. Note that, the proposed policy possesses linear computational complexity w.r.t. the number of jobs [J] and machines [M].
4.1 THE SEARCHING PROCEDURE AS AN MDP
States. A state St E S is the complete solution at step f, with so being the initial one. Each state represented its disjunctive graph. Features of each node Ojs is collected in vector xj; (Pjs, est,i, E R where est,; and isty; are the earliest and latest starting time of Oz respectively. For complete solution, est(O,;) is the actual start time of O5; in the schedule. If O located on critical path, then est,;; lst (Jungnickel & Jungnickel, 2005). This should be able to help the agent distinguish whether node is on the critical path.
Actions. Since we aim selecting solution within the neighbourhood, an action a, is one of the operation pairs (Ojs, Oыr) in the set of all candidate pairs defined by Nç. Note that the action space A₁ is dynamic w.r.t each state.
Transition. The next state st+1 is derived deterministically from by swapping the two operations of action a, (O ,, Oki) the graph. An example is illustrated in Figure 2(b), where features est and 1st are recalculated for each node in S1+1- If there is no feasible action a, for some f, e.g. there only one critical block in 8t, then the episode enters an absorbing state and stays within it. We present example in Appendix J to facilitate better understanding the state transition mechanism.
Rewards. Our ultimate goal to improve the initial solution as much as possible. To this end, we design the reward function as follows:
r(st, 0z) max (Cmaz(s?) Cmaz (8141),) 0))
where si is the best solution found until step (the incumbent), which updated only if 814-1 is better, i.e. Omax (8141) Cmaz (z7). Initially, si = 8p- The cumulative reward until is
R, Ei r(e,, ar) Cmax (sn) Cmax (s7), which is exactly the improvement against initial
4

---

Published as a conference paper at ICLR 2024
Input:
Noea
Outgutt New Soluiia
Qureent Curcen Solatson
Topskoghol habolling
Ioan
Frsh Candade
Modsie (1750)
Sampled Node Pair (Oay On)
Calted-keawr Tesheding Madkle Madkde (Co00)
teleeking
Marged Greph
Eash Candads
Exandding
Figure 3: The architecture of our policy network.
solution Su- When the episode enters the absorbing state, by definition, the reward is always 0 since there is no possibility of improving the incumbent from then on.
Policy. For state 8t, stochastic policy (ay)s)) (s) outputs distribution over the actions in A,. If the episode enters the absorbing state, the policy will output dummy action which has no effect.
4.2 POLICY MODULE
We parameterize the stochastic policy To (a (x) as a GNN-based architecture with parameter set 0. A GNN maps the graph to continuous vector space. The embeddings of nodes could be deemed as feature vectors containing sufficient information to be readily used for various downstream tasks, such selecting operation pairs for local moves in case. Moreover, GNN-based policy is able to generalize to instances of various sizes that are unseen during training, due to its size-agnostic property. The architecture of our policy network shown in Figure 3.
4.2.1 GRAPH EMBEDDING
For the disjunctive graph, we define node U as a neighbour of node V if an are points from U to V. Therefore, the dummy operation Og has no neighbours (since there are no nodes pointing to it), and Or has [J] neighbours (since every job's last operation is pointing to it). There are two no- table characteristics of this graph. First, the topology is dynamically changing due to the MDP state transitions. Such topological difference provides rich information for distinguishing two solutions from the structural perspective. Second, most operations in the graph have two different types of neighbours, i.e. its job predecessor and machine predecessor. These two types of neighbours hold respective semantics. The former is closely related to the precedence constraints, while the latter reflects the processing sequence of jobs on each machine. Based on this observation, we propose novel GNN with two independent modules to embed disjunctive graphs effectively. We will ex- perimentally prove by an ablation study (Appendix M) that the combination of the two modules are indeed more effective.
Topological Embedding Module. For two different solutions, there must exist machine on which jobs are processed in different orders, i.e. the disjunctive graphs are topologically different. The first module, which we call lopological embeddding module (TPM), is expected to capture such structural differences, so as help the policy network distinguish different states. To this end, we exploit Graph Isomorphism Network (GIN) (Xu et al., 2019), a well-known GNN variant with strong discriminative power for non-isomorphic graphs as the basis of TPM. Given disjunetive graph G, TPM performs K iterations of updates to compute p-dimensional embeddings for each node V E O, and the update at iteration is expressed as follows:
E = ( A-1 +
Σ CEN(V)
A-1 P
(2)
where up is the topological embedding of node V at iteration & and u = Xja is its raw features, MLP is Multi-Layer Perceptron (MLP) for iteration k, ch is arbitrary number that can be learned, and (VV) is the neighbourhood V in G. For each k., we attain a graph-level embedding n IP by average pooling function L with embeddings of all nodes as input as follows:
L = :
Eni. VEO
(3)
10
5

---

Published as a conference paper at ICLR 2024
Gar
Finally, the topological embeddings of each node and the disjunctive graph after the K it- erations are {uv Ex u AV O} and
JAG = Ex p.c respectively. For representation learning with GIN, layers of different depths learn different structural information (Xu al., 2019). The representations acquired by the shallow layers sometimes generalize better, while the deeper layers are more oriented for the target task. To consider all the discrepant structural infor- mation of the disjunctive graph and align the hidden dimension, we sum the embeddings from all layers.
Figure 4: Example of G. and GM-
Context-aware Embedding Module. Now we present the second module to capture information from the two types of neighbouring nodes, which we call context-aware embedding module (CAM). Specifically, we separate disjunctive graph G' into two subgraphs G, and G i.e. contexts, as shown in Figure 4. Both subgraphs contain all nodes G, have different sets of edges to reflect respective information. G. contains only conjunctive arcs which represent precedence constraints, while Gm contains only (directed) disjunctive arcs to represent the job processing order on each machine. Note that the two dummy nodes Os and Or are isolated in G.. since they are not involved any machine.
Similar to TPM, CAM also updates the embeddings for K iterations by explicitly considering the two contexts during message passing and aggregation. Particularly, the update node embeddings CAM iteration k is given as follows:
VV GAT (+t
J.
(4)
M,k GAT (ut (/ (VN-IV)NN(VV)) Vv
(5)
v uv + +
where GAT and GAT are two graph attention layers (Veličković et al., 2018) with na attention heads, vti R' the context-ave aware embedding for V at layer k. vV J.K E R2 and By M,& R2 are V's embedding for precedence constraints and job processing sequence, and (VVV) and W (V) are V's neighbourhood in G, and GM, respectively. For the first iteration, we initialize vf Xza. E. Finally, we compute the graph-level context-aware embedding VG using average pooling as follows:
|0| Σ En
VG
VV.
To generate a global representation for the whole graph, we merge the topological and context-aware embeddings by concatenating them and yield:
(hy (u n JVV E O}, (HG vG).
Remark. We choose GIN as the building block for TPM mainly because it is one of the strongest GNN architectures with proven power discriminate graphs from topological point of view. may benefit identifying topological discrepancies between solutions. As for GAT, it is an equivalent counterpart of Transformers (Vaswani al., 2017) for graphs, which a dominant architecture for learning representations from element attributes. Therefore we adopt GAT as the building block of our CAM module to extract node embeddings for the heterogeneous contexts.
4.2.2 ACTION SELECTION
Given the node embeddings {hv} and graph embedding hG. we compute the "score" of selecting each operation pair as follows. First, we concatenate hGg each hy, and feed it into a network MLPA- to obtain latent vector denoted as hy with dimension which is collected as a matrix h' with dimension ( q. Then we multiply h' with its transpose h" to get matrix SC with dimension ( x [O] as the score of picking the corresponding operation pair. Next, for all pairs that Finally,
not included in the current action space, mask them by setting their scores

---

Published as a conference paper at ICLR 2024
flatten the score matrix and apply a softmax function to obtain the probability of selecting each feasible action.
We present the theoretical computational complexity of the proposed policy network. Specifically, for a JSSP instance of size (J] x M, we can show that:
Theorem 4.1. The proposed policy network has linear time complexity w.r. both |J| and [M].
The detailed proof is presented in Appendix C. In the experiments, we will also provide empirical analysis and comparison with other baselines.
4.3 THE n-STEP REINFORCE ALGORITHM
We propose an n-step REINFORCE algorithm for training the policy network. The motivation, benefits, and details of this algorithm are presented in Appendix A.
4.4 MESSAGE-PASSING FOR CALCULATING SCHEDULE
The improvement process requires evaluating the quality of neighbouring solutions by calculating their schedules. In traditional scheduling methods, this is usually done by using the critical path method (CPM) (Jungnickel & Jungnickel, 2005), which calculates the start time for each node cursively. However, it can only process a single graph and cannot make full use of the parallel computing power of GPU. Therefore, traditional CPM is time-costly in processing batch of in- stances. To alleviate this issue, we propose an equivalent variant this algorithm using a message- passing mechanism motivated by the computation of GNN, which enables batch processing and is compatible with GPU.
Our message-passing mechanism works follows. Given a directed disjunctive graph G repre- senting solution s, we maintain a message msy (dv, cy) for each node V E O, with initial values dy and cv 1, except cy passing operator with max-pooling as the neighbourhood aggregation function, based on which we perform series of message updates. During each of them, for V O, we update its message by dy = mPPmaa ( (PU + (1 cv) du VVU E (V)))) and cv mipmaz (fcu VV E (VV))) with Pv and (V)) being the processing time and the neighbourhood of V. respectively. Let H be the number of nodes on the path from Og to OT containing the most nodes. Then we can show that:
for =Os- Let mpmaz denote message-
Theorem 4.2. After at most H times of message passing, dv = estv, VV O, and dr = Cmar(s))
The proof is presented in Appendix D.I. This proposition indicates that our pesssag--pssiing eval- uator is equivalent to CPM. easy to prove that this proposition also holds for a batch of graphs. Thus the practical run time for calculating the schedule using our evaluator is significantly reduced due to computation in parallel across the batch. We empirically verify the effectiveness by compar- ing it with CPM (Appendix D.3).
Similarly, Isty can be calculated by a backward version of our message- message-passing evaluator where the message is passed from node Or Og in graph G with all edges reversed. Each node V maintains a message m&v = (dy, ,čv), ). The initial values are dy = and ōy = 1, except dy = -Cma (8) and = for V = =O. The message of V updated dy mpmaa ((po + (1-ōo) -du EN((V)) and čv = mpmaa [V EN((V)) We can show that:
Corollary 4.3. After at most H times of message passing, dy = 1stv, VV E O, and dg = 0.
The proof is presented Appendix D.2. Please refer to an example in D.4 for the procedure of computing est using the proposed message-passing operator.
EXPERIMENTS
5.1 EXPERIMENTAL SETUP
Datasets. We perform training on synthetic instances generated following the widely used conven- tion in (Taillard, 1993). We consider five problem sizes, including 10x 10, 15x10, 15, 20x 10, and 20x 15. For evaluation, we perform testing seven widely used classic benchmarks unseen
7

---

Published as a conference paper at ICLR 2024
Table 1: Performance on classic benchmarks. "Gap": the average gap to the best solutions in the literature. "Time": the average time of solving a single instance ("s", "m", and "h" means seconds, minutes, and hours, respectively.). For each problem size, results in bold and bold blue represent the local and overall best results, respectively.
Taillard
Methaal
x
30
15
x0xx 20 15
20
10xx
20 x
Time
Time
Time
Time
Clpp
Gop
Cup
Time
Time
Time
Time
Time
Time
Time
CP-SAT
0.1%
7.7g
0.25
0.64
9.7%
1.04
2.3%
1.00
2.8%
1:N
0.0%
0.40
2.8%
0.94
3.9%
1.08
0.0%
0.54
1,0%
1.0h
0.09
0.14
0.0%
4.14 0.0%
4.8%
1.20
24.7%
0..00.0%
066288
64.50
1.542296
155.0.0%
2.2.23.9%
28
04.99
0.6.14.55
0.1.21.05
00.
0.2.66.35
0.2.
BL.GNN
20.14
3.044.99
3.029.2
C2.99
24.792.00
15.9
1.
3.3m
20.
2..05
7.3.29
19
0.1.22.8%
0.5 14.5%
1.3-
ScheduleNee
6.641.2%
110-19.15
17. 123.29
28.34
18.341399
53.5413556
1.mm
6.7%
7.8m 6.1%
0.450.55
6.06
7.3%
0:2419.55
08
1.66
GD-500
11.9%
4.44%
75.341
7%
1.7m
1%
1.5m
1.3m
1..7.
2.6m
7.94
4m
6.2%
16.9%
5.6%
15
37.0-
F1-500
12: 12.96
5%
18.4%
3.0r
6.5m
4.3m
0.39
7.4m 3.5%
18.8-1.777
16.7%
85-44
18.2400.144222
40.7%
51,500
11.7%
53.5414.3%
1..2%
2.90
2.509
2.7
4.0m
9.1%
7.0ml
4.115
16.2916.5%
94.9%
0.0%
18.001299441333
40.06
Our
93%
4.361..6%
10.1412.4%
10.9447%
12.7447..5
14.001100
16.240344%
22.84
7.9%
50.34
1.8%
7.4.1.991
10.24
0.0%
6.34
9.9
7.5g
6.115
7.46
GD 5000
11.9%
1,7004.45
12.2011.5%
7.39
Zo:
6.2%
4.50416.5%
3,6%
6.1m
5000
9.8%
7.55
4m3 1.9%544.5
6.498
Zm:
2.7%
5.5m
5.6% 7.3ml
5.9g
310000
10.5%-11.5m
15.6ml
04.4%
9.29
52..1111100 (1.9%
43.433.4m
5.6%676..40
2.15
10.9%
0.0%
7.
7.0m
Ous 1600
8.6%
187440..4
20:341
22.2412.%
24.7615.7%
28-44
9,0%
32.961
45
2.8%
15.00
1.25%
0.0%
15:36
8.09-15.11
15.0s
7.1% 37.7 9.4%
41.5413.26
44.711.00
49.1414.05
S6.8
6.9%
65.74
9.3%
90.5%
5.1%
3.4m:
2.8%
30.1
9.5%
39.3.
0.0%
27.34
5.70-3001
1.5%
29.5%
Ous 5000
6.2%
92.2
8.3%
1.7g
9.0%
1.5g
9.0%
200:124%
2.40
4.6%
2.8m
6.5%
3.8m
3.0%
8.4mi
1.4%
75.24
8.4%
99.60
0.0%
67.74
74.7
1.1%
73.5%
SWV
ORB
Methol
10
5
15x
10
10
10 Clpp
15
30%
90
50
Cup
Time:
Gop
Time:
Clap
Time
Gop
Time
Cop
Cup
Cop
Time
Clap
Time
Cop
Time
Gup
Time:
Cop
Time
Cop
CP-SAT
0.0%
0.14
0.0%5
0.34
0.0%
0.54
0.0%
0.44
0.0%
21
04
0.0%
0.0%
13.24
0.0%
90.14
0.1%
2.5%
1.6
1.6%
0.54
0.0%
1.00
L3D
14.3%
0.14
5.35
0.18
4.2%
0.241.9%
0.1824.06
0.244.7%
0.64
8.0%
0.247.1%
0.6611
0.3400.0%
0.66308
1.2451
8% 0.14222
0.9%
RE-GNN
16.1%
0.24
1.0%
0.54
2.1%
1.247.05
0542200
1.447:95
1.34
5.3%
11:441144 11.4%
2.8628
as
3.4.9.4%
7. 1.26683%
51
11.4421
8%
85
11.00
0.6
2.7%
1:34
1.6%
19991
0.8414 mm
20415.05
4.14
31%
9.346.11
1.5434
4%
8.0
90.9%
6 7708 19
15.
20.0s
11:25
GD-500
4.8%
0.66%
23.34
0.8%
11.44
5.8%
26. 44144
19.3 19.2-
66.94
2.6%
58.44
0.5%
49
743377 75 61
20.10
9.02
2.
no 14.5%%
86
F1 500
4.5%
17.54
0.1%
23.84
0.5%
30.9
5.9%
35.34
8.0%
495.1377
59.04
2.9%
745400.38
03
4652.3%
15.3451.0%
1.7m2533
2.4m
13.55%
2.3mz
Bl.500
4.2%
1934
0.0%
23.84
0.5%
30.94
5.1%
34.34
8.9
47.3400.9%
00.56
2.7%
73.1410.15
75.
02
51.56333.6
28.75
1.7m22
15.
2.
Our--500
1.1%
6.5
0.0%%
0.8g
8.8%
7.14
4.4%
7:54
64%
8.0
7.0%
3.5%
0.3%
10:24
7.3%
9:062944
8.3455.5%
9. 49
12.55
9.2%
7.442.4%
11.7%
5000
48%
2.mm
0.6%%
0.3%
5.8%
6.5ml11
7.te
9.
8.3633.7
9m3m
916
11.511
5.2%
B1-5000
1.9%
11.5a
7.7u
2.3%
18.22445%
17.623.5%
19.0.20.15
6.6% 150-0..9
23.4-
27.9
35,9621 18%
34.722.7%
2.79
47.0k
88.8.17.%
88
56.547..0%
99.8617.4%
75.9
1.9mz
in training?, including Taillard (Taillard, 1993), ABZ (Adams et al., 1988), FT (Fisher, 1963), LA (Lawrence, 1984). SWV (Storer et al., 1992). ORB (Applegate & Cook, 1991). and YN (Yamada & Nakano, 1992). Since the upper bound found in these datasets is usually obtained with different SOTA metaheuristic methods (e.g., (Constantino & Segura, 2022)), we have implicitly compared with them although we did not explicitly list those metaheuristic methods. It is also worth noting that the training instances are generated by following distributions different from these benchmark- ing datasets. Therefore, we have also implicitly tested the zero-shot generalization performance of our method. Moreover, we consider three extremely large datasets (up to 1000 jobs), where our method outperforms CP-SAT by a large margin. The detailed results are presented in Appendix L.
Model and configuration. Please refer to Appendix B for the hardware and training (and testing) configurations of our method. Our code and data are publicly available at httss//githbb.com/ccccaarrr////
Baselines. We compare our method with three state-of-thh-ar DRL-based methods, namely L2D (Zhang et al., 2020), RL-GNN (Park et al., 2021b), and ScheduleNet (Park al., 2021a). The online methoo in (Tassel et al., 2021) is only compared on Taillard 30x instances for which they re- port results. We also compare with three hand-crafted rules widely used in improvement heuristics, i.c. greedy (GD), cest-improvement (BI) and fist-improvement (FI), to verify the effectiveness of automatically learning improvement policy. For a fair comparison, we let them start from the same initial solutions as ours, and allow BI and FI to restart so as to escape local minimum. Also, we equip them with the cessage-passing evaluator, which can significantly speed up their calculation since they need to evaluate the whole neighbourhood at each step. More details are presented in Appendix E. The last major baseline is the highly efficient constraint programming solver CP-SAT (Perron & Furnon, 2019) in Google OR- which has strong capability in solving scheduling problems (Da Col & Teppan, 2019), with 3600 seconds time limit. We also compare our method with advanced tabu search algorithm (Zhang et al., 2007). The results demonstrate the advanta- geous efficiency of our approach in selecting moves and achieving better solutions within the same computational time (see Section H for details).
TThe best-known results for these public benchmarks are available in http://optimiiirer.cmm////pppppp and htt::/jobshop.jjp jjvh.nl
8

---

Published as a conference paper at ICLR 2024
5.2 PERFORMANCE ON CLASSIC BENCHMARKS
We first evaluate our method on the seven classic benchmarks, by running 500 improvement steps as in training. Here, we solve each instance using the model trained with the closest size. In Appendix I, we will show that the performance of our method can be further enhanced by simply assembling all the trained models. For the hand-crafted rules, we also run them for 500 improvement steps. We reproduce RL-GNN and ScheduleNet since their models and code are not publicly available. Note that to have a fair comparison of the run time, for all methods, we report the average time of solving a single instance without batching. Results are gathered in Table (upper part in each of the two major rows). We observe that method is computationally efficient, and almost consistently outperforms the three DRL baselines with only 500 steps. RL-GNN and ScheduleNet are relatively slower than L.2,, especially for large problem sizes, because they adopt event-driven based MDP formulation. On most of the instances larger than 20x 15, our method is even faster than the best learning-based construction heuristic ScheduleNet, and meanwhile delivers much smaller gaps. In Appendix C.2, we will provide a more detailed comparison on the efficiency with RL-GNN and ScheduleNet. With the same 500 steps, our method also consistently outperforms the conventional hand-crafh craf-rd improvement rules. This shows that the learned policies are indeed better in terms of guiding the improvement process. Moreover, our method is much faster than the conventional ones, which verifies the advantage of our method in that the neighbour selection is directly attained by neural network, rather than evaluating the whole neighbourhood.
5.3 GENERALIZATION TO LARGER IMPROVEMENT STEPS
We further evaluate the capability of our method in generalizing to larger improvement steps (up to 5000). Results are also gathered Table I (lower part in each major row), where we report the results for hand-crafted rules after 5000 steps. We can observe that the improvement policies learned by our agent for 500 steps generalize fairly well to a larger number of steps. Although restart is allowed, the greedy rule (GD) stops improving after 500 steps due to the appearance of "cycling" as it could be trapped by repeatedly selecting among several moves (Nowicki & Smutnicki, 1996). This is notorious issue that causes the failure hand-craft rules for JSSP. However, our agent could automatically learn to escape the cycle even without restart, by maximizing the long-term return. In addition, is worth noticing that our method with 5000 steps is the only one that exceeds CP-SAT on Taillard x00x20 instances, the largest ones in these benchmarks. Besides the results in Table 1, our method also outperforms the online DRL-based method (Tassel et al., 2021) on Taillard 30 instances, which reports gap of 13.08% with 600s run time, while our method with 5000 steps produces a gap of 12.6% in 144s. The detailed results are presented in Appendix F. It is also apparent from Table I that the run time of our model is linear w.r. the number of improvement steps for any problem size.
5.4 COMPARISON WITH TABU SEARCH
Due to the page limit, we refer readers to Appendix H for details. In nutshell, the performance of our method is comparable to that of tabu search when using the same number of improvement steps but with significant speed advantage. On the other hand, our method outperforms tabu search when the computational time (wall clock time) is the same.
6 CONCLUSIONS AND FUTURE WORK
This paper presents DRLe method to learn high-quality improvement heuristics for solving JSSP. By leveraging the advantage of disjunetive graph in representing complete solutions, we pro- pose a novel graph embedding scheme by fusing information from the graph topology and hetero- geneity of neighbouring nodes. We also design a novel message-passing evaluator to speed up batch solution evaluation. Extensive experiments on classic benchmark instances well confirm the superi- ority of our method to the state-of thett-rrrt DRL baselines and hand-crafted improvement rules. Our methods reduce the optimality gaps seven classic benchmarks by large margin while maintain- ing a reasonable computational cost. In the future, we plan to investigate the potential of applying our method to more powerful improvement frameworks to further boost their performance.

---

Published as a conference paper at ICLR 2024
7 ACKNOWLEDGEMENT
This research was supported by the Singapore Ministry of Education (MOE) Academic Research Fund (AcRF) Tier 1 grant. This work also partially supported by the MOE AcRF Tier fund- ing (RG13/23). This research was also supported by the National Natural Science Foundation of China under Grant 62102228, and the Natural Science Foundation of Shandong Province under Grant ZR2021QF063. The authors sincerely thank Yifan Yang from the School of Engineering and Computer Science Victoria University of Wellington for her help on improving the camera-ready version of the manuscript.
REFERENCES
Joseph Adams, Egon Balas, and Daniel Zawack. The shifting bottleneck procedure for job shop scheduling. Management Science, 34(3):391-401, 1988.
David Applegate and William Cook. A computational study of the job-shop scheduling problem. ORSA Journal on Computing, 3(2): 149-15,, 1991.
Egon Balas. Machine sequencing via disjunctive graphs: an implicit enumeration algorithm. Oper- ations Research, 17(6):941995) 1969.
Yoshua Bengio, Andrea Lodi, and Antoine Prouvost. Machine learning for combinatorial optimiza- tion: methodological tour d' d'horizon. European Journal of Operational Research, 2020.
Xinyun Chen and Yuandong Tian. Learning to perform local rewriting for combinatorial optimiza- tion. Advances in Neural Information Processing Systems,
2019.
Jinho Choo, Yeong- Dae Kwon, Jihoon Kim, Jeongwoo Jae, André Hottung, Kevin Tiemey, and Youngjune Gwon. Simulation-guided beam search for neural combinatorial optimization. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho (eds.), Advances in Neu- ral Information Processing Systems, 2022. URL https: /wtp///eeeeeeeeeeeeeeeee net htt/foormmiie YAS 1R
Oscar Hernández Constantino and Carlos Segura. A parallel memetic algorithm with explicit man- agement of diversity for the job shop scheduling problem. Applied Intelligence, 52(1):141-15) 2022.
Giacomo Da Col and Erich C Teppan. Industrial size job shop scheduling tackled by present day cp solvers. In International Conference on Principles and Pructice of Construint Programming, pp. 144-160. Springer, 2019.
Matthias Fey and Jan Lenssen. Fast graph representation learning with PyTorch Geometric, In ICLR Workshop on Representation Learning on Graphs and Manifolds, 2019.
Henry Fisher. Probabilistic learning combinations of local job-shop scheduling rules. Industrial Scheduling, pp. 225-251, 1963.
Pierre Hansen and Nenad Mladenović. First vs. best improvement: An empirical study. Discrete Applied Mathematics, 154(5):802 817.8000-8818800 2006.
André Hottung, Yeong-Dae Kwon, and Kevin Tierney. Efficient active search for combinatorial
optimization problems. In International Conference on Learning Representations, 2022. URL https: http:://///peeeeieww .et/ wtwprrrrwwwweeeetooreiieeeeeeeee
Zangir Iklassov, Dmitrii Medvedev, Ruben Solozabal, and Martin Takac. Learning to generalize dispatching rules on the job shop scheduling. arXiv preprint SZIv:2206.044233 2022.
Sergey loffe and Christian Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. In International conference on machine learning, pp. 448 456. PMLR, 2015.
Dieter Jungnickel and D Jungnickel. Graphs, networks and algorithms. Springer, 2005.
10

---

Published as a conference paper at ICLR 2024
Wouter Kool, Herke van Hoof, and Max Welling. Attention, learn to solve routing problems! In International Conference on Learning Representations, 2018.
Yeong-Dae Kwon, Jinho Choo, Byoungjip Kim, Iijoo Yoon, Youngjune Gwon, and Seung- jai Min. Pomo: Policy optimization with multiple optima for reinforcement learning. In H. Larochelle. M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin (eds.), Advances in Neu- ral Information Processing Systems, volume 33, pp. 21188-21198, Curran Associates, Inc., neurips cc/ cwtpaperpaaaeeeeeeeeeeeee www.ee/ppppeee//00/ 2020. URL https::/proceed//e 2aw.:0000182222220 Paper. pdf. file/ fnle//23122211ff00a00aa33222
Yeong-Dae Kwon, Jinho Choo, I1jo0 Yoon, Minah Park, Duwon Park, and Youngjune Gwon. Matrix encoding networks for neural combinatorial optimization. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan (eds.), Advances Neu- ral Information Processing Systems, volume 34, pp. 5138-5149. Curran Associates, Inc., 2021. URL https:/ http::/:/ppcooeeenngeee neurips cct wwtppperr.pppppppppppeeeeeeeeeep fi
pddf.
Stephen Lawrence. Resouce constrained project scheduling: An experimental investigation of heuristic scheduling techniques (supplement). Graduate School of Industrial Administration, Carnegie-Mellon University, 1984.
Helena Ramalhinho Lourenço, Olivier C Martin, and Thomas Stützle. Iterated local search: Frame- work and applications. In Handbook of metaheuristics, pp. 129-168. Springer, 2019.
Hao Lu, Xingwen Zhang, and Shuang Yang. A learning-basel iterative method for solving vehicle routing problems. In International Conference on Learning Representations, 2019.
Yining Ma, Zhiguang Cao, and Yeow Meng Chee. Learning to search feasible and infeasible regions of routing problems with flexible neural k-opt. Advances Neural Information Processing Systems, volume 36, 2023.
Ashvin Nair, Bob McGrew, Marcin Andrychowicz, Wojciech Zaremba, and Pieter Abbeel. Over- coming exploration in reinforcement learning with demonstrations. In 2018 IEEE International Conference on Robotics and Automation (ICRA), pp. 6292-6299. IEEE, 2018.
Fei Ni, Jianye Hao, Jiawen Lu, Xialiang Tong, Mingxuan Yuan, Jiahui Duan, Yi Ma, and Kun He. A multi-graph attributed reinforcement learning based optimization algorithm for large-scale hybrid flow shop scheduling problem. Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining, pp. 3441-3451, 2021.
Eugeniusz Nowicki and Czeslaw Smutnicki. A fast taboo search algorithm for the job shop problem. Management science, 42(6):797-813, 1996.
Eugeniusz Nowicki and Czestaw Smutnicki. An advanced tabu search algorithm for the job shop problem. Journal of Scheduling, 8(2):145-159, 2005.
Junyoung Park, Sanjar Bakhtiyar, and Jinkyoo Park. Schedulenet: Learn to solve multi-agent
scheduling problems with reinforcement learning. arXiv preprint arXiv:2106.0305/ 202 la.
Junyoung Park, Jaehyeong Chun, Sang Hun Kim, Youngkook Kim, Jinkyoo Park, et al. Learning to schedule job-shop problems: representation and policy learning using graph neural network and reinforcement learning. International Journal of Production Research, 59(11):336-3337, b021b.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. Pytorch: An imperative style, high-performance deep learning library. Advances in Neural Information Processing Systems, 32: 8026-8037, 2019.
Laurent Perron and Vincent Furoon. Or-tools, 2019. URL https: http:///eeeellleeeeee http///vvollpprooooooo........ com/optimizate on/.
11

---

Published as a conference paper at ICLR 2024
Martin Riedmiller, Roland Hafner, Thomas Lampe, Michael Neunert, Jonas Degrave, Tom van de Wiele, Vlad Mnih, Nicolas Heess, and Jost Tobias Springenberg. Learning by playing solving sparse reward tasks from scratch. In Jennifer Dy and Andreas Krause (eds.). Proceedings of the 35th International Conference on Machine Learning, volume 80, pp. 1344-4355. PMLR, 2018.
Veronique Sels, Nele Gheysen, and Mario Vanhoucke. A comparison of priority rules for the job shop scheduling problem under different flow time-and tardiness-related objective functions. lernational Journal of Production Research, 50(15):4255-4222 2012.
Robert H Storer, S David Wu, and Renzo Vaccari. New search spaces for sequencing problems with application to job shop scheduling. Management Science, 38(10):1495-1335 -550, 1992.
Eric Taillard. Benchmarks for basic scheduling problems. European Journal of Operational Re- search, 64(2):278-28) 285, 1993.
Pierre Tassel, Martin Gebser, and Konstantin Schekotihin. A reinforcement learning environment job-shop scheduling. arXiv preprint arXiv:2104.03760, 2021.
Pierre Tassel, Martin Gebser, and Konstantin Schekotihin. An end-to-end reinforcement learning approach for job-shop scheduling problems based constraint programming. arXiv preprint 2.ii:22306.05747, 2023a.
Pierre Tassel, Benjamin Kovács, Martin Gebser, Konstantin Schekotihin, Patrick Stöckermann, and Georg Seidel. Semiconductor fab scheduling with self-supervised and reinforcement learning. arXiv preprint arXiv:2302.07112, 2023b.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Eukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Advances in neural information 2017.
processing systems, pp.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pictro Liò, and Yoshua Bengio. Graph Attention Networks. International Conference on Learning Representations, 2018. URL https: /ttts:///peeeeeeeeee wtt.:eeeeeeeooooooeeeeeeeeeeeeee
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. International Conference on Learning Representations, 2018.
Ronald J Williams. Simple statistical fraliint- algorithms for connectionist reinforcement learning, Machine Learning, 8(3):299-266, 1992.
Yaoxin Wu, Wen Song, Zhiguang Cao, Jie Zhang, and Andrew Lim. Learning improvement heuris- tics for solving routing problem. IEEE Transactions on Neural Networks and Learning Systems, 2021.
Liang Xin, Wen Song, Zhiguang Cao, and Jie Zhang. Multi-decoder attention model with embedding glimpse for solving vehicle routing problems. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pp. 12042-12044 2021a
Liang Xin, Wen Song, Zhiguang Cao, and Jie Zhang. Neurolkh: Combining deep learning model with hn-kernnghhan-helggam heuristic for solving the traveling salesman problem. In Advances in Neural Information Processing Systems, volume 34, 2021b.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In International Conference on Learning Representations, 2019. URL https: / //openeevieww.. wwt///etonnnnee wwt.orrmmmidd.i........
Takeshi Yamada and Ryohei Nakano. genetic algorithm applicable large-scale job-shop prob- lems. In PPSN, volume 2, pp. 281 281-290, 1992.
Chao Yong Zhang, PeiGen Li, ZaiLin Guan, and YunQing Rao. A tabu search algorithm with neighborhood structure for the job shop scheduling problem. Computers Operations Research, (2211):322--2222 2007.
12

---

Published as a conference paper at ICLR 2024
Cong Zhang, Wen Song. Zhiguang Cao, Jie Zhang, Puay Siew Tan, and Xu Chi. Learning to dispatch for job shop scheduling via deep reinforcement learning. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin (eds.), Advances in Neural Information Processing Systems, volume 33, pp. 1621-1632. Curran Asso- ciates, Inc., 2020. URL httpt:tt///......t. ptattp:://prroceednngg iew.eeeiiiinns.uuiiip...... seeurrps... wttpssssrrrp.s...pppppreree wwtpppppe///22//E1..... pdf.
Jianan Zhou, Yaoxin Wu, Wen Song. Zhiguang Cao, and Jie Zhang. Towards onni-generalizable neural methods for vehicle routing problems. In International Conference on Machine Learning, 2023.
A THE n-STEP REINFORCE ALGORITHM
We adopt the REINFORCE algorithm (Williams, 1992) for training. However, here the vanilla REINFORCE may bring undesired challenges training for two reasons. First, the reward sparse in our case, especially when the improvement process becomes longer. This is notorious reason causing various DRL algorithms to fail (Nair et al., 2018; Riedmiller et al., 2018). Second, will easily cause out-of-memory issue if we employ large step limit T, which is often required for desirable improvement performance. To tackle these challenges, we design an n-step version of REINFORCE, which trains the policy every steps along the trajectory (the pseudo-code is given below). Since the ntstep REINFORCE only requires storing every n steps of transitions, the agent can explore a much longer episode, This training mechanism also helps deal with sparse reward, as the agent will be trained first on the data at the beginning where the reward is denser, such that is ready for the harder part when the episode goes longer.
We present the pseudo-code of the n-step REINFORCE algorithm in Algorithm 1.
Algorithm n-step REINFORCE
Policy ( (.). step limit T, step size n, learning rate a, training problem size |J] x [M]. batch size B. total number of training instances I
Input:
Output: Trained policy Tg- mg-((a (s)))))
1: for i= to é < do
2: Randomly generate B instances of size |J] [M], and compute their initial solutions
$6) by using the dispatching rule FDD/MWKR
3: Initialize a training data buffer De with size 0 for each $ E {0b ... :
4: for = 0 T do
5:
for s
do Compute a local move at To(a?ls))
6:
7:
Update sy w.r.t at and receive reward r(a., st)
8:
if mod == then
9:
loss =
10:
for to 0 do
11:
loss + = log To To(af_, 180,-))) Rh where Rh_ is the return for step - j
12:
end for
13:
= + a V (loss));
14:
end if
15:
end for
end for
17: i i= i B
end for
19:
return Tpr (a, ss))
B HARDWARE AND CONFIGURATIONS
We fixed hyperparameters empirically tuned small problems. We adopt K 4 iterations of TPM and CAM updates. In each TPM iteration, MLP has 2 hidden layers with dimension 128,
13

---

Published as a conference paper at ICLR 2024
and e² is set to 0 following (Xu et al., 2019). For CAM, both GAT and GAT have one attention head. For action selection, MLPA A has 4 hidden layers with dimension 64. All raw features are normalized by dividing large number, where Pj; is divided by 99, and est;; and lstye are divided by 1000. For each training problem size, we train the policy network with 128000 instances, which generated the fly in batches of size 64. We use step REINFORCE (refer to Appendix A for the pseudo-code), with Adam optimizer and constant learning rate a = 10 5 Another set of 100 instances generated for validation, which is performed every 10 batches of training. Throughout our experiments, we sample actions from the policy. All initial solutions are computed by a widely used dispatching rule, i.e. the minimum ratio of Flow Due Date to Most Work Remaining (FDD/MWKR) (Sels et al., 2012). During testing, we let our method run for longer improvement steps by setting T to 500, 1000, 2000, and 5000, respectively. Our model is implemented using Pytorch-Geemmtrric (PyG) (Fey & Lenssen, 2019). Other parameters follow the default settings in PyTorch (Paszke et al., 2019). We use a machine with AMD Ryzen 3600 CPU and single Nvidia GeForce 2070S GPU. We will make our code and data publicly available.
10 and step limit T = 500 in n-
C COMPUTATIONAL COMPLEXITY ANALYSIS
C.I PROOF OF PROPOSITION 4.1
We first prove that the computational complexity for TMP and CAM is linear for the number of jobs [J] and the number of machines [M], respectively. Throughout the proofs, we let [O] = [ +-2 and [g] = |C U D = [C] + [D] = 2| [MM [M]+ total number of edges in G, respectively.
[M] denote the total number of nodes and the
Lemma C.1. Any layer k of TPM possesses linear computational complexity w.r.t. both |J] and [M] when calculating node embedding pły and graph level embedding P.
Proof. For the k-th TPM layer, the matrix form of each MLP layer Ç can be written as:
M2 = BN (d(S) (((A + (1+ I) Ma-1) W())) for 1- Z
where M Mj E 1 are the node embeddings from layer k - 1 and k respectively, <x E R and w( E RPxp are learnable parameters, is an element-wise activation function (e.g. relu or tanh), BN is a layer of batch normalization (Ioffe & Szegedy, 2015), and the operator "." denoting the matrix multiplication. Then, the computational time of equation (9) can be bounded by O(EEpp + 1 + Z|O| (p² + p)). Specifically, O(Elpp) is the total cost for message passing and aggregation. Note that since we adopt the sparse matrix representation for A, the complexity of message passing and aggregation will be further reduced to ((E'p) in practice. The term Z|O is
the total cost for feature transformation by applying w(O) and 0 (p² +p) is the cost for batch normalization. This analysis shows that the complexity of TPM layer for embedding a disjunctive graph G is linear w.r.t. both |J] and MM Finally, since we read out the graph level embedding by averaging the node embeddings, f াo Eveo Héy and the final graph-level embedding is
just the sum of all that of each layer, i.e. Ma = Σx Hgg we can conclude that the layer of TPM possesses linear computational complexity.
Next, we show that the computational complexity of each CAM layer is also linear w.r.. both the number of jobs [J] and the number of machines MM
Lemma C.2. Any layer k of CAM possesses linear computational complexity want both [J] and [M] when calculating node embedding vt.
Proof. Since we employ GAT as the building block for embedding G. and GM, the computational complexity of the k-th layer of CAM is bounded by that of the GAT layer. By referring to the complexity analysis in the original GAT paper (Veličković et al., 2018), it is easy to show that the computational complexity of any layer & of CAM equipped with single GAT attention head com- puting p features is bounded by O O p2 + (E)p), since G, and GM both contain all nodes in G but disjoint subsets of edges in G (see Figure 4). Similar to TPM, employ average read-out function
14

---

Published as a conference paper at ICLR 2024
RL-GNN
RL-GNN ScheduleNet
ScheduleNet
Average time (Seconds)
500
Average time (seconds)
25
290
13
100
10
15
20
30
1.0
20
30
35
Number of machines
Number of jobs
(a) Fixed [J]
(b) Fixed |M|
Figure 5: The computational complexity of RL-GNN, ScheduleNet, and our method (500 im- provement steps). In the left figure, we fix | = 40 and test on various number of machines [M]. While the right figure, we [M| = and test on various number of jobs [T].
for the final graph level embedding vG = 1o Eveo u8. where wa the node embeddings from the last layer K. Thus, the overall complexity of CAM is linear w.r.t. both | and [M].
Finally, the Theorem 4.1 is proved by the fact that our action selection network is just another MLP whose complexity is linear to the input batch size, which is the total number of nodes in G.
C.2 COMPUTATIONAL COMPLEXITY COMPARED WITH DRL BASELINES
In this part, we empirically compare the computational complexity with the two best-performing DRL baselines RL-GNN (Park et al., 2021b) and ScheduleNet (Park et al., 2021a). While L2D (Zhang et al., 2020) very fast, here we do compare with due its relatively poor perfor- mance. We conduct two sets of experiments, where we fix one element in the number of jobs J and machines _MI, and change the other to examine the trend of time increase. For each pair of [J] and IM we randomly generate 10 instances and record the average run time.
In Figure 5, we plot the average run time of RL-GNN, ScheduleNet and our method (500 steps) in these two experiments. We can tell that the computational complexity of our method is linear w.rt. line with our theoretical analysis in Proposition 4.1. I. In Figure 5(a) where [J] is fixed, the run time of RL-GNN and ScheduleNet appears to be lincarly and quadratically increasing w.r.t [M], respectively. This is because the number edges in the graph representations of RL-GNN and ScheduleNet are bounded by O(L and ((IM ()) respectively. While in Figure 5(b) where [M| is fixed, the run time of RL-GNN and ScheduleNet are quadratically and linearly increasing w.r.t (T], because the number of edges tively. In Figure 5(b), the reason why our method takes longer time when the problem size is small, e.g. 10x 10, is that our method performs 500 improvement steps regardless of the problem size. In contrast, RL-GNN and ScheduleNet are construction methods, for which the construction step closely depends on the problem size. For smaller problems, they usually take less steps construct solution, hence are faster. However, when the problem becomes larger, their run time increase rapidly and surpass ours, as shown in the right part of Figure 5(b).
[J] and [M], which
bounded by O(TT(2 and O(JT)), respec-
D MESSAGE-PASSING FOR CALCULATING SCHEDULE
D. PROOF OF THEOREM 4.2
We first show how to compute esty by the critical path method (CPM) (Jungnickel & Jungnickel, 2005). For any given disjunctive graph = (O, CUD) of a solution s, there must exist topological order among nodes of G Φ (1,2,-. |O]] where node V is said to have the higher order
15

---

Published as a conference paper at ICLR 2024
Table 2: Run time of our evaluator (MP) versus CPM. "Speedup" is the ratio of CPM (CPU) to MP (GPU).
Batch size
32
64
128
256
512
MP (CPU)
0.051s
0.674s
1.216s
2.569s
5.219;
10.258s
MP (GPU)
0.058s
0.094s
0.264s
0.325s
0.393s
0.453s
CPM (CPU)
0.009s
0.320s
0.634s
1.269s
2.515s
5.183s
Speedup
0.16x
3.40x
2.40x
3.90x
6,42x
11.4x
than node U if (VV) can be calculated recursively by following the topological order Φ, i.. esty = max; + esty) where U E Ny is a neighbour of V.
o(U). Let ests 0 for node Og. Then for any node V 0110s). esty
Proof. Now we show that the message passing is equivalent to this calculation. Specifically, for any node V, if YU E .Nv ct 0 then dy mpmma ((r (1 (l) dr|vv E (VV))) maxteeNy (pu + dr). Then it is easy to show that the message cv = 0 if and only if cw = 0 for ((V) and there is path from W to V. This is because of reasons. First, the message always passes from the higher rank nodes to the lower rank nodes following the topological order in the disjunctive graph G. Second, cv otherwise message c (W) = 1 will be recursively passed to node V via the message passing calculation ev mpmaz ((cu VVU EV(()). Hence, dy = esty for all U Ny when all cy = Therefore, dy maXueNy (pu + du) maxueN, (Pu + esty) = esty. Finally, dr estt = Cmaz as the message will take up to H steps to reach Or from Os and the processing time of Or is O.
all W (W))
D.2 PROOF OF COROLLARY 4.3
Computing Isty by CPM follows similar logic. We define 3 - (1,2....,10)) as the reversed topological order of V E O, ΦVV) < Φ(U) if and only if <(V) > 6(U) (in this case, node Or will rank the first according to Φ). Let (st, Cmaz for node Or. Then for any node V E OV10r}. lsty can be calculated recursively by following the reversed topological order o, i..
lsty ming( (-p pu + (sty) where V E No is neighbour of U in G.
Now, we can show that dy mpmar {PC + +1 - ) du }) = mpmaa (ppu+du +dy })- = maxu
dy) = maxy (PU 1styy ) = -Isty when ēy
for all U E Ny by following the same procedure in the above proof for Proposition 4.2. Finally, ds = 1st, = O as the message will take up to H
steps to reach Og from Or, since the lengths of the longest path in G and G are equal.
D.3 EFFICIENCY OF THE HEESAGEEPASSSIN EVALUATOR
We compare the computational efficiency of our message-passing evaluator with traditional CPM on problems of size 100x20, which are the largest in our experiments. We implement CPM in Python, following the procedure in Section 3.6 of (Jungnickel & Jungnickel, 2005). We randomly generate batches of instances with size 1, 32, 64, 128, 256 and 512, and randomly create directed disjunctive graph (i.e. a solution) for each instance. We gather the total run time of the two methods in Table 2. where we report results of both the CPU and GPU versions of our evaluator. We can observe that although our message-pasee -aasagggggagnngggggg evaluator does not present any advantage on a single graph, the performance drastically improves along with the increase of batch size. For a batch of 512 graphs, our evaluator runs on GPU is more than 1l times faster than CPM. We can conclude that our message-passing evaluator with GPU is superior in processing large graph batches, confirming its effectiveness in utilizing the parallel computational power of GPU. This offers significant advantage for deep (reinforcement) learning based scheduling methods, in terms of both the training and testing phase (for example, solving a batch of instances, or solving multiple copies of a single instance in parallel and retrieving the best solution).
16

---

Published as a conference paper at ICLR 2024
D.4 AN EXAMPLE OF CALCULATING est BY USING THE PROPOSED MESSAGE- PASSING EVALUATOR.
In Figure 6 we present an example of calculating the earliest starting time for each operation in disjunctive graph using our proposed meessage-assingg operator.
11-41
(1.00 U
11:81
80.0
11-21
01
$1.25
O
Du
Drabi
Or
Oiabi
Or
OriPi
ITURE
11-21
11.22
O&/i
OLR
Gall
Orlal
OLB
Dmll
Orlel
Ga/
OLB
DalB
Dull
Orli
0.00
0,
0.33
Duaht
Duab
(a) Before message passing
(b) 1 message passing
(c) 2nd message passing
80.0 dt
O T)
1)
10. 91
01
Oul
Pis
OLR
PaiBi
OLR
Paita
Pia
11.31
13m0
19.00
13.0
Ov
Pmili
Orttl
PhiBo
Gmil
11
0 30
OuP
Puli
Oug
Oua
DulBi
Dial
(d) 3rd message passing
(e) 4thh message passing
(f) 5th message passing
di
13. d
10
J0. 31
30.0
J0
Oma
Orala
On
Orali
12)
10)
31. 131
10
33, 121
32. 121
Owl
Dull
On
(g) 6th message passing
(h) 7th message passing
(i) 8 message passing
Figure 6: An example of the forward message passing for calculating est. The pair of numbers (dy, ) in the open bracket and the number in the square bracket [pv] denote the messages and the processing time for each vertex V, respectively. In each graph, highlight the nodes V with cv = 0. After eight times of message passing, ey for any node V equals 0, which can be utilized as a signal for termination. Then, the message dy equals the earliest starting time esty for each V. It is clear that the frequency of message passing (8) is less than H, the length of the longest path containing the most nodes, which 9 (Os, O1, O12, O13, O21, O22, O23, O33, OT).
E HAND-CRAFTED IMPROVEMENT RULES
Here we present details of the three hand-crafted rule baselines, i.e. greedy (GD), best-improvement (BI), and firs-immprovement (FI). The greedy rule is widely used in the tabu search framework for JSSP (Zhang al., 2007). The restoimppoveeent and the introvipproeeentt rules are widely used in solving combinatorial optimization algorithms (Hansen & Mladenović, 2006). Specifically, the greedy rule selects the solution with the smallest makespan in the neighbourhood, while the best-improvement and the fist-impprvemment rules select the best makespan -eeuuciign and the first lalkespan-reducingg solution in the neighbourhood, respectively. If there is no solution in the neigh- bourhood with makespan lower than the current one, the best-improvement and frst-inprovement rules cannot pick any solutions. However, the greedy rule will always have solutions to pick.
It is unfair to directly compare with BI and Fl since they may stuck in the local minimum when they cannot pick any solutions. Thus we augment them with restart, a simple but effective strategy widely used in combinatorial optimization, to pick new starting point when reaching local minimum
17

---

Published as a conference paper at ICLR 2024
(Lourenço et al., 2019). While random restart is simple and direct choice, it performs poorly probably because the solution space is too large (Lourenço et al., 2019). Hence, we use a more advanced restart by adopting memory mechanism similar to the one in tabu search (Zhang al., 2007). Specifically, we maintain a long-term memory which keeps tracking the w latest solutions in the search process, from which random solution is sampled for restart when reaching local minimum. The memory capacity w controls the exploitation and exploration of the algorithm. If too large, it could harm the performance since bad solutions may be stored and selected. On the contrary, too small could be too greedy to explore solutions that are promising, Here we set 100 for a balanced trade-off. We do not equip GD with restart since it always has solutions to select unless reaching the absorbing state.
F COMPARISON WITH THE ONLINE DRL-BASED METHOD
The makespan of our method (trained on size 20x 15) with 5000 improvement steps and the online DRL-based method (Tassel al., 2021) 1) in solving the Taillard 30x20 instances are shown in Table
3. Note that this method performs training for each instance individually, while our method learns only one policy offline without specific tuning for each instance.
Table 3: Detailed makespan values compared with the online DRL method
Method
Tai41
Tai42
Tai43
Tai44
Tai45
Tai46
Tai47
Tai48
Tai49
Tai50
(Tassel al., 2021)
2208
2168
2086
2261
2227
2349
2101
2267
2154
2216
Ours-5000
2248
2186
2144
2202
2180
2291
2123
2167
2167
2188
G TRAINING CURVES
15
w5 15
TPM CAM: 10
Ca-SAF
6.14
20 20
Nr My MW
Man
215
130
Every batches.
Every batches.
(a) For various problem sizes
(b) For different modules
10x10
10x20
10K10
Cmnax
batshes.
(c) For different of heads CAM
(d) For different seeds
Figure 7: Training curves.
18

---

Published as a conference paper at ICLR 2024
H COMPARISON WITH TABU SEARCH
We compare our method with a Tabu search-based metaheuristic algorithm with the dynamic tabu size proposed in (Zhang al.. 2007). Since the neighbourhood structure in (Zhang al., 2007) is different from Ns. to make the comparison fair, we replace it with N₂ (TSN5). We also equip the tabu search method with our passage-passingg evaluator to boost speed. We test on all seven public datasets, where we conduct two experiments. In the first experiment, we fix the search steps to 5000. In the second one, we adopt the same amount of computational time of 90 seconds (already sufficient for method generate competitive results) for both methods. The results for these two experiments are presented in Table and Table 5, respectively.
Table 4 indicates that our method closely trails Tabu search with a 1.9% relative gap. This is due to the simplicity of our approach as a local search method without complex specialized mechanisms (Figure 2). making direct comparison less equitable. However, our method is significantly faster than Tabu search since it avoids evaluating the entire neighbourhood for move selection. Conversely, Table 5 reveals that our method outperforms Tabu search under the same time constraint. This is attributed to the desirable ability of our method to explore the solution space more efficiently within the allotted time, as does not require full neighbourhood evaluation for move selection.
Table Performance compared with Tabu search for 5000 improvement steps. For each prob- lem size, we compute the average relative gap of the makespan of our method to the tabu search algorithm, and we report the time (in seconds) for each method for solving a single instance.
Tailard
ABZ
FT
Metiun
15 15 20 15 20 x
50 15 x 20
50 x 15 50 x 20 100 x 20
10 1o 20 x 15 6 10x 10
20 x
Cup Time
Gup
Time
(Cup Time
Clp
Time Cup Time
Cap
Time
Time
(lup
Time
Gup
Time
Time
(up
Time
Cup
Time
Cup
Time
TSN5
100%
3T1.5.0000 311,4 369 as 0.0% 378.s uos 422.5 422.540.0% 547.590:0% 573.051.0
1045.8g p00% 177.8/0000 263,5 124.00.05 213. 235.46
Ours
2.8
02.25
102. 1.,....8. 2.2 114.3, 2.8% 120 4.11 3.55
168. 2.77 228.1 1.59 504.5--111 3.. 99 996.000 67 7777 74 73.3.
LA
SWV
ORB YN
Medbod
x.
15 x.
x0 x 10
10 x0 10 30 x 10 15 x.
20.x 10 20 x 15
50 x 10
x
Gop
Time (op
Time (Gap Time Gap
Time Gap
Time Cap
Time
GGa
Time
Gaa
Time
Cop
Time Cop
Time Oap
Time
Gap
Time Cop Time
TSNS
100%
56.54p00s
81.948006 11888 0.0% 192 0.00 225 14005
213.40000% 149 50000% 283.14
0.0% Isbb0% 460 9:0.0 225 04000% 318.25 88.80
Ours
1.4%
50.00p.0r
71.0s0.00 73.96-0.9% 15.160.55 8096/188 85.41p.00 99.34 19.36
2.7% 6696/1.9 29.8 126 1.1% 75.94500 113.3.
Table 5: Performance compared with Tabu search for two minutes. We report the average gap to the upper bound solution.
Method
Taillad
ABZ
15x15
20x15
20:20
30x
30x20
50x15
50=20
100x20
10xc
20x
6xx6
10x:1
20x5
7.9%
12.9%
5.3%
6.7%
TSNS
SWV
YN
15x5
20x55
10
15x
30x00
1.7%
5.3%
14.7%
2.7%
TSNS
0.0%
5.4%
14.8%
I ENSEMBLE PERFORMANCE
The ensemble results for testing and generalization on the seven benchmarks are presented in Table 6. For each instance, we simply all the five trained policies and retrieve the best solution. We can observe that for most of the cases, with the same improvement steps, the ensemble strategy can further improve the performance.
J STATE TRANSITION
The state transition is highly related to the N₂ neighbourhood structure. As we described in Prelim- inaries (Section 3), once our DRL agent selects the operation pair, say (O13, O21) in the sub-figure on the right of Figure 1, the N₂ operator will swap the processing order of O13 and O21 Originally, the processing order between O13 and Oz1 is O13 - Oz1 After swapping, the processing order will become 013 < O21- However, solely changing the orientation of are O13 - O21 is not enough. In this case, we must break the are Oz1 - Oyz and introduce a new disjunctive O13 - Ozz since
19

---

Published as a conference paper at ICLR 2024
Table 6: Ensemble results on classic benchmarks. Values in the table are the average gap to the best solutions in the literature. Bold means the ensemble strategy performs better with the same improvement steps.
Taillard
ABZ
Method
15x
20x 15
x0
30x 15
30x 20
50x 15
50
x
10x 10
20x 15
6x6
10x
20x5
Closest-500
9.3%
11.6%
12.4%
14.7%
17.5%
11.0%
13.0%
7.9%
2.8%
11.9%
0.0%
9.9%
6.1%
Closest-1000
8.6%
10.4%
11.4%
12.9%
15.7%
9.0%
11.4%
6.6%
2.8%
11.2%
0.0%%
8.0%%
3.9%
Plosest-2000
7.1%
9.4%
10.2%
11.0%
14.0%
6.9%
9.3%
5.1%
2.8%
9.5%
0.0%
5.7%
1.5%
Closest-5000
6.2%
8.3%
9.0%
9.0%
12.6%
4.6%
6.5%
3.0%
1.4%
8.0%
0.0%
5.6%
1.1%
Ensemble-500
8.8%
11.6%
12.0%
14.4%
17.5%
10.4%
12.9%
7.6%
2.4%
11.5%
0.0%
8.5%
6.1%
Ensemble- 1000
6.3%
10.4%
10.9%
12.2%
15.7%
8.5%
11.0%
6.2%
1.7%
10.6%
0.0%
8.0%
3.9%
Ensomble-2000
5,9%
9.1%
9.6%
10.6%
14.0%
6.5%
9.2%
4.3%
1.7%
9.4%
0.0%
5.7%
1.5%
Easemble-5000
4.7%
1.1%
Method
LA
SWV
ORB
YN
10x5
15x5
20x5
10x 10
15x 10
20 10
30x 10
15x 15
20 10
20x
50x 10
10x
20x20
Closest-500
2.1%
0.0%
0.0%
4.4%
6.4%
7.0%
0.2%
7.3%
29.6%
25.5%
21.4%
8.2%
12.4%
6.6%
Closest-2000
1.8%
0.0%
0.0%
1.8%
4,0%
3,4%
0.0%
6.3%
21.8%
21.7%
19.0%
5.7%
9.6%
Closest 5000
1.8%
0.0%
0.0%
0.9%
3.4%
2.6%
0.0%
5.9%
17.8%
17.0%%
17.1%
3.8%
8.7%
Ensemble-500
2.1%
0.0%
0.0%
3,0%
4.7%
7.3%
27.2%
25.5%
8.0%
12.4%
Ensemble-1000 1000
1.6%
0.0%
0.0%
2.3%
3,9%
5.7%
0.0%
6.6%
24.5%
23.5%
19.9%
6.5%
10.5%
Ensemble-222 2000
1.6%
0.0%
0.0%
1.8%
3,9%
3.4%
0.0%
6.2%
21.7%
21.7%
18.9%
5.4%
9.4%
Ensemble-505 5000
1.6%
0.0%
0.0%
0.9%
3.4%
2.6%
0.0%
5.0%
17.8%
17.0%
17.1%
3.8%
7.4%
Operation
Operation
Critical Block
Transit
2
3
5
2
4
Swap the first two operations
6
6
Figure An example of state transition using N3 neighbourhood structure.
the operation Oz2 is now the last operation to be processed on the blue machine. In some cases, the state transition involves several steps. For example, in Figure 8 below, given processing order O + O3 + O₂ + O₂ some machine, if we swap O2 and O₃ (O2 and Og are the first two operations of some critical block), we need break disjunctive ares O₁ - O2 and O3 + O4, flip the orientation of are O₂ > O₃ as O₂ t O3, finally, add new arcs O₂ + O and O₂ + O4. So, the new processing order after the transition will be O - O3 + O₂ ~> O4 (right figure).
In summary, after the transition, the new disjunctive graph (state) will have a different processing order for the machine assigned to the selected operation pair, but other machines stay unaffected.
Then, the starting time (schedule) of every operation is re-calculated according to the proposed message-passing evaluator (Theorem 4.2).
K THE TOPOLOGICAL RELATIONSHIPS COULD BE MORE NATURALLY MODELLED AMONG OPERATIONS IN THE DISJUNCTIVE GRAPH.
disjunctive graph effectively represents solutions by using directed arrows to indicate the order of processing operations, with each arrow pointing from preceding operation its subsequent The primary purpose of the disjunctive graph is to encapsulate the topological relationships among the nodes, which defined by these directional connections. Thus, the disjunctive graph excels
20

---

Published as a conference paper at ICLR 2024
in illustrating the inter-dependencies between operations, in contrast to other visualization methods, such as Gantt charts, which are better suited for presenting explicit scheduling timelines.
In formulating partial solutions within construction step, the agent must possess accurate work-in- progress information, which encompasses specifics such as the extant load on each machine and the current status of jobs in process. The challenge encountered in this scenario relates to the difficulty in identifying suitable entities within the disjunctive graph that can store and convey such informa- tion effectively. While it is conceivable to encode the load of machine using numerical values, no discrete node within the disjunctive graph explicitly embodies this information. Instead, a ma- chine's s representation is implicit and discerned through the collective interpretation the operations it processes, effectively forming what is termed a 'machine clique.' This indirect representation ne- cessitates more nuanced approach to ensuring that the agent obtains the necessary information to construct viable partial solutions.
L RESULT FOR EXTREMELY LARGE INSTANCES
To comprehensively evaluate the generalization performance of our method, we consider another three problem scales (up to 1000 jobs), namely 200 x 40 (8,000 operations), 500 x 60 (30,000 operations), and 1000 x 40 (40,000 operations). We randomly generate 100 instances for each size and report the average gap to the CP-SAT. Hence, the negative gap indicates the magnitude in percentage that our method outperforms CP-SAT. We use model trained with size 20 x 15 for comparison. The result is summarized in Table 7.
Table 7: Generalization performance on extremely large datasets.
200x40
500x60
1000x40
CP-SAT
0.0% (1h)
0.0% (1h)
0.0% (1h)
Ours-500 -24.31% % (88.7s) -0.556% (3.4m)
-15.99% (4. (4.1m)
From the results in the table, our method shows its advantage against CP-SAT by outperforming it for the extremely large-scale problem instances, with only 500 improvement steps. The number in the bracket is the average time of solving a single instance, where "s", "m", and "h" denote seconds, minutes, and hours, respectively. The computational time can be further reduced by batch processing.
M ABLATION STUDIES
In Figure 7(a) and Figure 7(d) (Appendix G), we display the training curves of our method on all five training problem sizes and for three random seeds size 10x 10, respectively. We can confirm that our method is fairly reliable and stable for various problem sizes and different random seeds. We further conduct ablation study on the architecture of the policy network to verify the effectiveness
combining TPM and CAM in learning embeddings of disjunctive graphs. In Figure 7(b), we display the training curve of the original policy network, as well as the respective ones with only TPM or CAM, on problem size 10x 10. In terms of convergence, both TPM and CAM are inferior to the combination, showing that they are both important in extracting useful state features. Additionally, we also analyze the effect of different numbers of attention heads in CAM, where we train policies with one and two heads while keeping the rest parts the same. The training curves in Figure 7(c) show that the policy with two heads converges faster. However, the converged objective values have no significant difference.
21


Reviews:
[{"review_id": "fdusfbcHot", "reviewer": "Reviewer_Sv6i", "summary": "This articled studied the problem of solving Job-shop scheduling problems using deep reinforcement learning focusing on heuristics. The authors have proposed a novel deep reinforcement learning based improvement heuristics where the graph representations are employed to encode complete solutions.", "questions": "how does the transition state in MDP (section 4.1) is calculated? need to explore in detail on how the transition space is updated with the current status information of all jobs and machines.\nwhy the reward function goal is to improve the initial solutions? isn't closely correspond to scheduling goal?\nHow does the generalization capability of the agents are addressed in this article? \nOne way is to introduce order swapping mechanism with an instance and evaluate with another instance of the same size.\nOpenAI Gym toolkit and associated kits provide reinforcement learning environment API - any exploration on this would have yielded results that could also be validated", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "Good and decent review of literature based introduction gives a good readability.\nClear articulation of the MDP process with an example of state transition\nComparative study with Tabu Search algorithm for solving the instance \nThe computation complexity of the proposed method is linear with respect to the number of jobs and number of machines.", "weaknesses": "There are many studies that job shop scheduling that has been modeled as a MDP but very few citations are present in the article.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "DawZKuzUR1", "reviewer": "Reviewer_jCmi", "summary": "The paper presents a local search method based on deep reinforcement learning (RL) for the job shop scheduling problem. The authors propose to encode solutions as disjunctive graphs and design a novel graph neural network architecture to process them. In addition, they propose an efficient technique to compute the schedule of a solution on GPU.", "questions": "In the n-step REINFORCE, how is the return R_{t-j}^b computed? If it's over n steps, it means the RL agent basically ignores future rewards after n steps. In a general RL problem, this may lead to bad performance, but I guess for a local search method like in this paper, this may not be important. Could you comment on that point?\n\nWhat did you choose to compare with Tabu search? \nWhat are the state-of-the-art methods for the job shop scheduling problem? How does the proposed method compared to them?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "A novel graph neural network architecture is proposed to process the different type of information encoded in a disjunctive graph: graph topology, operation order in the solution, and operation order on a machine.\n\nAn efficient method to compute the schedules of batch of solutions is proposed, which can accelerate training deep RL training.\n\nThe authors performed a broad series of experiments on various instances comparing their proposed method with other deep RL algorithms, some basic heuristic methods, but also a meta-heuristic method (tabu search).", "weaknesses": "The presentation is generally clear. However, some parts could be improved.\n\nI believe that some notions could be explained in a better way. For instance:\n- page 1: \"given that the topological relationships could be more naturally modeled among operations\" is not clear to me.\n- page 3: the notion of N5 neighborhood could be more explained more formally (instead of the current text and the example).\n- Some sentences/expressions are unclear (see Questions).\n\nSection 4.2.1: The first two sentences seem to contradict themselves.\nWhat is meant by \"machine predecessor\" becomes only clear later on.\n\nMinor:\npage 7: a closing curly brace is missing for c_V.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "FqGCVmX0Wo", "reviewer": "Reviewer_Yw7H", "summary": "This work addresses the job shop scheduling problem (JSSP), a classic combinatorial optimization task. It proposes a solution based on deep reinforcement learning to learn improvement heuristics, which iteratively refines an existing solution. The authors leverage a disjoint graph representation of the state (which is more complete than that employed in prior works), and propose a GNN architecture for its representation. The proposed MDP formulation chooses a pair of operations to be swapped, and the RL model is trained via the policy gradient. An experimental evaluation is presented, which compares the method with a large set of prior approaches, spanning deep RL, metaheuristic, and exact methods. The evaluation shows favorable results in comparison with these baselines.", "questions": "**C1**. There are some typos / informal language / awkward word choices in the manuscript, and it would benefit from further revisions until publication. Some examples: \n\n- \"receives relatively less attention\" -> received / has received (p1)\n- \"In specific\" -> specifically (p1)\n- \"A delicate Markov decision process formulation\" (p2)\n- \"graph-based ones aforementioned\" -> aforementioned graph-based ones\n- \"Precedent constraints\" -> precedence constraints (p3)\n- \"To fast calculate\" -> to quickly calculate (p3)\n- \"till\" -> until (p4)\n\n**C2**. The results in Appendix H / Table 4 appear very positive and show good generalization performance and scalability. I think it is worth making room for them in the main text.\n\n**C3**. \"Parameter $\\theta$\" -> Parameter *set* $\\theta$ in 4.2?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "**S1**. The paper addresses a highly practical problem that has received comparatively less attention (e.g., compared with routing problems) in the combinatorial optimization literature. The proposed method is fairly original, and is similar in spirit with other learned improvement heuristics.\n\n**S2**. The evaluation performed by the authors is very comprehensive (in terms of datasets, instance sizes, baselines, and scenarios). Most importantly, it shows that the method attains excellent performance while requiring a reasonable time budget. It is one of the few cases where opting for the ML model over a classic solver or metaheuristic may actually be preferable in practice.", "weaknesses": "**W1**. The only issues that I have identified relate to the clarity of the presentation of the problem formulation and solution method. More specifically:\n\n- The problem formulation uses two different semantics for the $ji$ notation ($O_{ji}$ and $m_{ji}$). A different subscript is needed to indicate the machine, and it should be reflected in the figures as well.\n- I was not able to fully understand the transitions induced by the swapping of the two operations, given that it appears to trigger other reconfigurations of the disjunctive graph beyond the two vertices indicated by the action (e.g., the changes to the edges connecting the red machine in Figure 2b). How are these other reconfigurations determined? This further detail should be added in Section 4.1.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "LZ9oVTRil4", "reviewer": "Reviewer_W4mB", "summary": "The paper proposes a novel, learning-based improvement heuristic for the job shop scheduling problem. It uses a novel graph neural network  to select operations that modify a solution from a set of candidate operations defined by the N5 neighborhood structure. The novel network architecture consists of a topology embedding module and a context-aware embedding module that are designed to encode the problem instances and their solutions. The authors prove that their method scales linearly with the problem size. Furthermore, they evaluate their method on a variety of instances from the literature and compare it to state-of-the-art ML methods, simple handcrafted heuristics, and a tabu search using the same neighborhood structure. Overall, the proposed method shows good performance outperforming existing ML methods in most settings.", "questions": "- Have you experimented with different ways to calculate the reward? For your current method, the network might receive different rewards when picking the same actions at the same state depending on what solutions were found in previous states. While I understand the motivation of your current choice, I wonder if this might impact learning.\n- Have you tried to use a baseline during learning for REINFORCE?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The proposed method introduces several novel concepts. In contrast, to many other approaches it is an improvement heuristic (instead of a construction heuristic). The novel network architecture is specifically designed to encode existing solutions and consists of two components that both are independently evaluated in an ablation study and seem to be well suited for the task. Furthermore, the REINFORCE algorithm has been slightly adapted for the task at hand.\n- The method scales linearly with the problem size. In contrast, to many other machine learning based approaches the proposed method can thus scale to larger problem instances. \n- The proposed method outperforms other state-of-the-art learning-based approaches for the job shop scheduling problem.\n- Overall, the paper is well written.\n- The authors conduct ablation studies that evaluate individual components of the method.", "weaknesses": "- The method uses the handcrafted N5 neighborhood to generate candidate operations (i.e., the set of possible actions for the model). This means that the method relies on a handcrafted component specific to the job shop scheduling problem. It is thus unclear how easily the method can be modified to solve other scheduling problems. Despite being based on a handcrafted heuristics it does not outperform the handcrafted tabu search using the same neighborhood structure in all settings.\n- The authors only evaluate their method on the job shop scheduling problem and not on any other scheduling problems.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)