# Randomized Greedy Sampling for JSSP

Henrik Abgaryan, Ararat Harutyunyan, Tristan Cazenave

► To cite this version:

Henrik Abgaryan, Ararat Harutyunyan, Tristan Cazenave. Randomized Greedy Sampling for JSSP. The 18th Learning and Intelligent Optimization Conference (LION 2024), Jun 2024, Île d'Ischia, Italy. pp.1-12, 10.1007/978-3-031-75623-8_1 . hal-05418033

HAL Id: hal-05418033

https://hal.science/hal-05418033v1

Submitted on 15 Dec 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

Public Domain
# Randomized Greedy Sampling for JSSP

Henrik Abgaryan, Ararat Harutyunyan, and Tristan Cazenave

LAMSADE, Université Paris Dauphine - PSL, CNRS, Paris, France

**Abstract.** The job shop scheduling problem (JSSP) is a fundamental challenge in the field of operations research and manufacturing, representing the task of optimally assigning a set of jobs to a limited number of machines to optimize one or more objectives, such as minimizing the total processing time or reducing the delay of jobs. In recent years, AI-driven methods have introduced new approaches to solving the JSSP. Continuous exploration in deep reinforcement learning (DRL) is currently concentrated on refining strategies to address the JSSP. Established DRL techniques mostly focus on better modeling and training of the Policy networks for solving JSSP problems. This paper explores the utilization of Policy networks in search algorithms. We propose two novel algorithms, Random Second Greedy Choice (RSGC) and Greedy Sampling (GS). RSGC and GS employ a randomized approach to consider alternative paths, deviating from the primary heuristic, while adjusting the probability of selecting these paths dynamically during the search process. Through experimentation, we show the effectiveness of the proposed algorithms in comparison to the usual greedy first choice inference technique and the usual sampling method.

**Keywords:** Job Shop Scheduling, RSGC, GS, GNN, reinforcement learning, limited discrepancy search, sampling, search algorithms

## 1 Introduction

The job shop scheduling problem (JSSP) stands as a pivotal challenge in operations research and manufacturing [9]. This problem entails a set of jobs, each bound by specific processing rules (like the sequential use of assigned machines), across a variety of machines. The aim here is to optimize certain parameters such as the overall completion time, workflow duration, or delay minimization.

It is proved that for JSSP instances having more than 2 machines is NP-hard [10]. Therefore, deriving precise solutions for JSSP is generally unfeasible, thereby making heuristic and approximate strategies more common for practical efficiency [6]. Traditional approaches to this problem have predominantly relied on search and inference techniques developed by the constraint programming community [1]. These techniques effectively utilize constraints to define the relationships and limitations between jobs and resources, thus enabling efficient exploration of feasible solution spaces and the identification of optimal or near-optimal schedules [13]. Another common technique is the Priority dispatching rule (PDR). It is a heuristic method that is widely used in real-world scheduling systems [17]. However, designing an effective PDR is very time-consuming, it requires solid domain knowledge for complex JSSP problems. Another
approach for finding suboptimal solutions is through the help of Deep Learning and
Neural Networks [3], [18]. The method based on learning can generally be categorized
into two paradigms: supervised learning and reinforcement learning (RL). Ongoing re-
search in deep reinforcement learning (DRL) is actively focused on developing new
and improved methods to tackle the JSSP. Existing DRL methods represent Job Shop
Scheduling Problem (JSSP) as a Markov decision process (MDP) and then learn the
Policy network based on DRL. The prevailing trend leans towards refining policy net-
works or MDP formulation to generate better solutions. However, the exploration of
effective search methods on top of the policy networks decisions and the integration of
alternative strategies such as tree search, have received less attention. This indicates a
potential area for further research.

In this paper, we present two search algorithms RSGC, GS, provided by pretrained
Policy network inspired by [11] that utilize the categorical distribution of the pretrained
Policy network to find a solution to JSSP problem. In order to check the effectiveness
of the proposed search methods, we have experimented on 2 public test datasets: TA
dataset [15], and DMU dataset [7]. Then we compare the results of RSGC and GS to
the usual sampling algorithm and the current state-of-the-art results [18].

## 2 Related Work

The success of Deep Reinforcement Learning (DRL) represents a significant advance-
ment in the field of artificial intelligence. Generally, DRL combines the principles of
deep learning and reinforcement learning, enabling computers to learn complex behav-
iors by interacting with an environment and optimizing actions based on feedback.

In [12] the authors utilized deep Q-network (DQN) to solve a JSSP in semicon-
ductor manufacturing plant. In [18], a new method using Deep Reinforcement Learn-
ing (DRL) is introduced to develop effective Priority Dispatching Rules (PDRs) for
the Job Shop Scheduling Problem (JSSP). The approach involves formulating an MDP
(Markov Decision Process) for PDR-oriented scheduling. This method utilizes a dis-
junctive graph representation of JSSP to capture the states, efficiently integrating oper-
ation dependencies and machine statuses for informed scheduling decisions. Addition-
ally, the paper uses a Graph Isomorphism Network (GIN) strategy that efficiently en-
codes disjunctive graph nodes into fixed-dimensional embeddings. On top of the these
embeddings the authors utilized Proximal Policy Optimization (PPO) algorithm [14] to
train Policy network. [16] introduces a new approach for solving JSSP with DRL. It
addresses the deficiencies in state representation, adding more features. This approach
also models JSSP as a Markov decision process, employing a new state representation
based on bidirectional scheduling. This representation allows the agent to capture more
effective state information and avoid the issue of multiple optimal action selections.
They also utilize the technique of Invalid Action Masking (IAM), which narrows the
search space, steering the agent away from sub-optimal solutions.

Current methods are mostly based on modeling state representation and the archi-
tecture of the models. There are very few papers that use sampling or search algorithms
on top of policy network to solve JSSP. A widely recognized strategy is to facilitate
the step-by-step development of solutions to JSSP problems, guided by a single-shot
(greedy) policy derived from a neural network, as documented in sources like [18] and
[16]. These methods primarily concentrate on developing robust policy network models,
aiming to elevate the quality of solutions generated in a single iteration as close to the
optimal as possible. However, there is a noticeable scarcity of studies dedicated to find-
ing effective inference methods for neural JSSP. In addition to designing and training
high-quality policy networks, devising an effective inference strategy is equally crucial
to maximize the quality of solutions within a specified time budget. In contrast, neural
construction methods focus on generating solutions by sampling from the neural net-
work's output probability distributions, a technique highlighted in studies such as [2].
An alternative approach to sampling is the use of Monte-Carlo Tree Search (MCTS) [4],
and its variants [5]. These methods create partial solutions within a search tree using
rollouts. MCTS requires a lot of resources and long running time. Beam search rep-
resents another method used in combinatorial optimization problems [8]. Nevertheless,
beam search operates on a greedy algorithm, which unconditionally adheres to the neu-
ral network's predictions, regardless of their accuracy. Like MCTS, Beam search also
requires a lot of resources and long running time. Another approach called Limited Dis-
crepancy Search (LDS) incorporates the idea of deviating from the main heuristic and
sometimes selecting less promising choices [11]. It is based on the idea that sometimes,
choosing solutions that don't initially seem promising might actually lead to better re-
sults. This approach acknowledges that the most obvious choice is not always the best
one.

In developing our approach, we focus on a key strategy: introducing variations to the
primary heuristic, specifically diverging from the initial greedy choice recommended by
the policy network. This strategy lays the groundwork for our newly designed proba-
bilistic sampling algorithms. The essence of these algorithms lies in the smart utilization
of the Policy network's probability distribution also incorporating a measure of random-
ness to enrich decision-making processes. By integrating randomness at the beginning
of our algorithm, it diverges from conventional deterministic methods, offering a nu-
anced way to explore the search space. It harnesses the robustness of greedy strategies
while mitigating their inherent limitations through calculated randomness. This hybrid
approach aims to strike a balance between the exploration and exploitation, optimizing
the search process.

3 Preliminary

The Job-Shop Scheduling Problem (JSSP) is formally defined as a problem involving
a set of jobs *J* and a set of machines *M*. The size of the JSSP problem instance is
described as *N*\_J × *N*\_M, where *N*\_J represents the number of jobs and *N*\_M the
number of machines. For each job *J*<sub>*i*</sub> ∈ *J*, it must be processed through *n*<sub>*i*</sub> machines in
a specified order *O*<sub>*i*1</sub> → ... → *O*<sub>*in*<sub>*i*</sub></sub>, where each *O*<sub>*ij*</sub> (for 1 ≤ *j* ≤ *n*<sub>*i*</sub>) represents
an operation of *J*<sub>*i*</sub> with a processing time *p*<sub>*ij*</sub> ∈ N. This sequence also includes a
precedence constraint. Each machine can process only one job at a time, and switching
jobs mid-operation is not allowed. The objective of solving a JSSP is to determine a
schedule, that is, a start time *S*<sub>*ij*</sub> for each operation *O*<sub>*ij*</sub>, to minimize the makespan
$C_{\max} = \max_{i,j}\{C_{ij} = S_{ij} + p_{ij}\}$ while meeting all constraints. The complexity of a JSSP instance is given by $N_J \times N_M$.

