Year: 2021

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 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 of scheduling.

heading: 1 INTRODUCTION
text: 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 facilities. As the size of the problems increases, solving largescale scheduling problems using mathematical programming becomes infeasible or ineffective due to the expensive computational cost. Furthermore, such optimization approaches cannot solve realtime scheduling problems where the new tasks appear dynamically.
Target Problem & Challenges. In this paper, we propose ScheduleNet, an RL-based decentralized constructive scheduler for coordinating multiple agents to 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 to minimize the total completion time (i.e., makespan) for various time-critical distributed tasks (e.g., vaccine delivery). Most multi-agent scheduling problems are designed to 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 is 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 a solution sequentially by assigning an 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 reschedule whenever a new event occurs (i.e., an agent finishes the assigned task or a new task appears). However, it is more challenging to find a better plan due to its sequential solution construction; a wrong choice at the early stage can cause irreversible poor results at the end.
• Decentralized vs 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 can solve a large-scale problem 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.
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 decision-making procedure of ScheduleNet is as follows:
• ScheduleNet first represents the MDP state as an 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) to 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 a decentralized scheduling policy using this reward is extremely difficult due to the credit assignment issues (Riedmiller et al., 2018; Hare, 2019). Additionally, makespan is highly volatile due to the combinatorial aspect of mSPs’ solution space; a 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) in a computationally efficient manner. The computationally-efficient 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.e., 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.

