Residual Scheduling: A New Reinforcement Learning Approach to Solving Job Shop Scheduling Problem

Summary

This paper studied the problem of learning a graph neural network based policy network as a construction heuristic for solving job shop scheduling problems. This paper proposed an idea called residual scheduling to remove irrelevant operations and machines from the graph based state representation. This has been shown experimentally to perform well on several benchmark job shop scheduling problem instances.

Strengths

With the fast advancement of deep learning technologies, it becomes increasingly interesting to develop deep neural network models that can effectively solve complex combinatorial optimization problems, including job shop scheduling problems. The newly developed deep learning system in this paper appears to be very effective and highly competitive in performance, compared to similar approaches from the literature.

Weaknesses

The idea of using graph neural networks or other forms of deep neural networks trained through reinforcement learning to solve job shop scheduling problems has been studied in many past research works. The main text of this paper lacks a comprehensive review of these research works, making it hard to clearly understand the key technical novelty and contribution of this paper, compared to other recently published works. The development of the residual scheduling technique is not strongly motivated in this paper. It is hard to understand why it is essential to remove irrelevant operations and machines from the graph based state representation. The development of this technique also appears to be very highly intuitive and lacks thorough theoretical analysis. Hence, the technical contribution of this development remains largely questionable. The authors stated that in order for the process of learning the construction heuristic to be formulated as an MDP, they introduced several attributes for the operation nodes and machine nodes in the graph based state representation. However, it remains largely unknown whether, with the introduced attributes, the state representation can satisfy the Markov property of the MDP. The importance of using any newly introduced attributes should be more thoroughly evaluated experimentally. The associated technical contributions should be clarified and strongly justified. Some other key aspects of the new system design should also be justified more. For example, the use of GIN needs to be supported with more convincing reasons. The focus on learning a construction heuristic rather than an improvement heuristic, which is gaining increasing popularity and attention, should be better justified and experimentally validated in this paper.

Questions

What are the key novelties of this research work, compared to existing deep learning based methods for combinatorial optimization, including job shop scheduling? At the theoretical level, why is it essential to remove irrelevant operations and machines from the graph based state representation? With the newly introduced attributes, why will the state representation satisfy the Markov property of the MDP? What are the theoretical and empirical advantages of learning a construction heuristic, in comparison to learning an improvement heuristic?

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

2 fair

Presentation

2 fair

Contribution

2 fair

Limitations

I do not have any concerns regarding this question.

Summary

The paper introduces a novel approach called residual scheduling for solving the Job-shop scheduling problem (JSP) and its variant, flexible JSP (FJSP), focusing on removing irrelevant machines and jobs from the consideration set. Despite these problems being NP-hard, the proposed method demonstrates state-of-the-art performance across standard benchmarks, even performing well when scaled to larger problem sizes, achieving a zero gap in 49 out of 50 instances with more than 150 jobs on 20 machines.

Strengths

The method developed claims that for the 98% of the cases, the zero gap is achieved for fairly large instances.

Weaknesses

The zero gap is mentioned. Upon reading, readers find out that the gap refers to "makespan gap." Understandably, significant bulk of existing papers on job-shop focus on makespan rather than tardiness. Ignoring tardiness may lead to poorer on time delivery, which is a weakness in itself, but with respect to the "makespan gap" measure it is not clear whether zero gap will result in zero (or small gap) is tardiness is considered or, generally, if the standard duality or MIP gaps are used instead. The gap is misleading at best.

Questions

The paper claims to beath SOTA heuristics. Lagrangian heuristic is definitely missing. How does the new method compare against Lagrangian heuristic? Understandably, Lagrangian relaxation has been used for a long time, the reviewer is asking about recent rather than historical Lagrangian heuristics, since their quality may differ.

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

In light of the above comments, the limitations are 1. only makespan is considered, 2. only one type of gap seems to be introduced and considered, and 3. major heuristics are not used/compared with.

Summary

This paper proposed DRL based method to learn dispatching polices for (flexible) job-shop scheduling problems (JSP/FJSP). The main idea is to remove the completed operations from the state embedding, which is called residual scheduling, so as to improve the representation accuracy. The DRL agent uses a graph representation, which is processed by a Graph Neural Network (GNN) architecture. Experiments on JSP and FJSP benchmarks show that the proposed residual scheduling scheme outperforms recent DRL baselines.

Strengths

1. The idea of residual scheduling makes great sense and is interesting. 2. The method is generally applicable to both JSP and FJSP, which are important scheduling problems. 3. Good empirical performance, comparing to recent DRL based scheduling methods.

Weaknesses

1. The main weakness is that the technical contribution is incremental. While the redisual scheduling idea is interesting and novel, a large part of the proposed method is similar to existing works. Specifically, the graph representation and heterogeneous graph neural network in Section 3.2 and 3.3 is similar to the heterogeneous graph and heterogeneous GNN in (Song et al., 2023). This is not mentioned in Section 3, and the differences between the proposed method and existing works are not discussed. 2. Some design choices need to be justified. Please see the below questions. 3. Empirical evaluation needs to be improved. * It is unclear whether the models in other works (e.g. L2D, SchN, DRL-G) are retrained using the same dataset as the proposed method. If not, then directly comparing their performance (even on the same benchmark instances) is not fair due to different training data. * The discussion for Figure 4 is not surprising. It is well known that for JSP, problems with larger $n/m$ ratios are easier to solve (Taillard 1993). That is why the gaps on large problems in Figure 4 are smaller. Actually this is true for most algorithms, and cannot be claimed as a major advantage of the proposed method. * Training time is not reported. 4. The authors made several inappropriate statements in the paper, mainly in introduction. The authors should be more precise about the related concepts. * In the first paragraph, it is better to describe JSP as a combinatorial optimization problem, instead of mathematical optimization. * In the second paragraph, Constraint Satisfaction Problem (CSP) should be not stated as a type of mathematical optimization. In addition, Constraint Programming (CP) here is more suitable than CSP. * In the fourth paragraph, the approaches that automate the design of heuristics should be hyperheuristics, instead of metaheuristics. 4. The language needs to be improved. Besides, there are quite a few grammar errors and typos.

