On the Study of Curriculum Learning for Inferring Dispatching Policies on the Job Shop Scheduling

1 Introduction

The Job-shop Scheduling Problem (JSP) is a combinatorial problemwith vast implications on real-world tasks. It is formulated as a set of jobs, each consisting of a set of operations, to be processed on a set of heterogeneous machines. Furthermore, each operation has a specific machine assigned to it, and the operational time it takes to complete is known in advance. The goal is to define the scheduling order of the operations such that the total completion time or makespan is minimized. This problem applies to many tasks concerned with the optimal assignment of capital goods versus means of production, e.g., manufacturing, storage, transportation, etc. However, the JSP is an NP-hard problem, and it is therefore impractical to solve optimally. Optimization methods such as integer programming or constraint programming are computationally expensive methods that are unrealistic to use when fast solutions are required. Therefore, in practice, hand-engineered heuristics are commonly used to find approximate solutions to the problem.

However, designing such heuristic rules is a daunting task that requires specialized knowledge of the problem. In the case of the JSP, Priority Dispatch Rules (PDRs) are a family of constructive heuristics used on scheduling problems that are fast to compute and easy to implement. Although, it is not clear how to extrapolate these rules to different problems. Therefore, recent studies have focused on using Reinforcement Learning (RL) to derive domain-specific heuristics automatically. This technique is known in the literature as Neural Combinatorial Optimization (NCO). Unlike traditional PDRs that use the same dispatching rule for any instance in the problem, NCO particularizes a solution based on the instance information, which makes this technique very compelling. This technique has already demonstrated promising results in the JSP [Zhang et al.2020a,Wang et al.2021a].

This paper provides a nostrum for improving the learning strategy on the JSP using Curriculum Learning (CL). To this end, we design a problem-specific architecture and novel training approach that stresses this direction. Our main contributions are summarized below:

• This work particularizes a deep learning model to address the JSP. Particularly, we present an autoregressive model that iteratively constructs the solution based on the operations that are yet to be scheduled, as well as on the state of the machines during the resolution process. The model is equivariant w.r.t. the job information but also size-agnostic, which enables to seamlessly use it on different problem sizes and train it performing a curriculum strategy.
• We also present Reinforced Adaptive Staircase Curriculum Learning (RASCL), a novel CL strategy that improves the model's performance based on the flexible assignment of difficulty levels during the learning process. In this work, we identify the difficulty for traditional RL methods to learn on large instances of the problem. To mitigate this issue, RASCL dynamically reinforces the model by revisiting the worst-performing instances. Conducted experiments show that this strategy

presents an improvement when compared to previous CL approaches.

The aforesaid ideas deliver an improvement in the scheduling solutions when compared to state-of-the-art works on JSP [Zhang et al.2020a]. Notably, we reduce the optimality gap from 19.35% to 10.46% on Taillard's instances and from 38.43% to 18.85% on Demirkol's instances 1 .

The remainder of this paper is organized as follows. In Section 2, we present the state-of-the-art of NCO applied on the JSP. In Section 3, we provide a formal description of the method. Then, in Section 4 the architecture description, and in Section 5 the learning strategy are provided. In Section 6 the method is experimentally validated. Finally, Section 7 concludes the paper.

2 RelatedWork

The first attempts of using RL to address scheduling problems date back to the 90s [Mahadevan et al.1997,Mahadevan and Theocharous1998, Zhang and Dietterich1995]. Of specific relevance is Zhang and Dietterich's paper [Zhang and Dietterich1995] on allocating resources for NASA shuttle missions. As it was reflected in the literature, one of the advantages of using RL for such a purpose is that it can be seamlessly used for static, dynamic [Gabel and Riedmiller2008, Aydin and ¨Oztemel2000], and stochastic variants of the problem. However, due to technological limitations, this technique could only be applied to small instances of the problem, limiting its applicability significantly.

