Self-Labeling the Job Shop Scheduling Problem

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

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. The 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. The 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. The 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. I 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.

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. Do 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? I 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?

Rating

6

Confidence

3

Soundness

3

Presentation

4

Contribution

3

Limitations

Yes

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.

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? 2. 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. 3. 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. [1] J. Adams, E. Balas, and D. Zawack. The shifting bottleneck procedure for job shop scheduling. Management Science, 34.3: 391-401, 1988. [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. [3] S. Lawrence. Resource Constrained Project Scheduling. An Experimental Investigation of Heuristic Scheduling Techniques (Supplement). Carnegie-Mellon University, 1984. [4] D. Applegate and W. Cook. A computational study of job-shop scheduling. ORSA Journal of Computing, 3.2: 149-156, 1991. [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. [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.

Questions

1. Have you explored the possibility of transitioning your work to a different variant of JSP, like FJSP? 2. 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. 3. 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?

Rating

5

Confidence

4

Soundness

3

Presentation

3

Contribution

3

Limitations

The paper has discussed some limitations in the appendix.

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.

Strengths

* The paper is clear and well written. In particular, the description of the model and the experiments is clear and detailed enough. * 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. * The strong performance on the Taillard and Demirkol datasets, even on instances with a number of jobs or machines not seen in training. * 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. 1. 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. 1. 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. 1. 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. [1] Chalumeau et al, Combinatorial Optimization with Policy Adaptation using Latent Space Search. NeurIPS 2023

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? 1. 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? 1. Eq (5): On the right hand-side, shouldn't it be $\bar{\pi}$ instead of $\pi$? 1. It would be interesting to discuss concurrent work [2] and previous work [3] which also propose self-improvement training strategies with related pseudo-labels. [2] Pirnay et al, Self-Improvement for Neural Combinatorial Optimization: Sample Without Replacement, but Improvement. Transactions on Machine Learning Research (06/2024) [3] Luo et al, Self-Improved Learning for Scalable Neural Combinatorial Optimization. arXiv:2403.19561

Rating

6

Confidence

4

Soundness

3

Presentation

3

Contribution

3

Limitations

Yes, the limitations were addressed.

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.

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. --- ### References [1r] Pirnay, Jonathan, and Dominik G. Grimm. "Self-Improvement for Neural Combinatorial Optimization: Sample without Replacement, but Improvement." arXiv preprint arXiv:2403.15180 (2024). [2r] Luo, Fu, et al. "Self-Improved Learning for Scalable Neural Combinatorial Optimization." arXiv preprint arXiv:2403.19561 (2024).

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. 2. 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?

Rating

7

Confidence

4

Soundness

3

Presentation

4

Contribution

3

Limitations

Addressed in the text. Also, see the above weaknesses.

Thanks!

Thanks for your reply. The authors resolved my concerns and ran additional experiments that demonstrated the applicability and validity of their approach. In light of this, I will raise my score and recommend the paper for acceptance.