Questions

1. Why use fully connected edges to link the operations in the same job? How about using only precedence relationship as a directed edge? 2. The second graph below Figure 3, for flexible problems, how to define the ready status for an operation considering there could be multiple compatible machines? 3. According to Figure 3(b), the graph embedding $h_{\mathcal{G}}^{(k)}$ is not used in the action score prediction as in Figure 3(c). So what is $h_{\mathcal{G}}^{(k)}$ used for? 4. In the experiments, to generate number of jobs and machines, why use the uniform distribution $\mathcal{U}(3, N)$ and $\mathcal{U}(3,n)$ (should be $\mathcal{U}(3,M)$ for machines)? The value 3 seems arbitrary.

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

5: You are absolutely certain about your assessment. You are very familiar with the related work and checked the math/other details carefully.

Soundness

3 good

Presentation

2 fair

Contribution

2 fair

Limitations

The authors did not give a particular discussion on the limitations. One limitation could be the computational efficiency. As shown in Table 13 in the appendix, the runtime increase rapidly with the number of jobs. This could affect both training and inference efficiency, and limit its applicability to larger problems.

Summary

This paper proposes a deep reinforcement learning-based constructive heuristic to solve the (Flexible) Job Shop Scheduling Problem. An instance of the problem is represented as a graph and fed into a Graph Neural Network-based model which outputs a score for each candidate (operation-machine) pair. The model is trained with the REINFORCE algorithm with as baseline a classic Priority Dispatching Rule-based heuristic. The novelty of the paper lies in the update of the state after each action: the graph is updated by removing the operations which have already been executed to focus on the most relevant information, which is the residual operations and remaining times of the ongoing ones. The proposed approach is experimentally shown to outperform RL-based constructive heuristics on classic JSSP and FJSSP benchmarks.

Strengths

1. Sound and interesting idea of removing irrelevant information from the state 1. The paper is fairly clear and I appreciated the illustrations Fig 1-3. 1. The model was proposed for the JSSP and easily adapted to the Flexible JSSP 1. The approach outperforms deep RL-based construction heuristics on classic benchmarks

Weaknesses

1. Limited novelty: the main contribution is the definition of the residual state at each step of the construction process by removing irrelevant operations and resetting the time reference. This seems to me an incremental improvement of the approach L2D [1], which already proposed a similar state graph representation and the use of the Graph Isomorphism Network architecture for the JSSP. 1. The proposed approach seems very specific to (F)JSSPs (state representation, baseline) and it's not clear what could be transferable to DRL heuristics for solving other optimization problems. 1. In the experiments, the presented non-learning-based baselines seem pretty weak: only greedy (see more in Questions) 1. Lots of English typos (I noted a few per page) [1] C Zhang et al, Learning to Dispatch for Job Shop Scheduling via Deep Reinforcement Learning, Neurips 2020

Questions

1. Where dos the attributes of edges (L205) appear in the GNN model (Sec 3.3)? 1. The paper claims: “Interestingly, using RS, the average gaps are nearly zero for the collections with sizes larger than 100 … A strong implication is that our RS approach can be scaled up for job sizes and even reach the optimal for sufficient large job count.” Do you have an idea of why the model would work better on unseen large instances versus instances of the same size as the training ones? Does OR-tools return the optimal solutions for these larger instances? Can it be that the quality of the reference solutions decreases and therefore the “optimality” gap becomes smaller? 1. Are there stronger non-learning-based baselines for the JSPP other than the greedy PDR heuristics presented in Table 2? To be able to appreciate the performance of the proposed approach, it would be useful and more convincing to compare it to the best heuristics for this problem, beyond simple greedy ones. For example maybe [2]? 1. Appendix, Algorithm 1, Line 6: to compute this makespan at state s_t, given action a_t, do you do a rollout of the current policy \pi_{\theta} with the updated parameter \theta? This would mean doing a rollout until the end of both the baseline and current policy at each step of the trajectory? How long did the training take? 1. How is the average computation time computed? (Table 13) In particular, was the policy applied to each instance individually or were instances batched? 1. The discussion L322 about the time it takes for RS/L2D/ScheduleNet versus OR-Tools can be a bit misleading: OR-tools is an exact solver. If spends a lot of time proving the optimality of the solution. Probably it could return a good quality solution much faster if used as a heuristic. In addition it runs on CPUs and not GPUs therefore just comparing the time is not really fair. [2] CY Zhang, A tabu search algorithm with a new neighborhood structure for the job shop scheduling problem, Computers & Operations Research, 2007

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

5: You are absolutely certain about your assessment. You are very familiar with the related work and checked the math/other details carefully.

Soundness

2 fair

Presentation

2 fair

Contribution

2 fair

Limitations

Not explicitly addressed by the paper.