Self-Labeling the Job Shop Scheduling Problem
Authors: Andrea Corsini
Angelo Porrello
Simone Calderara
Mauro Dell'Amico
Venue: NeurIPS 2024 poster (2024)
Keywords: Self-Labeling
Generative Model
Job Shop Scheduling
Traveling Salesman Problem
Primary area: machine_learning_for_other_sciences_and_fields
TL;DR: We propose a novel self-labeling improvement method for combinatorial problems that enables the training of state-of-the-art generative models without requiring optimality information or defining Markov Decision Processes.

Abstract: This work proposes a self-supervised training strategy designed for combinatorial problems. An obstacle in applying supervised paradigms to such problems is the need for costly target solutions often produced with exact solvers. Inspired by semi- and self-supervised learning, we show that generative models can be trained by sampling multiple solutions and using the best one according to the problem objective as a pseudo-label. In this way, we iteratively improve the model generation capability by relying only on its self-supervision, eliminating the need for optimality information. We validate this Self-Labeling Improvement Method (SLIM) on the Job Shop Scheduling (JSP), a complex combinatorial problem that is receiving much attention from the neural combinatorial community. We propose a generative model based on the well-known Pointer Network and train it with SLIM. Experiments on popular benchmarks demonstrate the potential of this approach as the resulting models outperform constructive heuristics and state-of-the-art learning proposals for the JSP. Lastly, we prove the robustness of SLIM to various parameters and its generality by applying it to the Traveling Salesman Problem.

Self-Labeling the Job Shop Scheduling Problem
Andrea Corsini
Angelo Porrello
Simone Calderara
Mauro DelioOmico
University of Modena and Reggio Emilia, Italy (name, surname @unimore.11
Abstract
This work proposes supe-supe training strategy designed for combinatorial problems. An obstacle in applying supervised paradigms to such problems is the need for costly target solutions often produced with exact solvers. Inspired by semi- and self-supervised learning. we show that generative models can be trained by sampling multiple solutions and using the best one according the problem objective as a pseudo-label. In this way, we iteratively improve the model generation capability by relying only on its self-supervision, eliminating the need for optimality information. We validate this Self-Labeling Improvement Method (SLIM) on the Job Shop Scheduling (JSP), complex combinatorial problem that is receiving much attention from the neural combinatorial community. We propose a generative model based on the well-known Pointer Network and train it with SLIM. Experiments on popular benchmarks demonstrate the potential of this approach as the resulting models outperform constructive heuristics and state-of-the-ar learning proposals for the JSP. Lastly, we prove the robustness of SLIM to various parameters and its generality by applying it to the Traveling Salesman Problem.
Introduction
The Job Shop Problem (JSP) is a classic optimization problem with many practical applications in industry and academia [56]. At its core, the JSP entails scheduling set of jobs across multiple machines, where each job has to be processed on the machines following a specific order. The goal of this problem is generally to minimize the makespan: the time required complete all jobs [40].
Over the years, various approaches have been developed to tackle the JSP. common one adopting exact methods such as Mixed Integer Programming solvers (MIP). However, these methods often struggle to provide optimal or high-quality solutions on medium and large instances a reasonable timeframe [29]. As remedy, metaheuristics have been extensively investigated [36, 13, 24] and constitute an alternative to exact methods. Although sfatc-of-the-ar metaheuristics like [37] can rapidly provide quality solutions, typically within minutes, they are rather complex to implement and their results can be difficult to reproduce [6]. Therefore, due to their lower complexity, Priority Dispatching Rules (PDR) [40] frequently preferred in practical applications with tighter time constraints. The main issue of PDRs is their tendency to perform well some cases and poorly in others, primarily due to their rigid, hand-crafted prioritization schema based hardcoded rules [21].
Recent works have increasingly investigated Machine Learning (ML) to enhance or replace some of these approaches, primarily focusing on PDRs. MI--based approaches, specifically Reinforcement Learning (RL) ones, proved to deliver higher-quality solutions than classic PDRs at the cost of a small increase in execution time [33]. Despite the potential of RL [54, 25], training RL agents is complex task [45, 34], is sensitive to syper-parameterr [43], and has reproducibility issues [22].
Contrary, supervised learning is less affected by these issues but heavily relies on expensive anno- tations [32]. This is particularly problematic in combinatorial problems, where annotations in the
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

form of (near-) optimal information are generally produced with expensive exact solvers. To contrast labeling cost and improve generalization, semi-supervised [48] and self-supervised [32] are gaining popularity in many fields due to their ability to learn from unlabeled data. Despite this premise, little to no application of these paradigms can be found in the JSP and the combinatorial literature [5, 9].
Motivated by these observations, we introduce a novel self-supervised training strategy that is simpler than most RL algorithms, does not require the formulation of the Markov Decision Process [45], and relies only on model-generated information, thus removing the need for expensive annotations. Our proposal based on two weak assumptions: i) we suppose to be able to generate mulriple solutions for problem, a common characteristic of generative models [38]; and ii) we suppose it is possible to discriminate solutions based on the problem objective. When these assumptions are met, we train a model by generating multiple solutions and using the best one according to the problem objective as a pseudo-label [31]. This procedure draws on the concept of Maauud-i from semi-supervised learning, but it does not require any external and expansive annotation as in self-supervised learning. Hence, we refer to it as a SLIM: Sell-nabe Improvement Method.
We prove the effectiveness of SLIM primarily within the context of Job Shop, a challenging schedul- ing problem with many baseline algorithms [1, 36] and established benchmarks [44, 46, 16]. As recognized in other works [54, 39, 25], focusing on the JSP is crucial because its study helps address related variants, such as Dynamic JSP [51] and Flow Shop [42], while also establishing a concrete base for tackling more complicated scheduling problems like Flexible JSP [53].
Similar PDRs, cast the generation of solutions as a sequence of decisions, where at each decision one job operation is scheduled in the solution under construction. This is achieved with a generative model inspired by the Pointer Network [50], well-known architecture for dealing with sequences of decisions in combinatorial problems [5]. We train our model on random instances of different sizes by generating multiple parallel solutions and using the one with the minimum makespan to update the model. This training strategy produces models outperforming state-of-the-art learning proposals and other conventional JSP algorithms on popular benchmark sets. Furthermore, our methodology demonstrates robustmess and effectiveness across various training regimes. including a brief analysis on the Traveling Salesman Problem emphasize the broader applicability of SLIM beyond scheduling. In summary, the contributions of this work are:
Our key contribution is the introduction of SLIM, novel self-labeling improvement method for training generative models. Thanks its minimal assumptions, SLIM can be easily applied as-is to other combinatorial problems.
Additionally, we present a generative encoder-decoder architecture capable of generating high- quality solutions for JSP instances in matter of seconds.
The remainder of this work is organized as follows:
Sec. 2 reviews related ML works; Sec. 3 formalizes the JSP; Sec. 4 introduces our generative model and SLIM; Sec. 5 compares our approach with others; Sec. 6 studies additional aspects of our proposal; and Secs. 7 and 8 close with general considerations, some limitations, and potential future directions.
2
Related Works
ML approaches have been recently investigated to address issues of traditional JSP methodologies.
Motivated by the success of supervised learning, various studies have employed exact methods to generate optimality information for synthetic JSP instances, enabling the learning of valuable scheduling patterns. For example, [26] used imitation learning [5] to derive superior dispatching rules from optimal solutions, highlighting the limitations of learning solely from optimal solutions. [28] proposed a joint utilization of optimal solutions and Lagrangian terms during training to better capture JSP constraints. Whereas, in [14], the authors trained a Recurrent Neural Network (RNN) to predict the quality of machine permutations generated during training with MIP for guiding a metaheuristic. Despite their quality, these proposals are limited by their dependence on costly optimality information.
To avoid the need for optimality, other works have turned to reinforcement learning. The advantage of RL lies in its independence from costly optimal information, requiring only the effective formula- tion of the Markov Decision Process [45]. Several works focused on creating better neural PDRs, showcasing the effectiveness of policy-based methods [54, 39, 25, 11]. All these methods adopted

---

