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.037arXiv2110.09076OpenAlexW4385431284MaRDI QIDQ6087487FDOQ6087487

Authors: Marta Monaci, Valerio Agasucci, Giorgio Grani 

Publication date: 15 November 2023

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

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.

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)

Cites Work

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

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)