Furthermore, a JSSP instance can be represented through a disjunctive graph, a concept well-established in the literature [18]. Let $O = \{O_{ij} | \forall i, j\} \cup \{S, T\}$ represent the set of all operations, including two dummy operations *S* and *T* that denote the starting and ending points with zero processing time. A disjunctive graph $G = (O, C, D)$ is thus a mixed graph (a graph consisting of both directed edges (arcs) and undirected edges) with *O* as its vertex set. Specifically, *C* comprises of directed arcs (conjunctions) that represent the precedence constraints between operations within the same job, and *D* includes undirected arcs (disjunctions) connecting pairs of operations that require the same machine. Solving a JSSP is equivalent to determining the direction of each disjunctive arc such that the resulting graph becomes a Directed Acyclic Graph (DAG) [18]. Markov Decision Process Formulation (MDP), state representation, action space, state transition follow the methods described in [18]. An action $a_t \in A_t$ is an eligible operation at decision step *t*. The Policy is a neural network $\pi(a_t|s_t)$ that outputs a distribution over the actions in $A_t$. We use the same 2D raw features as in [18], namely a binary indicator $I(O, s_t)$ which equals to 1 only if *O* is scheduled in $s_t$, and an integer CLB(*O*, $s_t$) which is the lower bound of the estimated time of completion (ETC) of *O* in $s_t$. The training has been done using Proximal Policy algorithm, which is an actor-critic algorithm [14]. "Actor" denotes the Policy network, whereas the "critic" is a distinct network that evaluates the outcomes of the decisions made by the Policy network. Both the Actor (Policy) network and the Critic network have multilayer perceptron architecture. We use the same Graph Isomorphism Network (GIN) as feature extractor, the Actor and the Critic networks as presented in [18]. GIN extracts feature embeddings of each node in an iterative and non-linear fashion. Then the Policy network uses these fixed-size embeddings for outputting a distribution over the actions. The training has been done on 20x20 training instances for 10000 steps. The training is as described in [18]. Because the Policy network is based on the fixed-sized embeddings outputted by the GIN network, it is size-agnostic which enables generalization to instances of different sizes without requiring any additional training. During the training we sample the actions according to the probability distribution outputted by the Policy network. During the inference time we utilize our search algorithms over the probability distribution outputted by the Policy network.

# 4 Search Algorithm

Finding the right action $a_t$ at each state $s_t$ is a search problem, where the Policy network $\pi(a_t|s_t)$ is used as a heuristic. When the $\pi(a_t|s_t)$ is trained and is ready for the inference, the usual method is to pick the first greedy choice action $a_t$, where $a_t$ is the action with the highest probability at the state $s_t$, according to the categorical probability distribution of $\pi(a_t|s_t)$.

Our approach is slightly different; we formulate the problem of selecting the "correct" action $a_t$ at each state $s_t$ as a search problem. Let us denote by *T* the binary search tree. At each node $n_i$ of the search tree *T* there are two options: selecting the action with the highest probability (the first greedy choice), or another action according to the
probability distribution recommended by $\pi(a_t|s_t)$. Then the height of the search tree $T$ becomes $h = N_J \times N_M$. At each node $n_i$ the approach of [18] is to always choose the first greedy choice, action $a_t$ with the highest probability at the state $s_t$. However as described in [11], always following the heuristic, or in our case only the first greedy choice recommended by $\pi(a_t|s_t)$, might not lead to the best possible solution. We argue that doing "discrepancies" or deviating from the first greedy choice of $\pi(a_t|s_t)$ can sometimes be better. In the context of the search trees, a "discrepancy" refers to a deviation from the most preferred or recommended path, typically represented as taking a right turn in a binary search tree that is organized based on heuristic evaluations (where the left path is usually considered the default or the more promising direction based on some criteria). There is a systematic approach of considering all of the paths in a binary search tree, as described in [11]. This systematic approach allows the search to first consider paths that are closely aligned with heuristic recommendations, and only later to explore less recommended paths. But this method can quickly become unfeasible when the search tree is large, in our case when the set of jobs $J$ and a set of machines $M$ is large. Our Algorithm (RSGC) Random Second Greedy Choice with Decreasing Probability gets inspiration from [11], but it also utilizes randomness. The pseudo code of our algorithm is presented in Algorithm 1. Our algorithm has two hyperparameters $D_{min}$ and $D_{max}$, which are the least possible and the most possible second greedy choices we can make during the search. At each node $n_i$ of the search tree $T$ we compute the probability (based on the hyperparameters) of selecting the second greedy choice action. At the beginning, the probability of selecting the second greedy choice action is high. The probability then decreases as we make more and more greedy second choices. The *greedy_2nd_action_count* is the number of second greedy choices done so far. Initially, *total_num_greedy_2nd_action_count* is set to $D_{min}$. The full search is done using this fixed hyperparameter $D_{min}$ obtaining the first makespan. Then we adjust the value of *total_num_greedy_2nd_action_count* by increasing it by an amount of 5% of the height $h$, obtaining the next makespan. We repeat this process until *total_num_greedy_2nd_action_count* reaches $D_{max}$. We then choose the best makespan.

$$ probability\_of\_2nd\_action = 1 - \frac{greedy\_2nd\_action\_count}{total\_num\_greedy\_2nd\_action\_count} $$

The idea is that it is harder for the policy network to select correct actions at the beginning of the search, than at the end. Through extensive experimentation, we found that it is best to start to do around 0.25h second greedy choice actions. We increment the value of 0.25h by 0.01h for each subsequent iteration until we reach 0.75h (i.e., $D_{min} = 0.25h$ and $D_{max} = 0.75h$). This methodical approach facilitates a more effective exploration of options, thereby aiding in the identification of the optimal path characterized by the minimal completion time (*makespan*).

We also have a second similar algorithm called Greedy Sampling (GS). In GS instead of randomly selecting second probable action in line 14 of the Algorithm 1 (RSGC) we randomly sample an action according to the probability distribution recommended by the policy network $\pi(a_t|s_t)$. Note that this is not the usual sampling algorithm, as we decide whether we sample or just take the first greedy choice with
probability *probability_of_2nd_action*. In the Experimental section we compare the results of these two algorithms with the usual sampling algorithm.

<caption>**Algorithm 1 (RSGC) Random Second Greedy Choice with Decreasing Probability**</caption>

**Require:** *dataset*
**Ensure:**
    1: $h \leftarrow N_J \times N_M$
    2: $D_{min} \leftarrow \text{integer}(0.25 \times h)$
    3: $D_{max} \leftarrow \text{integer}(0.75 \times h)$
    4: Initialize results list
    5: **for** each *data* in *dataset* **do**
        6:     Initialize best makespan tracking list
        7:     **for** total_num_greedy_2nd_action_count in $D_{min}$ to $D_{max}$ **do**
        8:         Reset environment with *data*
        9:         Initialize episode reward and *greedy_2nd_action_count*
    10:     **while** not Terminal **do**
    11:         *categorical_policy_distribution* $\leftarrow$ inference with policy network $\pi(a_t|s_t)$
    12:         *probability_of_2nd_action* = 1 - $\frac{\text{greedy_2nd_action_count}}{\text{total_num_greedy_2nd_action_count}}$
    13:         $r \sim \text{Uniform}(0, 1)$
    14:         **if** $r < \text{probability_of_2nd_action}$ **then**
    15:             Select the second probable action from *categorical_policy_distribution*
    16:         Increment *greedy_2nd_action_count*
    17:     **else**
    18:         **end if**
    19:     Execute the action
    20:     **end while**
    21:     Update best makespan if current makespan is better
    22:     Record makespan
    23:     **end for**
    24:     Save results for current data instance
    25:     **end for**
    26:     **return** Results list

# 5 Experimental Results

In order to show the effectiveness of our searching algorithm, we have conducted experiments on well known TA dataset [15], and DMU dataset [7]. The Policy network is trained on instances of size $N_J = 20$ and $N_M = 20$. We also compare the results with those of [18]. Each run of our search algorithm makes ($D_{max} - D_{min}$) $\times h$ calls to the Policy network, where $h = N_J \times N_M$ is the height of the search tree. During the experiments we have repeated the search algorithms 10 times and noted the overall minimum and the average makespans on the corresponding tables. We compare the makespans of (RSGC) Algorithm 1 with Greedy Sampling (Ours-GS). The two algorithms just differ on line 14 of the Algorithm 1, where instead of the Greedy second choice we randomly sample an action from the probability distribution provided by the
pre-trained Policy network. For the Taillard dataset instances 50 × 15, 50 × 20 and 100 × 20 and also for the DMU dataset 40 × 15, 40 × 20, 50 × 15, 50 × 20 we compared the best result of [18], which was inferred with Policy network trained on 30 × 20 instances. We have also tried to run beam search algorithm, however we had to keep many copies of the environment, and due to memory constraints it was unfeasible.

## 5.1 Result on Taillard's Benchmark Dataset