The recent rise of deep learning has allowed extrapolating this technique to more realistic problem instances. Prior works have particularized deep neural networks, e.g., Pointer Networks [Vinyals et al.2015b], to learn in combinatorial spaces. In [Bello et al.2016], deep RL was implemented for the first time to learn end-to-end solutions to combinatorial problems. The authors used the Pointer Network in an actorcritic architecture to address the Travelling Salesman Problem. Further studies implemented Transformer networks [Deudon et al.2018,Vaswani et al.2017,Kool et al.2018]. However, all these works share in common that they are based on sequenceto-sequence models, where the complete solution is output at once. Thereby, heavy sampling and searching techniques were required at interference to improve the solution. Our approach is in line with [Nazari et al.2018], where the Vehicle Routing Problem is described as a Markov Decision Process, and the solution is iteratively constructed based on sequential decisions.

In the particular case of the JSP, several techniques have been applied to learn on the problem. Imitation learning was used in [Ingimundardottir and Runarsson2018] to learn from optimal solutions on training instances that were labeled using a Mixed-Integer Programming (MIP) solver. RL has also been applied to the problem, e.g., to select pre-defined candidate PDRs according to the scheduling conditions [Aydin and ¨Oztemel2000, Lin et al.2019]. Other works have addressed the problem from a multi-agent perspective, e.g., in cooperative manufacturing [Gabel and Riedmiller2008,Waschneck et al.2018] where each agent controls a production line. Moreover, numerous examples of scheduling in many application domains, including manufacturing [Lin et al.2019,Wang et al.2021a], distributed computing [Mao et al.2019, Zhang et al.2020b, Sun et al.2021] or supply chains. Despite the effort, many of these approaches do not beat traditional heuristics. In addition, a major limitation in many of these works is that the state representation is hard-bounded by some factors (e.g., size of jobs or number of operations to consider), not enabling to scale the solution to arbitrary problem sizes.

1 Taillard and DMU datasets are publicly available on http://optimizizer.com/TA.php and http://optimizizer.com/DMU.php respectively.

Zhang et al. [Zhang et al.2020a] presented the first sizeagnostic model on the problem. It formulates the JSP as a disjunctive graph and uses a high discriminative Graph Isomorphism Network (GIN) to embed the states in the resolution procedure. They prove to capture raw features from small problem instances and successfully generalize solutions to much larger instances that the ones experienced during the training. Even though graph neural networks have shown unprecedented success embedding not-euclidean spaces, in this paper, we show that a simpler autoregressive neural network is enough to better capture the state information and infer a dispatching rule.

One of the key features of the model presented in this work is the use of CL to stress the learning capabilities of the model to even larger problem instances. This aspect has been pointed out several times in the literature, e.g. [Zheng et al.2019] employs transfer learning to reconstruct the trained policies on problems of different sizes. However, policy transfer is still relatively costly and inconvenient. Also, [Liu et al.2020] uses lifelong learning, where an agent will not only learn to optimize one specific problem instance but reuse what it has learned from previous instances. They also proposed a parallel training method that combines asynchronous updates with a deep deterministic policy gradient to speed up model training. In [Lisicki et al.2020], the authors use a CL strategy with an adaptive staircase mechanism, where, at each iteration, the model changes the difficulty level according to the model performance. In our work, we build on top of this idea, tracking the model's behavior during the learning stressing the worst-performing levels.

3 Method

In the JSP, a finite set of m jobs {Ji}mi=1 are to be processed on a finite set of n machines {Mk}nk=1 . Each job Ji consists of a sequence of n operations Oi,1 → Oi,2 → ... → Oi,n, that have to be processed in a predetermined order. For each operation, Oi,j , the machine Mk is assigned for a given processing time Di,j. The goal is to determine the scheduling order of the operations such that the total execution time or makespan is minimized.

There are several constraints that need to be taken into account when obtaining a solution on the problem:

• no-overlap constraints, determine that each machine shall process only one operation at a time;
• non-preemptive constraints, stating that once the process of an operation is initiated, it shall not be interrupted

before completion;

• precedence constraints, establishing that the order of operations inside a job Ji, where operation Oi,j+1 shall not be scheduled until the previous operation Oi,j of the job Ji is completed.