Proximal Policy Optimization algorithm [43] and proposed different architectures or training varia- tions. For instance, [54, 39] adopted Graph Neural Networks (GNN), [11] proposed a rather complex Transformer [49]. while [25] used RNNs and curriculum learning [58]. Differently, [20] presented a Double Deep Q-Network approach, proving the applicability of value-based methods.
Other works employed RL to enhance other algorithmic approaches. In [12], an iterative RL-based approach was proposed to rewrite regions of JSP solutions selected by learned policy. Whereas [17] utilized a Deep Q-learning approach to control three points of interventions within metaheuristics, and [55] recently presented an RL-guided improvement heuristic. Differently, [47] presented a hybrid imitation learning and policy gradient approach coupled with Constraint Programming (CP) for outperforming PDRs and CP solver.
3 Job Shop Scheduling
In the Job Shop Problem, we are given a set of jobs J = Jnh.. a set of machines M
comprises sequence of m, - 1) C O indicating the order in which the job must be performed on machines, where 1 = 1 + Eí=1 my is the index of its first operation (e.g.. 4 = for Jn and /2 = 3 for J2 in Fig. 1). An operation i E O has to be performed on machine M4 E .M for an uninterrupted amount of time Ti IRz- Additionally, machines can handle one operation at a time. The objective of the JSP is to provide an order to operations on each machine, such that the precedences within operations are respected and the time required to complete all jobs (makespan) is minimized. Formally, we indicate with π a JSP solution comprising a permutation of operations for each machine and use (T) to identify the completion time of operation E O in n.
; and a set of operations O = {1, .l. 0). Each job
my consecutive operations O, = (4,, (ly.....4, ....,,
A JSP instance can be represented with a disjunctive graph G = (V, A, E) [3], where: V contains one vertex for each operation E O: A is the set of directed arcs connecting consecutive operations of jobs reflecting the order in which operations must be performed: E is the set of disjunctive (undirected) edges connecting operations to perform on the same machines. When the JSP is represented disjunctive graph G, finding a solution means providing a direction to all the edges in E, such that the resulting graph is directed and acyelic (all precedences are respected). As in related works [54, 39], augment the disjunctive graph by associating to each vertex a set of 15 features I; E R describing information about operation i O. For lack of space, we present these features in App. A.
3.1 Constructing Feasible Job Shop Solutions
Feasible JSP solutions can be constructed step-by-step as sequence of decisions, a common approach adopted by PDRs [40] and RL algorithms [54, 25]. The con- struction of solutions can be visualized using branch- decision tree, shown the bottom of Fig. Each path from the root node (R) to leaf node presents a partic- ular sequence of o = |O| decisions and leads to valid ISP solution, such as the one highlighted in gray. At every node in the tree, one uncompleted job needs to be selected, and its ready operation is scheduled in the solution being constructed. Due to the precedence con- straints and the partial solution Tht constructed up to decision t, there is at most one operation oft, j) E O2 that is ready to be scheduled for any job J. Thus, by selecting a job j. we uniquely identify an operation o(t, j) that will be scheduled by appending it to the partial permutation of its machine. Notice that once a job is completed, it cannot be selected again, and such a situation is identified with a cross in Fig. 1.
Instance G
Solution
J
/a
Ja
Solve
h
2
42
5
12
11
1
3
2
2
3
3 Feastble soluctons
Figure The sequences of decisions for con- structing solutions in a JSP instance with two jobs (J1 and Jz) and two machines (identified in green and red). Best viewed in colors.
We emphasize that diverse paths can lead to the same solution, indicating certain solutions are more frequent than others. In some instances, near-optimal solutions may lie at the end of unlikely and hardly discernible paths, making their construction more challenging. This could explain why PDRs,
3

---

Table I: The features of context vector cj E IR that describes the status of a job within a partial solution Tet-
Recall that j(t, is the ready operation of job j at step Mo(s. its machine, and o(t, - its predecessor.
ID
Description
Rationsle
1
(( minus the completion time of machine Patt. 2)-
idle of job j scheclueed next machine () at time Negative if the joh could have started earlier.
2
Con.3) ((72))) divided by the makespan of mic--
How close job is to the makespan of the partial solution How early/late job completes wird. the avenge among all jobs in
3 Cott.)- ((fee))
((ffe)) minus the avernge completion time of all jobs.
The difference between Cict.p- g-1 (Tee)) and the 1st znd, and 3rd quartile computed among completion time all jobs.
Describe the relative completion of w.r.t other jobs. These features complement that with
The completion time of machine P)(t..) divided by the makespan of the partial solution
How close the completion time of machine Pot..)) is to the makespan of the partial solution dice-
7
The completion time of machine Potr, ji minus the average pletion of all machines Rice-
How early/lute machine Potr completes wir.. the average among machines in sice.
9. The difference between the completion of Port..) and the 1*,
Describe the relative completion time of machine Pult, w.C.L. all the other machines. These features complement with =D=8.
2nd,, and 3r quartile among the completion time all machines.
which rely on rigid, predefined rules, sometimes struggle to generate quality solutions, whereas neural algorithms able to leverage instance- and solution-widh features may perform better.
4 Methodology: Generative Model & Self-Labeling
As described in Sec. 3.1, we tackle the JSP as a sequence of decisions. Thus, we propose a generative model inspired by the Pointer Network [50] (a well-known encoder-decoder architecture generate sequences of decisions) whose goal is to select the right job at each decision step f. Formally, our model learns function fo(-), parametrized by 0, that estimates the probability po (G) of solution r being of high-quality, expressed as a product of probabilities:
[0|
pa pa
So(e TTe, G), 1=1
II
(1)
where fo(y: T<t. G) gives the probability of selecting job ye E JJ for creating æ,, conditioned on the instance G and the partial solution R<; constructed up to step By accurately learning fo(-). the model can construct high-quality solutions autoregressively. The following sections present the proposed encoder-decoder architecture and the self-labeling strategy to train this generative model.
4.1 The Generative Encoder-Decoder Architecture
Overview. Our model processes JSP instances represented as a disjunctive graph G and produces single deterministic multiple randomized solutions depending on the adopted construction strategy. The encoder operates at the instance level, creating embedded representations for all the operations in O with a single forward computation of G (hence, autoregression). Whereas the decoder operates at the solution level (job and machine level), using the embeddings of ready operations and the partial solution हh to produce a probability of selecting each job step Recall that after selecting a job j. its ready operation ott, j) is scheduled in T<e to produce the partial solution for step t + 1.
Encoder. It captures instance-wide wide relationships into the embeddings of operations, providing the decoder with a high-level view of the instance characteristics. The encoder can be embodied by any architecture, like Feedforward Neural Network (FNN), that transforms raw operation features I; E IR55 (see App. A for the features) into embeddings e; E R As in related works [54, 39], we also encode the relationships among operations present in the disjunctive graph. We thus equip the encoder with Graph Neural Networks [52], allowing the embeddings to incorporate topological information of G. In our encoder, we stack two Graph Attention Network (GAT) layers [8] as follows:
e, = [z; a (GATz [z, (GAT, (z,, G))], G)),
where a is the ReLU non-linearity and || stands for the concatenation operation.
Decoder. It produces at any step f the probability of selecting each job from the embeddings e; and solution-related features. The encoder is logically divided into two distinct components:
Memory Network: generates a state 8j E Rd for each job j E from the partial solution т<(- This is achieved by first extracting from Tet context vector сj (similarly to [27J), which contains

---

eleven hand-crafted features providing useful cues about the status of job j. We refer to Tab. 1 for the definition and meaning of these features. Then, these vectors are fed into Multi-Heas Attention layer (MHA) [49] followed by a non-linear projection to produce jobs" states:
$j ReLU(((e W1
MHA(c; W1) W2),
BEJ
where W2 and W₂ are projection matrices. Note that we use the MHA to consider the context of all jobs when producing the state for a specific one, similarly to [1]].
Classifier Network: outputs the probability Pj of selecting a job j by combining the embedding G)(t. of its ready operation and the state $, produced by the memory network. To achieve this, we first concatenate the embeddings cot,.)) j) with the states sy and apply an FNN:
2j (N 3) ||,)))-
Then, these scores 2y E RR are transformed into softmax probabilities: P, = = / EdeJ et The final decision which job to select at is made using a sampling strategy, as explained next.
Sampling solutions. To generate solutions, we employ a probabilistic approach for deciding the job selected at any step. Specifically, randomly sample job j with a probability pj, produced at step t by our decoder. We also prevent the selection of completed jobs by setting their scores 23 -00 to force p, = 0 before sampling. Note how this probabilistic selection is autoregressive, meaning that sampling a job depends on Pj which is a function of Co(t.)) and 8y resulting from earlier decisions (see Eqs. 3 and 4). Various strategies exist for sampling from autoregressive models, including top-k [23], nucleus [23], and random sampling [4]. Preliminary experiments revealed that these strategies perform similarly, with average optimality gap variations within 0.2% on benchmark instances. However, top-k and nucleus sampling introduce brittle hyperparameters that can hinder training convergence if not managed carefully. Therefore, we adopt the simplest strategy for training and testing, which is random sampling: sampling job with probability Pj at random. Note however that the sampling strategy remains a flexible design choice, not inherently tied to our methodology.
4.2 SLIM: Self-Labeling Improvement Method
We propose a self-supervised training strategy that uses the model's output as a teaching signal, eliminating the need for optimality information or the formulation of Markov Decision Processes. Our strategy exploits two aspects: the capacity of generative models to construct multiple (parallel) solutions and the ability to discriminate solutions of combinatorial problems based on their objective values, such as the makespan in the JSP. With these two ingredients, we design a procedure that at each iteration generates multiple solutions and uses the best one as pseudo-label [31].
More in detail, for each training instance G, we randomly sample a set of 33 solutions from the generative model fo()). We do that by keeping /3 partial solutions in parallel and independently sample for each one the next job from the probabilities generated by the model. Once the solutions have been completely generated, we take the one with the minimum makespan ग and use it to compute the Self-Labeling loss (LsL). This loss minimizes the eross-entropy across all the steps as follows:
10
LSL(T) O
log folve Tee, G),
(5)
t=1
where Y/ E is the index of the job selected at the decision step while constructing the solution т.
The rationale behind this training schema is to collect knowledge about sequences of decisions leading to high-quality solutions and distill in the parameters 6 of the model. This is achieved by treating the rest-generated solution मे for an instance G as pseudo-label and maximizing its likelihood using Eq. 5. Similar to supervised learning, repeated exposure to various training instances enables the model to progressively refine its ability to solve combinatorial problems such as the JSP. Hence, we named this training strategy Self-Labeling Improvement Method (SIJM).
Relations with Existing Works
Although our strategy was developed independently, attentive readers may find resemblance with the Cross-Entropy Method (CEM), a stochastic and derivative-free optimization method [15]. Typically applied to optimize parametric models such as Bernoulli and Gaussian mixtures models [57], the
5

---