<table><caption>Table 1: Results on Taillard's Benchmark (Part I). Ours - RSGC is the result of the Algorithm 1. In Ours-GS instead of randomly selecting second probable action in line 14 of the Algorithm 1 (RSGC) we randomly sample an action according to the probability distribution recommended by the policy network $\pi(a_t|s_t)$. We repeat each experiment 10 times due to the algorithm's randomness and record the minimum and the average makespan across the 10 experiment. The "Samp (min)" and the "Samp (avg)" columns are the results of the usual sampling method. The "UB" column represents the best-known solutions from literature, with "*" indicating optimal solutions.</caption><thead><tr><th>Instance</th><th>L2D</th><th>Ours-RS (min)</th><th>Ours-RS (avg)</th><th>Ours-RSGC (min)</th><th>Ours-RSGC (avg)</th><th>Samp (min)</th><th>Samp (avg)</th><th>UB</th></tr></thead><tbody><tr><td colspan="9" style="text-align:center; font-weight:bold;">15x15</td></tr><tr><td>Ta01</td><td>1443 (17.22%)</td><td>1401 (13.81%)</td><td>1413.4 (14.79%)</td><td><strong>1387 (12.66%)</strong></td><td>1403.9 (14.03%)</td><td>1444(17.30%)</td><td>1448.3(17.65%)</td><td>1231*</td></tr><tr><td>Ta02</td><td>1544 (24.12%)</td><td>1404 (12.86%)</td><td>1404.0 (12.86%)</td><td><strong>1361 (9.40%)</strong></td><td>1394 (12.06%)</td><td>1447(16.32%)</td><td>1462.0(17.52%)</td><td>1244*</td></tr><tr><td>Ta03</td><td>1440 (18.23%)</td><td>1420 (16.59%)</td><td>1420.6 (16.64%)</td><td><strong>1408 (15.60%)</strong></td><td>1430.1 (17.40%)</td><td>1447(18.80%)</td><td>1452.6(19.26%)</td><td>1218*</td></tr><tr><td>Ta04</td><td>1637 (39.32%)</td><td><strong>1412 (20.17%)</strong></td><td>1412.7 (20.23%)</td><td><strong>1423 (21.11%)</strong></td><td>1433.8 (22.04%)</td><td>1460(24.26%)</td><td>1484.0(26.30%)</td><td>1175*</td></tr><tr><td>Ta05</td><td>1619 (32.27%)</td><td><strong>1394 (13.89%)</strong></td><td>1410.0 (15.20%)</td><td>1431 (16.91%)</td><td>1435.7 (17.29%)</td><td>1437(17.40%)</td><td>1448.0(18.30%)</td><td>1224*</td></tr><tr><td>Ta06</td><td>1601 (29.32%)</td><td><strong>1392 (12.44%)</strong></td><td>1401.8 (13.23%)</td><td>1413 (14.12%)</td><td>1418.3 (14.55%)</td><td>1444(16.64%)</td><td>1444.6(16.69%)</td><td>1238*</td></tr><tr><td>Ta07</td><td>1568 (27.79%)</td><td>1402 (14.26%)</td><td>1411.5 (15.03%)</td><td><strong>1384 (12.78%)</strong></td><td>1392.3 (13.45%)</td><td>1451(18.26%)</td><td>1469.0(19.72%)</td><td>1227*</td></tr><tr><td>Ta08</td><td>1468 (20.62%)</td><td><strong>1372 (12.73%)</strong></td><td>1380.1 (13.39%)</td><td>1404 (15.36%)</td><td>1406.4 (15.53%)</td><td>1425(17.09%)</td><td>1427.3(17.28%)</td><td>1217*</td></tr><tr><td>Ta09</td><td>1627 (27.70%)</td><td>1483 (16.41%)</td><td>1491.4 (17.05%)</td><td><strong>1467 (15.15%)</strong></td><td>1469.4 (15.34%)</td><td>1544(21.19%)</td><td>1546.0(21.35%)</td><td>1274*</td></tr><tr><td>Ta10</td><td>1527 (23.04%)</td><td><strong>1401 (12.89%)</strong></td><td>1419.1 (14.34%)</td><td>1437 (15.79%)</td><td>1444.4 (16.39%)</td><td>1444(16.36%)</td><td>1466.6(18.18%)</td><td>1241*</td></tr><tr><td colspan="9" style="text-align:center; font-weight:bold;">20x15</td></tr><tr><td>Ta11</td><td>1794 (32.19%)</td><td><strong>1583 (16.65%)</strong></td><td>1622.4 (19.57%)</td><td>1617 (19.16%)</td><td>1631.1 (20.18%)</td><td>1668(22.92%)</td><td>1684.1(24.10%)</td><td>1357*</td></tr><tr><td>Ta12</td><td>1805 (32.01%)</td><td>1590 (16.31%)</td><td>1595.1 (16.68%)</td><td><strong>1568 (14.70%)</strong></td><td>1573.6 (15.11%)</td><td>1658(21.29%)</td><td>1665.0(21.80%)</td><td>1367*</td></tr><tr><td>Ta13</td><td>1932 (43.85%)</td><td>1628 (21.22%)</td><td>1634.5 (21.69%)</td><td><strong>1619 (20.55%)</strong></td><td>1619.0 (20.55%)</td><td>1693(26.06%)</td><td>1697.0(26.36%)</td><td>1343*</td></tr><tr><td>Ta14</td><td>1664 (23.72%)</td><td><strong>1596 (18.66%)</strong></td><td>1600.3 (18.97%)</td><td>1604 (19.26%)</td><td>1624.7 (20.78%)</td><td>1640(21.93%)</td><td>1651.1(22.76%)</td><td>1345*</td></tr><tr><td>Ta15</td><td>1730 (29.20%)</td><td><strong>1625 (21.36%)</strong></td><td>1629.1 (21.65%)</td><td>1633 (21.96%)</td><td>1640.1 (22.47%)</td><td>1690(26.21%)</td><td>1694.9(26.58%)</td><td>1339*</td></tr><tr><td>Ta16</td><td>1710 (25.74%)</td><td>1613 (18.60%)</td><td>1641.6 (20.71%)</td><td><strong>1598 (17.50%)</strong></td><td>1610.1 (18.39%)</td><td>1693(24.49%)</td><td>1696.3(24.73%)</td><td>1360*</td></tr><tr><td>Ta17</td><td>1897 (29.75%)</td><td><strong>1728 (18.19%)</strong></td><td>1728.0 (18.19%)</td><td>1735 (18.66%)</td><td>1736.5 (18.76%)</td><td>1797(22.91%)</td><td>1798.0 (22.98%)</td><td>1462*</td></tr><tr><td>Ta18</td><td>1794 (28.51%)</td><td><strong>1664 (19.20%)</strong></td><td>1667.9 (19.49%)</td><td>1675 (20.00%)</td><td>1679.0 (20.34%)</td><td>1712(22.64%)</td><td>1712.3(22.66%)</td><td>1396</td></tr><tr><td>Ta19</td><td>1682 (26.28%)</td><td><strong>1591 (19.44%)</strong></td><td>1602.2 (20.29%)</td><td>1592 (19.52%)</td><td>1603.5 (20.39%)</td><td>1650(23.87%)</td><td>1653.8(24.16%)</td><td>1332*</td></tr><tr><td>Ta20</td><td>1739 (28.97%)</td><td>1635 (21.29%)</td><td>1635.0 (21.29%)</td><td><strong>1628 (20.77%)</strong></td><td>1657.7 (22.98%)</td><td>1666 (23.59%)</td><td>1666.3 (23.61%)</td><td>1348*</td></tr><tr><td colspan="9" style="text-align:center; font-weight:bold;">20x20</td></tr><tr><td>Ta21</td><td>2252 (37.18%)</td><td>1964 (19.61%)</td><td>1973.5 (20.18%)</td><td><strong>1905 (16.02%)</strong></td><td>1914.6 (16.60%)</td><td>2021(23.08%)</td><td>2044.0(24.48%)</td><td>1642*</td></tr><tr><td>Ta22</td><td>2102 (31.38%)</td><td>1887 (17.94%)</td><td>1895.7 (18.48%)</td><td><strong>1853 (15.81%)</strong></td><td>1854.6 (15.91%)</td><td>1950(21.88%)</td><td>1953.7(22.11%)</td><td>1600</td></tr><tr><td>Ta23</td><td>2085 (33.91%)</td><td>1838 (18.05%)</td><td>1841.0 (18.24%)</td><td><strong>1818 (16.76%)</strong></td><td>1822.9 (17.05%)</td><td>1902(22.16%)</td><td>1918.8(23.24%)</td><td>1557</td></tr><tr><td>Ta24</td><td>2200 (33.82%)</td><td>1930 (17.40%)</td><td>1931.2 (17.48%)</td><td><strong>1907 (16.00%)</strong></td><td>1916.2 (16.54%)</td><td>1986(20.80%)</td><td>2035.3(23.80%)</td><td>1644*</td></tr><tr><td>Ta25</td><td>2201 (38.00%)</td><td>1918 (20.25%)</td><td>1924.4 (20.65%)</td><td><strong>1903 (19.31%)</strong></td><td>1904.6 (19.42%)</td><td>1997(25.20%)</td><td>2002.2(25.53%)</td><td>1595</td></tr><tr><td>Ta26</td><td>2176 (32.44%)</td><td>1961 (19.36%)</td><td>1970.4 (19.91%)</td><td><strong>1918 (16.73%)</strong></td><td>1928.9 (17.38%)</td><td>2014(22.58%)</td><td>2042.2(24.30%)</td><td>1643</td></tr><tr><td>Ta27</td><td>2132 (26.90%)</td><td><strong>2019 (20.18%)</strong></td><td>2028.8 (20.76%)</td><td>2026 (20.60%)</td><td>2026.0 (20.60%)</td><td>2092(24.52%)</td><td>2099.0(24.94%)</td><td>1680</td></tr><tr><td>Ta28</td><td>2146 (33.94%)</td><td>1883 (17.47%)</td><td>1886.6 (17.68%)</td><td><strong>1833 (14.35%)</strong></td><td>1841.5 (14.87%)</td><td>1947(21.46%)</td><td>1954.8(21.95%)</td><td>1603*</td></tr><tr><td>Ta29</td><td>1952 (20.12%)</td><td>1885 (16.00%)</td><td>1905.8 (17.28%)</td><td><strong>1877 (15.51%)</strong></td><td>1897.4 (16.76%)</td><td>1937(19.20%)</td><td>1984.4 (22.12%)</td><td>1625</td></tr><tr><td>Ta30</td><td>2035 (28.47%)</td><td><strong>1868 (17.93%)</strong></td><td>1868.8 (17.98%)</td><td>1876 (18.43%)</td><td>1892.2 (19.44%)</td><td>1927(21.65%)</td><td>1934.6(22.13%)</td><td>1584</td></tr><tr><td colspan="9" style="text-align:center; font-weight:bold;">30x15</td></tr><tr><td>Ta31</td><td>2565 (45.37%)</td><td><strong>2115 (19.91%)</strong></td><td>2121.0 (20.24%)</td><td>2169 (22.94%)</td><td>2183.5 (23.81%)</td><td>2170(23.02%)</td><td>2183.1(23.76%)</td><td>1764*</td></tr><tr><td>Ta32</td><td>2388 (33.87%)</td><td><strong>2212 (23.99%)</strong></td><td>2212.0 (23.99%)</td><td>2230 (24.94%)</td><td>2242.1 (25.65%)</td><td>2303(29.09%)</td><td>2318.0(29.93%)</td><td>1784</td></tr><tr><td>Ta33</td><td>2324 (29.80%)</td><td><strong>2204 (23.09%)</strong></td><td>2219.0 (23.92%)</td><td>2292 (28.03%)</td><td>2299.5 (28.45%)</td><td>2301(28.48%)</td><td>2307.8(28.86%)</td><td>1791</td></tr><tr><td>Ta34</td><td>2332 (27.60%)</td><td><strong>2207 (20.75%)</strong></td><td>2226.3 (21.81%)</td><td>2225 (21.74%)</td><td>2225.7 (21.79%)</td><td>2250(23.09%)</td><td>2262.7(23.78%)</td><td>1828*</td></tr><tr><td>Ta35</td><td>2505 (24.82%)</td><td><strong>2250 (12.08%)</strong></td><td>2260.5 (12.63%)</td><td>2256 (12.39%)</td><td>2256.0 (12.39%)</td><td>2293(14.25%)</td><td>2303.0(14.75%)</td><td>2007*</td></tr><tr><td>Ta36</td><td>2497 (37.31%)</td><td><strong>2243 (23.31%)</strong></td><td>2252.1 (23.83%)</td><td>2253 (23.87%)</td><td>2259.1 (24.22%)</td><td>2318(27.43%)</td><td>2320.6 (27.58%)</td><td>1819*</td></tr><tr><td>Ta37</td><td>2325 (31.28%)</td><td><strong>2146 (21.20%)</strong></td><td>2157.1 (21.79%)</td><td>2159 (21.93%)</td><td>2168.0 (22.44%)</td><td>2181(23.15%)</td><td>2213.4(24.98%)</td><td>1771*</td></tr><tr><td>Ta38</td><td>2302 (37.61%)</td><td>2046 (22.30%)</td><td>2048.6 (22.45%)</td><td><strong>2014 (20.38%)</strong></td><td>2017.8 (20.63%)</td><td>2079(24.27%)</td><td>2114.9(26.41%)</td><td>1673*</td></tr><tr><td>Ta39</td><td>2410 (34.26%)</td><td><strong>2152 (19.94%)</strong></td><td>2152.8 (19.99%)</td><td>2160 (20.33%)</td><td>2166.8 (20.77%)</td><td>2181(21.50%)</td><td>2199.7(22.55%)</td><td>1795*</td></tr><tr><td>Ta40</td><td>2140 (28.21%)</td><td>2002 (19.95%)</td><td>2018.5 (20.93%)</td><td><strong>1989 (19.17%)</strong></td><td>1989.0 (19.17%)</td><td>2067(23.85%)</td><td>2083.4(24.83%)</td><td>1669</td></tr></tbody></table>

