A Reinforcement Learning Approach for Scheduling Problems With Improved Generalization Through Order Swapping

• URL: http://arxiv.org/abs/2302.13941v1
• Date: Mon, 27 Feb 2023 16:45:04 GMT
• Title: A Reinforcement Learning Approach for Scheduling Problems With Improved Generalization Through Order Swapping
• Authors: Deepak Vivekanandan, Samuel Wirth, Patrick Karlbauer, Noah Klarmann
• Abstract summary: JSSP falls into the category of NP-hard COP, in which solving the problem through exhaustive search becomes unfeasible. In recent years, the research towards using DRL to solve COP has gained interest and has shown promising results in terms of solution quality and computational efficiency. In particular, we employ the PPO algorithm that adopts the policy-gradient paradigm that is found to perform well in the constrained dispatching of jobs.
• Score: 0.0
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: The scheduling of production resources (such as associating jobs to machines) plays a vital role for the manufacturing industry not only for saving energy but also for increasing the overall efficiency. Among the different job scheduling problems, the JSSP is addressed in this work. JSSP falls into the category of NP-hard COP, in which solving the problem through exhaustive search becomes unfeasible. Simple heuristics such as FIFO, LPT and metaheuristics such as Taboo search are often adopted to solve the problem by truncating the search space. The viability of the methods becomes inefficient for large problem sizes as it is either far from the optimum or time consuming. In recent years, the research towards using DRL to solve COP has gained interest and has shown promising results in terms of solution quality and computational efficiency. In this work, we provide an novel approach to solve the JSSP examining the objectives generalization and solution effectiveness using DRL. In particular, we employ the PPO algorithm that adopts the policy-gradient paradigm that is found to perform well in the constrained dispatching of jobs. We incorporated an OSM in the environment to achieve better generalized learning of the problem. The performance of the presented approach is analyzed in depth by using a set of available benchmark instances and comparing our results with the work of other groups.

Related papers

• Dancing to the State of the Art? How Candidate Lists Influence LKH for Solving the Traveling Salesperson Problem [1.6874375111244329]
  Solving the Traveling Salesperson Problem (TSP) remains a persistent challenge. Heuristic solvers address the demand for finding high-quality solutions efficiently. Among these solvers, the Lin-Kernighan-Helsgaun (LKH) stands out, as it complements the performance of genetic algorithms.
  arXiv  Detail & Related papers  (2024-07-04T13:38:19Z)
• 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)
• Surpassing legacy approaches to PWR core reload optimization with single-objective Reinforcement learning [0.0]
  We have developed methods based on Deep Reinforcement Learning (DRL) for both single- and multi-objective optimization. In this paper, we demonstrate the advantage of our RL-based approach, specifically using Proximal Policy Optimization (PPO) PPO adapts its search capability via a policy with learnable weights, allowing it to function as both a global and local search method.
  arXiv  Detail & Related papers  (2024-02-16T19:35:58Z)
• A Reinforcement Learning-assisted Genetic Programming Algorithm for Team Formation Problem Considering Person-Job Matching [70.28786574064694]
  A reinforcement learning-assisted genetic programming algorithm (RL-GP) is proposed to enhance the quality of solutions. The hyper-heuristic rules obtained through efficient learning can be utilized as decision-making aids when forming project teams.
  arXiv  Detail & Related papers  (2023-04-08T14:32:12Z)
• MARLIN: Soft Actor-Critic based Reinforcement Learning for Congestion Control in Real Networks [63.24965775030673]
  We propose a novel Reinforcement Learning (RL) approach to design generic Congestion Control (CC) algorithms. Our solution, MARLIN, uses the Soft Actor-Critic algorithm to maximize both entropy and return. We trained MARLIN on a real network with varying background traffic patterns to overcome the sim-to-real mismatch.
  arXiv  Detail & Related papers  (2023-02-02T18:27:20Z)
• A Survey of Meta-Reinforcement Learning [83.95180398234238]
  We cast the development of better RL algorithms as a machine learning problem itself in a process called meta-RL. We discuss how, at a high level, meta-RL research can be clustered based on the presence of a task distribution and the learning budget available for each individual task. We conclude by presenting the open problems on the path to making meta-RL part of the standard toolbox for a deep RL practitioner.
  arXiv  Detail & Related papers  (2023-01-19T12:01:41Z)
• Solving the Traveling Salesperson Problem with Precedence Constraints by Deep Reinforcement Learning [59.14935871979047]
  This work presents solutions to the Traveling Salesperson Problem with precedence constraints (TSPPC) using Deep Reinforcement Learning (DRL) Common to these approaches is the use of graph models based on multi-head attention layers.
  arXiv  Detail & Related papers  (2022-07-04T14:31:47Z)
• An actor-critic algorithm with policy gradients to solve the job shop scheduling problem using deep double recurrent agents [1.3812010983144802]
  We propose a deep reinforcement learning methodology for the job shop scheduling problem (JSSP) The aim is to build up a greedy-like able to learn on some distribution of JSSP instances, different in the number of jobs and machines. As expected, the model can generalize, to some extent, to larger problems or instances originated by a different distribution from the one used in training.
  arXiv  Detail & Related papers  (2021-10-18T07:55:39Z)
• Fast Approximations for Job Shop Scheduling: A Lagrangian Dual Deep Learning Method [44.4747903763245]
  The Jobs shop Scheduling Problem (JSP) is a canonical optimization problem that is routinely solved for a variety of industrial purposes. The problem is NP-hard and computationally challenging even for medium-sized instances. This paper explores a deep learning approach to deliver efficient and accurate approximations to the problem.
  arXiv  Detail & Related papers  (2021-10-12T21:15:19Z)
• Policy Information Capacity: Information-Theoretic Measure for Task Complexity in Deep Reinforcement Learning [83.66080019570461]
  We propose two environment-agnostic, algorithm-agnostic quantitative metrics for task difficulty. We show that these metrics have higher correlations with normalized task solvability scores than a variety of alternatives. These metrics can also be used for fast and compute-efficient optimizations of key design parameters.
  arXiv  Detail & Related papers  (2021-03-23T17:49:50Z)
• Combining Deep Learning and Optimization for Security-Constrained Optimal Power Flow [94.24763814458686]
  Security-constrained optimal power flow (SCOPF) is fundamental in power systems. Modeling of APR within the SCOPF problem results in complex large-scale mixed-integer programs. This paper proposes a novel approach that combines deep learning and robust optimization techniques.
  arXiv  Detail & Related papers  (2020-07-14T12:38:21Z)

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.