heading: 2 RELATED WORKS
text: 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 et al., 2020); (2) the construction heuristics that construct the solution sequentially by assigning idle vehicles to unvisited cities until the complete routing plan (sequence) is constructed (Bello et 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 a new customer appears. These RL approaches have exclusively focused on static planning in a single-agent perspective, which is far from the settings of real applications.
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 a complete end-to-end learned heuristic that constructs a feasible solution from “scratch” without relying on any existing solvers. Cao et al. (2021), which proposes a transformer-based construction policy to solve min-max mTSP, is 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 al. (2021); Zhang et al. (2020) have proposed to learn a 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-engineered dense reward, while ScheduleNet uses sparse and delayed reward (i.e., makespan) to train a policy.

heading: 3 PROBLEM FORMULATION
text: We formulate mSP as a 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 sτ as the τ -th partial solution of mSP (i.e., the completed/uncompleted tasks, the status of agents, and the sequence of the past assignments). The initial s0 and terminal state sT are defined as an empty and a complete solution, respectively.
Action. We define action aτ as the act of assigning an idle agent to one of the feasible tasks (unassigned tasks). We refer to aτ as the agent-to-task assignment. When the multiple agents are idle at the same time t, 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.
Transition. The proposed MDP is formulated with an event-based transition. An event is defined as the case where any agent finishes the assigned task (e.g., a salesman reaches the assigned city in mTSP). Whenever an event occurs, the idle agent is assigned to a new task, and the status of the agent and the target task are updated accordingly. We enumerate the event with τ to avoid confusion from the elapsed time of the problem; t(τ) is a function that returns the time of event τ .
Reward. The proposed MDP uses the negative makespan (i.e. total completion time of tasks) as the reward (i.e., r(sT) = −t(T)) that is realized only at sT.

heading: 3.1 EXAMPLE: MDP FORMULATION OF MTSP
text: 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 mTSP is considered to be 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τ = ({siτ}N+mi=1 , senvτ ), which is composed of two types of states: entity state siτ and environment state senvτ .
• siτ = (p i τ ,1 active τ ,1 assigned τ ) is the state of the i-th entity. piτ is the 2D Cartesian coordinate of the
i-th entity at the τ -th event. 1activeτ indicates whether the i-th agent/task is active (agent is working/ task is not visited). Similarly, 1assignedτ indicates whether agent/task is assigned. • senvτ contains the current time of the environment, and the sequences of cities visited by the salesmen.

heading: 4 SCHEDULENET
text: In this section, we explain how ScheduleNet recommends a scheduling action aτ of an idle agent from input sτ (partial solution). This is done by (1) constructing the agent-task graph Gτ , (2) embedding Gτ using TGA, and (3) computing the assignment probabilities. Figure 1 illustrates the decision-making process of ScheduleNet.

heading: 4.1 CONSTRUCTING AGENT-TASK GRAPH
text: ScheduleNet constructs the agent-task graph Gτ that reflects the complex relationships among the entities in sτ . Specifically, ScheduleNet constructs a directed complete graph Gτ = (V,E) out of sτ , where V is the set of nodes and E is the set of edges. The nodes and edges, and their associated features are defined as: • vi denotes the i-th node, which represents either an agent or a task. vi contains the node feature xi = (s i τ , ki), where s i τ is the state of entity i, and ki is the type of vi. For example, if the entity
i is an agent and 1activeτ = 1, then ki becomes active-agent. For the full list of the types, refer to Appendix C.2.
• eij denotes the edge between the source node vj and the destination node vi. The edge feature wij is equal to the Euclidean distance between the two nodes.
In the following subsections, we omit the event iterator τ for notational brevity, since the action selection procedure is only associated with the current event index τ .

heading: 4.2 GRAPH EMBEDDING USING TGA
text: ScheduleNet computes the node embeddings from the agent-task graph G using the TGA, which is designed to capture the different relations among the graph entities by applying attention mechanisms for each relational type. TGA uses three steps to compute the updated node/edge embedding as follows:
Type-aware edge update. Given the node embedding hi and edge embedding hij , TGA computes the type-aware edge embedding h′ij and the attention logit zij as follows:
h′ij = TGAE([hi, hj , hij ], kj) zij = TGAA([hi, hj , hij ], kj) (1)
where TGAE and TGAA are the type-aware edge update function and the type-aware attention function, respectively. TGAE and TGAA are parameterized using multilayer perceptrons (MLPs).
Type-aware message aggregation. Each entity in the agent-task graph interacts differently with the other entities, depending on the type of the edge between them. To preserve the different relationships among the entities during the graph embedding procedure, TGA gathers messages h′ij via the type-aware message aggregation.
First, TGA aggregates messages for each node type and produces the per-type message mki as follows:
mki = ∑
j∈Nk(i)
αijh ′ ij (2)
where Nk(i) = {vl|kl = k, vl ∈ N (i)} is the type k neighborhood of vi, and αij is the attention score that is computed using zij :
αij = exp(zij)∑
j∈Nk(i) exp(zij) (3)
TGA aggregates the per-type messages to compute the total aggregated message mi for vi as: mi = ∑ k∈K mki (4)
where K is the set of node types.
Type-aware node update. The total aggregated message mi is then used to compute the updated node embedding h′i as follows: h′i = TGAV([hi,mi], ki) (5)
where TGAV is the type-aware node update function that is parametrized using MLP. The detailed architectures of TGAE, TGAA, and TGAV are provided in Appendix A.
ScheduleNet computes the node embeddings from G using TGA. The embedding procedure first encodes the features of G into the initial node embeddings {h(0)i |vi ∈ V}, and the initial edge embeddings {h(0)ij |eij ∈ E}. ScheduleNet then performs TGA H times on all nodes to compute the final node embeddings {h(H)i |vi ∈ V} and edge embeddings {h (H) ij |eij ∈ E}.

heading: 4.3 COMPUTING ASSIGNMENT PROBABILITY
text: Using {h(H)i |vi ∈ V} and {h (H) ij |eij ∈ E}, ScheduleNet selects the assignment action aτ for the target idle agent. It computes the assignment probability of the target agent i to the unassigned task j as follows:
lij = MLPactor(h (H) i , h (H) j , h (H) ij )
pij = softmax({lij}j∈A(Gτ )) (6)
where A(Gτ ) denotes a set of feasible actions that is defined as {vj |kj = Unassigned-task, vj ∈ V}. Note that ScheduleNet allows an agent to process its local state information and make the assignment choice in a decentralized way. This enables ScheduleNet to solve mSPs with any number of agents and tasks even when the agents or tasks appear dynamically.

heading: 5 TRAINING SCHEDULENET
text: 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 a decentralized cooperative policy using a 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. To handle such difficulties, we employ two training stabilizers, reward normalization, and Clip-REINFORCE.

heading: 5.1 REWARD NORMALIZATION
text: We denote the makespan induced by policy πθ as M(πθ). We observe that M(πθ) is highly volatile depending on the problem size (N , m) and πθ. To reduce the variance of the reward incurred from
the problem size, we propose to use the normalized makespan M̄(πθ, πb) computed as:
M̄(πθ, πb) = M(πθ)−M(πb)
M(πb) (7)
where πθ, πb is the current policy and baseline policy respectively.
A similar normalization scheme that only measures the performance difference between π and πb has been investigated in RL applications for solving single-agent scheduling problems (Kool et al., 2018; Cao et al., 2021; Kwon et 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 is fixed, the (optimal) makespan of mTSP can differ severely as m changes. To reduce the variability of the makespan due to m, we further divide the makespan difference by M(πb).
Using M̄(πθ, πb), we compute the normalized return Gτ (πθ, πb) as follows:
Gτ (πθ, πb) ≜ −γT−τM̄(πθ, πb) (8)
where T is the index of the terminal state, and γ is the discount factor of MDP. The minus sign is for minimizing the makespan. Note that, in the early phase of mSP (when τ is small), it is difficult to estimate the makespan. Thus, we place a smaller weight (i.e, γT−τ ) on M̄(πθ, πb), which is evaluated when τ is small (early stage).

heading: 5.2 CLIP-REINFORCE
text: 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 is difficult. We thus propose to utilize Clip-REINFORCE, a variant of PPO (Schulman et al., 2017) without the learned value function, for training ScheduleNet. The objective of the ClipREINFORCE is given as follows:
L(θ) = E (Gτ ,aτ )∼πθ [min(clip(ρτ , 1− ϵ, 1 + ϵ)Gτ , ρτGτ )] (9)
where clip(x, a, b) = {a ifx ≤ a, x if a < x < b, b ifx ≥ b}, ϵ is the clipping parameter, Gτ is a shorthand notation for Gτ (πθ, πb), and ρτ = πθ(aτ |Gτ )/πθold(aτ |Gτ ) is the ratio between the current policy πθ and the policy before the update πθold .

heading: 6 EXPERIMENTS
text: In this section, we evaluate the performance of ScheduleNet on mTSP and JSP. To calculate the inference time, we run all experiements on the server equipped with AMD Threadripper 2990WX CPU. We use single CPU core for evaluating all algorithms.

heading: 6.1 MTSP EXPERIMENTS
text: Training. We denote (N × 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 all mTSP experimental results, we evaluate the performance of a 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 mTSP 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 nonlearning baselines, LKH3 (Helsgaun, 2017) and Google OR-Tools (Perron & Furnon) are used. It is noteworthy that LKH3 is known to find the optimal solutions for the mTSP problems with the identified optimal solutions. Thus, we use the makespans computed by LKH3 as the proxies for the
Table 1: Random mTSP results. GNN-DisPN results are reproduced from Hu et al. (2020).
N 30 50 100 200 Gap
m 3 5 5 7 10 5 10 15 10 15 20
LKH3 2.17 1.94 2.00 1.95 1.91 2.20 1.97 1.98 2.04 2.00 1.97 1.00 OR-Tools 2.25 1.95 2.04 1.96 1.91 2.41 2.03 2.03 2.33 2.33 2.37 1.07
GNN-DisPN - - 2.12 - 1.95 2.48 2.09 - - - - - DAN (g.) 2.32 2.02 2.29 2.11 2.03 2.72 2.17 2.09 2.40 2.20 2.15 1.13 DAN (s.64) 2.22 1.96 2.12 1.99 1.95 2.55 2.05 2.00 2.40 2.20 2.15 1.08
ScheduleNet (g.) 2.32 2.02 2.17 2.07 1.98 2.59 2.13 2.07 2.45 2.24 2.17 1.09 ScheduleNet (s.64) 2.22 1.96 2.07 1.99 1.92 2.43 2.03 1.99 2.25 2.08 2.05 1.04
30 x 3 30 x 5 50 x 5 50 x 7 50 x 1 0 10 0 x 5 10 0 x 10 10 0 x 15 20 0 x 10 20 0 x 15 20 0 x 20
100
101
102
103
Ru nt im
e (s ec
)
LKH OR-Tools ScheduleNet
Figure 2: mTSP runtimes
optimal solutions. As the RL baselines, GNN-DisPN (Hu et al., 2020) and DAN (Cao et al., 2021) are considered (To the best of our knowledge, these are the only RL-based algorithms tried to solve the min-max mTSP problems).
Table 1 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 is trained on the smallest test setup (30×3). In addition, Figure 2 compares the average computation times and their standard deviations for each problem size, clearly indicating that ScheduleNet is significantly faster than traditional heuristic solvers (LKH3 and OR-Tools). The computational time difference among RL-approaches is 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 mTSPLib dataset defined by Necula et al. (2015). mTSPLib consists of four instances of size 51, 52, 76 and 99 from TSPLib (Reinelt, 1991), each of which is extended to multi-agent setups where m 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 in solving both randomly generated and real-world mTSPs problems (i.e., robust transferability over data distribution shift).

heading: 6.2 ABLATION STUDIES
text: In this paper, we propose TGA as 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 to the training and testing performance of ScheduleNet.
We train variants of the ScheduleNet models as the target of the ablation studies as follows:
• TGA-REINFORCE: the model using TGA and is trained by REINFORCE (Williams, 1992).
• GN-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 (30×3) during training, and Table 3 shows the makespans on the test instances.
Figure 3: Training curves
0 1 2 3 4 5
1.0
1.1
1.2
1.3
No rm
.a ve ra ge
m ak es pa
n
50 x 5
0 3 5 7 9 10
100 x 10
0 11 15 17 19 20
200 x 20
Nr
Figure 4: Limited observation scenarios 10% 30% 50%
2.4
2.6
2.8
Av er ag
e m ak es pa
n
10% 30% 50%
2
4
6
Ru nt im
e (s ec )
Na
Oracle ScheduleNet Ortools-(R)
Figure 5: Online routing scenarios
• TGA-REINFORCE 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 a representation module. TGA induces more stabilized and faster performance improvement. In 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 in solving mTSP.

heading: 6.3 MTSP VARIANTS EXPERIMENTS
text: 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 to gather all the information about the other salesmen due to the limited communication capabilities (e.g., delivery trucks are located in distant). In such a scenario, the agent should decide the next city to visit with local observations. To consider this realistic scenario, we limit the number of observable salesmen Nr from the global state Gτ and investigate its performance. We employ ScheduleNet to solve the test instances, whose sizes are (50×5), (100×10), and (200×20), by varying Nr. As shown in Figure 4, the makespan decreases as Nr increases because the extended communication scope can induce enhanced coordinations among salesmen. Note that Nr = 0 indicates the case where each salesman makes entirely independent actions without considering the other salesmen at all. The results implies that ScheduleNet is 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, as a decentralized constructive heuristic, can solve the dynamic scheduling problem in an online manner; it reschedules inherently whenever a new event occurs (i.e., an agent finishes the assigned task or 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.
We first randomly generate 100 (30×3) test instances. Then, while simulating these scenarios with the scheduling policies, we sequentially add 30 × Na% cities to the simulation (the exact addition
moment and locations are unknown to policies before the addition) and evaluate how the policies effectively replan the schedules according to such online scenarios. We compare the makespan of ScheduleNet with (1) 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 sτ is updated. Please refer to Appendix C.4 for more details regarding the simulation and baselines.
Figure 5 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 Na values, proving its effective adaptability and robustness to dynamically changing cities. Note that as Na increases, the makespan and the runtime increase for all methods due to the increased uncertainty and the number of replanning.

heading: 6.4 JSP EXPERIMENTS
text: 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) in a 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 to be challenging since it imposes additional constraints that schedulers must obey: precedence constraints (i.e., an operation of a 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 an MDP where sτ is the partial solution of JSP, aτ is an agenttask assignment (i.e., assigning an idle machine to one of the feasible operations), and reward is the minus of makespan. Please refer to Appendix D.1 for the detailed formulation of MDP.
Training. We train ScheduleNet using the random JSP instances (N × m) that have N jobs and m machines. We sample N and m from U(7, 14) and U(2, 5) respectively to generate the training JSP instances, and randomly shuffle the order of the machines in a job to generate machine sharing constraints. Please refer to 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-in-first-out (FIFO), and Shortest Processing Time (SPT). Both baseline RL methods were specifically designed to solve JSP by utilizing the well-known disjunctive JSP graph representation (Roy & Sussmann, 1964) and wellengineered 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.

heading: 7 CONCLUSION
text: In this work, we propose ScheduleNet, an RL-based scheduler that can solve various types of multiagent scheduling problems (mSPs) in a 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 a 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.

heading: 8 ETHICS STATEMENT AND REPRODUCIBILITY DISCUSSION
text: 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 not consider the subjective values (social protections for the underprivileged or expedited dispatching for life-threatening demands) in the process of decisionmaking or learning. Thus, our method may produce scheduling results that are not well aligned with human decision-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 our experiments and confirmed the experiments were reproducible. Furthermore, we also prepare to open-source our mTSP MDP environments so that the follow-up research can be assessed in a unified way.

heading: ScheduleNet

heading: Supplementary Material

heading: Table of Contents

heading: A Details of Type-aware Graph Attention 14

heading: B Extended discussion for reward normalization scheme 15

heading: C Details of mTSP experiments 16
text: C.1 MDP formulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 C.2 Agent-task graph formulation . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 C.3 Training details . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 C.4 Online routing scenarios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

heading: D Details of JSP experiments 17
text: D.1 MDP formulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 D.2 Agent-task graph formulation . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 D.3 Training details . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 D.4 Baseline implementations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 D.5 Extended public benchmark JSP results . . . . . . . . . . . . . . . . . . . . . . 20

heading: A DETAILS OF TYPE-AWARE GRAPH ATTENTION
text: 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 hi and hij , and the embedded node and edge feature h′i and h ′ ij , 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-aware 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 cij of edge eij is computed using the source and destination node type ki, kj such that:
cij = [Emb(ki),Emb(kj)] (A.1) where Emb(·) is a trainable lookup table function. Next, the type-aware edge encoding uij is computed using a multilayer perceptron (MLP) as follows:
uij = MLPetype(hi, hj , hij , cij) (A.2) where MLPetype(·) is the type-aware edge encoding MLP. uij can be seen as a dynamic edge feature which varies depending on the source and destination node type. Then, the updated edge embedding h′ij and its attention logit zij are obtained as:
h′ij = MLPedge(uij) (A.3)
zij = MLPattn(uij) (A.4)
where MLPedge and MLPattn 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.1, A.2 and A.3 are defined as TGAE. Similarly, the computation steps of equations A.1, A.2 and A.4 are defined as TGAA.
Type-aware message aggregation We first define the type-k neighborhood of vi as Nk(i) = {vl|kl = k,∀vl ∈ N (i)}, where N (i) is the in-neigborhood set of vi. The proposed type-aware message aggregation procedure computes attention score αij for the eij , which starts from vj and heads to vi, such that:
αij = exp(zij)∑
l∈Nkj (i) exp(zil)
(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 mki for node vi is computed as:
mki = ∑
j∈Nk(i)
αijh ′ ij (A.6)
In this aggregation step, the incoming messages of node i are aggregated per type. All incoming type neighborhood messages are concatenated to produce (inter-type) aggregated message mi for vi, such that:
mi = ∑ k∈K mki (A.7)
Type-aware node update Similar to the edge update phase, the context embedding ci is computed first for each node vi:
ci = Emb(ki) (A.8) where Emb(·) is a trainable lookup table function. Then, the updated hidden node embedding h′i is computed as below:
h′i = MLPnode(hi,mi, ci) (A.9) where MLPnode(·) is the type-aware node updater. The computation steps of equations A.8, and A.9 are defined as TGAV.

heading: B EXTENDED DISCUSSION FOR REWARD NORMALIZATION SCHEME
text: In this section, we further discuss the effect of the proposed reward normalization scheme and its variants to the performance of ScheduleNet. The proposed reward normalization (i.e. normalized makespan) m(π, πb) is given as follows:
m(π, πb) = M(πθ)−M(πb)
M(πb) (A.10)
where πb is the baseline policy.
Effect of the denominator m(π, πb) measures the relative scheduling supremacy of π to the πb. Similar reward normalization scheme, but without M(πb) division, is employed to solve singleagent 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 to different geometries or the size of training instances are varying).
Effect of the baseline selection A proper selection of πb is essential to assure stable and asymptotically better learning of ScheduleNet. Intuitively speaking, choosing too strong baseline (i.e. policy having smaller makespan such as 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 can leads in virtually no learning since the m(π, πb) becomes nearly zero.
We select πb as Greedy(π) and this baseline selection has several advantages from selecting a fixed/pre-existing scheduling policy: (1) Entire learning process becomes independent from existing scheduling methods. Thus ScheduleNet is applicable even when the cheap-and-performing πb for some target mSP does not exist. (2) Greedy(π) serves as an appropriate πb (either not too strong or weak) during policy learning. We experimentally confirmed that the baseline section Greedy(π) results in a better scheduling policy as similar to the several literature Kool et al. (2018); Silver et al. (2016).

heading: C DETAILS OF MTSP EXPERIMENTS
text: In this section, we provide the details of mTSP exepriments.

heading: C.1 MDP FORMULATION
text: The formulated mTSP MDP is event-based. Here we discuss the further details about the eventbased 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 an event, meanwhile the other assigned salesman are still on the way to their correspondingly assigned cities. We assume that each worker transits towards the assigned city with unit speed in the 2D Euclidean space, i.e. the distance travelled by each worker equals the time past between two consecutive MDP events.
It is noteworthy that multiple events can happen at the same time, typically when time stamp t = 0. If the MDP has multiple available workers at the same time, we repeatedly choose an arbitrary idle agent and assign it to the one of an idle task until no 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 are homogeneous agents).

heading: C.2 AGENT-TASK GRAPH FORMULATION
text: In this section, we present the list of all possible node types in Gτ :(1) assigned-agent, (2) unassignedagent (i.e. idle), (3) assigned-task, (4) unassigned-task, (5) inactive-task (i.e. visited city) and (6) depot. Here, we do not include inactive-agent (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 as the edge type. All nodes in the Gτ are fully connected.

heading: C.3 TRAINING DETAILS
text: Network parameters. ScheduleNet is composed of three components. The first components generates the initial node embedding {h(0)i } and edge {h (0) ij } by using linear projections. The second component (TGA), which utilizes MLP(64) as MLPetype, MLPedge, MLPattn, and MLPnode, repeatedly updates the node and edge embedding 3 times to generate {h(3)i } and edge {h (3) ij }. The last component MLPactor, which is parametrized as MLP(64, 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 LeakyReLU.
Training pseudocode. We presents a pseudocode for training ScheduleNet.
Algorithm 2: ScheduleNet Training input : Training policy πθ, baseline policy πϕ output: Optimized policy πθ
1 Initialize the baseline policy with parameters ϕ← θ 2 for update step do 3 Initialize sample buffer D ← ∅ 4 for number of episodes E do 5 Generate a random mTSP instance I 6 πb ← Greedy(πϕ) 7 Construct mTSP MDP from the instance I 8 Collect samples S = {Gτ , aτ , πθold(aτ |Gτ ), Gτ (πθ, πb)}Tτ=0 with πθ and πb from the MDP. 9 D ← D ∪ S.
10 end 11 for inner updates K do 12 Calculate the loss L(θ) with D 13 θ ← θ + α∇θL(θ) 14 end 15 ϕ← βϕ+ (1− β)θ 16 end 17 return πθ
We set the MDP discounting factor γ to 0.99, learning rate α to 0.0001, E to 128, K to 4, β to 0.01, and the clipping parameter ϵ of Clip-REINFORCE to 0.2. We set training seed as 1234.

heading: C.4 ONLINE ROUTING SCENARIOS
text: 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 is 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 of the mTSP map. Similarly, the location of the second city is set as the midpoint between the second and third cities. Using the same logic, we decide all positions of the newly added cities. Lastly, we decide the timing of city addition by using (near) optimal solutions (e.g., LKH3) M∗(π). We first compute divide M∗(π) by 1.0 < s and then evenly allocate the timing of additions from 0.0 to M∗(π)/s. This ensures all “to be added” cities are added during the online routing simulation no matter what scheduling policies are evaluated. We set s = 2.
Baseline implementations In this paragraph, we explain the implementations of baseline algorithms. To implement the oracle planning, we reformulate the online routing problem as a vehicle routing problem with time constraints (VRP-TW). In the VRP-TW, we set 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 as their addition times and M . The re-planing heuristics are implemented with OR-tools (Perron & Furnon).

heading: D DETAILS OF JSP EXPERIMENTS
text: Job-shop scheduling problem (JSP) is a mSP that can be applied in various industries including the operation of semi-conductor chip fabrication facility and railroad system. The objective of JSP is 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 an extension of mTSP with two additional constraints: (1) precedence constraint that models a scenario where an operation of a job becomes processable only after all of its preceding operations are done; (2) agent-sharing (disjunctive) constraint that confines the machine to process only one operation at a time. Due to these additional constraints, JSP is considered to be a more difficult problem when it is solved via mathematical optimization
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 JSP, training details of ScheduleNet, and experiment results.

heading: D.1 MDP FORMULATION
text: 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τ = ({siτ}N+mi=1 , senvτ ) which is composed of two types of states: entity state siτ and environment state senvτ . • siτ = (p i τ ,1 processable τ ,1 assigned τ , 1accessibleτ , 1 waiting τ ) is the state of the i-th entity. piτ is the processing
time of the i-th entity at the τ -th event. 1processableτ indicates whether the i-th task is processable by the target agent or not. Similar to mTSP, 1assignedτ indicates whether an agent/task is assigned. • senvτ contains the current time of the environment, the sequence of tasks completed by each agent (machine), and the precedence constraints of tasks within each job.
Action. We define the action space at the τ -th event as a set of oeprations that is both processable and currently available. Additionally, we define the waiting action as a reservation of the target agent (i.e. the unique idle machine) until the next event. Having waiting as an 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.

heading: D.2 AGENT-TASK GRAPH FORMULATION
text: ScheduleNet constructs the agent-task graph Gτ that reflects the complex relationships among the entities in sτ . ScheduleNet constructs a directed graph Gτ = (V,E) out of sτ , where V is the set of nodes and E is the set of edges. The nodes and edges and their associated features are defined as:
• vi denotes the i-th node and represents either an agent or a task. vi contains the node feature xi = (s i τ , ki), where s i τ is the state of entity i, and ki is the type of vi (e.g. if the entity i is a task
and its 1processableτ = 1, then the ki becomes a processable-task type.) • eij denotes the edge between the source node vj and the destination node vi. The edge feature wij
is a binary feature which indicates whether the destination node vi is processable by the source node vj .
All possible node types in Gτ are: (1) assigned-agent, (2) unassigned-agent, (3) assigned-task, (4) processable-task, and (5) unprocessable-task. We do not include completed tasks in the graph. Thus, the currently active tasks are the union of the assigned tasks, processable-tasks, and unprocessabletasks. The full list of node features are as follows:
• 1agentτ indicates whether the node is a agent or a task. • 1target-agentτ indicates whether the node is a target-agent (unique idle agent that needs to be assigned). • 1assignedτ indicates whether the agent/task is assigned. • 1waitingτ indicates whether the node is an agent in waiting state. • 1processableτ indicates whether the node is a task that is processable by the target-agent. • 1accessibleτ indicates whether the node is processable by the target-agent and is 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-complete indicates the amount of time it will take to 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 in the job.
JSP graph connectivity. Figure 9 visualizes the proposed agent-task graph. From Figure 9, each agent is fully connected to 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 to the other agents.

heading: D.3 TRAINING DETAILS
text: We use the same training hyperparameters as in Appendix C.3.

heading: D.4 BASELINE IMPLEMENTATIONS
text: Priority dispatching rules (PDR) is one 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, at 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.

heading: D.5 EXTENDED PUBLIC BENCHMARK JSP RESULTS
text: 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).

Review summaries:
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.

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.

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.