Continued on next page
<table><caption>Table 1 continued from previous page</caption><thead><tr><th>Instance</th><th>L2D</th><th>Ours-GS (min)</th><th>Ours-GS (avg)</th><th>Ours-RSGC (min)</th><th>Ours-RSGC (avg)</th><th>Samp (min)</th><th>Samp (avg)</th><th>UB</th></tr></thead><tbody><tr><td colspan="9" style="text-align:center; font-weight:bold;">30x20</td></tr><tr><td>Ta41</td><td>2667 (33.02%)</td><td><strong>2489 (24.14%)</strong></td><td>2507.5 (25.06%)</td><td>2490 (24.19%)</td><td>2496.4 (24.51%)</td><td>2540 (26.68%)</td><td>2568.7 (28.11%)</td><td>2005</td></tr><tr><td>Ta42</td><td>2664 (37.53%)</td><td>2383 (23.03%)</td><td>2383.0 (23.03%)</td><td><strong>2358 (21.73%)</strong></td><td>2373.1 (22.51%)</td><td>2479 (27.98%)</td><td>2490.3 (28.56%)</td><td>1937</td></tr><tr><td>Ta43</td><td>2431 (31.69%)</td><td>2347 (27.14%)</td><td>2364.8 (28.10%)</td><td><strong>2332 (26.33%)</strong></td><td>2332.0 (26.33%)</td><td>2437 (32.02%)</td><td>2457.6 (33.13%)</td><td>1846</td></tr><tr><td>Ta44</td><td>2714 (37.14%)</td><td>2512 (26.93%)</td><td>2515.2 (27.09%)</td><td><strong>2471 (24.86%)</strong></td><td>2482.2 (25.43%)</td><td>2590 (30.87%)</td><td>2595.8 (31.17%)</td><td>1979</td></tr><tr><td>Ta45</td><td>2637 (31.85%)</td><td>2435 (21.75%)</td><td>2440.7 (22.03%)</td><td><strong>2380 (19.00%)</strong></td><td>2410.8 (20.54%)</td><td>2518 (25.90%)</td><td>2530.5 (26.53%)</td><td>2000</td></tr><tr><td>Ta46</td><td>2776 (38.38%)</td><td>2523 (25.77%)</td><td>2531.7 (26.21%)</td><td><strong>2435 (21.39%)</strong></td><td>2449.6 (22.11%)</td><td>2590 (29.11%)</td><td>2595.5 (29.39%)</td><td>2006</td></tr><tr><td>Ta47</td><td>2476 (31.07%)</td><td>2364 (25.15%)</td><td>2381.0 (26.05%)</td><td><strong>2344 (24.09%)</strong></td><td>2354.6 (24.65%)</td><td>2418 (28.00%)</td><td>2429.0 (28.59%)</td><td>1889</td></tr><tr><td>Ta48</td><td>2490 (28.55%)</td><td>2397 (23.75%)</td><td>2401.4 (24.00%)</td><td><strong>2339 (20.75%)</strong></td><td>2354.3 (21.54%)</td><td>2458 (26.90%)</td><td>2462.9 (27.15%)</td><td>1937</td></tr><tr><td>Ta49</td><td>2556 (30.34%)</td><td>2362 (20.45%)</td><td>2363.8 (20.54%)</td><td><strong>2349 (19.79%)</strong></td><td>2365.3 (20.62%)</td><td>2448 (24.83%)</td><td>2459.0 (25.40%)</td><td>1961</td></tr><tr><td>Ta50</td><td>2628 (36.66%)</td><td><strong>2395 (24.54%)</strong></td><td>2395.0 (24.54%)</td><td>2411 (25.38%)</td><td>2417.4 (25.71%)</td><td>2462 (28.03%)</td><td>2463.7 (28.12%)</td><td>1923</td></tr><tr><td colspan="9" style="text-align:center; font-weight:bold;">50x15</td></tr><tr><td>Ta01</td><td>3599 (30.40%)</td><td><strong>3361 (21.78%)</strong></td><td>3368.2 (22.04%)</td><td>3417 (23.80%)</td><td>3417.0 (23.80%)</td><td>3404 (23.33%)</td><td>3409.2 (23.52%)</td><td>2760*</td></tr><tr><td>Ta02</td><td>3341 (21.23%)</td><td><strong>3212 (16.55%)</strong></td><td>3212.0 (16.55%)</td><td>3249 (17.89%)</td><td>3270.0 (18.65%)</td><td>3304 (19.88%)</td><td>3313.8 (20.24%)</td><td>2756*</td></tr><tr><td>Ta03</td><td>3186 (17.26%)</td><td><strong>3000 (10.42%)</strong></td><td>3004.1 (10.57%)</td><td>3045 (12.07%)</td><td>3050.1 (12.26%)</td><td>3084 (13.51%)</td><td>3091.6 (13.79%)</td><td>2717*</td></tr><tr><td>Ta04</td><td>3266 (15.04%)</td><td><strong>3120 (9.90%)</strong></td><td>3132.6 (10.34%)</td><td>3134 (10.39%)</td><td>3134.0 (10.39%)</td><td>3183 (12.12%)</td><td>3201.0 (12.75%)</td><td>2839*</td></tr><tr><td>Ta05</td><td>3232 (20.64%)</td><td><strong>3132 (16.91%)</strong></td><td>3140.1 (17.21%)</td><td>3111 (16.13%)</td><td>3124.8 (16.64%)</td><td>3196 (19.30%)</td><td>3226.3 (20.43%)</td><td>2679*</td></tr><tr><td>Ta06</td><td>3378 (21.47%)</td><td><strong>3134 (12.69%)</strong></td><td>3146.7 (13.15%)</td><td>3169 (13.95%)</td><td>3175.4 (14.18%)</td><td>3197 (14.96%)</td><td>3206.4 (15.30%)</td><td>2781*</td></tr><tr><td>Ta07</td><td>3471 (17.94%)</td><td><strong>3310 (12.47%)</strong></td><td>3316.6 (12.69%)</td><td>3349 (13.80%)</td><td>3353.6 (13.95%)</td><td>3340 (13.49%)</td><td>3357.1 (14.07%)</td><td>2943*</td></tr><tr><td>Ta08</td><td>3732 (29.36%)</td><td>3289 (14.00%)</td><td>3296.6 (14.27%)</td><td><strong>3276 (13.55%)</strong></td><td>3300.3 (14.40%)</td><td>3350 (16.12%)</td><td>3352.9 (16.22%)</td><td>2885*</td></tr><tr><td>Ta09</td><td>3381 (27.34%)</td><td>3131 (17.93%)</td><td>3136.8 (18.15%)</td><td><strong>3129 (17.85%)</strong></td><td>3129.0 (17.85%)</td><td>3151 (18.68%)</td><td>3174.4 (19.56%)</td><td>2655*</td></tr><tr><td>Ta10</td><td>3352 (23.10%)</td><td><strong>3035 (11.46%)</strong></td><td>3045.5 (11.84%)</td><td>3065 (12.56%)</td><td>3067.7 (12.66%)</td><td>3076 (12.96%)</td><td>3078.7 (13.06%)</td><td>2723*</td></tr><tr><td colspan="9" style="text-align:center; font-weight:bold;">50x20</td></tr><tr><td>Ta11</td><td>3654 (27.40%)</td><td><strong>3447 (20.18%)</strong></td><td>3464.6 (20.78%)</td><td>3472 (21.04%)</td><td>3474.5 (21.11%)</td><td>3534 (23.22%)</td><td>3551.2 (23.82%)</td><td>2868*</td></tr><tr><td>Ta12</td><td>3722 (29.73%)</td><td>3419 (19.16%)</td><td>3461.7 (20.65%)</td><td><strong>3408 (18.78%)</strong></td><td>3411.7 (18.92%)</td><td>3544 (23.53%)</td><td>3555.3 (23.92%)</td><td>2869*</td></tr><tr><td>Ta13</td><td>3536 (28.32%)</td><td><strong>3143 (14.08%)</strong></td><td>3172.7 (15.17%)</td><td>3147 (14.23%)</td><td>3165.5 (14.88%)</td><td>3253 (18.08%)</td><td>3257.2 (18.23%)</td><td>2755*</td></tr><tr><td>Ta14</td><td>3631 (34.39%)</td><td>3143 (16.32%)</td><td>3149.1 (16.54%)</td><td><strong>3132 (15.91%)</strong></td><td>3135.2 (16.03%)</td><td>3239 (19.87%)</td><td>3239.8 (19.90%)</td><td>2702*</td></tr><tr><td>Ta15</td><td>3359 (23.28%)</td><td>3233 (18.67%)</td><td>3242.0 (18.98%)</td><td><strong>3186 (16.92%)</strong></td><td>3193.3 (17.19%)</td><td>3325 (22.02%)</td><td>3338.4 (22.51%)</td><td>2725*</td></tr><tr><td>Ta16</td><td>3555 (24.96%)</td><td>3296 (15.85%)</td><td>3304.1 (16.14%)</td><td><strong>3270 (14.94%)</strong></td><td>3275.5 (15.13%)</td><td>3374 (18.59%)</td><td>3393.2 (19.27%)</td><td>2845*</td></tr><tr><td>Ta17</td><td>3567 (26.27%)</td><td>3423 (21.17%)</td><td>3428.3 (21.36%)</td><td><strong>3384 (19.79%)</strong></td><td>3403.6 (20.48%)</td><td>3463 (22.58%)</td><td>3490.4 (23.55%)</td><td>2825*</td></tr><tr><td>Ta18</td><td>3680 (32.18%)</td><td><strong>3168 (13.79%)</strong></td><td>3168.0 (13.79%)</td><td>3178 (14.15%)</td><td>3196.9 (14.83%)</td><td>3300 (18.53%)</td><td>3304.7 (18.70%)</td><td>2784*</td></tr><tr><td>Ta19</td><td>3592 (16.97%)</td><td>3482 (13.38%)</td><td>3494.7 (13.80%)</td><td><strong>3480 (13.32%)</strong></td><td>3505.8 (14.16%)</td><td>3559 (15.89%)</td><td>3560.5 (15.94%)</td><td>3071*</td></tr><tr><td>Ta20</td><td>3643 (21.64%)</td><td>3551 (18.56%)</td><td>3601 (20.23%)</td><td><strong>3482 (16.26%)</strong></td><td>3490.8 (16.55%)</td><td>3596 (20.07%)</td><td>3599.7 (20.19%)</td><td>2995*</td></tr><tr><td colspan="9" style="text-align:center; font-weight:bold;">100x20</td></tr><tr><td>Ta21</td><td>6452 (18.08%)</td><td>6049 (10.71%)</td><td>6057.0 (10.85%)</td><td><strong>6023 (10.23%)</strong></td><td>6036.0 (10.47%)</td><td>6064 (10.98%)</td><td>6084.2 (11.35%)</td><td>5464*</td></tr><tr><td>Ta22</td><td>5695 (9.92%)</td><td>5609 (8.26%)</td><td>5615.0 (8.38%)</td><td><strong>5540 (6.93%)</strong></td><td>5540.6 (6.94%)</td><td>5667 (9.38%)</td><td>5698.1 (9.98%)</td><td>5181*</td></tr><tr><td>Ta23</td><td>6462 (16.06%)</td><td>6148 (10.42%)</td><td>6168.4 (10.78%)</td><td><strong>6109 (9.72%)</strong></td><td>6109.0 (9.72%)</td><td>6139 (10.26%)</td><td>6139.0 (10.26%)</td><td>5568*</td></tr><tr><td>Ta24</td><td>5885 (10.23%)</td><td><strong>5717 (7.08%)</strong></td><td>5731.0 (7.34%)</td><td>5749 (7.68%)</td><td>5749.0 (7.68%)</td><td>5775 (8.17%)</td><td>5780.0 (8.26%)</td><td>5339*</td></tr><tr><td>Ta25</td><td>6355 (17.86%)</td><td>6167 (14.37%)</td><td>6174.4 (14.51%)</td><td>6247 (15.86%)</td><td>6276.8 (16.41%)</td><td><strong>6137 (13.82%)</strong></td><td>6177.1 (14.56%)</td><td>5392*</td></tr><tr><td>Ta26</td><td>6135 (14.84%)</td><td><strong>5890 (10.26%)</strong></td><td>5890.0 (10.26%)</td><td>5905 (10.54%)</td><td>5932.0 (11.04%)</td><td>5909 (10.61%)</td><td>6019.2 (12.68%)</td><td>5342*</td></tr><tr><td>Ta27</td><td>6056 (11.41%)</td><td><strong>5768 (6.11%)</strong></td><td>5791.2 (6.53%)</td><td>5777 (6.27%)</td><td>5799.2 (6.68%)</td><td>5824 (7.14%)</td><td>5879.0 (8.15%)</td><td>5436*</td></tr><tr><td>Ta28</td><td>6101 (13.11%)</td><td>5924 (9.83%)</td><td>5926.0 (9.86%)</td><td>5984 (10.94%)</td><td>5985.4 (10.96%)</td><td><strong>5920 (9.75%)</strong></td><td>5958.0 (10.46%)</td><td>5394*</td></tr><tr><td>Ta29</td><td>5943 (10.92%)</td><td>5782 (7.91%)</td><td>5782.0 (7.91%)</td><td><strong>5738 (7.09%)</strong></td><td>5747.4 (7.27%)</td><td>5839 (8.98%)</td><td>5850.0 (9.18%)</td><td>5358*</td></tr><tr><td>Ta30</td><td>5892 (13.68%)</td><td><strong>5692 (9.82%)</strong></td><td>5705.2 (10.08%)</td><td>5695 (9.88%)</td><td>5705.0 (10.07%)</td><td>5707 (10.11%)</td><td>5717.0 (10.30%)</td><td>5183*</td></tr></tbody></table>