CEM relies on maximum likelihood approach to either estimate a random variable or optimize the objective function of problem [7]. According to Algorithm 2.2 in [7], the CEM independently samples N = 8 solutions, selects a subset based on the problem's 's objective ( ((v) in our case), and updates the parameters of the model.
While the CEM independently tackles instances by optimizing a separate model for each, SLIM trains a single model on multiple instances to globally Iearn how solve a combinatorial problem. Moreover, we adopt a more complex parametric model instead of mixture models, always select a single solution to update the model, and resort to the gradient descent for updating parameters A. Notably, our strategy also differs from CEM applications to basee RL, e.g., [57], as we do not rely on rewards in Eq. In summary, our strategy shares the idea of sampling and selecting with the CEM but globally operates as a supervised learning paradigm once the target solution is identified.
Other self-labeling approaches can be found, e.g., in [10, 2], where the former uses K-Means to generate pseudo-labels, and the latter assigns labels to equally partition data with an optimal transportation problem. As highlighted in [2], these approaches may incur in degenerate solutions that trivially minimize Eq. 5, such as producing the same solution despite the input instance in our case. We remark that SLIM avoids such degenerate solutions by jointly using a probabilistic generation process and the objective value (makespan) of solutions to select the best pseudo-label т.
5
Results
This section outlines the implementation details, introduces the selected competitors, and presents the key results. All the experiments were performed on an Ubuntu 22.04 machine equipped with an Intel Core 19-11900K and an NVIDIA GeForce RTX 3090 GPU having 24 GB of memory.
5.1 Experimental Setup
Dataset & Benchmarks. To train our model, we created a dataset of 30 000 instances as in [46] by
randomly generating 5000 instances per shape (n m) in the set: {10 x 10, 15 x 10, 15 x 15, 20 x 10, 20 x 15, 20 x 20). While our training strategy does not strictly require fixed dataset, we prefer using it to enhance reproducibility. For testing purposes, we adopted two challenging and popular benchmark sets to evaluate our model and favor cross-comparison. The first set is from Taillard [46], containing 80 instances of medium-large shapes (10 instances per shape). The second set is the Demirkol's 's one [16], containing 80 instances (10 per shape) which proved particularly challenging in related works [54, 25J. We additionally consider the smaller and easier Lawrence's 's benchmark [44] and extremely larger instances in Apps. C and E, respectively.
Metric. We assess performance on each benchmark instance using the Percentage Gap: PG 100 - (Calg. Cus 1), where Caty is the makespan produced by an algorithm and Cus is either the optimal or best-known makespan for the instance. Lower PG values indicate better results, as they reflect solutions with an objective value closer to the optimal or best-known makespan.
Architecture. In all our experiments, we configure the model of Sec. 4.1 in the same way. Our encoder consists of two GAT layers [8]. both with 3 attention heads and leaky slope at 0.15. In GAT,, we set the size of each head 64 and concatenate their outputs; while in GAT,, we increase the head's size to 128 and average their output to produce e, E R143 (h- 15 + 128). Inside the decoder's 's memory network, the MHA layer follows [49] but concatenates the output of 3 heads with 64 neurons each, while W1 E R 11x1192 and W₂ E R 1919xx12 128 use 192 and 128 neurons, respectively. Thus, the job states 8y E Id have size d 128. Finally, the classifier FNN features a dense layer with 128 neurons activated through the LeaL (slope = 0.15) and a final linear with 1 neuron.
Training. We train this generative model with SLIM (see Sec. 4.2) on our dataset for 20 epochs, utilizing the Adam optimizer [19] with a constant learning rate of 0.0002. In each training step, we accumulate gradients over a batch of size 16, meaning that we update the model parameters 0 after processing 16 instances. During training and validation, we fix the number of sampled solutions /3 to 256 and save the parameters producing the lower average makespan on hold-out set comprising 100 random instances per shape included in our dataset. Training in this way takes approximately 120 hours, with each epoch lasting around 6 hours.
Our code is available at: https: : ////t//ttta www./nndreaaoossnniiiioc Se Lngbeiiggoohhoh

---

Table 2: The average PG of the algorithms on the henchmarks, In each row, we highlight in blue (bold) the hest constructive (non-constructivv) gap. Shapes marked with * are larger than those seen in training by our GM.
Greedy Constructiies
Mubipie (Sundomiced) Constructives
Nov-roottuuciie
PDRs
RL
PDRs
RLa-
Our
Approucher
Shape
L2D
MWR
MOR
[SBR]
CL
(M GMass
L25
NLSA
L25aa
MIP
CP
15 15
26.1
19.1
20.4
14.4
26.0
14.3
13.8
13.5
13.5
12.5
11.6
17.1
9.0
7.2
6.5
9.3
7.7
6.2
0.1
0.1
Toiltned' theh-hmark
15
32.3
23.3
24.9
18.9
30.0
16.5
15.0
18.4
17.2
16.4
10.9
23.7
10.6
9.3
5.5
11.6
12.2
8.3
3.2
0.2
20
31.6
15.6
10.0
9.9
11.5
0.7
30 15"
35.0
24.1
22.9
21.1
33.0
18.5
17.1
23.2
19.0
17.3
15.1
24.4
14.0
11.0
10.6
14.7
14.1
9.0
10.7
2.1
90 20'"
13.4
24.8
26.8
22.6
33.6
21.5
18.5
23.6
19.9
20.4
17.7
28.4
16.1
134
12.7
17.5
16.4
12.6
13.2
2.8
500 1.5"
24.0
16.4
17.5
15.99
22.4
12.2
10.1
14.1
13.5
13.5
13.2
17.1
9.3
5.5
4.9
11.0
11.0
4.6
12.2
3.0
50 20"
25.6
17.8
16.8
20.3
26.5
13.2
11.6
17.6
14.6
14.0
20.8
20.4
9.9
8,4
7.6
13.0
11.2
6.5
13.6
2.8
100
13.6
7.0
2.3
5.9
11.0
3.9
Avg
27.1
14.9
15.0
14.5
10.5]
7.8
11.3
7.4
2.0
20 x0 15
27.9
27.5
30.7
21.2
39.0
18.0
17.2
22.3
23.8
12.5
29.3
19.41
12.0
11.3
5.3
1.8
Denirkal benchhaakk
37.7
18.9
13.5
12.3
1.9
301 13"
31.2
31.9
36.9
26.5
42.0
21.8
20.7
26.8
30.7
18.2
16.5
14,A
14.0
14.2
2.5
30 201"
34.4
32.1
32.3
28.5
39.7
25.7
23.3
26.1
28.3
17.3
33.6
20.2
17.1
15.8
16.7
4.4
60 15"
25.3
27.0
35.8
21.7
35.6
17.5
17.9
23.2
30.2
14.4
31.5
17.6
11.7
10.9
16.3
4.1
40 20"
33.8
32.3
35,9
29.4
79.6
22.2
24.5
27.6
31.8
20.3
35.8
25.6
16.0
14.8
22.5
4.6
50 15"
3.8
50 20"
30.0
30.3
36.8
39.5
26.8
32.7
36.1
15.2
15.8
15.0
4.8
Avg
30.0
29.4
33.7
26.0
38.7
20.3
20.4
24.5
28.8
17.2
32.5
19.0
14,0
13.1
14.6 3.5
Competitors. We compare the effectiveness of our methodology against various types of conventional algorithms and ML competitors reviewed in Sec. 2. We divide competitors follows:
Greedy Constructives generate a single solution for any input instance. We consider two corner- stone ML works for the JSP: the actor-critic (L.2D) of [54] and the recent curriculum approach (CL) of [25]. We also coded the INSertion Algorithm (INSA) of [36] and three standard dispatch- ing rules that prioritize jobs based on the Shortest Processing Time (SPT); Most Work Remaining (MWR); and Most Operation Remaining (MOR).
Multiple (Randomized) Constructives generate multiple solutions for an instance by introducing a controlled randomization in the selection process, simple technique for enhancing constructive algorithms [50, 25]. We consider randomized results of CL and I.2D. As only greedy results were disclosed for L2D, used the open-source code sample randomized solutions as described in Sec. 4.1. We also consider the three dispatching rules above, randomized by arbitrarily scheduling an operation among the three with higher priority, and the Shifting Bottleneck Heuristic (SBH) [1] that creates multiple solutions while optimizing. All these approaches were seeded with 12345, generate 3 = 128 solutions, and return the one with minimum makespan.
Non-construetive Approaches do not rely on a pure constructive strategy for creating JSP solutions. We include two RL-enhanced metaheuristics: the NLS, A in [18] (200 iterations) and the recent 1.2S proposal of [55] visiting 500 (0.2S500) and 5000 (1.2Saa) solutions. We also consider two state-of-the-an solvers for the JSP: Gurobi 9.5 (MIP) solving the disjunctive formulation of [29] and the CP-Sat (CP) of Google OR tools 9.8, both executing with time limit of 3600 seconds.
For lack of space, we compare our methodology against other learning proposals in App. B.
5.2 Performance on Benchmarks
This section evaluates the performance of our generative Graph Model (GM), configured and trained with SLIM as explained in Sec. 5.1. When contrasted with greedy approaches, our GM generates a single solution by picking the job with the highest probability. In the other comparisons, we randomly sample 128 (GM128) and 512 (GM512) solutions as explained in Sec. 4.1. Note that we coded our GM, PDRs, INSA, SBH, MIP, and CP; while we reported results from original papers of all the ML competitors but L2D, for which we used the open-source code to generate randomized solutions.
Tab. 2 presents the comparison of algorithms on Taillard's and Demirkol's benchmarks, each arranged in a distinct horizontal section. The table is vertically divided into Greedy Constructive, Multiple (Randomized) Constructive, and Non-constructive Approaches; with the results of algorithms catego- rized accordingly. Each row reports the average PG (the lower the better) on a specific instance shape while the last row (Avg) reports the average gap across all instances, regardless of their shapes.
This table shows that our GM and CL produce lower gaps than PDRs, INSA, and SBH in both the greedy and randomized cases, proving the superiority of neural constructive approaches. Surprisingly,
7

---

RL
Self-Labeling
L2D
Benchmark
CLuct
CL
CLst
FNNs.
GM
35
PPO
Ayerage tollbard
SUM-32
Taillard
17.3
10.5
10.7
9.5
8.4
SUM-64
Demirkol
19.0
20.9
14.9
14.0
25
Table 3:
The average gaps when sampling 128 so-
lutions from architectures trained without and with self sall-lab.ling. CLucI is the model obtained in [25] by training with reward-to-ge to-go on random instance shapes curriculum learning) and CL simi- larly obtained by applying curriculum learning.
1000
2000
3000
4000
5000
Training Stop
Figure 2: GM validation curves when trained with PPO and our SLIM in the same training setting of [54].
INSA and PDRs outperform L2D. This is likely related to how PDRs were coded [54], where ours align with those in [25]. Focusing our GM, we observe that it consistently archives lower gaps than all the greedy approaches and, when applied in a randomized manner (GM128), it outperforms all the randomized constructives. Notably, the GM generalizes well to instance shapes larger than training ones (marked with in Tab. 2), as its gaps do not progressively increase on such shapes.
Our GM is also competitive when compared with non-constructive approaches. The GM512 largely outperforms the NL.SA and 1.2S metaheuristics, and roughly align with 1.2S5t visiting 5000 solutions. On shapes larger than 20 x 20, the GM512 remarkably achieves lower gaps with just few seconds of computations than a MIP executing for 3600 sec. Therefore, we conclude that our methodology, encompassing the proposed GM and SLIM, is effective in solving the JSP.
As already observed in [25, 55]. our GM and other neural constructive approaches are generally outperformed by CP and state-of ahe-ttrrrt metaheuristics, e.g.. [36]. Although the performance gap is steadily narrowing, the higher complexity of CP solvers renders them more powerful, albeit the cost of longer execution time (often dozens of minutes). Therefore, neural constructive approaches may be preferable whenever quality solution must provided in a few minutes.
We refer the reader to Apps. D and E for statistical considerations and a comparison between our GM and CP on extremely large instances, respectively.
6 A Closer Look at SLIM
This section studies additional aspects of our proposed methodology. For these evaluations, we adopt the same setting described in Sec. 5.1 and explicitly indicate the varied aspects and parameters.
6.1 Self-Labeling other Architectures
To demonstrate the generality of our self-labeling improvement method beyond the proposed Graph Model (GM), we use it to train other architectures described in Sec. 5.1. Specifically, train the model proposed in [25] (CLst.) and a variation of our GM (named FNNst), where we replaced the Graph Attention and Multi-Head Attention layers with linear projections (ReLU activated) by maintaining the same hidden dimensionalities. Tab. reports the average gap of CLsL. FNNsL. and GM on each benchmark. As baselines for comparison, also include the average gap of CL and CLuci. reported in [25], the latter being trained without curriculum learning similarly to our setting.
Tab. 3 shows that CLsL nearly matches the performance of CL even without curriculum learning. Note that we intentionally avoided applying curriculum learning to eliminate potential biases when demonstrating the contribution of our self-labeling strategy. Furthermore, FNNsL and GM outperform CL, with GM achieving the best overall performance. Therefore, we conclude that SLIM can successfully train dell-designed architectures for the JSP.
observe that both
6.2 Comparison with Proximal Policy Optimization
The previous Sec. 6.1 proved the quality our GM when trained with SLIM. As Proximal Policy Optimization (PPO) is extensively used to train neural algorithms for scheduling problems (see Sec. 2). we contrast the GM's performance when trained with PPO and our self-laheling strategy (SLIM-8 with 3 E {32, 64, 128)). For this evaluation, we adopt the same hyper- parameersss of [54] for both

---

C-CL
o. MIP
+--322
P=64
P--188
--P-256
--0l
MiP
++8-32
-
+-88-188
-+-8--266
-B--12
Percentage Gap (PG)
20
20
10
15
11.22
.0.07
22.31
14.2
16.9
Percentage
20
15
9.10
10
13.35
$2.45
10.0
10.31
14.23
10.91
12.00
6.52
7.79
6.52
7.79
19x15
20415
20x20
20x15
30x20
4041 40620
50:15 50x20
100x20
15x15
20x15
20x20
20x15
40.15 40x20 Instance shape
30x20
50x15 50x20 100K20
Instance shape
Figure 3: The GM performance when trained by sam- Figure 4: The GM performance (trained as in Sec. 5.1) pling varying number of solutions 3. For each shape, for varying numbers of sampled solutions 3 at test time. report the average PG on instances of both bench- For each shape, we report the average PG instances of both benchmarks.
marks by sampling 512 solutions during testing.
PPO and SLIM by training on 40 000 random instances of shape 30 20 (same training of L2D [54]). We only double the batch size to 8 to reduce training noise. Fig. 2 reports the validation curves obtained by testing the GM on Taillard's benchmark every 100 training steps. We test by sampling 128 solutions and we also include the randomized results of L2D (dashed line) as a baseline for comparisons. From Fig. 2, we observe that training with our self-labeling improvement method results in faster convergence and produces better final models.
We justify this by hypothesizing that the reward received from partial solutions (makespan increments) may not always provide reliable guidance on how to construct the best final solution. While con- structing a solution, the critical path may change with implications on past rewards. Our self-labeling strategy does not rely on partial rewards and may avoid such a source of additional "noise". Note that this is only an intuition, proving would require deeper analysis, which we refer to in future works. Finally, we stress that we do not claim SLIM is superior to PPO. Instead, we believe it offers an alternative that provides fresh perspective and potential for integration with existing RL algorithms to advance the neural combinatorial optimization field.
6.3 The Effect of / on Training
As our self-labeling improvement method is based on sampling, we assess the impact of sampling different number of solutions B while training. We retrain new GM described in Sec. 5.1 with a number of solutions 3 E {32, 64, 128, 256), where we stop at 256 as the memory usage with larger values becomes impractical. We test the resulting models by sampling 512 solutions on all the instances of both benchmarks for broader assessment. Fig. 3 reports the average PG (the lower the better) of the trained GM (colored markers) on each shape. To ease comparisons, we also include the results of CL (dashed line) the second-best ML proposal in Tab. 2 - and the MIP (dotted line).
that training by sampling more solutions slightly improves the model's performance, as outlined by lower PGs for increasing 3. We also observe that such improvement is less marked on shapes seen in training, such in 15 x 15, 20 15, and 20 20 shapes, and more marked on others. This suggests that training by sampling more solutions results in better generalization, although is more memory-de -emanddn.. However, the GM's trends observed in Tab. 2 remain consistent with smaller 3, proving the robustness SLIM to variations in the number of sampled solutions 33.
Overall,
6.4 The Effect of 33 on Testing
We also assess how the number of sampled solutions / impacts the GM performance at test time. To evaluate such an impact, we plot in Fig. 4 the average PG on different shapes for varying E {32, 64, 128, 256 512}. For this analysis, we use the GM trained by sampling 256 solutions, the one of Tab. 2. As in Sec. 6.3, we also report the results of CL and MIP to ease the comparison.
Despite the reduced number of solutions, the GM remains a better alternative than CL the best RL proposal and still outperforms the MIP on medium and large instances. Not surprisingly, by sampling more solutions the GM performance keeps improving at the cost of increased execution times. Although we verified that sampling more than 512 solutions further improves results (see bottom of App. F), we decided to stop at B = 512 as good trade-off between performance and time. We refer the reader to App. F for other timing considerations.

---

6.5 Self-Labeling the Traveling Salesman Problem
Finally, we provide a brief analysis to demon- strate the broader applicability of our self- labeling improvement method other combi- natorial problems. Thus, we evaluate SLIM on the Traveling Salesman Problem (TSP), cor- nerstone in neural combinatorial optimization research [5, 50, 35]. by using it to train the well- known Attention Model [27] on TSP instances with 20 nodes. To assess SLIM's performance, we compare it against the established Policy Op- timization with Multiple Optima (POMO) ap- proach [30]. We train the Attention Model with both SLIM and POMO, using the same hyper- parameters and sampling strategy outlined in [30]. Training is carried out over 100,000 steps (equivalent to epoch in [30] by generating batches of 32 instances at each step.
35
POMO
Avarage TSPLIB Gap
POMO2O
25
20-
Training Step
Figure 5: Validation curves obtained by training with SLIM and POMO on random TSP instances with 20 nodes. POMO20 is the best model produced in [30]. trained instances with 20 nodes.
Fig. 5 presents the validation curves of SLIM and POMO obtained by testing the model every 100 steps on small instances (with up to 100 nodes) from the TSPLIB [41]. The results are reported in terms of the average optimality gap and,
baseline for comparison, the best model in [30] (POMO20) trained for hundreds of epochs. As shown, SLIM achieves faster convergence than POMO and produces a model comparable to POMO20 after just one epoch, thereby demonstrating that SLIM can be effective in other combinatorial problems.
include the performance of
Limitations
Despite the proven effectiveness of SLIM, it is important to note that only one of the sampled solutions per training instance used to update the model. This approach may be sub-optimal from an efficiency standpoint. Therefore, we see sigmificant potential in hybridizing our self-labeling strategy with existing (RL) methods to mitigate this inefficiency. Moreover, sampling multiple solutions during training requires substantial memory, which can limit batch sizes. Although we have shown that SLIM remains effective with a small number of sampled solutions (see Sec. 6.3), increasing their number accelerates training convergence and improves the resulting model. Consequently, developing new strategies that can sample sigher-quality solutions without generating numerous random ones promising future direction. Such advancements could reduce memory usage and further enhance our methodology as well as others the literature.
8 Conclusions
The key contribution of this work is the introduction of SLIM, a novel Self-Labeling Improvement Method to train generative models for the JSP and other combinatorial problems. Additionally, an efficient encoder-decoder architecture is presented to rapidly generate parallel solutions for the JSP. Despite its simplicity, learning algorithms for the JSP, even surpassing a powerful MIP solver. However, as a constructive approach, it still lags behind state-of-the-art approaches like constraint programming solvers, which nevertheless require more time. We also proved the robustness of SLIM across various parameters and architectures, and its generality by applying it successfully the Traveling Salesman Problem.
methodology significantly outperformed many constructive and
More broadly, self-labeling might be valuable training strategy as it eliminates the need for optimality information the precise formulation of Markov Decision Process. For instance, given a designed generative model (i.e., a constructive algorithm whose decisions are taken by a neural network), this strategy be applied as-is combinatorial problems with unconventional objectives or a combination of objective functions. In contrast, RL approaches require the careful definition of a meaningful reward function, which often complex and challenging task.
In future, we intend to apply our methodology to other shop scheduling and combinatorial problems as well as explore combinations of our self-supervised strategy with other existing learning approaches.
10

---

References
[1] Joseph Adams, Egon Balas, and Daniel Zawack. The Shifting Bottleneck Procedure for Job Shop Scheduling. Management Science, 34, 1988.
[2] Yuki M. Asano, Christian Rupprecht, and Andrea Vedaldi. Self-labelling via simultaneous clustering and representation learning. In International Conference on Learning Representations, 2020.
[3] Egon Balas, Machine sequencing via disjunctive graphs: an implicit enumeration algorithm. Operations Research, 17, 1969.
[4] Irwan Bello, Hieu Pham, Quoe V Le, Mohammad Norouzi, and Samy Bengio. Neural com- binatorial optimization with reinforcement learning. International Conference on Learning Representations, 2017.
[5] Yoshua Bengio, Andrea Lodi, and Antoine Prouvost. Machine learning for combinatorial optimization: A methodological tour d' d'horizon. European Journal of Operational Research, 290, 2021.
[6] Christian Blum and Andrea Roli. Metaheuristics in combinatorial optimization: Overview and conceptual comparison. ACM computing surveys (CSUR), 35, 2003.
[7] Zdravko Botev, Dirk P. Kroese, Reuven Y. Rubinstein, and Pierre L E'Euuyer. The Cross-Entropy Method for Optimization. In Handbbook of Statistics, volume 31. Elsevier, 2013.
[8] Shaked Brody, Uri Alon, and Eran Yahav. How Attentive are Graph Attention Networks? In International Conference on Learning Representations, 2022.
[9] Quentin Cappart, Didier Chételat, Elias B. Khalil, Andrea Lodi, Christopher Morris, and Petar Veličković. Combinatorial Optimization and Reasoning with Graph Neural Networks. In Proceedings of the International Joint Conference on Artificial Intelligence, 2021.
[10] Mathilde Caron, Piotr Bojanowski, Armand Joulin, and Matthijs Douze. Deep clustering for unsupervised learning of visual features. In Proceedings of the European Conference on Computer Vision, 2018.
[11] Ruiqi Chen, Wenxin Li, and Hongbing Yang. A Deep Reinforcement Learning Framework Based on an Attention Mechanism and Disjunctive Graph Embedding for the Job-Shop Schedul- ing Problem. IEEE Transactions on Industrial Informatics, 19, 2023.
[12] Xinyun Chen and Yuandong Tian. Learning to Perform Local Rewriting for Combinatorial Optimization. Advances in Neural Information Processing Systems, 32, 2019.
[13] Runwei Cheng, Mitsuo Gen, and Yasuhiro Tsujimura. A tutorial survey of job-shop scheduling problems using genetic algorithms, part II: hybrid genetic search strategies. Computers & Industrial Engineering, 36, 1999.
[14] Andrea Corsini, Simone Calderara, and Mauro Dell' Amico. Learning the Quality of Machine Permutations in Job Shop Scheduling. IEEE Access, 10, 2022.
[15] Pieter-Tjerk De Boer, Dirk P Kroese, Shie Mannor, and Reuven Y Rubinstein. A tutorial on the cross-entropy method. Annals of operations research, 134, 2005.
[16] Ebru Demirkol, Sanjay Mehta, and Reha Uzsoy. Benchmarks for shop scheduling problems. European Journal of Operational Research, 109, 1998.
[17] Jonas K Falkner, Daniela Thyssens, Ahmad Bdeir, and Lars Schmidt-Thiemas Learning to Control Local Search for Combinatorial Optimization. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases. Springer, 2022.
[18] Jonas K. Falkner, Daniela Thyssens, Ahmad Bdeir, and Lars Schmidt-Thiee Learning to control local search for combinatorial optimization. Machine Learning and Knowledge Discovery in Databases, 2023.

---

[19] Ian Goodfellow, Yoshua Bengio, and Aaron Courville. Deep Learning. MIT Press, 2016.
[20] Bao-An Han and Jian-Jun Yang. Research Adaptive Job Shop Scheduling Problems Based on Dueling Double DQN. IEEE Access, 8, 2020.
[21] Reinhard Haupt. A survey of priority rule-based scheduling. Operations Research Spektrum, 11, 1989.
[22] Peter Henderson, Riashat Islam, Philip Bachman, Joelle Pineau, Doina Precup, and David Meger. Deep Reinforcement Learning That Matters. Proceedings of the AAAI Conference on Artificial Intelligence, 32, 2018.
[23] Ari Holtzman, Jan Buys, Li Du, Maxwell Forbes, and Yejin Choi. The Curious Case of Neural Text Degeneration. In International Conference Learning Representations, 2020.
[24] Kuo-Ling Huang and Ching-Jong Liao. Ant colony optimization combined with taboo search for the job shop scheduling problem. Computers & Operations Research, 35, 2008.
[25] Zangir Iklassov, Dmitrii Medvedev, Ruben Solozabal Ochoa de Retana, and Martin Takac. On the Study of Curriculum Learning for Inferring Dispatching Policies on the Job Shop Scheduling. In Proceedings of the International Joint Conference on Artificial Intelligence, 2023.
[26] Helga Ingimundardottir and Thomas Philip Runarsson. Discovering Dispatching Rules from Data Using Imitation Learning: A Case Study for the Job-Shop Problem. Journal of Scheduling, 21, 2018.
[27] Wouter Kool, Herke Van Hoof, and Max Welling. Attention, learn solve routing problems! In International Conference on Learning Representations, 2018
(28) James Kotary, Ferdinando Fioretto, and Pascal Van Hentenryck. Fast approximations for job shop scheduling: A lagrangian dual deep learning method. In Proceedings of the AAAI Conference Artificial Intelligence, volume 36, 2022.
[29] Wen- Yang Ku and J. Christopher Beck. Mixed Integer Programming models for job shop scheduling: A computational analysis. Computers & Operations Research, 73, 2016.
[30] Yeong-Dae Kwon, Jinho Choo, Byoungjip Kim, Iijoo Yoon, Youngjune Gwon, and Seungjai Min. Pomo: Policy optimization with multiple optima for reinforcement learning. Advances in Neural Information Processing Systems, 33, 2020.
[31] Dong-Hyun Lee et al. Pseudo-label: The simple and efficient semi-supervised learning method for deep neural networks. In Workshop on challenges in representation learning, ICML, volume 3, 2013.
[32] Xiao Liu, Fanjin Zhang, Zhenyu Hou, Li Mian, Zhaoyu Wang, Jing Zhang, and Jie Tang. Self-Supervised Learning: Generative or Contrastive. IEEE Transactions Knowledge and Data Engineering, 35, 2023.
[33] Nina Mazyavkina, Sergey Sviridov, Sergei Ivanov, and Evgeny Burnaev. Reinforcement learning for combinatorial optimization: A survey. Computers & Operations Research, 134, 2021.
[34] Volodymyr Mnih, Adria Puigdomenech Badia, Mehdi Mirza, Alex Graves, Timothy Lilli- crap, Tim Harley, David Silver, and Koray Kavukcuoglu. Asynchronous methods for deep reinforcement learning. In International Conference on Machine Learning, 2016.
[35] Mohammadreza Nazari, Afshin Oroojlooy, Lawrence Snyder, and Martin Takác. Reinforcement learning for solving the vehicle routing problem. Advances in Neural Information Processing Systems, 31, 2018.
[36] Eugeniusz Nowicki and Czeslaw Smutnicki. A Fast Taboo Search Algorithm for the Job Shop Problem. Management Science, 42, 1996.
[37] Eugeniusz. Nowicki and Czeslaw Smutnicki. An Advanced Tabu Search Algorithm for the Job Shop Problem. Journal of Scheduling, 8, 2005.
12

---

[38] Achraf Oussidi and Azeddine Elhassouny. Deep generative models: Survey, In International Conference on Intelligent Systems and Computer Vision, 2018.
[39] Junyoung Park, Jaehyeong Chun, Sang Kim, Youngkook Kim, and Jinkyoo Park. Learning to schedule job-shop problems: representation and policy learning using graph neural network and reinforcement learning. International Journal of Production Research, 59, 2021.
[40] M.L. Pinedo. Scheduling: Theory, Algorithms, and Systems. SpringerL.ink: : Bücher. Springer
New York, 2012.
[41] Gerhard Reinelt. TSPLIB -A traveling salesman problem library. ORSA journal on computing.
3, 1991.
[42] Daniel Alejandro Rossit, Fernando Tohmé, and Mariano Frutos. The Son-Permutation Flow- Shop scheduling problem: A literature review. Omega, 77, 2018.
[43] John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint 177.v:1777 2017.
[44] Lawrence Stephen. Resource constrained project scheduling: an experimental investigation of heuristic scheduling techniques (Supplement). Graduate School of Industrial Administrationo, 1984.
[45] Richard Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press. 2018.
[46] Eric Taillard. Benchmarks for basic scheduling problems. European Journal of Operational Research, 64, 1993.
[47] Pierre Tassel, Martin Gebser, and Konstantin Schekotihin. An End-to-End Reinforcement Learning Approach for Job-Shop Scheduling Problems Based on Constraint Programming. Proceedings of the International Conference on Automated Planning and Scheduling, 33, 2023.
[48] Jesper Van Engelen and Holger H Hoos. A survey on semi-supervised learning. Machine learning, 109, 2020.
[49] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need, Advances in Neural Information Processing Systems, 30, 2017.
[50] Oriol Vinyals, Meire Fortunato, and Navdeep Jaitly. Pointer networks. Advances in Neural Information Processing Systems, 28, 2015.
[51] Libing Wang, Xin Hu, Yin Wang, Sujie Xu, Shijun Ma, Kexin Yang. Zhijun Liu, and Weidong Wang. Dynamic job-shop scheduling in smart manufacturing using deep reinforcement learning. Computer Networks, 190, 2021.
[52] Zonghan Wu. Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and Philip S. Yu. Comprehensive Survey on Graph Neural Networks. IEEE Transactions on Neural Networks and Learning Systems, 32, 2021.
[53] Jin Xie, Liang Gao, Kunkun Peng, Xinyu Li, and Haoran Li. Review on flexible job shop scheduling. IET collaborative intelligent manufacturing, 2019.
[54] 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. Advances in Neural Information Processing Systems, 33, 2020.
[55] Cong Zhang, Zhiguang Cao, Wen Song, Yaoxin Wu, and Jie Zhang. Deep Reinforcement Learning Guided Improvement Heuristic for Job Shop Scheduling. In International Conference on Learning Representations, 2024.
[56] Jian Zhang, Guofu Ding, Yisheng Zou, Shengfeng Qin, and Jianlin Fu. Review of job shop scheduling research and its new perspectives under Industry 4.0. Journal of Intelligent Manu- facturing, 30, 2019.
13

---

[57] Zichen Zhang, Jun Jin, Martin Jagersand, Jun Luo, and Dale Schuurmans. A Simple De- centralized Cross-Entropy Method. Advances in Neural Information Processing Systems, 35, 2022.
[58] Runlong Zhou, Yuandong Tian, Yi Wu, and Simon Shaolei Du. Understanding Curriculum Learning in Policy Optimization for Online Combinatorial Optimization. In NeurlPS Workshop: Optimization for Machine Learning, 2022.
14

---

Table 4: The features H; E R associated with a vertex E of the disjunctive graph that provide information about operation in the instance. Recall that T represents the processing time of operation i, and pi denotes the machine on which the operation is performed.
1D
Deseription
The processing time 7: of the operation.
The completion of job j up to Ld-t, To/ EvsO, T2.
The remainder of job j after Ei T/ Engo, ?b.
4-6
The 1 2nd and 3rd quartile among processing times of operations on oo.ob/ j.
7.9
The 1sf, 2nd and 3 quartile among processing times of operations on machine Ps.
10.12
The difference between and the 1 2nd,, and 3rd quartile among processing times of operations in job j.
13-15
The difference between and the 1 2ndd, and 3rd quartile among processing times operations on machine Ps-
Table 5: average greedy constructive approaches on same two Taillard's instances the ten available for each shape, as utilized [20, 11]. We highlight in bold the best PG on each instance shape.
PDRs
RL
Shape
SPT
MWR
MOR
INSA
TRL
L2D
CL
DQN
GM
15x x 15
17.5
18.8
15.2
15.5
35.4
22.3
15.2
7.1
15.1
20 x 15
29.7
24.5
26.8
15.3
32.1
26.8
17.9
13.9
14.0
20 x 20
27.8
22.0
23.1
16.7
28.3
30.3
16.2
17.9
17.4
30 15"
39.5
22.8
23.9
21.1
36.4
31.5
20.3
16.1
17.0
30 20"
30.0
27.7
27.5
19.2
34.7
38.3
22.15
21.8
21.1
x
30.1
23.8
26.2
12.4
31.85
24.6
15.6
17.7
11.8
50 x 20"
24.3
18.4
18.6
23.0
28.03
28.6
14.2
19.5
14.4
100 x 20*
14.2
8.2
8.5
15.2
18.0
12.5
5.5
9.5
5.0
Avg
26.6
20.8
21.2
17.3
30.6
26.9
15.9
15.4
14.5
Appendix
A Disjunctive Graph Features
Following ML works reviewed in Sec. 2, we augment the standard disjunctive graph representation of a JSP instance by incorporating additional features for each vertex E V. Tab. details these features. Some features, such as features 1-3, have been adapted from previous works [54, 39], while others have been introduced by us to better model JSP concepts like machines and jobs. For instance, features 4-6 take the same value for operations of the same job, emphasizing which operations belong to different jobs, while features 7-9 do the same for operations to be performed on the same machine.
Note that these features as well as those outlined in Tab. 1 can also be used for other shop scheduling problems, including Flow Shop, Flexible Flow Shop, and Flexible Job Shop.
B Additional Comparisons with Neural Algorithms
We additionally consider learning proposals reviewed in Sec. 2, which were tested only on a few benchmark instances which could not be included in Tab. due to how results are disclosed.
Regarding proposals not included in Tab. 2, we highlight that our GM outperforms the Graph Neural Network in [39] that exhibits significantly higher average gap of 19.5% on Taillard's benchmark. Note that only qualitative results are disclosed in [39]. we did our best to report them. Similarly, we remark that the GM performance is superior to the proposal in [47] (hCP), mixing RL and constraint programming. hCP achieves an average makespan of 2670 and 5701 on Taillard and Demirkol benchmarks respectively, while our greedy GM yet obtains average of 2642 and 5581.
As some other learning proposals like [11, 20] were tested only on certain benchmark instances, we provide an additional evaluation on such instances for fair comparison. We include in Tab. 5 the average PGs of greedy constructive approaches on the two Taillard's instances of each shape used in the Transformer (TRL) proposal of [11] and the Deep Q-Network (DQN) of [20]. On this subset of
15

---

Table 6: The average PGs of the algorithms on Lawrence's 's benchmark. For each row, we highlight in blue and bold the lowest (best) constructive and non-constructive gap, respectively.
Greedy Constructvves
Multiple (Randomized) Constructises
Non-constuuciive Approcher
PDRs
RL
Our
PDRs (5 = 128)
RL
Our
Shape
MWR
MOR
INSA
L.2
MWR MOR
SBH
L,D
2M
GMg12
1.25g00
1.25c.
10 x
14.8
15.9
14.6
7.3
14.3
9.3
3.8
9.0
5.6
2.0
8.8
1.9
1.1
2.1
1.8
0.0
0.0
x
14.9
5.5
5.0
2.2
7.8
2.6
2.3
1.2
1.1
0.0
2.8
0.0
0.0
0.0
20 x
16.3
5.2
6.7
2.7
6.3
2.1
5.8
1.4
2.6
0.1
3.1
0.0
0.0
0.0
0.0
0.0
0.0
10 10
15.7
12.2
12.0
7.9
23.7
8.5
7.6
6.9
5.7
10.4
3.1
2.5
0.9
15 x 10
28.7
17.8
23.4
12.1
27.2
11.6
15.2
11.1
11.6
7.6
16.2
5.2
5.0
6.4
3.4
0.0
0.0
36.9
17.9
21.9
16.0
24.6
12.1
12.5
12.9
5.8
18.3
6.9
5.6
2.6
300 x 10
16.6
9.2
7.7
3.9
8.4
2.0
8.5
3.5
2.3
0.0
6.8
0.0
0.0
0.2
0.0
0.0
0.00
18.2
18.7
14.8
27.1
13.6
12.2
12.8
6.8
5.6
Avg
21.2
12.7
13.7
8.4
17.4
7.8
9.3
7.3
7.0
3.7
10.6
3.0
2.5
3.4
1.8
0.0
0.0
Table 7: The average PG and its standard deviation (ang + std) of the best four multiple (randomized) constructive and con-tonstreetive algorithms on Taillard's benchmark. highlight blue (bold) the best constructive (non-constructive) gap.
Multiple (Randomized) Constructives
Non-constructive Approaches
Shape
MOR
CL
GM
GM512
NLSA
L25
MIP
CP
15 15
12.5 2.6
2.0
7.2 1.6
6,5 + 1.3
3.0
6.2 1.4
0.1
0.1
Taillard's benchmark
20 15
16.4
1..
9.3 1.8
8.8 1.4
12.2
8.3 1.7
3.2
0.4
20 20
14.7
10.9+1.6
10.0+13
1.0
11.5
11.5+1.5
9.0
2.9
0.7
30 15
4.5 14.0+3.8
11.0+3.8
1..6+3.6
14.1
9.0+3..0
10.7+3.1
2.1
30 20
2.22 16.1
1.64
1..7
16.4+24
12.6#2.1
13.2
28
50 15
13.5 4.5
9.
5.0
2.7
11.0
4.613.1
12.3
0.0
50 20
1.
9.2
8412.0
7.6
11.32.1
6.5
13.6
1.9
100 x 20
2.1
2.0
2.3
2.1
5.9
3.7
11.0
1.5
Tot Avg Std
14.5 4.6
4.2
8.4
3.6
11.344.1
7.4
8.4
2.0 + 1.9
instances, we see that TRL is the worst-performing approach and that DQN roughly aligns with CL. As our GM is always the best or second best algorithm on each shape, it achieves the lowest overall average gap (Avg).
C Performance on Lawrence's Benchmark
Lawrence's benchmark has been extensively used in the JSP literature to develop various resolution approaches, e.g. [1, 36, 55]. This benchmark includes 40 instances of different shapes and features smaller (and easier) instances compared to the Taillard's 's and Demirkol's 's ones. To complement the evaluation of Sec. 5.2 on small instances, we provide in Tab. comparison of approaches included in Tab. 2 on Lawrence's benchmark. Note that we could not include CL and NLS, as they were not tested on these instances.
Tab. 6 shows that our GM remains the best constructive approach for small instances. However, we observe that L2Sga achieves slightly better results than GM512 at the cost of significantly longer execution times. Specifically, L2S;4 always requires more than 70 sec on such instance shapes (as reported in [55]). whereas our GM512 always completes in less than 0.5 sec (see also App. for timing considerations). Finally, we highlight that on small instances like those in Lawrence's s benchmark, exact methods such as MIP and CP can effectively solve them to optimality.
D Statistical Analysis
Due to space constraints, we evaluate algorithms in Tab. 2 solely in terms of average gaps. This approach justified as the average trends are consistent with other statistical measures. For ex- ample, Tab. 7 reports the average and standard deviation of the best four multiple (randomized) constructive and non-constructive approaches on Taillard's benchmark. We omit Demirkol's instances since not all algorithms report results for them. Each row in Tab. 7 presents the average gap and standard deviation for instances of specific shape, but the last row, which reports the average and standard deviation all instances, regardless of their shapes. This table confirms that the
16

---

Table 8: Average makespan (weg + std) and execution time of CP-Sat and our GM (when sampling / = 512 solutions) on very large instances.
Instance shape
200x20
x00
500x20
500
CP-Sat
Cmux lime
21848.5 331
23154.6 350
53572.7
743
546064.0 = 443
3600 sec
3600 see
3600 sec
3600 sec
Cooz
21794.5
324 31 soc
22795.0 + 277
53288.4
737
53942.9 - 425
GM
time
64 sec
164 sec
343 sec
Gap sum from CP-Sat
-3,30
-30.88
-6,30
-26.14
observations made for Tab. 2 remain valid when considering standard deviations. Specifically, GM512 remains the best constructive approach, aligning closely with the RL-enhanced metaheuristic L2S5k- The MIP still has worse overall performance than GM512 while CP produces the best average gaps and standard deviations.
E Extremely Large Instances
As shown in Tab. 2, constructive approaches are generally inferior to state-of-the-ar art metaheuris- tics [36] (see also [55]), Mixed Integer Programming (MIP) [29], and Constraint Programming (CP) solvers. These resolution methods employ more complex frameworks, making them more effective for solving combinatorial problems. However, neural constructive approaches closing the gap as remarked by the GM's performance matching that of MIP solvers. Herein, we also prove that our GM generally produces better results than CP solvers on very large instances.
continuously
To this end, we randomly generated 20 JSP instances with shapes {200 x 20, 200 x 40, 500 x 20, 500 x 40} and solved them with the CP-Sat solver of Google OR-tools 9.8, executing for 1 hour, and our GM (trained as described in Sec. 5.1), sampling / = 512 solutions. Tab. 8 reports the average exccution time (time), the average makespan and its standard deviation (Cmaz) of CP-Sat and our GM512 on each shape. The last row (Gap sum from CP-Sat) offers a relative comparison by summing up the gaps of the GM512 computed from the solutions produced by CP-Sat. A negative value means that the GM produced better solutions.
As one can see, the GM512 produces better average results than CP-Sat with just a fraction of time. On these 80 instances, we observed only 7 cases in which the solutions of CP-Sat are slightly better than those of the GM. This remarks once more the quality of our proposal, making it valid alternative to CP solvers for extremely large instances.
Lastly, we remark that on these large instances, the execution times of our GM can be further reduced by employing speed-up techniques such as model quantization (i.e., converting floats to lower precision numbers) and the new compile functionality available in PyTorch 2 2.0. Our model did not undergo any of the above (herein and in any other evaluation) and has been coded by keeping the implementation simple possible.
F Execution Times
We additionally assess the timing factor, an important aspect in some scheduling scenarios. To this end, we plot in the left of Fig. 6 the execution time trends of dispatching rules (PDR), INSA, I.2D (we omit CL as it has slightly higher exccution times than L2D), and GM on typical benchmark shapes, all applied in greedy constructive manner. We also include the execution time of our GM when sampling 512 solutions (GM512) to prove that sampling multiple parallel solutions does not dramatically increase times. Note that all these algorithms were executed on the machine described at the beginning of Sec. 5. We omit other RL proposals as they do not publicly release the code, do not disclose execution times, or is unclear whether they used GPUs.
When sampling 512 solutions, the GM512 takes less than a second on medium shapes, less than sec on large ones, and around 10 sec on the big 100 x 20. As these trends align with L.2D, which only constructs a single solution, our GM much faster neural alternative, despite being also better in terms of quality. We also underline that the GM and any ML-based approach are likely to be
17

---

+.M
Greedy Conseuutive
Our Graph Model (GM)
Shape
PDRs
INSA
L.D
CL
3=1
3-64
2-128
(2-256
9:512
0..03
0.21
0.23
80 13
0.00
1.10
0.28
0.38
0.28
0.36
Scoondss
20 20
0.00
0.03
0.72
1.39
0.37
0.37
0.37
0.57
0.48
0.66
30 15
0.01
0.08
0.55
144
0.0
0.41
0.41
0.47
0.61
0.92
30.x4 87
0.01
0.11
141
1.22
0.54
0.56
0.56
0.62
0.82
1.22
60 15
0.01
0.14
1.45
181
0.55
0.56
0.56
0.68
0.53
1.45
0.55
1.22
035
0.20
80.
0.01
0.01
0.20
0.25
131
160
2.82
2.07
0.70
0.30
0.79
0.74
0.74
0.33
0.92
0.90
1.23
1.32
2.15
1.91
0.02
1.5
0.58
13615
20835
20020
3005
10520
42455
50025 50c00
Instance shape
Figure 6: The average execution time in seconds of the coded algorithms on different instance shapes considered in Tab. 2. The times of PDRs, INSA, I.2D, and CL. refer the construct of single solution. Whereas report the times of the GM for varying numbers of sampled solution E {1, 12,3 64, 128, 256, 512).
slower than PDRs and constructive heuristics, either applied in a greedy or randomized way. One can see that such approaches work faster: PDRs take 0.2 sec and INSA 1.61 sec on 100 20 instances. However, this increase in execution time is not dramatic and is largely justified by better performance, especially in the case of our GM.
We finally provide in the right table of Fig. the precise GM timing for varying numbers of sampled solutions 3 during testing. Each row reports the average execution time benchmark shape and the last row (Tot Sum) sums up all the times for an overall comparison. We observe that sampling 32 and 64 solutions from the GM takes the same except in large instances (50 15, 50 20, and 100 x 20 shapes), where variations are small. Therefore, sampling less than 32 solutions is pointless, as the reduction the execution times is negligible while the quality is further reduced. Additionally, sampling more than 512 solutions further improves the GM's results at the cost of consistent increment in the execution time. As an example, by sampling 1024 solutions, the overall average gap (Avg row in Tab. 2) is reduced by 0.4% in both benchmarks with respect to the 3 = 512 case, but the execution time is roughly 1.9 times larger. Instead of blindly sampling many random solutions with long executions, it should be possible to achieve better results in less time with ad-hoc strategies, such as Beam-Search or other strategies, that sample differently based on the generated probabilities or other information. We leave this study on testing strategies to future work.
G Extended Results
The extended results of the coded algorithms (PDRs, INSA, SBH, L2D, MIP, CP, and the GM's configurations) are available at ? For computing the percentage gap (PG), used the optimal or best-known makespan of an instance (Cut), available at: https: / opt imi 2 size..r com/ jobshop - php. The extended results highlight that models trained using Self-Labeling strategy with 8 < 256 exhibit competitive performance and, in some instances, even surpass the model trained with 3 256. This indicates the efficacy of our strategy even with a reduced number of sampled solutions. However, as remarked in the paper, sampling larger number of training solutions yields improved overall performance, evidenced by the lower total sums observed for larger values of B.
results: http:://wwhh...coo......cccaa/aa
main/oottuu//Resllee xlsx
18

---

NeurIPS Paper Checklist
1. Claims
Question:
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes].
Justification:
The abstract and introduction in Sec. I present the intuitions that guided our work and the assumptions behind it. All these statements are used throughout the paper and backed up by the main results and additional studies provided respectively in Secs. and 6.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contribu- tions made in the paper and important assumptions and limitations. A No NA answer this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes].
We discussed limitations in Sec. 7 and used them to point out potential future improvements.
Justification:
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those
diseussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to vi- olations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. general. empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that inffuence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images taken in low lighting. Or speech-to- textexxt system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by review- ers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor transparency play an important role in developing norms that preserve the integrity the community. Reviewers will be specifically instructed not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
19

---

Answer: [NA].
Justification:
The paper does not provide theoretical results.
Guidelines:
The answer NA means that the paper does not include theoretical results.
the theorems, formulas, and proofs in the paper should be numbered and cross-referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proof' can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged provide a short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by
formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes).
Justification: We provided necessary information to reproduce experiments in Secs. 4.1, 5.1, and 6. We also included our code and dataset to maximize reproducibility and cross-comparisons.
Guidelines:
The answer NA means that the paper does not include experiments. If the paper includes experiments, No answer this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided not.
If the contribution is a dataset and/or model, the authors should describe the steps taken to make their results reproducible verifiable.
Depending the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, if the contribution is a specific model and empirical evaluation, may be necessary to either make it possible for others to replicate the model with the same dataset, provide access the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to hosted model (e.g.. in the case of large language model), releasing of model checkpoint, or other means that are appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm.
(b) If the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., large language model), then there should either be a way to access this model for reproducing the results or a way to reproduce the model (e.g., with open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility. In the case of flosedsouuce models, it may be that access to the model is limited in some way (e.g., to registered users), but should be possible for other researchers to have some path to reproducing verifying the results.
5. Open access to data and code
Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, described in supplemental material?
Question:
Answer: [Yes].
20

---

Justification:
We included a link to the GitHub repository containing the code, trained models, and the created dataset.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https: /nwpsnip....o cc/ public/quide
CodeSubmi ss ooiooiicyy for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this central the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https: //nips. tttppp.cccpppeeee www.cc/pplll.cc i des/Ceaee Code/obbemmmm ss onPolinooo imPolicy) cy) for more details.
The authors should provide instructions data access and preparation, including how to access raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
Experimental Setting/Details
Question:
Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes].
Justification: We described the adopted experimental details in Sec. 5.1 and at the beginning of Sec. 5.2. Any modifications this setup. as in the studies presented in Sec. 6, are explicitly described where they occur.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report eтrоr bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes].
Justification: We provided statistical considerations in App. D. In addition, we exposed our methodologies to various training regimes and models in the additional studies of Sec. 6, demon- strating the significance of our contribution in different setups.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
21

