ScheduleNet: Learn to solve multi-agent scheduling problems with reinforcement learning
Authors: Junyoung Park
Sanzhar Bakhtiyarov
Jinkyoo Park
Venue: ICLR 2022 Submitted (2022)
Keywords: scheduling problems
combinatorial optimization
reinforcement learning
graph
graph neural network

Abstract: We propose ScheduleNet, an RL-based decentralized constructive scheduler for coordinating multi-agent to finish tasks with minimum completion time. We formulate multi-agent scheduling problems (mSPs) as an event-based Markov decision process (MDP) with an episodic reward (e.g., makespan) and derive a decentralized decision-making policy using reinforcement learning. The decision making procedure of ScheduleNet includes: (1) representing the state of a scheduling problem with the agent-task graph, (2) extracting node embeddings for agent and tasks nodes by employing the type-aware graph attention (TGA), and (3) computing the assignment probability with the computed node embeddings. We validate the effectiveness of ScheduleNet on two types of mSPs: multiple traveling salesmen problem (mTSP) and job-shop scheduling problem (JSP). We empirically show that ScheduleNet can outperform other heuristic approaches and existing deep RL approaches, particularly validating its exceptional effectiveness in solving large and practical problems. Furthermore, we have demonstrated that ScheduleNet can effectively solve online vehicle routing problems where the new target customer appears dynamically during the course of scheduling.

Under review as a conference paper at ICLR 2022
SCHEDULENET: LEARN TO SOLVE MULTI-AGENT SCHEDULING PROBLEMS WITH REINFORCEMENT LEARNING
Anonymous authors Paper under double-blind review
ABSTRACT
We propose ScheduleNet, an RL-based decentralized constructive scheduler for coordinating multi-agent to finish tasks with minimum completion time. We formulate aggent scheduling problems (mSPs) as an event-based Markov decision process (MDP) with an episodic reward (e.g., makespan) and derive a decentralized decision-making policy using reinforcement learning. The decision making procedure of ScheduleNet includes: (I) representing the state of scheduling problem with the agent-task graph, (2) extracting node embeddings for agents and tasks by employing the type-aware graph attention (TGA), and (3) computing the assignment probability with the computed node embeddings. We validate the effectiveness of ScheduleNet on two types of mSPs: multiple traveling salesmen problem (mTSP) and job-shop scheduling problem (JSP). We empirically show that ScheduleNet can outperform other heuristic approaches and existing deep RL approaches, particularly validating its exceptional effectiveness in solving large and practical problems. Furthermore, we have demonstrated that ScheduleNet can effectively solve online vehicle routing problems where the new target customer appears dynamically during the course scheduling.
INTRODUCTION
Optimal assignments of multiple autonomous agents for sequential completion of distributed tasks are necessary to solve various types of scheduling problems in the logistics, transportation, and manufacturing industries. Examples of such scheduling problem include finding the optimal delivery plans for vaccines, customer pickup orders for ride-sharing services, and machine operation sequence in modern manufacturing facilitics. As the size of the problems increases, solving large- scale scheduling problems using mathematical programming becomes infeasible or ineffective due to the expensive computational cost. Furthermore, such optimization approaches cannot solve real- time scheduling problems where the tasks appear dynamically.
Target Problem & Challenges. In this paper, we propose ScheduleNet, an RL-based decentralized constructive scheduler for coordinating multiple agents finish tasks with minimum completion time. The objectives of the target problems and their associated technical challenges are as follows:
Min-Max vs Min-Sum: ScheduleNet seeks minimize the total completion time (i.e.. makespan) for various time-critiess distributed tasks (c.g., vaccine delivery). Most multi-agent scheduling problems are designed minimize the total traveling distance of all agents, which often result in unbalanced task assignments among the agents (Bakach et al., 2021). Although the makespan the most direct and intuitive reward for inducing coordination, it is notoriously difficult to train the decentralized policy with this sparse and delayed reward due to the temporal and spatial credit assignment issues.
Construction Heuristic vs Improvement heuristic: ScheduleNet builds solution sequentially by assigning idle agent to one of the remaining tasks while considering the relationships among the remaining tasks and agents. This construction heuristic ensures that the learned policy can task
reschedule whenever new event occurs (i.e., agent finishes the assigned task appears). However, it is more challenging to find a better plan due to its sequential solution construction; wrong choice the early stage can cause irreversible poor results at the end.

---

Under review as a conference paper at ICLR 2022
Decentralized Centralized: ScheduleNet allows each agent to choose its destination independently while using its local observations and incorporating other agents' assignments. This decentralization ensures that the learned policy without having to search over the joint action space for all agents. However, to make the independently-chosen scheduling decision produce an excellent global performance, a sophisticated coordination mechanism should be incorporated into decentralized policy implicitly.
solve large-scale problem
Proposed Decision-Making Scheme. We formulate the multi-agent scheduling problems (mSPs) as an event-based Markov decision process (MDP) with an episodic reward, and derive a decentralized decision-making policy using reinforcement learning, At every step, ScheduleNet accepts the MDP state as an input and assigns an idle agent to one of the feasible tasks. The mecisinn-making procedure of ScheduleNet is as follows:
ScheduleNet first represents the MDP state as agent-task graph, which captures the complex relationships among the entities effectively and is general enough to be applied to various mSPs.
ScheduleNet then employs the type-aware graph attention (TGA) extract important relational features among the agents and tasks for making the best cooperative task assignment.
Lastly, ScheduleNet computes the agent-task assignment probability by utilizing the computed node embeddings.
Training Method. Although the makespan (shared team reward) is the most direct and general reward design for solving mSPs, training decentralized scheduling policy using this reward extremely difficult due to the credit assignment issues (Riedmiller et al., 2018; Hare, 2019). Additionally, makespan is highly volatile due the combinatorial aspect of mSPs' solution space; slight change in the solution can drastically alter the outcome. To overcome these issues, we employ the Clip-REINFORCE algorithm with normalized reward to train the decentralized cooperative policy effectively.
Novelties. The proposed method that derives the decentralized constructive schedulers to coordinate multiple agents has the following novelties and advantages:
Balance between Representability & Scalability: ScheduleNet can extract crucial features effectively using TGA and make the best cooperative task assignment (representability) a computationally efficient manner. The computationaally-fficie representation scheme and the constructive decision-making scheme allows ScheduleNet to solve large-scale scheduling problems.
Transferability & Generalizability: The type-aware graph representation allows the trained policy to solve problems with different numbers of agents and tasks (size transferability). Furthermore, this general state representation with the universal reward signal (i.c., makespan) allows ScheduleNet to be used to solve various multi-agent scheduling problems (generalizability). We validate this by showing that ScheduleNet can learn to solve multiple traveling salesmen problem (mTSP), as well as jop-shop scheduling problem (JSP) whose constraints are more complex than that of mTSP.
2 RELATED WORKS
RL approaches that solve vehicle routing problems. According to Mazyavkina et al. (2020), the RL approaches that solve vehicle routing problems can be categorized into: (1) the improvement heuristics that rewrite the complete solution iteratively to obtain a better routing plan (Wu et al., 2020: da Costa et al., 2020; Chen & Tian, 2019; Lu al., 2020); (2) the construction heuristies that construct the solution sequentially by assigning idle vehicles to unvisited cities until the complete routing plan (sequence) is constructed (Bello al., 2016; Nazari et al., 2018; Kool et al., 2018; Khalil et al., 2017), and (3) the hybrid approaches that blend both approaches (Joshi et al., 2020; Fu et al., 2021; Kool et al., 2021; Ahn et al., 2020). Typically, the improvement heuristics show better performances than construction heuristics as they revise the complete plan iteratively. However, the construction heuristics are more effective for online vehicle routing problems, where the routes should be updated whenever focused on static planning in a single-agent perspective, which is far from the settings of real applications.
customer appears. These RL approaches have exclusively
2

---