3.1 Learning the Dispatching Policy

In this work, we formulate the resolution process on the JSP as a Markov Decision Process (MDP), in which the solution is iteratively constructed according to the dispatching decisions inferred. This process resembles how constructive heuristic algorithms operate. We are therefore concerned with learning the dispatching policy that based on the state on the resolution process infers the operation to schedule next. To this end, we propose learning an autoregressive model that dispatches the operations according to the scheduling policy πθ, which is parameterized using a neural network and optimized using RL.

More formally, we consider that a solution to an instance x ∈ X of the JSP consists of t ∈ {1, ..., m · n} decision steps that correspond to the dispatching operations. We denoted as st ∈ S the state of the machinery, which evolves with the scheduling decisions at every step. The actions denoted as at ∈ A correspond to the job for which the next pending operation is dispatched at that step. The goal is therefore learning a dispatching policy π : X × S → ∆|A| that for an instance x at the resolution state st, outputs the probability distribution over the next pending operations. The transition function P : X × S × A → S corresponds to the dynamics on the problem, which are deterministic. The model dynamics are therefore expressed as

The process repeats until all operations are scheduled. At that point, the solution y is defined as the sequence of dispatch actions (a1, a2, ..., am·n).

Regarding the cost function C : X × S ×A → R, it is defined as the temporal increment in the completion time τ between two successive states

where τ(x, st) refers to the time required to complete all operations from the initial state until st, which is computed using the Gantt diagram of a given instance. The cost function can be seen as the negative of the RL reward, and it is formulated to easily apply the reward-to-go trick [Sutton and Barto2018]. This uses causality to remove the past sum over rewards so that only rewards collected after the current decision step are considered, which helps in reducing the variance of policy gradient. The makespan T(x) is therefore directly obtained as the sum of collected costs along the resolution process T (x) = ∑t Ct(x, st, at).

In order to learn the policy we resort to the Reinforce algorithm [Williams1992] and the model is optimized for minimizing the expected makespan,

Following the common variation of Policy Gradient Theorem [Sutton et al.1999], the gradient of the objective function is obtained as

(4)

where bϕ(st, x) is the baseline - the estimate of the value function at state st of the problem instance x, and G, called return, is the actual cumulative cost starting at time step t and till all n · m operations are schedule G(st, x) = ∑n·m t Ct(st, at). The baseline is computed using a critic head and it is used to reduce the variance of the gradients, and therefore, to speed up the convergence. The critic is parameterized with parameters ϕ and it is trained to minimize

3.2 Inference Strategies

As reflected in the literature [Bello et al.2016,Kool et al.2018], the greedy inference of scheduling decisions from the policy function πθ used to result in poor results in NCO. Therefore, inference strategies, although sometimes quite computationally expensive [Bello et al.2016], are commonly used to report competitive solutions. In the following, we describe the inference strategies considered in this paper:

Sampling. This technique produces several scheduling solutions by repeating the inference process directly sampling from the policy distribution. Sometimes a temperature hyperparameter is used to soften the output distribution and increase the diversity of the solutions. We denote as s the width of the sampling strategy.

POMO [Kwon et al.2020]. Policy Optimization with Multiple Optima mixes both, greedy and sampling inference strategies. At the initial state, this method rolls out p initial scheduling actions {a(1) 0 , ..., a(p) 0 }. Then, the solutions are completed using the greedy strategy. This creates p solutions to the problem {y(1) , ..., y(p) } that are evaluated to select the best one. The authors demonstrate that this approach is competitive and computationally efficient compared to the sampling strategy.

Beam search [Joshi et al.2019,Wang et al.2021a]. This strategy explores a beam of b dispatches at each decision step. At the initial state, the b most likely scheduling actions {a(1) 0 , ..., a(b) 0 } are selected. Then, at the next decision step for each candidate solution, a new set of b actions is rolled out, thus, the total number of available actions becomes b × b. To prevent the number of candidate solutions from exploding in number, beam search only selects the b candidates with the highest likelihood at each step. At the end of the inference process, b candidate solutions are created.