<table><caption>Table 2: Results on DMU's Benchmark (Part I). Ours - RSGC is the result of the Algorithm 1. In Ours-GS instead of randomly selecting second probable action in line 14 of the Algorithm 1 (RSGC) we randomly sample an action according to the probability distribution recommended by the policy network $\pi(a_t|s_t)$. We repeat each experiment 10 times due to the algorithm's randomness and record the minimum and the average makespan across the 10 experiment. The "Samp (min)" and the "Samp (avg)" columns are the results of the usual sampling method. The "UB" column represents the best-known solutions from literature, with "*" indicating optimal solutions.</caption><thead><tr><th>Instance</th><th>L2D</th><th>Ours-GS (min)</th><th>Ours-GS (avg)</th><th>Ours-RSGC (min)</th><th>Ours-RSGC (avg)</th><th>Samp (min)</th><th>Samp (avg)</th><th>UB</th></tr></thead><tbody><tr><td colspan="9" style="text-align:center; font-weight:bold;">20x15</td></tr><tr><td>Dmu01</td><td>3323 (29.65%)</td><td><strong>3132 (22.20%)</strong></td><td>3132.0 (22.20%)</td><td>3198 (24.78%)</td><td>3204.7 (25.04%)</td><td>3218 (25.56%)</td><td>3270.4 (27.60%)</td><td>2563</td></tr><tr><td>Dmu02</td><td>3630 (34.15%)</td><td>3269 (20.81%)</td><td>3302.5 (22.04%)</td><td><strong>3266 (20.69%)</strong></td><td>3270.8 (20.87%)</td><td>3360 (24.17%)</td><td>3363.8 (24.31%)</td><td>2706</td></tr><tr><td>Dmu03</td><td>3660 (34.02%)</td><td><strong>3287 (20.36%)</strong></td><td>3287.0 (20.36%)</td><td>3375 (23.58%)</td><td>3384.4 (23.93%)</td><td>3392 (24.20%)</td><td>3429.9 (25.59%)</td><td>2731*</td></tr><tr><td>Dmu04</td><td>3816 (42.97%)</td><td><strong>3171 (18.81%)</strong></td><td>3192.9 (19.63%)</td><td>3261 (22.18%)</td><td>3267.4 (22.42%)</td><td>3229 (20.98%)</td><td>3286.7 (23.14%)</td><td>2669</td></tr><tr><td>Dmu05</td><td>3897 (41.76%)</td><td><strong>3377 (22.84%)</strong></td><td>3392.0 (23.39%)</td><td>3394 (23.46%)</td><td>3394.0 (23.46%)</td><td>3465 (26.05%)</td><td>3491.5 (27.01%)</td><td>2749*</td></tr><tr><td>Dmu41</td><td>4316 (32.88%)</td><td>4070 (25.31%)</td><td>4085.2 (25.78%)</td><td><strong>4050 (24.69%)</strong></td><td>4070.0 (25.31%)</td><td>4250 (30.85%)</td><td>4256.8 (31.06%)</td><td>3248</td></tr><tr><td>Dmu42</td><td>4858 (43.30%)</td><td><strong>4493 (32.54%)</strong></td><td>4493.0 (32.54%)</td><td>4526 (33.51%)</td><td>4541.3 (33.96%)</td><td>4650 (37.17%)</td><td>4654.6 (37.30%)</td><td>3390</td></tr><tr><td>Dmu43</td><td>4887 (42.02%)</td><td><strong>4373 (27.09%)</strong></td><td>4373.0 (27.09%)</td><td>4445 (29.18%)</td><td>4455.1 (29.47%)</td><td>4531 (31.68%)</td><td>4558.4 (32.47%)</td><td>3441</td></tr><tr><td colspan="9" style="text-align:center; font-weight:bold;">Continued on next page</td></tr></tbody></table>
<table><caption>Table 2 continued from previous page</caption><thead><tr><th>Instance</th><th>L2D</th><th>Ours-GS (min)</th><th>Ours-GS (avg)</th><th>Ours-RSGC (min)</th><th>Ours-RSGC (avg)</th><th>Samp (min)</th><th>Samp (avg)</th><th>UB</th></tr></thead><tbody><tr><td>Dmu44</td><td>5151 (47.68%)</td><td><strong>4592 (31.65%)</strong></td><td>4604.9 (32.02%)</td><td>4637 (32.94%)</td><td>4637.0 (32.94%)</td><td>4692(34.52%)</td><td>4807.5(37.83%)</td><td>3488</td></tr><tr><td>Dmu45</td><td>4615 (41.05%)</td><td><strong>4377 (33.77%)</strong></td><td>4387.4 (34.09%)</td><td>4387 (34.08%)</td><td>4399.6 (34.46%)</td><td>4454(36.12%)</td><td>4472.4(36.69%)</td><td>3272</td></tr><tr><td colspan="9" style="text-align: center;">20x20</td></tr><tr><td>Dmu06</td><td>4358 (34.34%)</td><td>3880 (19.61%)</td><td>3890.2 (19.92%)</td><td><strong>3844 (18.50%)</strong></td><td>3876.0 (19.48%)</td><td>3977(22.60%)</td><td>4011.5(23.66%)</td><td>3244</td></tr><tr><td>Dmu07</td><td>3671 (20.51%)</td><td>3621 (18.88%)</td><td>3640.3 (19.51%)</td><td><strong>3621 (18.88%)</strong></td><td>3637.8 (19.43%)</td><td>3733(22.55%)</td><td>3750.2(23.12%)</td><td>3046</td></tr><tr><td>Dmu08</td><td>4048 (26.98%)</td><td><strong>3726 (16.88%)</strong></td><td>3760.2 (17.95%)</td><td>3730 (17.00%)</td><td>3755.1 (17.79%)</td><td>3882(21.77%)</td><td>3946.3(23.79%)</td><td>3188</td></tr><tr><td>Dmu09</td><td>4482 (44.95%)</td><td>3790 (22.57%)</td><td>3817.8 (23.47%)</td><td><strong>3695 (19.50%)</strong></td><td>3695.0 (19.50%)</td><td>3893(25.91%)</td><td>3925.0(26.94%)</td><td>3092</td></tr><tr><td>Dmu10</td><td>4021 (34.75%)</td><td><strong>3494 (17.09%)</strong></td><td>3551.9 (19.03%)</td><td>3519 (17.93%)</td><td>3550.2 (18.97%)</td><td>3578(19.91%)</td><td>3632.5(21.73%)</td><td>2984</td></tr><tr><td>Dmu46</td><td>5876 (45.63%)</td><td>5066 (25.55%)</td><td>5066.0 (25.55%)</td><td><strong>5063 (25.48%)</strong></td><td>5085.5 (26.03%)</td><td>5310(31.60%)</td><td>5314.3(31.71%)</td><td>4035</td></tr><tr><td>Dmu47</td><td>5771 (46.51%)</td><td>4930 (25.16%)</td><td>4965.7 (26.06%)</td><td><strong>4872 (23.69%)</strong></td><td>4962.5 (25.98%)</td><td>5177(31.43%)</td><td>5227.6(32.71%)</td><td>3939</td></tr><tr><td>Dmu48</td><td>5034 (33.78%)</td><td>4725 (25.56%)</td><td>4741.0 (25.99%)</td><td><strong>4640 (23.31%)</strong></td><td>4667.0 (24.02%)</td><td>4891(29.98%)</td><td>4906.5(30.39%)</td><td>3763</td></tr><tr><td>Dmu49</td><td>5470 (47.44%)</td><td>4671 (25.90%)</td><td>4683.3 (26.23%)</td><td><strong>4731 (27.52%)</strong></td><td>4738.8 (27.73%)</td><td>4952(33.48%)</td><td>4984.1(34.34%)</td><td>3710</td></tr><tr><td>Dmu50</td><td>5314 (42.50%)</td><td>4862 (30.38%)</td><td>4880.1 (30.87%)</td><td><strong>4837 (29.71%)</strong></td><td>4845.5 (29.94%)</td><td>5052(35.48%)</td><td>5088.6(36.46%)</td><td>3729</td></tr><tr><td colspan="9" style="text-align: center;">30x15</td></tr><tr><td>Dmu11</td><td>4435 (29.30%)</td><td><strong>4183 (21.95%)</strong></td><td>4194.5 (22.29%)</td><td>4232 (23.38%)</td><td>4236.5 (23.51%)</td><td>4282(24.84%)</td><td>4285.3(24.94%)</td><td>3430</td></tr><tr><td>Dmu12</td><td>4864 (39.17%)</td><td>4247 (21.52%)</td><td>4260.3 (21.90%)</td><td><strong>4247 (21.52%)</strong></td><td>4254.5 (21.73%)</td><td>4414(26.29%)</td><td>4431.4(26.79%)</td><td>3495</td></tr><tr><td>Dmu13</td><td>4918 (33.60%)</td><td>4486 (21.87%)</td><td>4515.2 (22.66%)</td><td><strong>4457 (21.08%)</strong></td><td>4478.5 (21.67%)</td><td>4613(25.32%)</td><td>4641.5(26.09%)</td><td>3681*</td></tr><tr><td>Dmu14</td><td>4130 (21.69%)</td><td>3969 (16.94%)</td><td>3977.7 (17.20%)</td><td><strong>3930 (15.79%)</strong></td><td>3933.5 (15.90%)</td><td>4085(20.36%)</td><td>4097.5(20.73%)</td><td>3394*</td></tr><tr><td>Dmu15</td><td>4392 (31.38%)</td><td><strong>4054 (21.27%)</strong></td><td>4064.0 (21.57%)</td><td>4072 (21.81%)</td><td>4076.4 (21.94%)</td><td>4114(23.06%)</td><td>4138.1(23.78%)</td><td>3343*</td></tr><tr><td>Dmu51</td><td>6241 (49.77%)</td><td><strong>5919 (42.04%)</strong></td><td>5951.7 (42.83%)</td><td>6090 (46.15%)</td><td>6095.2 (46.27%)</td><td>6093(46.22%)</td><td>6128.1(47.06%)</td><td>4167</td></tr><tr><td>Dmu52</td><td>6714 (55.74%)</td><td><strong>6032 (39.92%)</strong></td><td>6093.2 (41.34%)</td><td>6081 (41.06%)</td><td>6172.6 (43.18%)</td><td>6235(44.63%)</td><td>6266.0(45.35%)</td><td>4311</td></tr><tr><td>Dmu53</td><td>6724 (53.03%)</td><td><strong>6010 (36.78%)</strong></td><td>6096.0 (38.73%)</td><td>6163 (40.26%)</td><td>6187.8 (40.82%)</td><td>6287(43.08%)</td><td>6308.5(43.57%)</td><td>4394</td></tr><tr><td>Dmu54</td><td>6522 (49.52%)</td><td><strong>6034 (38.33%)</strong></td><td>6050.8 (38.72%)</td><td>6072 (39.20%)</td><td>6072.0 (39.20%)</td><td>6201(42.16%)</td><td>6234.9(42.94%)</td><td>4362</td></tr><tr><td>Dmu55</td><td>6639 (55.44%)</td><td><strong>5917 (38.54%)</strong></td><td>5917.0 (38.54%)</td><td>5931 (38.87%)</td><td>5945.2 (39.20%)</td><td>6031(41.21%)</td><td>6042.4(41.48%)</td><td>4271</td></tr><tr><td colspan="9" style="text-align: center;">30x20</td></tr><tr><td>Dmu16</td><td>4593 (32.04%)</td><td><strong>4462 (18.95%)</strong></td><td>4656.7 (24.15%)</td><td>4696 (25.19%)</td><td>4713.5 (25.66%)</td><td>4773(27.24%)</td><td>4801.6(28.00%)</td><td>3751</td></tr><tr><td>Dmu17</td><td>5379 (41.03%)</td><td>4747 (24.46%)</td><td>4751.0 (24.57%)</td><td><strong>4710 (23.49%)</strong></td><td>4736.9 (24.20%)</td><td>4907(28.65%)</td><td>4930.0(29.26%)</td><td>3814</td></tr><tr><td>Dmu18</td><td>5100 (32.67%)</td><td>4639 (20.68%)</td><td>4651.8 (21.01%)</td><td><strong>4546 (18.26%)</strong></td><td>4564.4 (18.74%)</td><td>4804(24.97%)</td><td>4834.9(25.77%)</td><td>3844*</td></tr><tr><td>Dmu19</td><td>4889 (29.75%)</td><td>4659 (23.65%)</td><td>4668.5 (23.90%)</td><td><strong>4651 (23.43%)</strong></td><td>4678.5 (24.16%)</td><td>4780(26.85%)</td><td>4792.8(27.19%)</td><td>3768</td></tr><tr><td>Dmu20</td><td>4859 (30.97%)</td><td>4442 (19.73%)</td><td>4489.7 (21.02%)</td><td><strong>4388 (18.27%)</strong></td><td>4441.5 (19.72%)</td><td>4554(22.75%)</td><td>4628.2(24.75%)</td><td>3710</td></tr><tr><td>Dmu56</td><td>7328 (48.31%)</td><td><strong>6784 (37.30%)</strong></td><td>6784.0 (37.30%)</td><td>6861 (38.86%)</td><td>6861.7 (38.87%)</td><td>6924(40.13%)</td><td>6998.7(41.65%)</td><td>4941</td></tr><tr><td>Dmu57</td><td>6704 (44.02%)</td><td><strong>6421 (37.94%)</strong></td><td>6435.0 (38.24%)</td><td>6428 (38.09%)</td><td>6509.0 (39.83%)</td><td>6625(42.32%)</td><td>6638.0(42.60%)</td><td>4655</td></tr><tr><td>Dmu58</td><td>6721 (42.76%)</td><td><strong>6322 (34.28%)</strong></td><td>6353.7 (34.96%)</td><td>6398 (35.90%)</td><td>6427.9 (36.53%)</td><td>6564(39.42%)</td><td>6584.0(39.85%)</td><td>4708</td></tr><tr><td>Dmu59</td><td>7109 (53.74%)</td><td><strong>6388 (38.15%)</strong></td><td>6420.2 (38.85%)</td><td>6486 (40.27%)</td><td>6492.4 (40.41%)</td><td>6398(38.37%)</td><td>6579.3(42.29%)</td><td>4624</td></tr><tr><td>Dmu60</td><td>6632 (39.47%)</td><td><strong>6400 (34.60%)</strong></td><td>6471.4 (36.10%)</td><td>6459 (35.84%)</td><td>6465.4 (35.97%)</td><td>6631(39.45%)</td><td>6665.5(40.18%)</td><td>4755</td></tr><tr><td colspan="9" style="text-align: center;">40x15</td></tr><tr><td>Dmu21</td><td>5317 (21.42%)</td><td><strong>5034 (14.91%)</strong></td><td>5069.7 (15.75%)</td><td>5072 (15.82%)</td><td>5077.8 (15.95%)</td><td>5162(17.85%)</td><td>5235.3(19.53%)</td><td>4380*</td></tr><tr><td>Dmu22</td><td>5534 (17.12%)</td><td><strong>5293 (12.03%)</strong></td><td>5360.3 (13.45%)</td><td>5316 (12.51%)</td><td>5331.9 (12.85%)</td><td>5432(14.96%)</td><td>5475.5(15.88%)</td><td>4725*</td></tr><tr><td>Dmu23</td><td>5620 (20.41%)</td><td><strong>5171 (10.78%)</strong></td><td>5195.8 (11.30%)</td><td>5178 (10.92%)</td><td>5179.4 (10.94%)</td><td>5291(13.35%)</td><td>5303.3(13.61%)</td><td>4668*</td></tr><tr><td>Dmu24</td><td>5753 (23.77%)</td><td><strong>5138 (10.54%)</strong></td><td>5138.0 (10.54%)</td><td>5224 (12.41%)</td><td>5236.5 (12.68%)</td><td>5324(14.54%)</td><td>5353.5(15.18%)</td><td>4648*</td></tr><tr><td>Dmu25</td><td>4775 (14.66%)</td><td>4659 (11.89%)</td><td>4662.2 (11.97%)</td><td><strong>4618 (10.90%)</strong></td><td>4618.0 (10.90%)</td><td>4755(14.19%)</td><td>4756.4(14.23%)</td><td>4164*</td></tr><tr><td>Dmu61</td><td>8203 (58.62%)</td><td><strong>7634 (47.58%)</strong></td><td>7685.5 (48.54%)</td><td>7818 (51.14%)</td><td>7829.2 (51.37%)</td><td>7802(50.85%)</td><td>7829.1(51.37%)</td><td>5172</td></tr><tr><td>Dmu62</td><td>8091 (53.66%)</td><td><strong>7528 (42.96%)</strong></td><td>7561.4 (43.59%)</td><td>7810 (48.32%)</td><td>7810.0 (48.32%)</td><td>7768(47.54%)</td><td>7799.9(48.15%)</td><td>5265</td></tr><tr><td>Dmu63</td><td>8031 (50.76%)</td><td><strong>7543 (41.66%)</strong></td><td>7597.2 (42.69%)</td><td>7610 (42.92%)</td><td>7621.2 (43.15%)</td><td>7636(43.37%)</td><td>7744.8(45.41%)</td><td>5326</td></tr><tr><td>Dmu64</td><td>7738 (47.39%)</td><td><strong>7628 (45.20%)</strong></td><td>7670.0 (46.10%)</td><td>7757 (47.66%)</td><td>7773.5 (47.97%)</td><td>7717(46.99%)</td><td>7797.6(48.53%)</td><td>5250</td></tr><tr><td>Dmu65</td><td>7577 (46.07%)</td><td><strong>7345 (41.58%)</strong></td><td>7370.5 (42.00%)</td><td>7648 (47.40%)</td><td>7648.0 (47.40%)</td><td>7583(46.11%)</td><td>7584.0(46.13%)</td><td>5190</td></tr><tr><td colspan="9" style="text-align: center;">40x20</td></tr><tr><td>Dmu26</td><td>5946 (27.94%)</td><td>5646 (21.51%)</td><td>5662.9 (21.86%)</td><td><strong>5583 (20.14%)</strong></td><td>5592.2 (20.34%)</td><td>5769(24.14%)</td><td>5823.2(25.31%)</td><td>4647*</td></tr><tr><td>Dmu27</td><td>6418 (32.38%)</td><td>5874 (21.14%)</td><td>5902.2 (21.74%)</td><td><strong>5849 (20.63%)</strong></td><td>5851.7 (20.68%)</td><td>6014(24.05%)</td><td>6046.4(24.72%)</td><td>4848*</td></tr><tr><td>Dmu28</td><td>5986 (27.57%)</td><td>5610 (19.56%)</td><td>5622.8 (19.81%)</td><td><strong>5604 (19.43%)</strong></td><td>5609.8 (19.54%)</td><td>5831(24.28%)</td><td>5848.5(24.65%)</td><td>4692*</td></tr><tr><td>Dmu29</td><td>6051 (29.00%)</td><td>5776 (23.09%)</td><td>5776.0 (23.09%)</td><td><strong>5685 (21.14%)</strong></td><td>5685.0 (21.14%)</td><td>5928(26.37%)</td><td>5942.8(26.69%)</td><td>4691*</td></tr><tr><td>Dmu30</td><td>5988 (26.58%)</td><td><strong>5584 (18.01%)</strong></td><td>5676.0 (19.95%)</td><td>5718 (20.85%)</td><td>5718.0 (20.85%)</td><td>5791(22.38%)</td><td>5847.2(23.57%)</td><td>4732*</td></tr><tr><td>Dmu66</td><td>8475 (48.24%)</td><td><strong>8069 (41.14%)</strong></td><td>8106.8 (41.80%)</td><td>8099 (41.67%)</td><td>8129.0 (42.19%)</td><td>8224(43.85%)</td><td>8265.6(44.57%)</td><td>5717</td></tr><tr><td>Dmu67</td><td>8832 (51.94%)</td><td><strong>8227 (41.53%)</strong></td><td>8259.6 (42.09%)</td><td>8252 (41.96%)</td><td>8318.0 (43.09%)</td><td>8361(43.83%)</td><td>8377.3(44.11%)</td><td>5813</td></tr><tr><td>Dmu68</td><td>8693 (50.58%)</td><td><strong>8198 (42.01%)</strong></td><td>8259.6 (43.07%)</td><td>8364 (44.88%)</td><td>8432.7 (46.07%)</td><td>8348(44.60%)</td><td>8348.0(44.60%)</td><td>5773</td></tr><tr><td>Dmu69</td><td>8634 (51.23%)</td><td><strong>8107 (42.00%)</strong></td><td>8159.4 (42.92%)</td><td>8202 (43.67%)</td><td>8228.3 (44.13%)</td><td>8209(43.79%)</td><td>8240.7(44.34%)</td><td>5709</td></tr><tr><td>Dmu70</td><td>8735 (48.33%)</td><td>8341 (41.64%)</td><td>8375.2 (42.22%)</td><td><strong>8230 (39.75%)</strong></td><td>8244.0 (39.99%)</td><td>8416(42.91%)</td><td>8531.2(44.86%)</td><td>5889</td></tr><tr><td colspan="9" style="text-align: center;">50x15</td></tr><tr><td>Dmu31</td><td>7156 (26.88%)</td><td><strong>6400 (13.48%)</strong></td><td>6423.2 (13.89%)</td><td>6512 (15.48%)</td><td>6524.3 (15.70%)</td><td>6552(16.17%)</td><td>6603.6(17.09%)</td><td>5640*</td></tr><tr><td>Dmu32</td><td>6506 (9.76%)</td><td><strong>6025 (1.65%)</strong></td><td>6032.9 (1.78%)</td><td>6168 (4.06%)</td><td>6175.2 (4.18%)</td><td>6133(3.48%)</td><td>6137.6(3.55%)</td><td>5927*</td></tr><tr><td>Dmu33</td><td>6192 (8.08%)</td><td>6001 (4.75%)</td><td>6016.9 (4.97%)</td><td><strong>5898 (2.96%)</strong></td><td>5929.1 (3.51%)</td><td>6015(5.01%)</td><td>6117.5(6.80%)</td><td>5728*</td></tr><tr><td>Dmu34</td><td>6257 (16.18%)</td><td>5948 (10.47%)</td><td>5954.1 (10.57%)</td><td><strong>5868 (8.95%)</strong></td><td>5892.4 (9.41%)</td><td>6133(13.89%)</td><td>6169.5(14.57%)</td><td>5385*</td></tr><tr><td>Dmu35</td><td>6302 (11.83%)</td><td>6012 (6.70%)</td><td>6021.3 (6.85%)</td><td><strong>6012 (6.70%)</strong></td><td>6015.2 (6.74%)</td><td>6084(7.97%)</td><td>6129.8(8.78%)</td><td>5635*</td></tr><tr><td>Dmu71</td><td>9797 (57.24%)</td><td><strong>9440 (51.47%)</strong></td><td>9461.6 (51.81%)</td><td>9521 (52.78%)</td><td>9526.9 (52.88%)</td><td>9571(53.55%)</td><td>9585.6(53.79%)</td><td>6233</td></tr><tr><td>Dmu72</td><td>9926 (53.11%)</td><td><strong>9681 (49.33%)</strong></td><td>9681.0 (49.33%)</td><td>9650 (48.85%)</td><td>9670.9 (49.17%)</td><td>9688(49.44%)</td><td>9710.2(49.78%)</td><td>6483</td></tr></tbody></table>

