Learning to Dispatch for Job Shop Scheduling via Deep Reinforcement Learning

Abstract

Priority dispatching rule (PDR) is widely used for solving real-world Job-shop scheduling problem (JSSP). However, the design of effective PDRs is a tedious task, requiring a myriad of specialized knowledge and often delivering limited performance. In this paper, we propose to automatically learn PDRs via an end-to-end deep reinforcement learning agent. We exploit the disjunctive graph representation of JSSP, and propose a Graph Neural Network based scheme to embed the states encountered during solving. The resulting policy network is size-agnostic, effectively enabling generalization on large-scale instances. Experiments show that the agent can learn high-quality PDRs from scratch with elementary raw features, and demonstrates strong performance against the best existing PDRs. The learned policies also perform well on much larger instances that are unseen in training.

References in corpus (8)

• Batch Normalization: Accelerating Deep Network Training by Reducing Internal Covariate Shift
• PyTorch: An Imperative Style, High-Performance Deep Learning Library
• Graph Neural Networks: A Review of Methods and Applications
• Learning Combinatorial Optimization Algorithms over Graphs
• A Gentle Introduction to Deep Learning for Graphs
• Combinatorial Optimization with Graph Convolutional Networks and Guided Tree Search
• Attention, Learn to Solve Routing Problems!
• Learning Improvement Heuristics for Solving Routing Problems

Cited by in corpus (17)

• Deep reinforcement learning for machine scheduling: Methodology, the state-of-the-art, and future directions
• Neural Airport Ground Handling
• A Reinforcement Learning Environment For Job-Shop Scheduling
• An actor-critic algorithm with policy gradients to solve the job shop scheduling problem using deep double recurrent agents
• Learning Variable Ordering Heuristics for Solving Constraint Satisfaction Problems
• Efficient Active Search for Combinatorial Optimization Problems
• Learning to Iteratively Solve Routing Problems with Dual-Aspect Collaborative Transformer
• ScheduleNet: Learn to solve multi-agent scheduling problems with reinforcement learning
• Towards Standardising Reinforcement Learning Approaches for Production Scheduling Problems
• Optimal Solving of Constrained Path-Planning Problems with Graph Convolutional Networks and Optimized Tree Search
• Learning Large Neighborhood Search Policy for Integer Programming
• schlably: A Python Framework for Deep Reinforcement Learning Based Scheduling Experiments
• A Reinforcement-Learning-Based Multiple-Column Selection Strategy for Column Generation
• Learning Practically Feasible Policies for Online 3D Bin Packing
• Flexible Manufacturing Systems Intralogistics: Dynamic Optimization of AGVs and Tool Sharing Using Coloured-Timed Petri Nets and Actor-Critic RL with Actions Masking
• Fair Allocation with Interval Scheduling Constraints
• Learning to Solve Combinatorial Optimization under Positive Linear Constraints via Non-Autoregressive Neural Networks