4 Architecture Details

Top view of the architecture. The proposed architecture is depicted in Fig. 1. The model receives the instance description x as well as the internal state during the problem resolution st and outputs π(x, st), the distribution over the next pending operations at the current decision step t. The state of the problem

Algorithm 1 RASCL algorithm

Data: Define the levels of difficulty L = {l0,...,lK} and the optimality threshold δth Initialize L = {l0}, l = l0, and k = 0 while k ≤ K do Update {g(l) | l ∈ L} according to the optimality gaps on the testing dataset. if max{g(l)} ≤ δth then Increase the difficulty k = k + 1 and L = L ∪ {lk} else Sample level l ∼ softmax({1 / g(l) | l ∈ L})) end Train policy πθ on level l end Result: Trained policy πθ

5 Learning Using a Curriculum Strategy

Curriculum Learning (CL) is a methodology that uses scenarios of increasing complexity to train the model. CL was adopted from social and educational systems to build a curricula of increasing complexity [Wang et al.2021b]. Such an approach allows the model to learn policies from the easiest scenario that can be extrapolated to harder levels of difficulty. In the case of the JSP, we identify the difficulty levels as the different sizes on the problemm×n. The bigger the number of jobs m and operations n, the harder is to learn. In this work, we consider the following most popular CL strategies:

Incremental curriculum learning (ICL). In CL a set of levels of difficulty L = {l0,...,lK} has to be predefined for performing the training. Incremental CL represents the simplest approach and it sequentially trains the model on increasing difficulty levels in a sequential manner. The drawback of this strategy is the model's tendency to catastrophic forgetting when trained on consecutive grades of complexity [Lisicki et al.2020], as previous levels of difficulty are not revisited.

Uniform curriculum learning (UCL). In uniform CL, at each iteration the model selects the training complexity with equal chances from the different difficulty levels. In this way, the model is exposed to various training levels and the policy stays inherent to different problem sizes. However, based on

consists of the following features: the index of the operations being currently processed, the status of machines and the remaining processing times. Regarding the job information, the sequencing of the operations for each job is obtained using a recurrent LSTM [Hochreiter and Schmidhuber1997] network. Once the operation sequencing is encoded, the job information is passed through a set2set module [Vinyals et al.2015a], which is particularly useful to aggregate the job descriptions in an equivariant manner. This module neglects the positioning of the jobs in the instance description, which increases the sample efficiency of the model as equivalent representations of the problem have the same representation. Finally, the embeddings of both descriptors are concatenated and passed into actor-critic networks to calculate the distribution over the dispatching actions, as well as the estimate of the return.

Operation sequencing. Considering that the dispatching actions at any given step only depend on the remaining operations, we use a LSTM network to capture this information. The LSTM operates backward, starting from the last operation in this job till the current operation. The embeding for the operation sequence is computed once for the instance description, and its result is stored for being used during the resolution process. Particularly, the index of the operation currently processed is used to select the output of the LSTM corresponding to the current step t. We denote this vector cit and it encodes the information of the pending operations for the job Ji.

Decoding the solution. The solution is sequentially constructed in an autoregressive process where at each step the model indicates the operation to dispatch next. This is done by sampling from the probability distribution the policy-head computes. The model tracks therefore the operations already scheduled and only operates over the next available operation in each job. Once the scheduling order is determined, we can compute the makespan. The model needs to track also when all the operations in a job are scheduled, as selecting the job is no longer a valid action. To this end, we use a masking scheme that operates on the policy-head and reduces to zero the chances of selecting an invalid dispatch.

the work of [Lisicki et al.2020], learning on small-size tasks is more accessible rather than sampling each training level from a uniform distribution of all sizes of interest, which eventually may not be the most helpful learning strategy.

Adaptive staircase curriculum learning (ASCL). Adaptive staircase is introduced to RL in [Lisicki et al.2020]. This strategy introduces flexibility in selecting the level of complexity during the training. Specifically, the model initializes the learning process on the easiest difficulty level l0 and adaptively increases the difficulty based on the observed optimality gap. At the level lk, ASCL revisits previous difficulty levels to not 'forget' its corresponding policies. The levels to revisit are selected are randomly selected following a uniform distribution.