---

It should be clear whether the error bar is the standard deviation or the standard error of the mean.
It is OK to report I-sigma error bars, but one should state it. The authors should preferably report 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not show in tables figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
If error bars are reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
Experiments Compute Resources
Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Answer:
[Yes].
Justification: We provided information about the employed computational resources at the beginning of Sec. 5.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experi- mental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported the paper (e.g.. preliminary or failed experiments that didn't make into the paper).
Code Of Ethics
Does the research conducted the paper conform, in every respect, with the NeurIPS Code of Ethies https: neurips http//ubblcc//hhccssttteee lines?
Question:
Answer: [Yes].
Justification:
We did our best to adhere to the NeurlPS Code Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA].
Justification: We briefly motivated at the beginning of Sec. why tackling the Job Shop Schedul- ing problem is of concern for the community. Additionally, provided analysis in Appendix on potential practical applications and pointed out extensions to other combinatorial problems in Sec. 8. Note however that discussing the socictal impacts is outside the scope or our work and is largely addressed by surveys papers on such problems.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address socictal impact.
22

---

Examples of negative societal impacts include potential malicious or unintended uses (e.g.. disinformation, generating fake profiles, surveillance), fairness considerations (e.g.. deploy- ment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications. let alone deployments. However, if there is direct path any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used intended but gives incorrect results, and harms following from (intentional unintentional) misuse the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release models, providing defenses addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA].
Justification:
The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use the model, for example by requiring that users adhere usage guidelines restrictions access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer:
[Yes].
Justification: We properly referenced throughout the paper the creators of original code and assets, like in Secs. 5.1 and 1.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use the package should be provided. For popular datasets, paper rsw thoode. com/ datasett has cu- rated licenses for some datasets. Their licensing guide can help determine the license of datasct.
23