Continued on next page
<table><caption>Table 2 continued from previous page</caption><thead><tr><th>Instance</th><th>L2D</th><th>Ours-GS (min)</th><th>Ours-GS (avg)</th><th>Ours-RSGC (min)</th><th>Ours-RSGC (avg)</th><th>Samp (min)</th><th>Samp (avg)</th><th>UB</th></tr></thead><tbody><tr><td>Dmu73</td><td>9933 (61.17%)</td><td><b>9298 (50.87%)</b></td><td>9365.8 (51.97%)</td><td>9545 (54.88%)</td><td>9545.0 (54.88%)</td><td>9447(53.29%)</td><td>9469.5(53.65%)</td><td>6163</td></tr><tr><td>Dmu74</td><td>9833 (58.09%)</td><td><b>9440 (51.77%)</b></td><td>9461.0 (52.11%)</td><td>9607 (54.45%)</td><td>9618.0 (54.63%)</td><td>9560(53.70%)</td><td>9581.0(54.04%)</td><td>6220</td></tr><tr><td>Dmu75</td><td>9892 (59.63%)</td><td><b>9287 (49.86%)</b></td><td>9300.9 (50.09%)</td><td>9299 (50.06%)</td><td>9307.0 (50.19%)</td><td>9397(51.64%)</td><td>9448.0(52.46%)</td><td>6197</td></tr><tr><td colspan="9" style="text-align: center;">50x20</td></tr><tr><td>Dmu36</td><td>7470 (32.89%)</td><td><b>6665 (18.57%)</b></td><td>6745.3 (20.00%)</td><td>6787 (20.74%)</td><td>6790.5 (20.81%)</td><td>6825(21.42%)</td><td>6840.6(21.70%)</td><td>5621*</td></tr><tr><td>Dmu37</td><td>7296 (24.70%)</td><td><b>6843 (16.95%)</b></td><td>6873.0 (17.47%)</td><td>6866 (17.35%)</td><td>6897.9 (17.89%)</td><td>6895(17.84%)</td><td>6927.4(18.40%)</td><td>5851*</td></tr><tr><td>Dmu38</td><td>7410 (29.70%)</td><td><b>6968 (21.97%)</b></td><td>7012.0 (22.74%)</td><td>7136 (24.91%)</td><td>7149.7 (25.15%)</td><td>7075(23.84%)</td><td>7079.8(23.92%)</td><td>5713*</td></tr><tr><td>Dmu39</td><td>6827 (18.79%)</td><td>6580 (14.49%)</td><td>6601.6 (14.87%)</td><td><b>6434 (11.95%)</b></td><td>6443.8 (12.12%)</td><td>6654(15.78%)</td><td>6706.7(16.70%)</td><td>5747*</td></tr><tr><td>Dmu40</td><td>7325 (31.34%)</td><td><b>6718 (20.46%)</b></td><td>6771.7 (21.42%)</td><td>6773 (21.45%)</td><td>6776.1 (21.50%)</td><td>6835(22.56%)</td><td>6841.6(22.68%)</td><td>5577*</td></tr><tr><td>Dmu76</td><td><b>9698 (42.35%)</b></td><td>9823 (44.18%)</td><td>9851.4 (44.60%)</td><td>9991 (46.65%)</td><td>9997.3 (46.74%)</td><td>9922(45.63%)</td><td>9963.5(46.24%)</td><td>6813</td></tr><tr><td>Dmu77</td><td>10693 (56.74%)</td><td><b>9930 (45.56%)</b></td><td>9940.8 (45.72%)</td><td>9948 (45.82%)</td><td>9974.4 (46.21%)</td><td>10070(47.61%)</td><td>10070.0(47.61%)</td><td>6822</td></tr><tr><td>Dmu78</td><td>9986 (47.50%)</td><td><b>9940 (46.82%)</b></td><td>10013.6 (47.91%)</td><td>9990 (47.56%)</td><td>10029.2 (48.14%)</td><td>10126(49.57%)</td><td>10151.5(49.95%)</td><td>6770</td></tr><tr><td>Dmu79</td><td>10936 (56.90%)</td><td>10303 (47.82%)</td><td>10310.6 (47.93%)</td><td><b>10181 (46.07%)</b></td><td>10181.0 (46.07%)</td><td>10457(50.03%)</td><td>10486.5(50.45%)</td><td>6970</td></tr><tr><td>Dmu80</td><td>9875 (47.70%)</td><td><b>9674 (44.69%)</b></td><td>9742.9 (45.73%)</td><td>9859 (47.46%)</td><td>9874.8 (47.69%)</td><td>9732(45.56%)</td><td>9803.5(46.3%)</td><td>6686</td></tr></tbody></table>