Reinforced adaptive staircase CL (RASCL). In this work we propose a methodology for dynamically adjusting the difficulty between the levels. Similar to ASCL, the agent's is initiated at the lowest difficulty level l0 with the aim to make its way to the top level lK. However, the limitation of ASCL is inherent in the randomness of revisiting the previous levels.

To tackle the problem, RASCL proposes a further improvement of ASCL by revisiting the levels where model shows the worst performance. Specifically, RASCL determines the level of difficulty comparing the estimation of the return to the optimal one. To this end, this method evaluates the optimality gap g(l) for each difficulty level and establishes a policy for revisiting levels inversely proportional to the gap observed. The bigger the optimality gap achieved in a level the higher the chances to revisit the level. The complete algorithm description can be found in Algorithm 1. Particularly, the method tracks a subset of levels L from where the training is performed. The subset of levels available starts as L = {l0} and it increases during the learning. Once the set of levels L are mastered, L is augmented incorporating the next difficulty level. The condition for incorporating the next level is by comparing the maximum optimality gap on L to a predetermined threshold δth. If the model's return is below the threshold, RASCL adds the new level of difficulty. Otherwise, the method keeps training sampling instances from the current subset of levels L. The proposed algorithm reinforces the learned policy by revisiting and anchoring the most problematic difficulty levels.

6 Experimentation

Datasets. We train and evaluate our model on scheduling instances of the sizes used on Taillard's [Taillard1993] and

(a) Taillard's instances

(b) DMU's instances

Table 2: Inference strategies for RASCL on Taillard's instances. Results are reported as average Objective (Gap).

Demirkol's (DMU) [Demirkol et al.1998] datasets: 15x15, 20x15, 20x20, 30x20 and 30x15. The instances are expressed as JSP m× n, where m represents the number of jobs, and n is the number of operations. To test the model's performance, we use substantially larger instances that are not included in the training set: 50x15, 50x20, and 100x20.

Baselines. For the choice of baselines, we resort to the analysis on priority dispatch rules (PDRs) in [Sels et al.2012] and choose the most popular ones in the research community: Shortest Processing Time (SPT), Minimum Ratio of Flow Due Date to Most Work Remaining (FDD/WKR), Most Work Remaining (MWKR), Most Operations Remaining (MOPNR). Among neural combinatorial solvers, we use the latest stateof-the-art results of the graph neural model on the public JSP benchmarks presented in [Zhang et al.2020a]. For approximating the optimal solution, required when estimating the optimality gap in RASCL, we resort to the constraint programming solver of Google OR-Tools CP-SAT. In the following, we refer to the Base model as architecture presented in Fig. 1 trained for a particular size of the JSP, without performing a curriculum.

First, we train five instances of the base model on five sizes: 15x15, 20x15, 20x20, 30x15, and 30x20. Each instance of the base model is dedicated to one of five problem sizes. Then, we test all base model instances on an extended set of sizes, adding 50x15, 50x20, and 100x20. The results reflect that the model achieves best performance when trained on the smallest size 15x15, where it shows the smallest optimality gap on all testing sizes, from 14.98% for 15x15 to 9.58% for 100x20. This reflects the difficulty for the model to directly learn on larger instances of the problem.

The model's results can be improved further, as the base model trained on a small size can hardly capture all combinatorial space of action policies inherent in large-size problems. To validate this hypothesis we incorporate different CL methods in the training. We start with ICL, for which we train five instances of the base model in the following manner: the model assigned to the 15x15 size is trained on this size only, the model assigned to 20x15 is trained sequentially on the previous size, which in this case 15x15, and on its assigned 20x15 size. The same logic applies for all sizes up to 30x20, and each learning cycle takes n iterations. Fig. 3 shows the results of this approach. Here, the 20x15 model, being trained consecutively on 15x15 and 20x15 sizes, exhibits the best performance reducing the average gap across all sizes tested. However, the ICL approach has an obvious drawback. The best result is still achieved on a small-size problem, 20x15, meaning that learning on larger-size instances is still hard.