---

For existing datasets that are re- ee-ackaaedd, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is available online, the authors are encouraged reach out to the asset's ' creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes].
Justification: We provided the necessary details of assets (like models and dataset) produced by research in the body of the paper (e.g., Sec. 5.1), and we included additional documentation in the released code.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model as part of their sub- missions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and Research with Human Subjects
For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, well as details about compensation (if any)?
Question:
Answer: [NA].
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Question:
Answer: [NA].
Justification: The paper does not involve crowdsourcing research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.


Reviews:
[{"review_id": "8IwfNFYGFf", "reviewer": "Reviewer_2iGC", "summary": "This paper introduces an effective method for learning to solve the Job Shop Scheduling Problem (JSP). The contribution is twofold: a pointer network architecture (encoder-decoder) to effectively represent the problem and an efficient learning paradigm based on self-supervised learning termed “self-labeling” in which a model is trained by supervising on the best self-generating solutions, thus not needing to collect labels. The proposed approach outperforms several SotA learning baselines.", "questions": "1. Why use random sampling instead of other techniques such as top-k and nucleus sampling? You mentioned that you made a preliminary analysis; however, results seem to be missing. According to recent literature, as [1r] above, nucleus sampling could help achieve better performance.\n    \n2. Why do you use a Pointer Network and not, for instance, re-encode step-by-step? Also, how did you choose parameters such as the number of attention heads in GAT?", "limitations": "Addressed in the text. Also, see the above weaknesses.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "The paper is well-written and clearly positioned in the literature. The proposed self-labeling approach, while simple, is a reasonable next step in the recent line of work of supervised approaches for combinatorial optimization, removing the reliance on optimal solutions while addressing the sparse credit assignment problem. This can be extended to other combinatorial problems. The proposed PN is not that new in terms of concept, but its execution such as feature engineering and the code implementation (which I appreciate) are pretty meaningful. The experiments are extensive in the JSP and provide clear evidence of the method’s benefits.", "weaknesses": "My main concern is about the applicability to other problems, which lacks experimental evidence - given this is a major point the authors make in the contributions and conclusions, I was expecting some pilot study on, say, the TSP showing the method’s applicability, but unfortunately, this was not provided. Note that given the limited time for rebuttal, I am not expecting the necessary results. Notably, there are concurrent/follow-up works that apply such an idea to other CO problems such as [1r, 2r]. Thus, I think these can make up for the lack of experiments in this area.\n\n---\n\n### References\n\n[1r] Pirnay, Jonathan, and Dominik G. Grimm. \"Self-Improvement for Neural Combinatorial Optimization: Sample without Replacement, but Improvement.\" arXiv preprint arXiv:2403.15180 (2024).\n\n[2r] Luo, Fu, et al. \"Self-Improved Learning for Scalable Neural Combinatorial Optimization.\" arXiv preprint arXiv:2403.19561 (2024).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Please find our responses to the main concerns and questions below:\n- **A1 (TSP pilot):** As noted by the reviewer, there are recent follow-up works adopting self-labeling and proving our method is applicable to other problems. We further back this claim up by including in Fig. 2 of the attached PDF file (above) the preliminary training curves comparing POMO and self-labeling on TSP. **These curves show that the renowned Attention Model for the TSP can be effectively trained with self-labeling, proving once more the applicability and generality of our method.** \n\n- **A2 (nucleus sampling):** We provide in Tab.1 below a comparison of sampling strategies at test time (due to limited time we were unable to reproduce the analysis at training). **The strategies are similar, however, top-k and nucleus sampling introduce hyperparameters that can hinder training convergence if not managed carefully (see the similar statement at the bottom of Sec. 4.2.2 in [1r]).** Consistently with policy optimization, we prefer random sampling as it has empirically shown a good balance between exploration and exploitation without introducing brittle hyperparameters. Notably, [1r] uses a more advanced sampling strategy, which is key to their performance boost. We can include in the paper a test and training time comparison of different strategies.\n\n**Tab. 1** : Comparison of random (rand), top-k, and nucleus sampling on Lawrence (LA), Taillard (TA), and Demirkol (DMU) benchmarks. For each benchmark, we report the overall average gap of the SPN when sampling $\\beta = 512$ solutions. Note there are small differences but not a sampling strategy consistently better than the others.\nSampling | LA | TA | DMU | Avg\n-----------|-----|-----|-------|------\nrand | 2.47 | 7.78 | 13.10 | 7.78\ntop-3 | 2.74 | 7.67 | 13.52 | 7.97\ntop-5 | 2.50 | 7.49 | 13.33 | 7.77\nnucleus (p=0.9) | 3.09 | 7.54 | 13.27 | 7.96\nnucleus (p=0.95) | 2.77 | 7.59 | 13.17 | 7.84\n\n- **A3 (why PN):** To the best of our knowledge, there is no standard reference architecture for the JSP. **We chose the well-studied PN, which has been effective in other CO problems like TSP and VRP.** However, any re-encoding strategy or generative model suitable for the problem can be used. **Note that our claim is not to propose a reference architecture for the JSP or scheduling problems, but just to have an effective one.** There is probably a need for a reference architecture for scheduling problems.\n\n- **A4 (parameters):** **We tuned hyperparameters with 5-fold cross-validation on a subset of training instances to balance performance and execution time, including the number of heads.** Although deeper (not larger) models may improve results, they also require more execution time. As constructive heuristics should be fast (metaheuristics generally run quite fast and are more powerful for CO problems, see lines 21-30), bigger models may be a drawback for their philosophy and practical applicability. Thus, we opted for a reasonable trade-off between performance and execution time.", "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": "3aSw4ndvP5", "reviewer": "Reviewer_pxef", "summary": "The paper proposes learning a constructive neural heuristic for the Job Shop Scheduling problem (JSP). The proposed policy network is an auto-regressive attention-based encoder-decoder model. A JSP instance is represented by a (commonly used) disjunctive graph with additional hand-crafted features. The paper proposes to train the policy network using a \"self-labeling\" strategy. This strategy consists in alternating for each training instance between (i) sampling a number of solutions from the current policy, selecting the one with the smallest makespan as a pseudo-label, and (ii) updating the policy using a supervised (cross entropy) loss based on the pseudo-label. The approach is tested on standard JSP benchmarks and shows superior performance to state-of-the-art neural baselines.", "questions": "1. Did the authors monitor the quality of the generated solutions during the training? For each training instance, does the makespan of the best sampled solution consistently decrease?\n\n1. Line 201: \"we generate with the PN a set of $\\beta$ different solutions.\" --> Is there a condition that ensures that the sampled solutions are different? In the experiments, did the author track if there are any duplicates among the $\\beta$ solutions? \n\n1. Eq (5): On the right hand-side, shouldn't it be $\\bar{\\pi}$ instead of $\\pi$?\n\n1. It would be interesting to discuss concurrent work [2] and previous work [3] which also propose self-improvement training strategies with related pseudo-labels.\n\n[2] Pirnay et al, Self-Improvement for Neural Combinatorial Optimization: Sample Without Replacement, but Improvement. Transactions on Machine Learning Research (06/2024)\n\n[3] Luo et al, Self-Improved Learning for Scalable Neural Combinatorial Optimization. arXiv:2403.19561", "limitations": "Yes, the limitations were addressed.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "* The paper is clear and well written. In particular, the description of the model and the experiments is clear and detailed enough. \n* In the experiments, the baselines are quite exhaustive: in addition to similar neural constructive heuristics, improvement heuristics as well as various non-learning-based approaches are considered.\n* The strong performance on the Taillard and Demirkol datasets, even on instances with a number of jobs or machines not seen in training.\n* The scaling of the approach is evaluated on instances with up to 100 jobs and 20 machines (versus at most 20x20 in training).", "weaknesses": "1. The proposed training strategy relies on stochastic sampling from the current policy to generate better-quality solutions to then improve the policy. However for a given training instance, there is no guarantee that one of the $\\beta$ sampled solutions should be better than the greedy policy solution. If the solutions do not improve consistently, I can't see how the training would work.\n\n1. Some previous works, such as [1], have shown the limitations of such random sampling in generating diverse and/or good-quality solutions, at least given a trained policy.\n\n1. The paper has a narrow scope since the approach is tailored for the JSP. Although I agree with the authors the principles of the training could be applied to other problems, it remains to be shown if it would actually work, especially given my previous points. \n\n1. The proposed heavy feature engineering (Tables 1 and 4) is obviously specific to the JSP and somehow goes against the end-to-end promise of neural combinatorial optimization.\n\n[1] Chalumeau et al, Combinatorial Optimization with Policy Adaptation using Latent Space Search. NeurIPS 2023", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Please find our responses to the main concerns and questions below:\n- **A1 (greedy solution concern):** We kindly disagree. If the model is highly confident in a decision, random sampling tends to align with a greedy argmax strategy. Whereas, similar to top-k and nucleus sampling (with small $k$ and $p$), enforcing (too) greedy selections can cause the model to converge prematurely to a sub-optimal policy (poor exploration issue) during training, as it only learns to amplify its sub-optimal decisions (see also Sec. 4.2.2 in your referenced [2]). Thus, **ensuring that sampled solutions always align or are better than greedy ones is not necessarily the best long-term strategy for training good models.** Empirically, if randomly sampled solutions were not better than the greedy one, we would not be able to train effective models nor produce the training curves shown in Fig. 1 of the attached PDF file (or Fig. 4 in the paper). Moreover, if that were the case, we would expect similar SPN's performance in both the greedy and randomized sections of Tab. 2 of the paper, but the results show otherwise.\n- **A2 (narrow scope):** We do agree that our model is tailored for the JSP like other models are for routing problems. However, this does not imply a narrow scope. **Effectively solving the JSP establishes a foundation for addressing other shop scheduling problems like Flow Shop (a special case of JSP) and Flexible JSP**; see also A2 of reviewer mZNb and A4 of reviewer NWh3. Furthermore, **self-labeling is a general approach that is getting applied in other CO problems**, e.g., routing ones in your referenced [2] and [3]. To back this up, we provide in Fig. 2 of the attached PDF file (above) preliminary results showing that self-labeling is indeed effective also in TSP. Thus, we are confident about the generality and wide-scope of our contribution.\n- **A3 (features):** To be precise, the features are specific to shop scheduling problems, i.e., problems having operations, jobs, and machines as entities. Note also that many of the features are taken from related published works (see e.g. App. A). **We apologize but we do not see issues in having an effective model suitable for the JSP as long as we are not claiming to have a new general end-to-end model for CO problems** (see also A3 of reviewer 2iGC). Lastly, in Section 6.3, we also proved that self-labeling allows to train well a recent end-to-end architecture (namely CL) that uses as features the processing times and machine indices only.\n- **A4 (training solution quality):** **Yes, we monitor the quality of training solutions (train.py file, line 126 of supplementary material)** to see whether the model keeps improving. Also, Fig. 4 (and the refined Fig. 1 in the attached PDF above) of our paper shows that the model improves on validation instances over the training because it improves on training instances.\n- **A5 (diverse solutions):** We agree that duplicates may happen (in very small instances), but we did check and this was not an issue. In JSP, the probability of duplicates in an instance with 10 jobs and 10 machines (smallest training instance) is in the order of 1 over $10!^{10}$, hence tiny. To further provide evidence, we use our best model (highest likelihood of producing duplicates) and count how many duplicates it generates when sampling 512 solutions (max number in our experiments). **As we count 0 duplicates in Taillard's and Demirkol's instances, we conclude that duplicates do not particularly limit our methods.**\n- **A6 (Eq. 5):** Yes, thank you for pointing this out.\n- **A7 (discuss [2] and [3]):** These recent follow-up works expand on our research in various directions. [2] uses self-labeling and proposes an advanced sampling strategy outperforming random, top-k, and nucleus sampling. The unpublished work [3] presents a local reconstruction approach to tackle large-scale routing instances, where the model is fine-tuned to reconstruct parts of a solution using self-labeling but requires pre-training with RL algorithms. **Our message is different, we prove that self-labeling can effectively train models from scratch for building complete solutions without any RL pre-training, addressing a broader and more challenging task.** Lastly, without violating anonymity, it is worth noting that these works may cite and explicitly build upon our work, which was publicly released on ArXiv before the submission. We can nevertheless include a discussion regarding these works in the paper.", "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": "3Zv8hGmBMg", "reviewer": "Reviewer_NWh3", "summary": "This paper proposes a job-shop scheduling method based on self-labeling strategy and pointer network. The structure of the paper is clear. The method is evaluated on public benchmarks Taillard and Demirkol’s.", "questions": "1. Have you explored the possibility of transitioning your work to a different variant of JSP, like FJSP?\n2. The paper appears to lack any discussion regarding the solution time of the proposed method. I am also interested in understanding the solution time of your algorithm and the duration required for its training.\n3. The Encoder in the paper operates at the operation level, while the Decoder functions at the job level. What factors influenced this design choice? Have you ever experimented with a network structure that is entirely operation-level or job-level?", "limitations": "The paper has discussed some limitations in the appendix.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Overall speaking, the self labeling strategy is an interesting approach because it only requires an objective function for determining the optimal solution in the current solution set in order to train the model. It avoids the expensive cost of using a solver. Also, this approach is easier to implement than reinforcement learning. The results show that the proposed method achieves better performance than PDRs and RL on two public benchmarks.", "weaknesses": "1. The self-labeling strategy necessitates the generation of a large number (denoted as beta) of solutions for each training epoch, with only one of these solutions being valid. Consequently, this method exhibits notably low sample utilization. As depicted in Figure 2, to achieve a well-trained model, beta typically needs to be set at 256 or even higher, resulting in sample utilization well below 1%. Are there any methods or ideas available to enhance sample utilization in this context?\n\n2. While the paper validates the method solely on two public benchmarks (TA and DMU), it's worth noting that there exist additional public benchmarks for JSP, including ABZ, FT, LA, ORB, SWV, and YN [1-6]. Considering these benchmarks could provide a more comprehensive evaluation of the proposed approach.\n\n3. To ensure the reproducibility of the experimental results, it is essential to make the source code publicly available on platforms like GitHub. This transparency is crucial for reviewers to verify the credibility of the results presented in the paper.\n\n[1] J. Adams, E. Balas, and D. Zawack. The shifting bottleneck procedure for job shop scheduling. Management Science, 34.3: 391-401, 1988.\n\n[2] H. Fisher and G. L. Thompson. Probabilistic learning combinations of local job-shop scheduling rules. In: Industrial Scheduling: 225-251. ed. by J.F. Muth and G.L. Thompson. Prentice Hall, 1963.\n\n[3] S. Lawrence. Resource Constrained Project Scheduling. An Experimental Investigation of Heuristic Scheduling Techniques (Supplement). Carnegie-Mellon University, 1984.\n\n[4] D. Applegate and W. Cook. A computational study of job-shop scheduling. ORSA Journal of Computing, 3.2: 149-156, 1991.\n\n[5] R.H. Storer, S.D. Wu and R. Vaccari. New search spaces for sequencing instances with application to job shop scheduling. Management Science, 38.10: 1495-1509, 1992. \n\n[6] T. Yamada and R. Nakano. A genetic algorithm applicable to large-scale job-shop instances. In: Parallel instance solving from nature II: 281-290. ed. by R. Manner and B. Manderick. Elsevier, 1992.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Please find our responses to the main concerns and questions below:\n- **A1 (large $\\beta$ and utilization):** Fig. 2 of our paper proves that training the SPN with $\\beta = 32$ significantly outperforms CL, the best neural constructive. **Increasing $\\beta$ enhances performance, but high $\\beta$ values are not needed to outperform baselines (see lines 322-327).** We agree about sample utilization: **in App. F we state that utilization is an efficiency limitation and constitute a potential for future improvements.** For instance, exploring the use of a portion of samples as labels may be beneficial, but is not required for our method effectiveness.\n- **A2 (benchmarks):** You are right. We realized that the evaluation in the main paper does not properly cover small-medium instances (contained in the cited benchmarks). Thus, **we have extended the evaluation on Lawrence's benchmark in the Tab. 1 of the attached PDF file (above).** Remarkably, the SPN remains the best constructive approach and the results show that MIP and CP close all these smaller and easier instances (quite fast). Note also that our experimental evaluation aligns with that of published works cited in the paper. Thus, we are very confident about the quality of our proposal as the SPN was thoroughly tested in challenging scenarios (including very large instances in App. D).\n- **A3 (code):** We totally agree. **The code is available in the supplementary material and also on GitHub** (we did not directly link to GitHub for keeping anonymity).\n- **A4 (FJSP extension):** **We are exploring extensions, including the FJSP.** While elements like the self-labeling strategy and features can be used for the FJSP, the architecture and solution construction process will need careful re-evaluation to ensure effectiveness. We would be happy to collaborate if there is the opportunity.\n- **A5 (execution times):** We point the reviewer to **lines 334-338**, where we consider execution time and refer to Appendix E for detailed considerations. Whereas, in **lines 258 and 259**, we state that training roughly takes 120 hours, around 6 hours per epoch.\n- **A6 (model choices):** Based on the considerations in Sec. 3.1, each job has a single active operation during the solution construction. We structure the decoder's decisions at the job-level to avoid accounting for inactive operations, thereby simplifying the decoder's task. Meanwhile, the encoder captures instance-wide relationships in the operations' embeddings using the disjunctive graph. **This approach allows the encoder to maintain a high-level view of the instance characteristics, while the decoder focuses on the solution construction, specifically the status of machines and jobs.** We did not explore models fully working at the operation or job level, but these are plausible alternatives (see also A3 of reviewer 2iGC).", "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": "VmlvYRuNce", "reviewer": "Reviewer_mZNb", "summary": "This paper is empirical in nature and studies generative models for the job shop scheduling problem (JSP).  JSP is well-studied in the scheduling community, both theoretically and empirically, in part because of its many applications. In JSP, a DAG is given of the precedence ordering of a set of operations (equipped with a specified machine it should be processed on and the amount of machine time it will require), and jobs are sequences of operations that must be completed respecting the order of the precedence relations. The available machines can process one operation at a time, and the goal is to minimize the makespan, i.e. the time when the last job is completed. \n\nThe training strategy (known as the self-labeling strategy) is to generate many solutions for an instance, then choose the best one according to the objective to be the ”pseudo-label”. Generating solutions is done by making sequential decisions about which operation per job should be scheduled next on a machine. The architecture for these decisions is called a Pointer Network, which basically makes its choices by learning a function estimating the probability of a solution being of high quality. Then, generating solutions is done via an intuitive sampling procedure. \n\nThe experimental sections compares against some baseline ML works for JSP called L2D and CL.  They additionally compare against some classic theoretical heuristics, including shortest processing time SPT and most work remaining MWR. The studies seemed well-constructed. The authors show that their algorithm (plural algorithms I suppose since they consider some different parameters for how many solutions for generated before the best is chosen of the pseudo-label) perform significantly better in terms of the quality in the solution on 2 standard sets of benchmarks. Additional strategies are compared against in the appendix, and the conclusion still stands.", "questions": "What specific combinatorial properties does JSP have that made this amenable to your techniques? I ask because while I believe these methods can be extended to some other CO problems, I’m trying to understand what broader class of CO problems your techniques could be effective for.\n\nDo you see any connection between the work in generative models for CO problems and the work on learning-augmented algorithms (also known as algorithms with predictions)?  In particular, is there any reason to believe the problems in CO for which generative models may be useful are the same as the problems that can be improved in the algorithms with predictions framework?\n\nI am unfamiliar with the empirical benchmarks in this area. Is there any reason to fear that Taillard’s,  Demirkol’s benchmarks, and the randomly generated instances have some similarities that are not shared by other JSP?", "limitations": "Yes", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "I find the paper to be well-motivated. The authors state that while meta-heuristics are state-of-the-art for the JSP, they are very expensive to compute. On the other hand, semi-supervised and self-supervised learning (which can learn from unlabeled data) seem more promising for combinatorial optimization problems, despite this area being understudied so far. \n\nThe assumptions for the broad techniques to be useful for other combinatorial optimization problems are rather weak: (1) one must be able to generate multiple feasible solutions to the problem and (2) one must be able to evaluate the objective of said solutions. Such weak assumptions suggest that this framework will likely be useful for a broader range of problems in CO. \n\nThe empirical results in this paper indicate that their strategy is better than previous works for JSP, excluding Constraint Programming (CP) solvers and meta-heuristics. Experiments feel complete and well-elaborated upon.\n\nThe presentation of the paper is very nice.", "weaknesses": "The authors note that while there are techniques that can produce higher quality solutions than their algorithms (Constraint Programming (CP) solvers and meta-heuristics), these seem to be much more computationally expensive techniques, which are not really useful for large instances. \n\nI am unsure how motivating JSP is for generative models, since simple algorithms already perform quite well, i.e. list scheduling. I don’t find it the most motivating scheduling problem for initiating the study of generative models in scheduling. Perhaps a bit niche.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Please find our responses to the main concerns and questions below:\n- **A1 (CP observation):** We agree: metaheuristics and CP require more time to provide quality solutions, especially on large instances. **This is the goal of Appendix D, showing that CP scales worse on very large instances.** Note our objective was to stress that neural constructive approaches still lag behind state-of-the-art methodologies in terms of quality and that further research is required to bridge this gap.\n- **A2 (motivating JSP):** Simple list schedulers are far from performing well as remarked by their large gaps in Tab. 2 of our paper. **The Job Shop is an extensively studied problem with many proposed algorithms, available benchmarks, and practical applications.** Despite this, (neural) constructive heuristics still have consistent limitations, see lines 21-35. **Effectively solving the JSP also allows solving special JSP cases (like Flow Shop) as well as establishing a concrete base for tackling more complicated variants such as Flexible JSP.** Note also the increasing number of neural combinatorial publications considering the JSP. Therefore, Job Shop constitutes a perfect playground for developing new learning-based generative solutions.\n- **A3 (broader impact):** We do not exploit specific JSP properties with our self-labeling strategy, but we do leverage JSP characteristics when designing our model. We focus on the renowned Job Shop problem because neural approaches tend to be less effective on scheduling problems (see also your A2) compared e.g. to routing ones. However, if you have an effective generative model (e.g., a Pointer Network) for a CO problem, you can apply our self-labeling strategy. For instance, there exist recent follow-up works (e.g., Pirnay and Dominik, 2024) using our strategy for routing problems (like TSP and VRP), demonstrating its versatility beyond scheduling. **More broadly, wherever you can apply a constructive algorithm, you can design a generative model and apply our strategy.** Thank you, we will include this consideration as broader impact.\n- **A4 (learning-augmented algorithms):** We apologize, but we are unsure about the meaning of learning-augmented algorithms. If you are referring to metaheuristics enhanced with deep learning, as long as you can have multiple solutions/options (generative model) and discriminate based on an objective, you can apply self-labeling as is. In the case of predictive and prescriptive models, it may still be possible. For instance, one may use the top $\\beta$ suggestions of the model, evaluate the responses of the algorithm, and reinforce (one-hot label) the one resulting in the best response. Hope this partially answers you.\n- **A5 (benchmark similarities):** In scheduling, benchmarks contain hard-to-solve instances that have been used throughout the literature. In our work, we use arbitrary generated instances to learn solving the JSP and the benchmarks serve as standard test sets to evaluate the model/algorithm. **There are no particular similarities that must be preserved in training instances, as long as they are JSP instances.** In JSP variants, like Flexible JSP, you can generate arbitrary instances, train on them, and evaluate on benchmarks. While some studies suggest that generating certain types of instances improve learning to solve CP problems, (especially routing ones), this is not what we did.", "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:
We would like to thank all the reviewers for their valuable comments.
We are glad the **contribution** and the **significance** of our work have been recognized by all the reviewers.

Note that after the initial submission and based on your feedback, we have made the following minor modifications/inclusions to the paper:
- **We have introduced an additional benchmark encompassing small-medium instances as requested by reviewer NWh3.** This was done to complement our evaluation on instances even smaller than training ones. You can find this evaluation in Tab. 2 of the attached PDF file. Note that the SPN remains the best constructive approach even on smaller instances.
- **We have updated Fig. 4 (Sec. 6.4) of the paper with Fig. 1 in the attached PDF file.** To make the training curves less noisy with our model, we changed the batch size from 4 to 8 by keeping the same training setting described in Sec. 6.4 (i.e., that of Zhang 2020). This was done to remove the misconception that may relate the training noise to the sampling strategy (comments of reviewer pxef).

As we are currently improving and extending our work, you will also find in the attached PDF file the preliminary training curves comparing POMO and self-labeling on TSP (Fig. 2). **This figure serves to answer questions of reviewers 2iGC and pxef as well as to show that self-labeling is indeed applicable to other CO problems** (also shown in recent follow-up works).

Finally, we understand those who expressed concerns about random sampling. While it is not the optimal strategy for combinatorial optimization problems, random sampling remains a standard approach in policy optimization. Given that variations like top-k and nucleus sampling introduce brittle hyperparameters and have shown similar effectiveness (see response A2 to reviewer 2iGC), we opted for random sampling. **It is important to note that the choice of the sampling strategy is a design decision, not inherently tied to our self-labeling method.** Our rationale is that if self-labeling is effective with basic random sampling, it should also work with more advanced strategies that refine and improve upon it. Moreover, there are already recent follow-up works, such as "Self-Improvement for Neural Combinatorial Optimization: Sample Without Replacement, But Improve", that demonstrate how advanced sampling procedures can enhance training strategies for CO problems.

We hope the answers provided below effectively address the main concerns of the reviewers.

Meta-review: The reviewers all support acceptance of this paper. The self-labeling strategy is novel and effective. Although other very recent works now exist using self-labeling strategies, they cannot be considered under the NeurIPS guidelines. The approach scales well and performs well against existing baselines.
Decision: Accept (poster)