Two-Stage Learning For the Flexible Job Shop Scheduling Problem
This addresses the challenge of solving realistic FJSP instances under uncertainties for manufacturing and service operations, representing an incremental improvement with a novel method for a known bottleneck.
The paper tackles the Flexible Job-shop Scheduling Problem (FJSP) by proposing a two-stage deep learning framework (2SL-FJSP) that explicitly models hierarchical decisions, using confidence-aware branching and symmetry-breaking to improve learnability, and it generates high-quality solutions in milliseconds, outperforming a state-of-the-art reinforcement learning approach and other heuristics.
The Flexible Job-shop Scheduling Problem (FJSP) is an important combinatorial optimization problem that arises in manufacturing and service settings. FJSP is composed of two subproblems, an assignment problem that assigns tasks to machines, and a scheduling problem that determines the starting times of tasks on their chosen machines. Solving FJSP instances of realistic size and composition is an ongoing challenge even under simplified, deterministic assumptions. Motivated by the inevitable randomness and uncertainties in supply chains, manufacturing, and service operations, this paper investigates the potential of using a deep learning framework to generate fast and accurate approximations for FJSP. In particular, this paper proposes a two-stage learning framework 2SLFJSP that explicitly models the hierarchical nature of FJSP decisions, uses a confidence-aware branching scheme to generate appropriate instances for the scheduling stage from the assignment predictions and leverages a novel symmetry-breaking formulation to improve learnability. 2SL-FJSP is evaluated on instances from the FJSP benchmark library. Results show that 2SL-FJSP can generate high-quality solutions in milliseconds, outperforming a state-of-the-art reinforcement learning approach recently proposed in the literature, and other heuristics commonly used in practice.