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

• Self-Evaluation for Job-Shop Scheduling [1.3927943269211593]
  Combinatorial optimization problems, such as scheduling and route planning, are crucial in various industries but are computationally intractable due to their NP-hard nature. We propose a novel framework that generates and evaluates subsets of assignments, moving beyond traditional stepwise approaches.
  arXiv  Detail & Related papers  (2025-02-12T11:22:33Z)
• On Sequential Fault-Intolerant Process Planning [60.66853798340345]
  We propose and study a planning problem we call Sequential Fault-Intolerant Process Planning (SFIPP) SFIPP captures a reward structure common in many sequential multi-stage decision problems where the planning is deemed successful only if all stages succeed. We design provably tight online algorithms for settings in which we need to pick between different actions with unknown success chances at each stage.
  arXiv  Detail & Related papers  (2025-02-07T15:20:35Z)
• Offline reinforcement learning for job-shop scheduling problems [1.3927943269211593]
  This paper introduces a novel offline RL method designed for optimization problems with complex constraints. Our approach encodes actions in edge attributes and balances expected rewards with the imitation of expert solutions. We demonstrate the effectiveness of this method on job-shop scheduling and flexible job-shop scheduling benchmarks.
  arXiv  Detail & Related papers  (2024-10-21T07:33:42Z)
• 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.