To address the problem, we test three additional CL strategies including our proposed RASCL, see Fig. 2(a). One can see that UCL generally shows near-ICL behavior, while ASCL and RASCL models demonstrate notably better performance. Particularly, RASCL shows the smallest optimality gap on all test sizes, except for 15x15, where ASCL slightly outperforms RASCL by 0.24%. The reinforced approach displays the smallest optimality gap from 10.58% for 20x15 instances to 3.96% for 100x20 instances.

We also provide in Table 2 a comparison for different inference strategies: Greedy, POMO, Sampling and Beam search, all applied to the RASCL model. POMO (p = 3) and Beam (s = 3), show very similar results, only slightly better than greedy inference. The sampling strategy (s = 128) shows the best result across all test sizes, and, consequently, it is the inference strategy used in the following experiments.

At this point, we summarize the results using RASCL at learning and Sampling as the inference strategy. Table 1(a) provides the comparison results on Taillard's dataset. RASCL model displays robust behavior on all test sizes, improving previous best results [Zhang et al.2020a] on average by 45.94%. This model shows a maximum optimality gap of 16.09% on Taillard's dataset, which is a much tighter bound than the offered by traditional PDRs.

To further test our model, we refer to DMU dataset consisting of 80 instances from 20x15 to 50x20 sizes. Table 1(b) shows outperforming behavior of RASCL model again. On average, it improves previous best results by 50.95%.

7 Conclusions and FutureWork

In this work, we present a deep-RL model to automatically learn a dispatching policy on the JSP. To this end, we formulate the resolution process as MDP, in which a solution is iteratively constructed based on intermediate states on the resolution process. In this work, we present a particularized deep learning model on the JSP that is size-agnostic and also equivariant w.r.t. the job information, which benefits the training as equivalent instances are similarly encoded. In order to improve the behavior of the model, this work relies on Curriculum Learning. In this direction, we present a novel RASCL strategy, which dynamically adjusts the difficulty of the learning according to the model's performance during the learning process. Experiments on Taillard's and Demirkol's instances show that our model improves the optimality gap w.r.t. the current state-of-the-art model by 45.94% and 50.95%, respectively. Our results corroborate that learning using a curricula is key for improving the results on the problem.

There are several future directions for this work. For example, we would like to remark the potential of this technology for addressing stochastic or partially observable problems, domains where traditional approaches have shown limited capabilities.

A Models and Configurations

We train the models using the same set of hyperparameters for every size on the problem (see Table 3). The validation set consists of 1,000 randomly generated JSP instances. Both the actor and critic utilized fully-connected networks with two layers: the first layer contained 16 neurons, while the second layer contained m neurons for the Actor and a single neuron for the Critic. ReLU activation was used for all layers. The training was conducted using the Adam optimizer with a learning rate of 10-4 and a batch size of 128. The Base, ICL and UCL models are trained for 45,000 iterations. Each model including ASCL and RASCL is tested every 100th iteration. During training, for ASCL and RASCL, a maximum gap of δth = 15% between the optimal test solutions and the model's solutions was used as the criterion for proceeding to the next level. Figure 4 shows the average makespan results for 50x15, 50x20, and 100x20 size instances during the training. Regarding the inference strategy, a tree-width of 3 is used for the Beam search and POMO selection strategies, and a sample size of 128 is used for the sampling strategy. Our implementation is available online. 2 Detailed instructions for reproducing the training, evaluation, and plotting the results are included. The model is implemented in PyTorch, and the JSP environment was created using the Gym library. The training was conducted on an NVIDIA A100 SXM 40GB GPU with 2x AMD EPYC 7742 CPUs (8 cores) and 256GB RAM. To train the RASCL model from scratch, it required approximately 8 hours using the described hardware.

2 https://github.com/Optimization-and-Machine-Learning-Lab/ Job-Shop/tree/main nips