Self-Labeling the Job Shop Scheduling Problem

Please find our responses to the main concerns and questions below:

• 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.
• 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.
• 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.
• 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.
• 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.

Thank you for your response.

I find your point (A3) to be rather motivating, and I see that you included similar responses to the other reviewers, particularly in mentioning TSP, flow shop, and flexible JSP. Just so you are aware, the line of work I was talking about is this: https://algorithms-with-predictions.github.io.

This was the main critique of the paper, so I have raised my score from a 5 to a 6.

Please find our responses to the main concerns and questions below:

• 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.
• 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).
• 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).
• 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.
• 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.
• 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).

Please find our responses to the main concerns and questions below:

• 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.
• 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.
• 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.
• 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.
• 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.
• A6 (Eq. 5): Yes, thank you for pointing this out.
• 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.

I thank the authors for addressing precisely all my comments. I appreciated:

• the additional preliminary experiments on the TSP that show the potential of the approach beyond the JSP
• the clarifications about the random sampling, the improvements during training and the lack of duplicates for the JSP
• the discussion of the follow-up works

As the first paper which introduces self-labeling as an effective training strategy for CO, I support the acceptance of the paper.

Please find our responses to the main concerns and questions below:

• 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.

• 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.

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.

• 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.

• 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.