An actor-critic algorithm with policy gradients to solve the job shop scheduling problem using deep double recurrent agents

DOI10.1016/J.EJOR.2023.07.037MaRDI QIDQ6087487zbMATH OpenOpenAlexFDO

Authors Marta Monaci, Valerio Agasucci, Giorgio Grani

Publication date 15 November 2023

Published in European Journal of Operational Research (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2110.09076

zbMATH Keywords

machine learningneural networksschedulingreinforcement learning

Mathematics Subject Classification ID

Operations research and management science (90Bxx)

Abstract: There is a growing interest in integrating machine learning techniques and optimization to solve challenging optimization problems. In this work, we propose a deep reinforcement learning methodology for the job shop scheduling problem (JSSP). The aim is to build up a greedy-like heuristic able to learn on some distribution of JSSP instances, different in the number of jobs and machines. The need for fast scheduling methods is well known, and it arises in many areas, from transportation to healthcare. We model the JSSP as a Markov Decision Process and then we exploit the efficacy of reinforcement learning to solve the problem. We adopt an actor-critic scheme, where the action taken by the agent is influenced by policy considerations on the state-value function. The procedures are adapted to take into account the challenging nature of JSSP, where the state and the action space change not only for every instance but also after each decision. To tackle the variability in the number of jobs and operations in the input, we modeled the agent using two incident LSTM models, a special type of deep neural network. Experiments show the algorithm reaches good solutions in a short time, proving that is possible to generate new greedy heuristics just from learning-based methodologies. Benchmarks have been generated in comparison with the commercial solver CPLEX. 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.

Cites work

• scientific article; zbMATH DE number 3550182 (Why is no real title available?)
• scientific article; zbMATH DE number 1206370 (Why is no real title available?)
• scientific article; zbMATH DE number 1416629 (Why is no real title available?)
• A Survey of Scheduling Rules
• A branch and bound algorithm for the job-shop scheduling problem
• A learning-based algorithm to quickly compute good primal solutions for stochastic integer programs
• A polynomial algorithm for the two machine job-shop scheduling problem with a fixed number of jobs
• A research survey: review of flexible job shop scheduling techniques
• Actor-Critic--Type Learning Algorithms for Markov Decision Processes
• Adaptive scheduling algorithm based on mixed graph model
• An Algorithm for Solving the Job-Shop Problem
• An Efficient Optimal Algorithm for the Two-Machines Unit-Time Jobshop Schedule-Length Problem
• An alternative framework to Lagrangian relaxation approach for job shop scheduling.
• An efficient algorithm for the job-shop problem with two jobs
• Benchmarking optimization software with performance profiles.
• Benchmarks for basic scheduling problems
• Complexity of shop-scheduling problems with fixed number of jobs: a survey
• Computational Complexity of Discrete Optimization Problems
• Dantzig-Wolfe Decomposition for Job Shop Scheduling
• Deep learning
• Deep learning assisted heuristic tree search for the container pre-marshalling problem
• Flowshop and Jobshop Schedules: Complexity and Approximation
• Machine learning for combinatorial optimization: a methodological tour d'horizon
• NP-hardness of shop-scheduling problems with three jobs
• Natural evolution strategies
• OnActor-Critic Algorithms
• Online Mixed-Integer Optimization in Milliseconds
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
• Reinforcement learning. An introduction
• Supervised sequence labelling with recurrent neural networks.
• The Complexity of Flowshop and Jobshop Scheduling
• The complexity of shop-scheduling problems with two or three jobs
• The disjunctive graph machine representation of the job shop scheduling problem
• The job shop scheduling problem: Conventional and new solution techniques
• The voice of optimization

Cited in

(1)

• Scheduling jobs using queries to interactively learn human availability times

This page was built for publication: An actor-critic algorithm with policy gradients to solve the job shop scheduling problem using deep double recurrent agents

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6087487)