# 6 Conclusion

In this study, we present RSGC and GS, algorithms designed to optimize JSSP through Policy network-guided search. By incorporating second greedy choices and policy network sampling methods with decreasing probabilities RSGC offers a balance between exploration and exploitation in the search space, thereby mitigating the risk of finding solutions having larger makespan. Our systematic approach to adjusting the probability of selecting alternative paths enables efficient exploration of the search tree, leading to improved makespan. Through extensive experimentation, we establish optimal parameters for RSGC and GS, enhancing its performance across two benchmark datasets. We also compare the minimum makespans and the average makespans using the two algorithms. The experiments showed that the GS algorithm results were slightly better on most instances, the reason perhaps being that it explored more. Overall, RSGC presents a promising avenue for enhancing scheduling algorithms, showcasing the potential of Policy networks in addressing complex optimization challenges.

# References

1. J. Christopher Beck, T. K. Feng, and Jean-Paul Watson. Combining constraint programming and local search for job-shop scheduling. *INFORMS Journal on Computing*, 23(1):1–14, 2010.

2. Irwan Bello, Hieu Pham, Quoc V. Le, Mohammad Norouzi, and Samy Bengio. Neural combinatorial optimization with reinforcement learning, 2017.

3. Giovanni Bonetta, Davide Zago, Rossella Cancelliere, and Andrea Grosso. Job shop scheduling via deep reinforcement learning: a sequence to sequence approach. *Not Specified*, Aug 2023.

