Job Shop Scheduling via Deep Reinforcement Learning: a Sequence to
Sequence approach
- URL: http://arxiv.org/abs/2308.01797v1
- Date: Thu, 3 Aug 2023 14:52:17 GMT
- Title: Job Shop Scheduling via Deep Reinforcement Learning: a Sequence to
Sequence approach
- Authors: Giovanni Bonetta, Davide Zago, Rossella Cancelliere, Andrea Grosso
- Abstract summary: This paper presents an end-to-end Deep Reinforcement Learning approach to scheduling that automatically learns dispatching rules.
We show that we outperform many classical approaches exploiting priority dispatching rules and show competitive results on state-of-the-art Deep Reinforcement Learning ones.
- Score: 0.0
- License: http://creativecommons.org/licenses/by-nc-sa/4.0/
- Abstract: Job scheduling is a well-known Combinatorial Optimization problem with
endless applications. Well planned schedules bring many benefits in the context
of automated systems: among others, they limit production costs and waste.
Nevertheless, the NP-hardness of this problem makes it essential to use
heuristics whose design is difficult, requires specialized knowledge and often
produces methods tailored to the specific task. This paper presents an original
end-to-end Deep Reinforcement Learning approach to scheduling that
automatically learns dispatching rules. Our technique is inspired by natural
language encoder-decoder models for sequence processing and has never been
used, to the best of our knowledge, for scheduling purposes. We applied and
tested our method in particular to some benchmark instances of Job Shop
Problem, but this technique is general enough to be potentially used to tackle
other different optimal job scheduling tasks with minimal intervention. Results
demonstrate that we outperform many classical approaches exploiting priority
dispatching rules and show competitive results on state-of-the-art Deep
Reinforcement Learning ones.
Related papers
- The Road Less Scheduled [75.09232139131437]
Existing learning rate schedules that do not require specification of the optimization stopping step T are greatly out-performed by learning rate schedules that depend on T.
We propose an approach that avoids the need for this stopping time by eschewing the use of schedules entirely.
arXiv Detail & Related papers (2024-05-24T16:20:46Z) - An End-to-End Reinforcement Learning Approach for Job-Shop Scheduling
Problems Based on Constraint Programming [5.070542698701157]
This paper proposes a novel end-to-end approach to solving scheduling problems by means of CP and Reinforcement Learning (RL)
Our approach leverages existing CP solvers to train an agent learning a Priority Dispatching Rule (PDR) that generalizes well to large instances, even from separate datasets.
arXiv Detail & Related papers (2023-06-09T08:24:56Z) - Reinforcement Learning with Success Induced Task Prioritization [68.8204255655161]
We introduce Success Induced Task Prioritization (SITP), a framework for automatic curriculum learning.
The algorithm selects the order of tasks that provide the fastest learning for agents.
We demonstrate that SITP matches or surpasses the results of other curriculum design methods.
arXiv Detail & Related papers (2022-12-30T12:32:43Z) - Learning to Optimize Permutation Flow Shop Scheduling via Graph-based
Imitation Learning [70.65666982566655]
Permutation flow shop scheduling (PFSS) is widely used in manufacturing systems.
We propose to train the model via expert-driven imitation learning, which accelerates convergence more stably and accurately.
Our model's network parameters are reduced to only 37% of theirs, and the solution gap of our model towards the expert solutions decreases from 6.8% to 1.3% on average.
arXiv Detail & Related papers (2022-10-31T09:46:26Z) - Non-Clairvoyant Scheduling with Predictions Revisited [77.86290991564829]
In non-clairvoyant scheduling, the task is to find an online strategy for scheduling jobs with a priori unknown processing requirements.
We revisit this well-studied problem in a recently popular learning-augmented setting that integrates (untrusted) predictions in algorithm design.
We show that these predictions have desired properties, admit a natural error measure as well as algorithms with strong performance guarantees.
arXiv Detail & Related papers (2022-02-21T13:18:11Z) - A Reinforcement Learning Environment For Job-Shop Scheduling [2.036811219647753]
This paper presents an efficient Deep Reinforcement Learning environment for Job-Shop Scheduling.
We design a meaningful and compact state representation as well as a novel, simple dense reward function.
We demonstrate that our approach significantly outperforms existing DRL methods on classic benchmark instances.
arXiv Detail & Related papers (2021-04-08T13:26:30Z) - Learning to Schedule DAG Tasks [7.577417675452624]
We present a novel learning-based approach to scheduling directed acyclic graphs (DAGs)
The algorithm employs a reinforcement learning agent to iteratively add edges directed to the DAG.
Our approach can be easily applied to any existing scheduling algorithms.
arXiv Detail & Related papers (2021-03-05T01:10:24Z) - Geometric Deep Reinforcement Learning for Dynamic DAG Scheduling [8.14784681248878]
In this paper, we propose a reinforcement learning approach to solve a realistic scheduling problem.
We apply it to an algorithm commonly executed in the high performance computing community, the Cholesky factorization.
Our algorithm uses graph neural networks in combination with an actor-critic algorithm (A2C) to build an adaptive representation of the problem on the fly.
arXiv Detail & Related papers (2020-11-09T10:57:21Z) - Continual Deep Learning by Functional Regularisation of Memorable Past [95.97578574330934]
Continually learning new skills is important for intelligent systems, yet standard deep learning methods suffer from catastrophic forgetting of the past.
We propose a new functional-regularisation approach that utilises a few memorable past examples crucial to avoid forgetting.
Our method achieves state-of-the-art performance on standard benchmarks and opens a new direction for life-long learning where regularisation and memory-based methods are naturally combined.
arXiv Detail & Related papers (2020-04-29T10:47:54Z) - Train No Evil: Selective Masking for Task-Guided Pre-Training [97.03615486457065]
We propose a three-stage framework by adding a task-guided pre-training stage with selective masking between general pre-training and fine-tuning.
We show that our method can achieve comparable or even better performance with less than 50% of cost.
arXiv Detail & Related papers (2020-04-21T03:14:22Z)
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.