Learning to schedule job-shop problems: Representation and policy
learning using graph neural network and reinforcement learning
- URL: http://arxiv.org/abs/2106.01086v1
- Date: Wed, 2 Jun 2021 11:40:22 GMT
- Title: Learning to schedule job-shop problems: Representation and policy
learning using graph neural network and reinforcement learning
- Authors: Junyoung Park, Jaehyeong Chun, Sang Hun Kim, Youngkook Kim, Jinkyoo
Park
- Abstract summary: We propose a framework to learn to schedule a job-shop problem (JSSP) using a graph neural network (GNN) and reinforcement learning (RL)
We empirically demonstrate that the GNN scheduler, due to its superb generalization capability, outperforms practically favored rules and RL-based schedulers on various benchmark JSSP.
- Score: 9.379652654427959
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We propose a framework to learn to schedule a job-shop problem (JSSP) using a
graph neural network (GNN) and reinforcement learning (RL). We formulate the
scheduling process of JSSP as a sequential decision-making problem with graph
representation of the state to consider the structure of JSSP. In solving the
formulated problem, the proposed framework employs a GNN to learn that node
features that embed the spatial structure of the JSSP represented as a graph
(representation learning) and derive the optimum scheduling policy that maps
the embedded node features to the best scheduling action (policy learning). We
employ Proximal Policy Optimization (PPO) based RL strategy to train these two
modules in an end-to-end fashion. We empirically demonstrate that the GNN
scheduler, due to its superb generalization capability, outperforms practically
favored dispatching rules and RL-based schedulers on various benchmark JSSP. We
also confirmed that the proposed framework learns a transferable scheduling
policy that can be employed to schedule a completely new JSSP (in terms of size
and parameters) without further training.
Related papers
- Graph Neural Networks for Job Shop Scheduling Problems: A Survey [9.072608705759322]
Job shop scheduling problems (JSSPs) represent a critical and challenging class of optimization problems.
Recent years have witnessed a rapid increase in the application of graph neural networks (GNNs) to solve JSSPs.
This paper aims to thoroughly review prevailing GNN methods for different types of JSSPs and the closely related flow-shop scheduling problems.
arXiv Detail & Related papers (2024-06-20T08:22:07Z) - Can Graph Learning Improve Task Planning? [61.47027387839096]
Task planning is emerging as an important research topic alongside the development of large language models (LLMs)
In this paper, we explore graph learning-based methods for task planning.
Our approach complements prompt engineering and fine-tuning techniques, with performance further enhanced by improved prompts or a fine-tuned model.
arXiv Detail & Related papers (2024-05-29T14:26:24Z) - Intelligent Hybrid Resource Allocation in MEC-assisted RAN Slicing Network [72.2456220035229]
We aim to maximize the SSR for heterogeneous service demands in the cooperative MEC-assisted RAN slicing system.
We propose a recurrent graph reinforcement learning (RGRL) algorithm to intelligently learn the optimal hybrid RA policy.
arXiv Detail & Related papers (2024-05-02T01:36:13Z) - Learning to Solve Job Shop Scheduling under Uncertainty [1.3002317221601185]
Job-Shop Scheduling Problem (JSSP) is a optimization problem where tasks need to be scheduled on machines in order to minimize criteria such as makespan or delay.
This paper introduces a new approach that leverages Deep Reinforcement Learning (DRL) techniques to search for robust solutions.
arXiv Detail & Related papers (2024-03-04T08:38:55Z) - Online Network Source Optimization with Graph-Kernel MAB [62.6067511147939]
We propose Grab-UCB, a graph- kernel multi-arms bandit algorithm to learn online the optimal source placement in large scale networks.
We describe the network processes with an adaptive graph dictionary model, which typically leads to sparse spectral representations.
We derive the performance guarantees that depend on network parameters, which further influence the learning curve of the sequential decision strategy.
arXiv Detail & Related papers (2023-07-07T15:03:42Z) - Deep Reinforcement Learning Guided Improvement Heuristic for Job Shop
Scheduling [30.45126420996238]
This paper proposes a novel DRL-guided improvement for solving JSSP, where graph representation is employed to encode complete solutions.
We design a Graph Neural-Network-based representation scheme, consisting of two modules to effectively capture the information of dynamic topology and different types of nodes in graphs encountered during the improvement process.
We prove that our method scales linearly with problem size. Experiments on classic benchmarks show that the improvement policy learned by our method outperforms state-of-the-art DRL-based methods by a large margin.
arXiv Detail & Related papers (2022-11-20T10:20:13Z) - Hybrid intelligence for dynamic job-shop scheduling with deep
reinforcement learning and attention mechanism [28.28095225164155]
We formulate the DJSP as a Markov decision process (MDP) to be tackled by reinforcement learning (RL)
We propose a flexible hybrid framework that takes disjunctive graphs as states and a set of general dispatching rules as the action space with minimum prior domain knowledge.
We present Gymjsp, a public benchmark based on the well-known OR-Library, to provide a standardized off-the-shelf facility for RL and DJSP research communities.
arXiv Detail & Related papers (2022-01-03T09:38:13Z) - Compositional Reinforcement Learning from Logical Specifications [21.193231846438895]
Recent approaches automatically generate a reward function from a given specification and use a suitable reinforcement learning algorithm to learn a policy.
We develop a compositional learning approach, called DiRL, that interleaves high-level planning and reinforcement learning.
Our approach then incorporates reinforcement learning to learn neural network policies for each edge (sub-task) within a Dijkstra-style planning algorithm to compute a high-level plan in the graph.
arXiv Detail & Related papers (2021-06-25T22:54:28Z) - Better than the Best: Gradient-based Improper Reinforcement Learning for
Network Scheduling [60.48359567964899]
We consider the problem of scheduling in constrained queueing networks with a view to minimizing packet delay.
We use a policy gradient based reinforcement learning algorithm that produces a scheduler that performs better than the available atomic policies.
arXiv Detail & Related papers (2021-05-01T10:18:34Z) - Policy-GNN: Aggregation Optimization for Graph Neural Networks [60.50932472042379]
Graph neural networks (GNNs) aim to model the local graph structures and capture the hierarchical patterns by aggregating the information from neighbors.
It is a challenging task to develop an effective aggregation strategy for each node, given complex graphs and sparse features.
We propose Policy-GNN, a meta-policy framework that models the sampling procedure and message passing of GNNs into a combined learning process.
arXiv Detail & Related papers (2020-06-26T17:03:06Z) - Graph Ordering: Towards the Optimal by Learning [69.72656588714155]
Graph representation learning has achieved a remarkable success in many graph-based applications, such as node classification, prediction, and community detection.
However, for some kind of graph applications, such as graph compression and edge partition, it is very hard to reduce them to some graph representation learning tasks.
In this paper, we propose to attack the graph ordering problem behind such applications by a novel learning approach.
arXiv Detail & Related papers (2020-01-18T09:14:16Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.