4. Cameron B. Browne, Edward Powley, Daniel Whitehouse, Simon M. Lucas, Peter I. Cowling, Philipp Rohlfshagen, Stephen Tavener, Diego Perez, Spyridon Samothrakis, and Simon Colton. A survey of monte carlo tree search methods. *IEEE Transactions on Computational Intelligence and AI in Games*, 4(1):1–43, 2012.

5. Tristan Cazenave. Nested Monte-Carlo search. In *Proceedings of the IJCAI International Joint Conference on Artificial Intelligence*, pages 456–461, 2009.

6. Ceren Cebi, Enes Atac, and Ozgur Koray Sahingoz. Job shop scheduling problem and solution algorithms: A review. In *2020 11th International Conference on Computing, Communication and Networking Technologies (ICCCNT)*, pages 1–7, 2020.
7. Ebru Demirkol, Sanjay Mehta, and Reha Uzsoy. Benchmarks for shop scheduling problems. *European Journal of Operational Research*, 109(1):137–141, 1998.

8. Rupert Ettrich, Marc Huber, and Günther Raidl. *A Policy-Based Learning Beam Search for Combinatorial Optimization*, pages 130–145. Springer, 03 2023.

9. Kaizhou Gao, Zhiguang Cao, Le Zhang, Zhenghua Chen, Yuyan Han, and Quanke Pan. A review on swarm intelligence and evolutionary algorithms for solving flexible job shop scheduling problems. *IEEE/CAA Journal of Automatica Sinica*, 6(4):904, 2019.

10. Michael R Garey, David S Johnson, and Ravi Sethi. The complexity of flowshop and jobshop scheduling. *Mathematics of Operations Research*, 1(2):117–129, 1976.

11. William D Harvey and Matthew L Ginsberg. Limited discrepancy search. In *IJCAI*, pages 607–615, 1995.

12. Chun-Cheng Lin, Der-Jiunn Deng, Yen-Ling Chih, and Hsin-Ting Chiu. Smart manufacturing scheduling with edge computing using multiclass deep q network. *IEEE Transactions on Industrial Informatics*, 15(7):4276–4284, 2019.

13. Eugeniusz Nowicki and Czesław Smutnicki. An advanced tabu search algorithm for the job shop problem. *Journal of Scheduling*, 8(2):145–159, 2005.

14. John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint arXiv:1707.06347, 2017.

15. Eric Taillard. Benchmarks for basic scheduling problems. *European Journal of Operational Research*, 64(2):278–285, 1993.

16. Erdőd Yuan, Shuli Cheng, Liejun Wang, Shiji Song, and Fang Wu. Solving job shop scheduling problems via deep reinforcement learning. *Applied Soft Computing*, 143:110436, 2023.

17. Mohamed Habib Zahmani, Baghdad Atmani, Abdelghani Bekrar, and Nassima Aissani. Multiple priority dispatching rules for the job shop scheduling problem. In *3rd International Conference on Control, Engineering Information Technology (CEIT'2015)*, Tlemcen, Algeria, 2015.

18. Cong Zhang, Wen Song, Zhiguang Cao, Jie Zhang, Puay Siew Tan, and Chi Xu. Learning to dispatch for job shop scheduling via deep reinforcement learning. In *34th Conference on Neural Information Processing Systems (NeurIPS)*, 2020.