Abstract
Scheduling problems are fundamental to logistics and manufacturing but are often NP-hard, making them computationally expensive to solve at scale. This paper presents the Unified Machine Scheduling Neural Network (UMSNN), a deep learning framework that combines offline training on mathematically guaranteed "special instances" with an online fine-tuning step. By utilizing a differentiable feasibility surrogate, the UMSNN achieves near-optimal solutions for single-machine scheduling problems with up to 1,000 jobs in seconds, effectively bypassing the traditional "label bottleneck" associated with large-scale combinatorial optimization.
Introduction
Single-machine scheduling involves determining the optimal sequence of jobs to minimize specific cost objectives, such as total weighted tardiness or completion time. While the premise is straightforward, most variations are NP-hard, meaning the computational effort required to find an optimal solution grows exponentially with the number of jobs.
Traditional approaches generally fall into two categories: exact mathematical solvers, which provide optimal solutions but fail to scale to large problems, and hand-crafted heuristics, which are fast but often limited to specific problem types. Machine Learning (ML) has emerged as a promising third path, yet it faces a significant "label bottleneck." Training supervised models requires optimal solutions for large-scale instances to serve as ground truth, which are precisely what exact solvers cannot provide. This paper introduces a unified approach that leverages a scaling theorem for offline training and a differentiable surrogate for online optimization, enabling high-performance scheduling across a wide variety of objectives.
Methodology
1. Unified Representation and Architecture
The core of the proposed framework is the Unified Machine Scheduling Neural Network (UMSNN). To handle diverse scheduling objectives (e.g., tardiness, multi-agent costs, non-linear functions) within a single model, the authors employ a time-indexed formulation. This allows different problems to be expressed in a common mathematical language.
The UMSNN architecture utilizes:
- Convolutional Neural Networks (CNNs): To extract local features from raw cost parameters.
- Transformer-based Encoders: To capture global dependencies and complex relationships between jobs, ensuring the model understands the relative importance and constraints of the entire job set.
2. Offline Training via "Special Instances"
To solve the label bottleneck, the authors introduce a novel training strategy based on a scaling theorem. Instead of attempting to solve 1,000-job NP-hard problems to generate training data, they solve small instances optimally. They then mathematically "stretch" these small instances into large "special instances" where the optimal solution remains known. This allows the UMSNN to learn the features of high-quality schedules for large-scale problems without the computational burden of running solvers on massive, difficult instances.
3. Online Single-Instance Learning
While the offline model provides a strong general foundation, the authors incorporate an online fine-tuning step to adapt the model to specific, "live" problem instances. Because scheduling is a discrete combinatorial problem, its objective functions are typically non-differentiable, preventing standard gradient descent.
To overcome this, the authors developed a feasibility surrogate. This differentiable function approximates the discrete objective value using sigmoid-based approximations. This "soft" landscape allows the model to perform gradient-based updates on its parameters for a specific instance, further refining the solution quality in real-time.
Experimental Evaluation
The UMSNN was evaluated across 17 distinct problem cases, including multi-criterion objectives and multi-agent scheduling. The testing involved two primary groups:
- Group 1: 500–700 jobs.
- Group 2: 800–1,000 jobs.
The model was trained on 10,000 special instances per case and tested against standard distributions found in scheduling literature to ensure robustness.
Results and Discussion
The integrated offline/online approach demonstrated significant improvements over traditional benchmarks:
- High Solution Quality: The solutions consistently stayed within 1% to 2% of the theoretical lower bound, indicating near-optimal performance across various cost functions.
- Operational Speed: For the largest instances (1,000 jobs), the model generated solutions in seconds. Even with the optional online fine-tuning, the total computation time typically remained under 100 seconds.
- Scalability: The UMSNN significantly outperformed "Shrink + IP" (Integer Programming) methods and proved more practical than Linear Programming (LP) relaxations, which often failed to find feasible solutions for large instances within a two-hour limit.
Conclusion
The UMSNN framework represents a significant advancement in applying deep learning to combinatorial optimization. By combining a scaling-based data generation strategy with a differentiable feasibility surrogate, the authors provide a general-purpose tool for single-machine scheduling that balances speed and optimality. While currently focused on min-sum objectives on single machines, the methodology offers a blueprint for extending neural optimization to more complex environments, such as Job Shop Scheduling and Vehicle Routing Problems.
Summary updated