Under review as a conference paper at ICLR 2022
RL approaches that solve min-max mTSP. There are only few RL approaches that solve min-max mTSP, which involves minimizing the makespan for multiple salesmen to visit all cities. Hu et al. (2020) applies RL to train the clustering algorithm that groups cities, and strong TSP heuristics (e.g.. OR-Tool) to optimize the sub-tours of the city clusters. This is fundamentally different from ScheduleNet, which derives complete end-to-end learned heuristic that constructs feasible solution from "scratch" without relying on any existing solvers. Cao et al. (2021), which proposes transformer-based construction policy to solve min-max mTSP, the most similar approach to ScheduleNet.
RL approaches that solve Job-shop scheduling problems. There are only few RL approaches that solve the JSPs, which involves minimizing the makespan for multiple machines to finish the sequence of operations that is required to finish their jobs. For example, Gabel & Riedmiller (2012); Lin et al. (2019) propose to learn a scheduling policy for each machine; hence, it requires additional training to solve JSPs with a different number of machines. Recently, Park et (2021); Zhang et al. (2020) have proposed to learn shared scheduling policy that can be used for all machines to minimize the makespan. Similar to ScheduleNet, these studies utilize the disjunctive graph representation of JSP. However, these methods utilize human-engineern dense reward, while ScheduleNet uses sparse and delayed reward (i.e., makespan) to train a policy.
3 PROBLEM FORMULATION
We formulate mSP as MDP with sparse reward, and aim to derive a decentralized scheduling decision-making policy that can be shared by all agents. The MDP is defined as:
State. We define state 8, as the r-th partial solution of mSP (i.e., the completed/uncompleeed tasks, the status of agents, and the sequence of the past assignments). The initial sg and terminal state sT are defined as an empty and a complete solution, respectively.
Action. We define action a, the act of assigning an idle agent to one of the feasible tasks (unassigned tasks). We refer to 0, as the agent-to-task assignment. When the multiple agents are idle at the same time f, we randomly choose one agent and assign an action to the agent. This is repeated until no agent is idle. Note that such randomness does not alter the resulting solutions, since the agents are considered to be homogeneous and the scheduling policy is shared.
The proposed MDP is formulated with an even/-based transition. An event is defined as the case where any agent finishes the assigned task (c.g., a salesman reaches the assigned city in mTSP). Whenever an event occurs, the idle agent is assigned to new task, and the status of the agent and the target task are updated accordingly. We enumerate the event with 7 to avoid confusion from the elapsed time of the problem; t(r) is function that returns the time of event т.
Transition.
Reward. The proposed MDP uses the negative makespan (i.e. total completion time of tasks) as the reward (i.e., r(ST) -(()) that is realized only at ST.
3.1 EXAMPLE: MDP FORMULATION OF MTSP
Let us consider the single-depot mTSP with two types of entities: m salesmen (i.e., m agents) and N cities (i.e., N tasks). All salesmen start their journey from the depot, and come back to the depot after visiting all cities (each city can be visited by only one salesman). The solution to mTPP considered to complete when all the cities have been visited, and all salesmen have returned to the depot. The MDP formulation for mTSP is similar to that of the general mSP. The specific definition of the state for mTSP is as follows:
State. We define s, (1 +m " which is composed of two types of states: entity state of
and environment state 5.th
(p/. netive pssigned is the state of the i-th entity. of is the 2D Cartesian coordinate of the i-th entity at the 7-th event. petiv indicates whether the i-th agent/task is active (agent is working/ task is not visited). Similarly, assigned indicates whether agent/task is assigned.
shn contains the current time of the environment, and the sequences of cities visited by the salesmen.
3

---

Under review as a conference paper at ICLR 2022
Rubus Tack Graph Constration
Graph Enshoiding with ItA
Assigmmen Computation
ST
O
O
O
X H
((0)
0
Total completion time: makespan
t(T)
Figure I: Solving mSP with ScheduleNet. At every event of the MDP, ScheduleNet constructs the agent-tass task graph G- from Sr, then computes the node embedding G- using TGA, and finally computes the agent-task assignment probabilities from node embedding.
SCHEDULENET
In this section, explain how ScheduleNet recommends scheduling action a, of an idle agent from input 8, (partial solution). This is done by (1) constructing the agent-task graph Gr, (2) embedding Gr using TGA, and (3) computing the assignment probabilities. Figure 1 illustrates the decision-making process of ScheduleNet.
4.1 CONSTRUCTING AGENT-TASE GRAPH
ScheduleNet constructs the agent-task graph G, that reflects the complex relationships among the entities in 87- Specifically, ScheduleNet constructs directed complete graph 9, (V, R) out of 8r. where V is the set of nodes and the set of edges. The nodes and edges, and their associated features are defined as:
o denotes the i-th node, which represents either an agent or a task. o contains the node feature (st, k;). where s is the state of entity i, and k; is the type of For example, if the entity is an agent and a = 1, then K becomes active-agent, For the full list the types, refer to Appendix C.2.
Ei denotes the edge between the source node and the destination node U/ The edge feature Wa is equal the Fuclidean distance between the two nodes.
In the following subsections, we omit the event iterator т for notational brevity, since the action selection procedure only associated with the current event index т.
4.2 GRAPH EMBEDDING USING TGA
ScheduleNet computes the node embeddings from the agent-task graph & using the TGA, which designed to capture the different relations among the graph entities by applying attention mechanisms for each relational type. TGA uses three steps compute the updated node/edge embedding as follows:
Type-aware edge update. Given the node embedding h, and edge embedding hig. TGA computes the type-aware edge embedding hly and the attention logit 2ij as follows:
h1 TGAg [he, hy. hisl, kg) 2y TGAa (1e,, hy, hig., ky)
where TGAg and TGA, are the type-aware edge update function and the type-aware attention function, respectively. TGAg and TGA2 parameterized using multilayer perceptrons (MLPs).
Type-aware message aggregation. Each entity in the agent-task graph interacts differently with the other entities, depending the type of the edge between them. To preserve the different relationships among the entities during the graph embedding procedure, TGA gathers messages My via the aype-aware message aggregation.
4

---

Under review as a conference paper at ICLR 2022
First, TGA aggregates messages for each node type and produces the per-type message m as follows:
m
Σ
(
(EN(()
where (i) (u k M(i) is the type neighborhood of us. and ai is the attention score that is computed using Ziz!
exp(2.) Egg
0n Σ (i) exp(zig)
(3)
TGA aggregates the per-type messages to compute the total aggregated message m, for U, as:
m
my
kEK
where K. is the set of node types.
Type-aware node update. The total aggregated message my is then used to compute the updated node embedding K; follows:
h = TGA(((, m.]. kz)
(5)
where TGAy is the type-aware node update function that is parametrized using MLP. The detailed architectures of TGAg, TGA,, and TGAy are provided in Appendix A.
ScheduleNet computes the node embeddings from & using TGA. The embedding procedure first encodes the features of G into the initial node embeddings {4. (ey E V), and the initial edge embeddings {hi leis E IB). ScheduleNet then performs TGA H times all nodes compute the (0)
(0)
(I) final node embeddings (h, joy V) and edge embeddings (h Jey E}.
(!))
4.3 COMPUTING ASSIGNMENT PROBABILITY
lei E E}. ScheduleNet selects the assignment action a, for the target idle agent. It computes the assignment probability of the target agent to the unassigned task j as follows:
Using {h, b E V} and (
(H)
(H) (1)) b MLP octor (h (M(H) n
(6)
P. softmax ((G))EAA(G))
where AG+) denotes set of feasible actions that is defined as (uglky Unassigned-task, vy V).
Note that ScheduleNet allows an agent to process its local state information and make the assignment choice in decentralized way. This enables ScheduleNet to solve mSPs with any number of agents and tasks even when the agents or tasks appear dynamically.
5 TRAINING SCHEDULENET
We utilize the sparse team reward (makespan) as the reward to train the decentralized scheduler (ScheduleNet) that aims complete the tasks as quickly as possible by coordinating multiple agents. Even though this team reward is the most direct signal that can be used for solving various types of mSPs, training decentralized cooperative policy using single sparse and delayed reward is notoriously difficult (Riedmiller et al., 2018; Hare. 2019). The high variance of the reward, due to the combinatorial nature of mSP, adds an additional difficulty. handle such difficulties, we employ two training stabilizers, reward normalization, and Clip-REINFORCE.
5.1 REWARD NORMALIZATION
We denote the makespan induced by policy no as M (TT). We observe that (T)) is highly volatile depending the problem size (N, m) and no- To reduce the variance of the reward incurred from
5

---

Under review as a conference paper at ICLR 2022
the problem size, propose to the normalized makespan M (To, mb) computed as:
M(TTO - ((m)
M (TO, mT)
M (
where To. is the current policy and baseline policy respectively.
A similar normalization scheme that only measures the performance difference between and me has been investigated in RL applications for solving single-agent scheduling problems (Kool et al., 2018: Cao al.. 2021: Kwon al., 2020). Such normalization can provide consistent learning signals when the training instance sizes (i.e. N) are fixed, which is a common practice for training RL methods to solve single-agent scheduling problems. However, we observed that even if N fixed, the (optimal) makespan of mTSP can differ severely m changes. To reduce the variability of the makespan due to m, we further divide the makespan difference by M (T6).
Using M (To, To), we compute the normalized return (TT, To) as follows:
(To, Tb) - ---->MMa Tb)
where T is the index of the terminal state, and y is the discount factor of MDP. The minus sign is for minimizing the makespan. Note that, in the early phase of mSP (when 7 is small), is difficult estimate the makespan. Thus, we place smaller weight (i.e, - M (TT, mb), which is evaluated when r is small (early stage).
5.2 CLI-REINFORCE
Even a small change in a single assignment can result in a dramatic change to the makespan due to the combinatorial nature of mSP. Hence, training the value function that predicts G, reliably difficult. We thus propose to utilize Clip-REINFORCE, a variant PPO (Schulman et al., 2017) without the learned value function, for training ScheduleNet. The objective of the Clip- REINFORCE is given as follows:
E [min(clip(pr.) -,,-e,,11 G)GT,,,G.) ((0)= (0.RR))NT
where clip(r, b) {a if a. < < b.b if 2 b), is the clipping parameter, Gr shorthand notation for G- Tb), and Pr x (a/119/)/ Tom (47) is the ratio between the current policy me and the policy before the update T8
EXPERIMENTS
In this section, we evaluate the performance of ScheduleNet mTSP and JSP. To calculate the inference time, we run all experiements on the server equipped with AMD Threadripper 2990WX CPU. We single CPU core for evaluating all algorithms.
6.1 MTSP EXPERIMENTS
Training. We denote (N X m) as the mTSP with N cities (tasks) and m salesmen (agents). To generate a random mTSP instance, we sample N and m from U(15, 30) and U(3, 4), respectively. Similarly, the Euclidean coordinates of N cities are sampled uniformly from the unit square. ScheduleNet is trained on random mTSP instances that are generated on-the-fly. For MSP experimental results, evaluate the performance of single trained ScheduleNet model. Please refer to Appendix C.3 for more information regarding the training details.
Results on random mTSP datasets. To investigate the generalization capacity of ScheduleNet to various problem sizes, we evaluate ScheduleNet on the randomly generated mSP datasets. Each (N m) dataset consists of 100 random uniform mTSP instances.
We consider the four baseline algorithms to measure the performance of ScheduleNet. As the non- learning baselines, LKH3 (Helsgaun, 2017) and Google OR-Tools (Perron & Furnon) are used. It noteworthy that LKH3 known to find the optimal solutions for the mTSP problems with the identified optimal solutions. Thus, the makespans computed by LKH3 the proxies for the

---

Under review as a conference paper at ICLR 2022
LGH
OR Tools
Schedkleket
Table 1: Random mTSP results. GNN-DisPN results are reproduced
from Hu et al. (2020).
Runtirme (sac)
N
30
100
200
Gop
3
5
10
10
15
2.37
194
200
1.95
1.91
2.50
1.97
1.98
2.04
2,00
1.97
1.00
OR Tools
225
195
2.04
2.41
2.03
2.03
2.33
2.33
GNN-DIPP
2.12
1.95
2.48
2.09
(A.
2.32
2.00
2.29
2.11
2,03
2.72
2.47
2.09
2.40
2.20
1.13
DAN (x66)
2.2
1.66
2.12
1,95
2.55
2.05
2.00
2.40
2.20
1.08
8.3
30
4.9
50 4.9
50 k7
50
100
x
100
100 10
10
200 10
210
200
ScheduleNer (g)
2.32
2,17
2.07
1.9%
2.59
2.83
2.07
2.45
2.24
1.09
SchedbleNet (x66)
2.2
1.96
2.07
1.99
1.92
2.43
2.03
1.99
2.25
2.08
2.05
1.04
Figure 2: mTSP runtimes
Table 2: mTSPLib results. CPLEX results with are optimal solutions. Otherwise, the known-best upper bound of CPLEX results reported.
Instance
e951
Berlin32
et76
Gap
LKHB
222.7
159.6
124.0
112.1
4110.2
3244.4
2441.4
2440.5
250.9
197.3
728.5
587.2
469.3
443.9
OR-Toools
243.3
120.5
137.5
112.1
4665.
33113
24826
2440.9
318.0
212.4
143.4
126.3
262.3
552.1
473,7
462.5
DAN (g)
274.2
176.9
158.6
118.
5,2260
4,2784
2,75888
2,6068
361.1
251.5
170.9
148.5
930.8
674.1
504.0
466.4
1.18
DAN 64)
252.
176.9
128.2
114.3
5,097.7
3,45877
2,677.1
2,494.
336.7
228.1
157.9
134.5
966.5
097.7
495.6
462.0
1.11
ScheduleNet (p.)
2639
200.5
131.7
1169
4,826
3,6422
27578
25146
330.2
228.8
163.9
144.8
843.8
0913
524.5
480.5
1.33
SchchileNet
230.3
173.5
125.8
112.
4,901.6
3,276.
2,51733
2,41.4
317.7
220.8
153.8
131.7
78L2
627.1
502.3
464.4
1.03
optimal solutions. As the RL baselines, GNN-DisPN (Hu et al., 2020) and DAN (Cao et al., 2021) considered (To the best of our knowledge, these the only RL-based algorithms tried solve the min-max mTSP problems).
Table shows the average makespans and average gaps (i.e., the relative makespan w.r.t LKH3) of ScheduleNet and the baseline algorithms on various-sized random mTSP instances. ScheduleNet generally shows leading performances compared to the baseline algorithms even though it trained on the smallest test setup x30x3). 3). In addition, Figure compares the average computation times and their standard deviations for each problem size, clearly indicating that ScheduleNet significantly faster than traditional heuristic solvers (LKH3 and OR-Tools). The computational time difference among RL-approaches almost not noticeable.
Results on Public Benchmarks. Next, to explore the generalization of ScheduleNet to problems that come from completely different distributions (e.g., real-world data), we present the results on the TSPib dataset defined by Necula et al. (2015). mTSPLib consists of four instances of size 5 51, 52, 76 and 99 from TSPLib (Reinelt, 1991), each of which is extended to multi-agent setups where equals to 2, 3, 5, and 7.
Table 2 shows the the makespans and average gaps w.r.t CPLEX of the algorithms. ScheduleNet still exhibits comparable performance to OR-tools, while DAN shows significant performance drops. From this experiment, we can observe that ScheduleNet is effective solving both randomly generated and real-worke mTSPs problems (i.e., robust transferability over data distribution shift).
6.2 ABLATION STUDIES
In this paper, we propose TGA the representation learning module, and Clip-REINFORCE (CR) as the training method. Here, we provide the experimental results that show the effect of proposed TGA and CR the training and testing performance of ScheduleNet.
We train variants of the ScheduleNet models as the target of the ablation studies as follows:
IGA-RRENNORRHE the model using TGA and is trained by REINFORCE (Williams, 1992).
CN-CR: the model using the graph network (GN) layer (Battaglia et al., 2018) is trained by CR.
TGA-CR: the model using TGA and is trained by CR; the proposed ScheduleNet.
Figure 3 compares the normalized makespans of the three ablation models on the validation test instance (30x3) during training, and Table 3 shows the makespans on the test instances.

---

Under review as a conference paper at ICLR 2022
2.5
N
TGA-R.
GN-CR
TGA-CE CR
Norm, pert.
6.04
2.67
2.59
2.0
4.59
2.26
2.13
15
3.56
2.36
2.07
10
11.27
2.61
2.45
200
6.18
2.41
2.24
1.0
20
4.55
2.52
2.17
2000
4000
6000
8000
10000
Training step
Table 3: mTSP ablation results
Figure 3: Training curves
50
100 10
200 20
Oracle
Scheduletiet
Ortools-(R)
Norm average makesgan
Average makespan
2.8
Runtime
10%
30%
50%
10%
30%
50%
N.
Figure 4: Limited observation scenarios
Figure Online routing scenarios
REA-FORREO vs. TGA-CR: By comparing the learning curves of these two ablation models, we can see the effect of the proposed CR as a learning algorithm. The REINFORCE is not able to learn meaningful policy.
GN-CR vs. TGA-CR: By comparing the learning curves of these two models, we can see the effect of TGA as representation module. TGA induces more stabilized and faster performance improvement. addition, as shown in Table 3, TGA-CR (ScheduleNet) consistently shows better performance than GN-CR in the test datasets. The performance difference between the two models becomes severe as N and m increase. This again highlights the role of TGA solving mTSP.
6.3 MTSP VARIANTS EXPERIMENTS
In this section, we further investigate the performance of ScheduleNet in more practical scenarios of mTSP: (1) limited observation, and (2) online routing.
Limited observation scenarios. In the real-world application of mTSP, some salesmen may not be able gather all the information about the other salesmen due the limited communication capabilities (e.g., delivery trucks are located in distant). In such a scenario, the agent should decide the next city visit with local observations. To consider this realistic scenario, limit the number of observable salesmen N, from the global state G, and investigate its performance.
We employ ScheduleNet solve the test instances, whose sizes are (50x5), (100x 10), and (200x20), by varying N,. As shown in Figure 4, the makespan decreases as N, increases because the extended communication scope can induce enhanced coordinations among salesmen. Note that N, = ( indicates the case where each salesman makes entirely independent actions without considering the other salesmen at all. The results implies that ScheduleNet able to learn an effective cooperative policy that minimizes the makespan, and can perform well robustly even with limited communication capabilities.
Online routing scenarios. ScheduleNet, dynamic scheduling problem in an online manner, it reschedules inherently whenever a new event occurs (i.e., agent finishes the assigned task the new task appears) while considering the updated agent and task distribution. We evaluate this capability by solving the online mTSP problem where new cities arise dynamically during the course of the scheduling problem.
decentralized constructive heuristic, can solve the
We first randomly generate 100 (30x3) test instances. Then, while simulating these scenarios with the scheduling policies, sequentially add 30 x N,% % cities the simulation (the exact addition
8

---

Under review as a conference paper at ICLR 2022
Table 4: Taillard's 80 results. The gaps measured w.r.t the optimal (or the best-known) makespan.
15x
10x
20
30
30
50x
50x
x00
Gap
MOR
1,205
1.236
1.217
1.249
1.173
1.177
1.092
1.092
1.197
FIFO
1.239
1.314
1.275
1.319
1.310
12206
1.239
1.136
1.255
SPT
1.258
1.329
1.278
1.349
1.344
1.241
1.256
1.144
1.275
Zhang al. (2020)
1.259
1,300
1,316
1,319
1,336
1.224
1.264
1.136
1.269
Park et al. (2021)
1.171
1.202
1.228
1.189
1.254
1.159
1.174
1.070
1.181
ScheduleNet
1.153
1.194
1.172
1.180
1.187
1,138
1.135
1.066
1.154
moment and locations are unknown to policies before the addition) and evaluate how the policies effectively replan the schedules according such online scenarios. We compare the makespan of ScheduleNet with (I) oracle planning that plans once while knowing all future demands (its appearing locations and times), and (2) re-planing heuristics that replans the future actions whenever 8, is updated. Please refer to Appendix C.4 for more details regarding the simulation and baselines.
Figure shows the average makespans computed using 100 random online scenarios. As shown in the left plot, ScheduleNet always produces a shorter makespan and shorter runtime than the replanning heuristic for all N, values, proving its effective adaptability and robustness to dynamically changing cities. Note that as No increases, the makespan and the runtime increase for all methods due the increased uncertainty and the number of replanning.
6.4 JSP EXPERIMENTS
We employ ScheduleNet to solve JSP, another important class of mSP, to evaluate its generalization capacity in solving various types of mSPs. The goal of the JSP is to schedule machines (i.e., agents) manufacturing facility to complete the jobs that consist of a series of operations (tasks) while minimizing the total completion time (makespan). Solving JSP is considered be challenging since it imposes additional constraints that schedulers must obey: precedence constraints (i.e., an operation of job cannot be processed until its precedence operation is done) and agent-sharing constraints (i.e., each agent has a unique set of feasible tasks).
Formulation. We formulate JSP as MDP where 8, is the partial solution of JSP, 0,, is agent- task assignment (i.e., assigning an idle machine to one of the feasible operations), and reward is the minus of makespan. Please refer Appendix D.I for the detailed formulation of MDP.
Training. We train ScheduleNet using the random JSP instances (N x m) that have N jobs and m machines. We sample N and from (7, 14) and U(2, 5) respectively generate the training ISP instances, and randomly shuffle the order of the machines in job to generate machine sharing constraints. Please refer Appendix D.3 for more information.
Results on public benchmarks. We evaluate the makespan to verify ScheduleNet's generalization capacity to unseen JSP distributions on the Taillard's 80 dataset (Taillard, 1993). We compare ScheduleNet against the deep RL baselines (Park et al., 2021; Zhang et al., 2020), as well as three JSP heuristics; Most Operation Remaining (MOR), First-n--frsstoot (FIFO), and Shortest Processing Time (SPT). Both baseline RI. methods were specifically designed to solve JSP by utilizing the well-known disjunctive JSP graph representation (Roy Sussmann, 1964) and well- engineered dense reward functions. Nevertheless, we can observe that ScheduleNet outperforms all baselines in all of the cases while utilizing only a sparse episodic reward (see Table 4). Please refer to Appendix D.5 for the extended benchmark results.
7 CONCLUSION
In this work, we propose ScheduleNet, an RL-based scheduler that can solve various types multi- agent scheduling problems (mSPs) in decentralized manner. Through the extensive experiments, we empirically verified that ScheduleNet is an effective general scheduler that can solve various mSPs, a cooperative scheduler that induces multi- agent coordination to achieve common objective, and a scalable scheduler that can solve large scale static scheduling problems. Furthermore, we have validated that ScheduleNet can be used to solve online scheduling problems.

---

Under review as a conference paper at ICLR 2022
8 ETHICS STATEMENT AND REPRODUCIBILITY DISCUSSION
Ethics statement The proposed method aims to learn a decentralized policy to solve practical large-scale multi-agent scheduling problems. With the recent advanced robotics and communication technologies, the proposed method can be considered and employed as a solver for real-life logistic problems. However, our method does consider the subjective values (social protections for the underprivileged or expedited dispatching for life-threatening demands) in the process of decision- making or learning. Thus, our method may produce scheduling results that are not well aligned with human decision-makee makers in such cases.
reproducibility As machine learning researchers, we consider the reproducibility of numerical results as one of the top priorities. Thus, we put a significant amount of effort into pursuing the reproducibility of our experimental results. As such efforts, we set and tracked the random seed used for experiments and confirmed the experiments were reproducible. Furthermore, also prepare to open-source our mTSP MDP environments so that the follow-up research can be assessed in unified way.
REFERENCES
Sungsoo Ahn, Younggyo Seo, and Jinwoo Shin. Learning what to defer for maximum independent sets. In Hal Daumé and Aarti Singh (eds.), Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pp. 134-144. PMLR, 13-18 Jul 2020.
David Applegate and William Cook. A computational study of the job-shop scheduling problem. ORSA Journal computing, 3(2):149-13) 156, 1991.
Iurü Bakach, Ann Melissa Campbell, Jan Fabian Ehmke, and Timothy L Urban. Solving vehicle routing problems with stochastic and correlated travel times and makespan objectives. EURO Journal on Transportation and Logistics, 10:100029 2021.
Peter W Battaglia, Jessica B Hamrick, Victor Bapst, Alvaro Sanchez-Gonzalez, Vinicius Zambaldi, Mateusz Malinowski, Andrea Tacchetti, David Raposo, Adam Santoro, Ryan Faulkner, et al. Relational inductive biases, deep learning, and graph networks. arXiv preprint arXiv:1806.012200 2018.
Irwan Bello, Hieu Pham, Quoc V Le, Mohammad Norouzi, and Samy Bengio. Neural combinatorial optimization with reinforcement learning. arXiv preprint arXiv: 1.09940, 2016.
Yuhong Cao, Zhanhong Sun, and Guillaume Sartoretti. Dan: Decentralized attention-base based neural network to solve the minmax multiple traveling salesman problem. arXiv preprint arXiv:2/09.060 04205, 2021.
Xinyun Chen and Yuandong Tian. Learning to perform local rewriting for combinatorial optimization. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buce Buc, Fox, and R. Gamett (eds.), Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
Paulo R O da Costa, Jason Rhuggenaath, Yingqian Zhang, and Alp Akcay. Learning 2-opt heuristics for the traveling salesman problem via deep reinforcement learning. In Sinno Jialin Pan and Masashi Sugiyama (eds.), Proceedings The 12th Asian Conference on Machine Learning, volume 129 of Proceedings of Machine Learning Research, pp. 465-480, Bangkok, Thailand, 18-20 Nov 2020. PMLR.
Henry Fisher. Probabilistic learning combinations of local job-shop scheduling rules. Industrial scheduling, pp. 225-251, 1963.
Zhang-Hua Hua Fu, Kai-Bin Qiu, and Hongyuan Zha. Generalize small traited model arbitrarily large tsp instances, 2021.
Thomas Gabel and Martin Riedmiller. Distributed policy search reinforcement learning for job-shop scheduling tasks. International Journal of production research, (0(1):41-61, 2012.
10

---

Under review as a conference paper at ICLR 2022
Joshua Hare. Dealing with sparse rewards in reinforcement learning. arXiv:1910.09281. 2019.
arXiv preprint
Keld Helsgaun. An extension of the wekkeeniggan--hlssgeee tsp solver for constrained traveling salesman and vehicle routing problems. Roskilde: Roskilde University, 2017.
Yujiao Hu, Yuan Yao, and Wee Sun Lee. A reinforcement learning approach for optimizing multiple traveling salesman problems over graphs. Knowledge- -ased Systems, 204:106244, 2020.
Chaitanya K. Joshi, Quentin Cappart, Louis-Martin Rousseau, Thomas Laurent, and Xavier Bresson.
Learning tsp requires rethinking generalization, 2020.
Elias Khalil, Hanjun Dai, Yuyu Zhang, Bistra Dilkina, and Le Song. Learning combinatorial optimization algorithms over graphs. In Advances in Neural Information Processing Systems, pp. 6348-6358, 2017.
Wouter Kool, Herke Van Hoof, and Max Welling, Attention, learn to solve routing problems! arXiv preprint 1803
2018.
Wouter Kool, Herke van Hoof, Joaquim Gromicho, and Max Welling. Deep policy dynamic programming for vehicle routing problems, 2021.
Yeong-Dac Kwon, Jinho Choo, Byoungjip Kim, Iljoo Yoon, Youngjune Gwon, and Seungjai Min. Pomo: Policy optimization with multiple optima for reinforcement learning. Advances Neural Information Processing Systems, 33, 2020.
S Lawrence. Resouce constrained project scheduling: An experimental investigation of heuristic scheduling techniques (supplement). Graduate School of Industrial Administration, Carnegie- Mellon University, 1984.
Chun-Cheng Lin, Der-Jiunn Deng, Yen-Ling Chih, and Hsin Hsin-Ting Chiu. Smart manufacturing scheduling with edge computing using multi-class deep q network. IEEE Transactions Industrial Informaics, 2019.
Hao Lu, Xingwen Zhang, and Shuang Yang. A learning-based iterative method for solving vehicle routing problems. In International Conference on Learning Representations, 2020.
Nina Mazyavkina, Sergey Sviridov, Sergei Ivanov, and Evgeny Burnaev. Reinforcement learning for combinatorial optimization: A survey. arXiv preprint WxXiv:2003.03600 2020.
Mohammadreza Nazari, Afshin Oroojlooy, Lawrence Snyder, and Martin Takác. Reinforcement learning for solving the vehicle routing problem. In Advances in Neural Information Processing Systems, pp. 9839-9849, 2018.
Raluca Necula, Mihaela Breaban, and Madalina Raschip. Tackling the bi-criteria facet of multiple traveling salesman problem with ant colony systems. In 2015 IEEE 27th International Conference on Tools with Artificial Intelligence (ICTAI), pp. 873-880, IEEE, 2015.
Junyoung Park, Jaehycong Chun, Sang Hun Kim, Youngkook Kim, and Jinkyoo Park. Learning to schedule job-shop problems: representation and policy learning using graph neural network and reinforcement learning. International Journal of Production Research, pp. 1-18, 2021.
Laurent Perron and Vincent Furnon. Or-tools.
Gerhard Reinelt. Tsplib a traveling salesman problem library. ORSA journal on computing. 3(4): 376-384, 1991.
Martin Riedmiller, Roland Hafner, Thomas Lampe, Michael Neunert, Jonas Degrave, Tom Wiele, Vlad Mnih, Nicolas Heess, and Jost Tobias Springenberg. Learning by playing solving sparse reward tasks from scratch. In International Conference on Machine Learning, pp. 4344-4353. PMLR, 2018
Bernard Roy and B Sussmann. Scheduling problems with disjunctive constraints. Note ds, 9, 1964.
11

---

Under review as a conference paper at ICLR 2022
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint arXiv:1707.06347, 2017.
David Silver, Aja Huang, Chris Maddison, Arthur Guez, Laurent Sifre, George Van Den Driessche, Julian Schrittwieser, Ioannis Antonoglou, Veda Panneershelvam, Marc Lanctot, al. Mastering the game of go with deep neural networks and tree search. nature, 529(7587):4844489 2016.
Robert H Storer, S David Wu, and Renzo Vaccari. New search spaces for sequencing problems with application to job shop scheduling. Management science, 38(10): 14900-109999 1509, 1992.
Eric Taillard. Benchmarks for basic scheduling problems. european journal of operational research, 64(2):278-285 1993.
Ronald J Williams.
Simple statistical gradient-foloownng algorithms for connectionist reinforcement learning, Machine learning, 8(3-4):229-23) 256, 1992.
Yaoxin Wu, Wen Song, Zhiguang Cao, Jie Zhang, and Andrew Lim. Learning improvement heuristies for solving routing problems, 2020.
Takeshi Yamada and Ryohei Nakano. A genetic algorithm applicable to large-scale job-shop problems. In PPSN, volume 2, pp. 281-290, 1992.
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, arXiv preprint arXiv:2010.12361 2020.
12

---

Under review as a conference paper at ICLR 2022
ScheduleNet Supplementary Material
Table of Contents
A Details of Type-aware Graph Attention
14
B Extended discussion for reward normalization scheme
15
C Details of mTSP experiments
16
MDP formulation
Agent-tash task graph formulation
................................
C33 Training details
16
C.4 Online routing scenarios
17
D Details of JSP experiments
17
D.1 MDP formulation
18
D.2 Agent-task graph formulation
18
Training details
D.4 Baseline implementations
D.5 Extended public benchmark JSP results
20
13

---

Under review as a conference paper at ICLR 2022
A DETAILS OF TYPE-AWARE GRAPH ATTENTION
In this section, we thoroughly describe the computation procedures of type-aware graph attention (TGA). Similar to the main body, We overload notations for the simplicity of notation such that the input node and edge feature as h2 and hiy. and the embedded node and edge feature hy and hlg respectively.
The proposed TGA performs graph embedding with the following three phases: (1) type-aware edge update, (2) type-aware message aggregation, and (3) type-aypaar node update.
Type-aware edge update The edge update scheme is designed to reflect the complex type relationship among the entities while updating edge features. First, the context embedding Gjj of edge ejj is computed using the source and destination node type kú ky such that:
Cjj [Emb(k),, Emb(ky)
(A.1)
where Emb(.) is trainable lookup table function. Next, the type-aware edge encoding ui is computed using a multilayer perceptron (MLP) as follows:
Wkj MLP MeLPetype (hi; htj Cij)
(A.2)
where MI. pttppe (-) is the type-aware edge encoding MLP. uij can be seen as dynamic edge feature which varies depending on the source and destination node type. Then, the updated edge embedding hly and its attention logit 2ij are obtained as:
Mij MLP edge (Maz)
(A.3)
2ij MLP (uig)
(A.4)
where MLP edge and MLP attn is the edge updater and logit function, respectively. The edge updater and logit function produce updated edge embedding and logits from the type-aware edge.
The computation steps of equations A.I, A.2 and A.3 are defined as TGAr- Similarly, the computation steps of equations A, A.2 and A.4 are defined as TGA
Type-aware message aggregation We first define the type-k neighborhood of i as N₂ = {mikk = k, Vu, Mii), where (iii) is the in-neigborhood set of 0, The proposed type-aware message aggregation procedure computes attention score Oij for the eij. which starts from vy and heads to ni such that:
exp(zi))
Oij- EIENs, (1) exp(zu)
(A.5)
Intuitively speaking, The proposed attention scheme normalizes the attention logits of incoming edges over the types. Therefore, the attention scores sum up to 1 over each type-k neighborhood. Next, the type-k neighborhood message m for node es is computed as:
m
Σ asyhly
(A.6)
JENL()
In this aggregation step, the incoming messages of node are aggregated per type. All incoming type neighborhood messages are concatenated to produce (inter-type) aggregated message m, for v. such that:
Σ m KEK
m,
(A.7)
Type-aware node update Similar to the edge update phase, the context embedding e; is computed first for each node ey:
=
Emb(ks)
(A.8)
where Emb(.) a trainable lookup table function. Then, the updated hidden node embedding hy is computed as below:
K MIP node (hi, ma, G3)
(A.9)
where MLP MLP is the type-aware node updater. The computation steps of equations A.8, and A.9 defined TGAy-
14

---

Under review as a conference paper at ICLR 2022
B EXTENDED DISCUSSION FOR REWARD NORMALIZATION SCHEME
In this section, we further discuss the effect of the proposed reward normalization scheme and its variants the performance of ScheduleNet. The proposed reward normalization (i.e. normalized makespan) mn(T, TT) is given as follows:
m(T, mb) M M(TO) M (mb)
(A.10)
M (TD)
where my is the baseline policy.
Effect of the denominator m(T,, nT. measures the relative scheduling supremacy of the Th- Similar reward normalization scheme, but without (T²) division, is employed to solve single- agent scheduling problems Kool et al. (2018). We empirically found that the division leads in much stable learning when the scale of makespan change (e.g. the area of map change from the unit square different geometries or the size of training instances are varying).
Effeet of the baseline selection A proper selection of Ta is essential to assure stable and asymptotically better learning of ScheduleNet. Intuitively speaking, choosing too strong baseline (i.e. policy having smaller makespan such LKH3 and OR-tools) can makes the entire learning process unstable since the normalized reward tends to have larger values. On the other hand, employing too weak baseline leads in virtually no learning since the m(T, mb) becomes nearly zero.
We select Ty Greedy(1) and this baseline selection has several advantages from selecting fixed/pre-existing scheduling policy: (1) Entire learning process becomes independent from existing scheduling methods. Thus ScheduleNet applicable even when the theap-and--erformiin some target mSP does not exist. (2) Greedy(T) serves as an appropriate T6 (either not too strong or weak) during policy learning. We experimentally confirmed that the bascline section Greedy(m) results in better scheduling policy as similar to the several literature Kool et al. (2018); Silver et al. (2016).
Ta for
15

---

Under review as a conference paper at ICLR 2022
C DETAILS OF MTSP EXPERIMENTS
In this section, we provide the details of mTSP exepriments.
C.I MDP FORMULATION
The formulated mTSP MDP is event-based. Here we discuss the further details about the event- based transitions of mTSP MDP. Whenever all agents are assigned to cities, the environment transits in time, until any of the workers arrives to the city (i.e. completes the task). Arrival of the worker to the city triggers correspondingly assigned cities. We assume that each worker transits towards the assigned city with unit speed in the 2D Euclidean space, ie. the distance travelled by each worker equals the time past between two consecutive MDP events.
event, meanwhile the other assigned salesman are still the way to their
It is noteworthy that multiple events can happen at the same time, typically when time stamp t 0. the MDP has multiple available workers at the same time, we repeatedly choose an arbitrary idle agent and assign it the one of idle task until agent is idle, while updating event index т. This random selections do not alter the resulting solutions since we do not differentiate each agent (i.e. agents homogeneous agents).
C.2 AGENT-TASK GRAPH FORMULATION
In this section, present the list of all possible node types in G,:(I) assigned-agent, (2) unassigned-
agent (i.e. idle), (3) assigned-task, (4) unassigned-task, (5) inactive-task (i.e. visited city) and (6) depot. Here, do not include inactive-agen (i.e. salesmen already return to the depot) to the graph. For edge types, we don't define them explicitly rather we consider the combination of source and destination types the edge type. All nodes in the G, are fully connected.
C.3 TRAINING DETAILS
Network parameters. ScheduleNet is composed of three components. The first components generates the initial node embedding (n()) and edge {h.y by using linear projections. The second component (TGA), which utilizes MLP(64) as MLP MLPedge- MLP and MLP repeatedly updates the node and edge emhedding 3 times to generate ( and edge (1, ). The last component MIP which is parametrized as MLP(66,, 32), generates action logits from the set
of node and edge embedding. All input and output dimensions of MLPs are 64 and hidden actions are Lea
16

---

Under review as a conference paper at ICLR 2022
Training pseudocode.
We presents pseudocode for training ScheduleNet.
Algorithm 2: ScheduleNet Training
input : Training policy тæ. baseline policy T
output: Optimized policy Tee
Initialize the baseline policy with parameters & +-
for update slep do
Initialize sample buffer <- for number of episodes E do
Generate random mTSP instance I
Th < aT))
Construct mTSP MDP from the instance I
Collect samples S = (gr, dr To (r) (Too, mb)) with and ma from the MDP.
DUS.
end 10
11
for inner updates K do
Calculate the loss (()) with D
13
0 v
14
end
15
< 36 + (1 3)0
16
end
17
return T2
We set the MDP discounting factor 7 to 0.99, learning rate a to 0.0001, E' to 128, K to 4, 3 to 0.01, and the clipping parameter of Clip-REINFORCE to 0.2. We training seed as 1234.
C.4 ONLINE ROUTING SCENARIOS
Scenario generation In this paragraph, we thoroughly explain the online routing scenario generation scheme. To generate the scenarios, we first fix the number of cities added during the online routing. Once the number of cities given, we then decide the locations of the cities by taking midpoints of cities. We assign the location of the city that will be first added as the midpoint between the first and second cities the mTSP map. Similarly, the location of the second city is set the midpoint between the second and third cities. Using the same logic, of the newly added cities. Lastly, we decide the timing of city addition by using (near) optimal solutions (e.g., LKH3) M (TT). We first compute divide M (ær) by 1.0 < and then evenly allocate the timing of additions from 0.0 to M (T(T)/s.. This ensures all "to be added" cities are added during the online routing simulation no matter what scheduling policies are evaluated. We set =
decide all positions
explain the implementations of baseline algorithms. To implement the oracle planning, we reformulate the online routing problem as vehicle routing problem with time constraints (VRP-TW). In the VRP-TW, we the time window constraints for the originally existing cities as (0, M), where M is a large number. For the newly added cities, the lower and upper bounds of the time window are set their addition times and M. The re-planing heuristics are implemented with OR-tools (Perron & Furnon).
Baseline implementations In this paragraph,
D DETAILS OF JSP EXPERIMENTS
Job-shop scheduling problem (JSP) mSP that can be applied various industries including the operation of semi-conductor chip fabrication facility and railroad system. The objective of JSP to find the sequence of machine (agent) allocations to finish the jobs (a sequence of operations; tasks) as soon as possible. JSP can be seen as extension of mTSP with two additional constraints: (1) precedence constraint that models a scenario where an operation a job becomes processable only after all of its preceding operations confines the machine to process only one operation at time. Due to these additional constraints, JSP is considered to be more difficult problem when it is solved via mathematical optimization
done; (2) agent-sharing (disjunctive) constraint that
17

---

Under review as a conference paper at ICLR 2022
Job: series of operations
0
0
0,
Job
0
O2
O
Machine
Machine 2
Machine 3
Figure 7: Precedence constraint
Job 2
0
05
O6
Job
0
Machine
Job
07
Og
Job 2
O4
Operation
Figure 6: Disjunctive graph representation JSP
Figure 8: Agent-sharing constraint
techniques. A common representation of JSP is the disjunctive graph representation. As shown in Figures 6, 7 and 8, JSP contains the set of jobs, machines, precedence constraints, and disjunctive constraints as its entities. In the following sections, we provide the details of the proposed MDP formulation of ISP, training details ScheduleNet, and experiment results.
D.1 MDP FORMULATION
The MDP formulation of JSP is similar to that of mTSP. The specific definitions of the state and action for JSP are as follows:
State. We define S. (fs² N+m sm which is composed of two types of states: entity state s and environment state ..Th
[{$>)==1 7]i=1
s (pt, processabll 1, assigned 1 aecessible 1 waiting) the state the i-th entity, pf is the processing
time of the i-th entity at the t-th event. 1, Processable indicates whether the i-th task is processable by the target agent or not. Similar to mTSP, 1 ussigned indicates whether agent/task is assigned. s, contains the current time of the environment, the sequence of tasks completed by each agent (machine), and the precedence constraints tasks within each job.
Action. We define the action space at the 7-th event as set of oeprations that is both processable and currently available. Additionally, define the waiting action reservation of the target agent (i.e. the unique idle machine) until the next event. Having waiting as action allows the adaptive scheduler (e.g- ScheduleNet) to achieve the optimal scheduling solution (and also makespan) from the JSP MDP, where the optimal solution contains waiting (idle) time intervals.
D.2 AGENT-TASK GRAPH FORMULATION
ScheduleNet constructs the agent-task graph G, that reflects the complex relationships among the entities in s,. ScheduleNet constructs directed graph G, (V, E) out of s,, where V is the set of nodes and is the set of edges. The nodes and edges and their associated features are defined as:
denotes the i-th node and represents either agent task. contains the node feature xy = ( where s² the state of entity i, and k; the type of ; (e.g. if the entity is task and its 1processable = 1, then the k; becomes processable-tast type.)
eij denotes the edge between the source node v, and the destination node v, The edge feature wij is a binary feature which indicates whether the destination node v; is processable by the source node U/-
All possible node types in Gr are: (1) ussigned-agent, (2) umassigned-agent agent, (3) assigned-taske (4) processable-task. and (5) unprocessable-task. We do not include completed tasks in the graph. Thus, the currently active tasks are the union the assigned tasks, pancessable-tssee. and unprocessable- tasks. The full list of node features are follows:
18

---

Under review as a conference paper at ICLR 2022
Agent (Machine
01
02
0
Agent 2
04
05
06
Agent
07
03
Figure JSP agent-lask graph representation
1 agent indicates whether the node is agent or task.
jarget-agent indicates whether the node is target-agent (unique idle agent that needs to be assigned).
assigned indicates whether the agent/task is assigned.
1, waiting indicates whether the node is agent in waiting state.
pmocessable indicates whether the node is task that is processable by the target-agent.
socessblle indicates whether the node processable by the target-agent and available.
Task wait time indicates the amount of time passed since the operation became accessible.
Task processing time indicates the processing time of the operation.
Time-to-comee comclleeee indicates the amount of time it will take complete the task, i.e. the time- distance to the given task.
Remain ops. indicates the number of remaining operations to be completed for the job where the task belongs to.
Job completion ratio is the ratio of completed operations within the job to the total amount of operations the job.
JSP graph connectivity. Figure 9 visualizes the proposed agent-task graph. From Figure 9, each agent is fully connected the set of processable tasks by that agent, and vice versa. Each task is fully connected to the other tasks (operations) that belong to the same job. Each agent is fully connected the other agents.
D.3 TRAINING DETAILS
We use the same training hyperparameters as Appendix C.3.
D.4 BASELINE IMPLEMENTATIONS
Priority dispatching rules (PDR) is of the most common JSP solving heuristics. PDR computes the priority of the feasible operations (i.e. the set of operations whose precedent operation is done and, the same time, the target machine is idle) by utilizing the dispatching rules. As the JSP heuristic baselines, we consider the following three dispatching rules:
Most Operation Remaining (MOR) sets the highest priority to the operation that has the most remaining operations to finish its corresponding job.
First-in-first-out (FIFO) sets the highest priority to the operation that joins to the feasible operation set first.
Shortest Processing Time (SPT) sets the highest priority to the operation that has the shortest processing time.
19

---

Under review as a conference paper at ICLR 2022
Table 5: Job-shop scheduling makespans TA dataset (Part
Instance
N
SPT
FIFO
MOR
Park et al. (2021)
Zhang al. (2020)
ScheduleNet
OPT
Ta01
15 15
1462
1486
1438
1389
1443
1452
1231
Ta02
15 x
1446
1486
1452
1519
1544
1411
1244
Ta03
15
1495
1461
1418
1457
1440
1396
1218
Ta04
15 15
1708
1575
1457
1465
1637
1348
1175
Ta05
15 x 15
1618
1457
1448
1352
1619
1382
1224
Ta06
15 x 15
1522
1528
1486
1481
1601
1413
1238
Ta07
15 x 15
1434
1497
1456
1554
1568
1380
1227
Ta08
15 x 15
1457
1496
1482
1488
1468
1374
1217
Ta09
15 x 15
1622
1642
1594
1556
1627
1523
1274
Ta1o
15 x 15
1697
1600
1582
1501
1527
1493
1241
Tal
20 x 15
1865
1701
1665
1626
1794
1612
1357
Tal2
20 x 15
1667
1670
1739
1668
1805
1600
1367
Ta13
20 x 15
1802
1862
1642
1715
1932
1625
1342
Ta14
20 x 15
1635
1812
1662
1642
1664
1590
1345
Ta15
20 15
1835
1788
1682
1672
1730
1676
1339
Ta16
20
1965
1825
1638
1700
1710
1550
1360
Ta17
20 15
2059
1899
1856
1678
1897
1753
1462
Ta18
20 15
1808
1833
1710
1684
1794
1668
1396
Ta19
20 x 15
1789
1716
1651
1900
1682
1622
1332
Ta20
20 x 15
1710
1827
1622
1752
1739
1604
1348
Ta21
20 20
2175
2089
1964
2199
2252
1921
1642
Ta22
20 20
1965
2146
1905
2049
2102
1844
1600
Ta23
20 x 20
1933
2010
1922
2006
2085
1879
1557
Ta24
20 x 20
2230
1989
1943
2020
2200
1922
1644
Ta25
20 x 20
1950
2160
1957
1981
2201
1 1897
1595
Ta26
20 x 20
2188
2182
1964
2057
2176
1887
1643
Ta27
20 x 20
2096
2091
2160
2187
2132
2009
1680
Ta28
20 x 20
1968
1980
1952
2054
2146
1813
1603
Ta29
20
2166
2011
1899
2210
1952
1875
1625
Ta30
20
1999
1941
2017
2140
2035
1913
1584
Ta31
30 x 15
2335
2277
2143
2251
2565
2055
1764
Ta32
30
2432
2279
2188
2378
2388
2268
1784
Ta33
30
2453
2308
2316
2324
2281
1791
Ta34
30 15
2434
2546
2193
2319
2332
2061
1829
Ta35
30 15
2497
2478
2255
2333
2505
2218
2007
Ta36
30 x 15
2445
2433
2307
2210
2497
2154
1819
Ta37
30 x 15
2664
2382
2190
2201
2325
2112
1771
Ta38
30 x 15
2155
2277
2179
2151
2302
1970
1673
Ta39
30 x 15
2477
2255
2167
2138
2410
2146
1795
Ta40
30 x 15
2301
2069
2028
2007
2140
2030
1669
D.5
EXTENDED PUBLIC BENCHMARK JSP RESULTS
We provide the detailed JSP results for the following public datasets: TA (Taillard, 1993) (Tables 5 and 6). ORB Applegate & Cook (1991), FT Fisher (1963), YN Yamada & Nakano (1992) (Table 7), SWV Storer et al. (1992) (Table 8), and LA Lawrence (1984) (Table 9).
20

---

Under review as a conference paper at ICLR 2022
Table 6: Job-shop scheduling makespans TA dataset (Part
Instance
N
SPT
FIFO
MOR
Park (2021)
Zhang (2020)
ScheduleNet
OPT
Tu41
30 20
2499
2543
2654
2667
2572
2005
Ta42
30 20
2710
2669
2440
2579
2664
2397
1937
Ta43
30 20
2434
2506
2432
2737
2431
2310
1846
Ta44
30 20
2906
2540
2426
2772
2714
2456
1979
Ta45
30 x 20
2640
2565
2487
2435
2637
2445
2000
Ta46
30 x 20
2667
2582
2490
2681
2776
2541
2004
Ta47
30 x 20
2620
2508
2286
2428
2476
2280
1889
Ta48
30 20
2620
2541
2371
2440
2490
2358
1941
Ta49
30
2666
2550
2446
2556
2301
1961
Ta50
30 20
2429
2531
2469
2530
2628
2453
1923
Ta51
50 x
3856
3590
3145
3599
3382
2760
Ta52
50 15
3266
3365
3303
3157
3341
3231
2756
Ta53
50 15
3507
3169
3115
3103
3186
3083
2717
Ta54
50 15
3142
3218
3265
3278
3266
3068
2839
Ta55
50 x 15
3225
3291
3279
3142
3232
3078
2679
Ta56
50 x 15
3530
3329
3100
3258
3378
3065
2781
Ta57
50 x 15
3725
3654
3335
3230
3471
3266
2943
Ta58
50 15
3365
3362
3420
3469
3732
3321
2885
Ta59
50 15
3294
3357
3117
3108
3381
3044
2655
Ta60
50 15
3500
3129
3044
3256
3352
3036
2723
Ta61
50
3606
3690
3376
3425
3654
3202
2868
Ta62
50 20
3639
3657
3417
3626
3722
3339
2869
Ta63
50 20
3521
3367
3276
3110
3536
31 11
2755
Ta64
50 x 20
3447
3179
3057
3329
3631
2989
2702
Ta65
50 x 20
3332
3273
3249
3339
3359
3168
2725
Тaб6
50 x 20
3677
3610
3335
3340
3555
3199
2845
Ta67
50 x 20
3487
3612
3392
3371
3567
3236
2825
Ta68
3336
3471
3251
3265
3680
3072
2784
Ta69
50 20
3862
3607
3526
3798
3592
3535
3071
Ta70
50 20
3801
3784
3590
3919
3643
3436
2995
Ta71
100
6233
6270
5938
5962
6452
5879
5464
Ta72
100 20
5973
5671
5639
5522
5695
5456
5181
Ta73
100 20
6482
6357
6128
6335
6462
6052
5568
Ta74
100 x 20
6062
6003
5642
5827
5885
5513
5339
Ta75
100 x 20
62.17
6420
6212
6042
6355
5992
5392
Ta76
100 20
6370
6183
5936
5707
6135
5773
5342
Ta77
100
6045
5952
5829
5737
6056
5637
5436
Ta78
100
6143
6328
5886
5979
6101
5833
5394
Ta79
100
20
6018
6003
5652
5799
5943
5556
5358
Ta80
100 20
5848
5763
5707
5718
5892
5545
5183
21

---

Under review as a conference paper at ICLR 2022
Table 7: Job-shop scheduling makespans on ABZ, FT, ORB, and YN datasets.
Instance
N x m
SPT
FIFO
MOR
Park et al. (2021)
ScheduleNet
OPT
abv55
10 10
1352
1467
1336
1353
1336
1234
abz6
10 10
1097
1045
1031
1043
981
943
abz.
20 15
849
803
775
887
791
656
abz8
20 15
929
877
810
843
787
665
abz9
20 15
887
946
899
848
832
678
ft06
6 6
88
65
59
71
59
55
ft10
10 10
1074
1184
1163
1142
1111
930
ft20
20
1267
1645
1601
1338
1498
1165
orb01
10 10
1478
1368
1307
1336
1276
1059
orb02
10 10
1175
1007
1047
1067
958
888
orb03
10 10
1 1179
1405
1445
1202
1335
1005
orb04
10 10
1236
1325
1287
1281
1178
1005
orb05
10 10
1152
1155
1050
1082
1042
887
orb06
10 10
1190
1330
1345
1178
1222
1010
orb07
10 10
504
475
500
477
456
397
orb08
10 10
1107
1225
1278
1156
1178
899
orb09
10 10
1262
I 1189
1165
1143
1145
934
orb10
10 10
1113
1303
1256
1087
1080
944
ynl
20 20
1196
1113
1045
1118
1027
884
yn2
20 20
1256
I 1148
1074
1097
1037
904
yn3
20 20
1042
1135
1100
1083
1046
892
yn4
20 20
1273
1194
1267
1258
1216
968
22

---

Under review as a conference paper at ICLR 2022
Table Job-shop scheduling makespans on SWV datasets.
Instance
N x
SPT
FIFO
MOR
Park ct al. (2021)
ScheduleNet
OPT
swv01
20 10
1737
2154
1971
1761
1913
1407
swv02
20 10
1706
2157
2158
1846
1998
1475
swv03
20 10
1806
2019
1870
1892
1830
1398
swv04
20 x 10
1874
2015
2026
1908
1971
1464
swv05
20 10
1922
2003
2049
1796
1922
1424
swv06
20 x 15
2140
2519
2287
2068
2216
1671
Swv07
20 15
2146
2268
2101
2194
2037
1594
swv08
20
2231
2554
2480
2191
2255
1752
swv09
20 15
2247
2498
2553
2278
2196
1655
swv10
20 15
2337
2352
2431
2141
2279
1743
swvll
50 10
3714
4427
4642
3989
4390
2983
swv12
50 10
3759
4749
4821
4136
4532
2977
swv13
50 10
3657
4829
4755
4008
4602
3104
swv14
50 10
3506
4621
4740
3758
4387
2968
swv15
50 10
3501
4620
4905
3860
4402
2885
swv16
50 10
3453
2951
2924
2924
2924
2924
Swv17
50 10
3082
2962
2848
2840
2794
2794
swv18
50 10
3191
2974
2852
2852
2852
2852
swv19
50 10
3161
3095
3060
2961
2992
2843
Swv20
50 10
3125
2853
2851
2823
2823
2823
23

---

Under review as a conference paper at ICLR 2022
Table 9: Job-shop scheduling makespans LA datasets.
Instance
N x
SPT
FIFO
MOR
Park ct al. (2021)
ScheduleNet
OPT
la01
10 x 5
751
772
763
805
680
666
la02
10 x 5
821
830
812
687
768
655
la03
10 5
672
755
726
862
734
597
la04
10 x 5
711
695
706
650
698
590
la05
10 x 5
610
610
593
593
593
593
la06
15 x 5
1200
926
926
926
926
926
la07
15 x 5
1034
1088
1001
931
1008
890
la08
15
942
980
925
863
863
863
la09
15 x 5
1045
1018
951
951
951
951
la 10
15 x 5
1049
1006
958
966
958
958
lall
20 x 5
1473
1272
1222
1276
1254
1222
la
20
1203
1039
1039
1039
1039
1039
la13
20 x
1275
1199
1150
1150
1150
1150
la14
20 x 5
1427
1292
1292
1292
1292
1292
la15
20 x 5
1339
1587
1436
1282
1395
1207
la16
10 10
1156
1180
1108
1134
1047
945
la17
10 10
924
943
844
953
888
784
la18
10 10
981
1049
942
1049
947
848
la
10 10
940
983
1088
880
963
842
la20
10 10
1000
1272
1130
1042
989
902
la21
15 10
1324
1265
1251
1309
1261
1046
la22
15 10
1312
1198
1158
1027
927
la23
15 10
1162
1354
1268
1085
1145
1032
la24
15 10
1203
1141
1149
1129
1088
935
la25
15 10
1449
1283
1209
1308
1117
977
la26
20 10
1498
1372
1411
1553
1458
1218
la27
20 x 10
1784
1644
1566
1624
1516
1235
la28
20 10
1610
1474
1477
1438
1357
1216
la29
20 10
1556
1540
1437
1582
1320
1152
la30
20 10
1792
1648
1565
1649
1490
1355
la31
30 10
1951
1918
1836
1817
1906
1784
la32
30 10
2165
2110
1984
1977
1850
1850
la33
30 10
1901
1873
1811
1795
1731
1719
la34
30 10
2070
1925
1853
1895
1784
1721
la.5
30 10
2118
2142
2064
2041
1969
1888
la36
15 15
1799
1516
1492
1489
1449
1268
la37
15 15
1655
1873
1606
1623
1653
1397
la38
15 15
1404
1475
1455
1421
1444
1196
la39
15 15
1534
1532
1540
1555
1430
1233
la40
15 15
1476
1531
1358
1570
1357
1222
24


Reviews:
[{"review_id": "sQsDFOUitdT", "reviewer": "Reviewer_VLpo", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "----A post rebuttal edit: \nThanks for providing the detailed clarifications, a revised manuscript, and new experimental results. I have read all these responses. I agree with the advantages of ScheduleNet over other RL-based methods; however, I’m just still not convinced about the novelty of the three modules themselves. Besides, the explanation about not using the value function is far-fetched, and there is already much research about assignments in the MARL community. In addition, when comparing with other RL-based methods, I suggest that the authors provide the number of network parameters to ensure that the advantages achieved by ScheduleNet do not depend on a larger network. However, I keep my positive impression on this work. \n\n\n**Strengths**:\n\n1. The paper is well-organized, and the writing logic is very clear. The Introduction section does not give a flat description but introduces the features of the proposed method one by one; therefore, the readers can have a quick glance at the advantages of the ScheduleNet. The Method section is also clearly structured and easy to understand.\n2. The reinforcement learning framework is suitable for solving sequential decision problems, so it is a reasonable and clever attempt to apply the framework to multi-agent scheduling problems. This paper's adjustments in modeling, representation, and training techniques are all good practices to involve the RL framework.\n\n**Weaknesses**:\n\n1. This submission has some mistakes and typos in writing, including grammar and expression problems, some of which may affect understanding. I only list some of them here. \n\n   (1) Verb mistakes. For example, in the last paragraph on page one, \"a wrong choice at the early stage can results (result) in irreversible poor results at the end\"; In the part about Job-shop scheduling problems on page three, \"However, these methods utilizing (utilize) human-engineered dense reward\"......\n\n   (2) Third-person singular. For example, \"learning-based improvement (improvements) have shown better performance\" in the paragraph about vehicle routing problems on page two; \"such randomness do (does) not alter\" in the action paragraph on page three; \n\n   (3) Writing standard mistakes. For example, nearly all the \"i.e.\" miss the comma (i.e.,); \n\n   (4) Compilation problems. For example, Figure 1 on page three is mentioned on page four for the first time; \n\n   (5) Many article usage mistakes. For example, you should remove the word \"the\" of \"following novelties and the advantages\" in the Novelties paragraph on the second page; In the paragraph about Job-shop scheduling problems on page three, \"solving job-shop scheduling problem\" should be revised as \"solving the job-shop scheduling problem\" or \"solving job-shop scheduling problems\"; Besides, the \"an\" in \"requires an additional training\" should be removed; There are two \"the\" in the transition paragraph on page three;\n\n   (6) Sentence break mistakes. For example, \"A solution to mTSP is considered to be complete when all the cities have been visited (, ) and all salesmen have returned to the depot\" in the first paragraph of page four, a comma should be put before \"and\" because the subject of the sentence changes;\n\n   (7) ......\n\n   While some of these errors do not affect comprehension, they may influence the cogency of this paper. Besides, these basic errors may give the impression that the essay has not been adequately prepared. \n\n2. There are linguistic repetitions in the formulation section. The authors try to give examples to clearly explain some of the definitions but mostly just repeat the definitions—for example, the reward part in subsection 3.1. If the paper sets a subsection about examples, it is recommended to give a straightforward and real example rather than repetition.\n\n3. Why does the essential difference between min-max and min-sum affect the solutions to scheduling problems? This point is understandable but not theoretically stated in the paper. Therefore, the reader cannot tell whether the proposed framework can also solve the min-sum problem. I believe that different scheduling problems may pursue various goals, and the problem with min-max as the goal that this paper tries to solve is only one class of scheduling problems. If the proposed method cannot solve problems with min-sum as the goal, then the proposed approach may have some limitations. I suggest that the authors analyze and explain these issues in their submission.\n\n4. About Novelty. The approach proposed in this paper is an attempt to apply reinforcement learning to scheduling problems. The modeling technique, representation technique, and RL technique are minor improvements on traditional methods and can be summarized as implementation tricks to adapt to scheduling problems. I am therefore skeptical about this paper's novelty and contribution. In terms of the RL community, the contribution of this paper is low. \n\n   I have not previously delved into scheduling problems and have only a passing knowledge in this area, so I cannot accurately assess this method's academic and theoretical contributions in the scheduling area. However, by reading this submission, I believe that its theoretical contribution may be small and the experimental performance is not significantly improved compared to other methods. \n\n   However, if the authors can provide more convincing explanations during the discussion period, I will change my opinion on this problem.", "summary_of_the_paper": "This paper tries to solve traditional scheduling problems by using the deep reinforcement learning (RL) framework. To make the RL framework applicable to such problems, the authors model the problem states as an agent-task graph and encode the nodes in the graph utilizing a type-aware graph attention technique they proposed. The obtained node embeddings are next used to compute the final assignment probabilities. The authors use implementation tricks such as reward normalization and clip-loss to accelerate training or achieve better performance in the training process. The proposed method performs well in the traveling salesmen problem and the job-shop scheduling problem.", "summary_of_the_review": "This paper is an attempt to combine the DRL framework with scheduling problems. It deserves credit for modeling the scheduling problems as MDPs to fit the RL framework and for providing new implementation insights for solving mSPs by utilizing reinforcement learning. However,  this paper has no major innovations or new theoretical insights at the methodological level but minor changes to existing techniques to make a REINFORCE variant applicable to the scheduling problem. Therefore, this paper's contribution to the community may be limited.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "pjyp4jwIcsz", "reviewer": "Reviewer_6uYb", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths: The proposed ScheduleNet can make a tradeoff between computation time and solution efficiency (i.e., makespan).\nWeaknesses: \n1)\tFrom the experimental results, I find the proposed ScheduleNet less attractive. Specially, in the large-scale instance (200, 20), the LKH3 can also return the optimal solution. Although the running time of LKH3 is nearly 1,000 seconds, the ScheduleNet also takes hundreds of seconds. Considering the solution gap between LKH3 and ScheduleNet is 1.04, it is worth of waiting LKH3, especially in the offline settings, where the agents and jobs are known. \n2)\tThe JSP task seems easier than the mTSP task, since the machine in JSP is homogeneous while the salesman in mTSP is heterogeneous with different positions. Thus, my question is that why unify the training frame for these two different scenarios? I am convinced that the ScheduleNet is suitable for mTSP, but more smart mechanism is necessary for JSP. This can also explain that the ScheduleNet performs worse in JSP (Table 4) than that in mTSP. A potential re-organization is to first propose a more simple mechanism for the JSP with homogenous agents, and then to propose a complex mechanism (e.g., ScheduleNet) for the mTSP.\n3)\tIn section 4.1, agent-task graph, the edge e_{ij} between nodes should be defined more clearly. Especially when there should be an edge between two nodes?\n4)\tThis paper claims to propose a coordinated multi-agent approach, ScheduleNet seems like a centralized training and execution framework. Although the authors state “Note that ScheduleNet allows an agent to process its local state information,….appear dynamically.”, it is not clear how these agents coordinate their behavior, for example, when two agents are assigned to the same job, which agent really executes it?    \n5)\tTypos: Section 3: “An event is defined as the the case”->“An event is defined as the case”.\n", "summary_of_the_paper": "This paper proposes a multi-agent reinforcement learning approach to solve scheduling problems (including mTSP and job-shop scheduling (JSP)), with the objective of makespan minimization. In the mTSP, the agent represents salesman, and in JSP, the agent represents machine. The core idea is to employ the type-aware graph attention mechanism to learn the assignment probability of agents to tasks. Experiments on mTSP and JSP simulations validate the strength of the proposed approach ScheduleNet. ", "summary_of_the_review": "This paper proposes a multiagent reinforcement learning approach to solve scheduling problems (including mTSP and job-shop scheduling (JSP)). However, the techniques are not clearly described and the experimental results are not fascinating. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "ljzYP_lIrnr", "reviewer": "Reviewer_7p6U", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "==== A post rebuttal edit: I am satisfied with the author's extended answer, therefore I raise my score.\n\nThe paper is an interesting application of RL coupled with some tricks to the well-known optimization problems. Below are the detailed remarks.\n\n​1. Description of MDP:\n\n * $p_\\tau^i$ is defined as 'position' in Section 3.1. This is not clear. Section C.1. suggests that positions are 2D points.​\n * The generative process of MDP should be explained: how are $p_\\tau^i$ generated, what is the distribution of distances between 'positions'? This could help to give context to the numbers in Tables 1-4.​\n * In the context of the above, the definition of makespan should be made more explicit.\n\n2) Training:\n* PPO uses an advantage normalization trick (among others). It bears some resemblance to the normalization trick in the paper (which is on the reward side, though). Is there some deeper similarity here?​\n* Using advantage makes the method invariant to scalar shift in the rewards. This seems not to be the case for normalized rewards used in the paper. Is this issue a limitation for the method to use it for different optimization problems?  ​\n* It is not clear how the formula (9) is computed, in particular using data gathered in Algorithm 2. This should be made explicit. Similarly, the meaning of the expected value in formula (9) should be described.​\n* It would be interesting to know why the choice of \"slowly varying\" policy as baseline helps. In particular, it seems that this choice has to be related to the *inner updates* loop from Algorithm 2 (lines 9-12) and the choice of $K$. It also somewhat resembles the use of target networks in contemporary RL algorithms.\n  ​\n3) Experiments:\n\n* The description of training in Section 6.1 is slightly confusing. Is the ScheduleNet trained on $30x3$ setup for both Table 1 and Table 2? What is the choice of the *update steps* (lines 2 in Algorithm 2)?​\n* It seems from Appendix C.1. that only one seed is used for training (1234). If so, then this could be worrying, as RL training is known to have high variance.​\n* Values from tables 1-4 are not clear: \n    - what are the entries (makespan? normalized? discounted?)?\n    - can we interpret these numbers (see the questions in point 1)?\n    - what are the confidence intervals for these results?\n    - how does this result compares to the \"size of the graph\", e.g. its\n      diameter?\n    - lack of the above make is if difficult to assess the difference between\n      ScheduleNet and the baselines.​\n* \"Gap\" (last column in Tables 1, 2, 4) is not defined. Make sure that the entries in this column reflect the values computed according to the definition and the values in the table.​\n* The Authors mention real-life applications; however do not specify their scale.\n  In particular, are the problems in the experiments section close to real\n  applications?\n  ​\n* What are the computational limits of the method? How much larger problems can\n  be tackled larger computational resources?", "summary_of_the_paper": "The paper considers solving two well-known combinatorial optimization problems (multiple traveling salesmen problem and job-shop scheduling problem) using neural networks trained with the help of Reinforcement Learning. The approach embeds the problem in an MDP framework with rewards corresponding to a normalized makespan metric and trains the policy using a PPO-like objective.", "summary_of_the_review": "The paper is an interesting application of RL coupled with some tricks to the\nwell-known optimization problems.\nIn its current form, it is below the acceptance threshold, but I am willing\nto increase my score if the authors address the issues raised above.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "96MyybtLfBS", "reviewer": "Reviewer_XP6V", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper proposes a generic framework for solving multi-agent combinatorial scheduling problems. The type-aware embedding for agent-task relationship graph construction is novel and has a distributed framework which can be developed using message passing framework among neighbours. The reward normalization and usage of clip parameter in training REINFORCE algorithm are shown to be effective. I appreciate the extensive amount of empirical results on both mTSP and JSP domains, which demonstrate that the ScheduleNet not only performs efficiently during training process as compared to state-of-the-art methods, but also generalizes well to other real-world datasets. Ablation study also demonstrates the efficacy of embedding methods and two practical modifications made for REINFORCE algorithm. Having said that I have a few comments: (a) The runtime comparison between RL and OR methods is not completely fair as the RL method only consider inference time (training time is not included if I am not wrong). (b) The multi-agent aspect of the problem is somewhat not discussed in properly. I would appreciate adding a distributed RL training algorithm using the messages generated for each node in each time-step. One key issue in multi-agent RL training is non-stationarity; I am not sure how this problem is tackled. (c) Please explain how the different hard constraints for these combinatorial problems are satisfied during RL training? Is it generalizable enough to tackle additional constraints, e.g., time window constraints? (d) I am interested to understand the problem setting for the results of Table 2. The RL algorithm is trained using synthetic dataset (results of Table 1) and then executed in these public datasets? Have you done any incremental training on these public datasets? If not, do you have any insights on why it generalizes so well to these public datasets; does the parametric distribution matches between the synthetic and public dataset? Please clarify.", "summary_of_the_paper": "The paper proposes a generic approach called ScheduleNet to solve combinatorial multi-agent scheduling problems using neural network and reinforcement learning. An agent-task relationship graph is first constructed through edge and node embedding (using message passing framework among neighbours). Message values for each node is computed using type-aware edge embedding value and then a node embedding is performed using the message values. Using these embedding values, ScheduleNet computes assignment probability between idle agent and active tasks. ScheduleNet is trained using reinforcement learning and two methods are proposed to improve training performance: (a) reward normalization and (b) adding clip parameter in REINFORCE algorithm training. Extensive experimental results are demonstrated on mTSP and job-shop scheduling problems. Through benchmarking against state-of-the-art OR heuristics and RL methods, and using ablation studies, it is shown that the ScheduleNet performs efficiently and generalizes well to unknown or online scenarios.", "summary_of_the_review": "The paper solves a combinatorial multi-agent scheduling problem using graph embedding and RL methods. Both type-aware message embedding and practical suggestions to improve REINFORCE algorithm are interesting and performs well. I also appreciate extensive empirical results on two general problem classes against both state-of-the-art OR and RL based techniques. Having said that, I am not confident on how the multi-agent aspect of the problem is tackled. No theoretical result is provided to demonstrate that the ScheduleNet can handle all the hard domain constraints of a problem and can tackle the multi-agent interactions in a principled way.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes a deep RL framework for the traditional schedule problem. The proposed algorithm is shown to be effective and has zero-shot generalization abilities. Reviewers are mostly satisfied with the response and the overall evaluation is slightly positive. However, there are some drawbacks of the current paper preventing it from getting a higher evaluation: (1) The reviewers believe that the contribution might be small -- at least for the RL area; the experimental performance for the scheduling problem is also not significantly improved compared to other methods (e.g. the search-based ones). Hence the reviewers believe the contribution of the paper is limited. (2) There is a number of typos and language issues in its present version. The paper may need several rounds of polishment before publication. (3) There is a lack of theoretical justification for the proposed method.  In sum, the AC recommends a borderline rejection.
Decision: Reject