Deep Learning for Unrelated-Machines Scheduling: Handling Variable Dimensions
This addresses a difficult scheduling problem for operations research and AI optimization, though it appears incremental as it builds on existing deep learning methods for optimization.
The paper tackles the problem of offline deterministic scheduling on unrelated parallel machines with variable dimensions, aiming to minimize makespan and weighted tardiness. Their neural network approach achieved costs only 2.51% above optimal on 8-job/4-machine instances and consistently outperformed an advanced dispatching rule by 22.22% on average across configurations up to 100 jobs and 10 machines.
Deep learning has been effectively applied to many discrete optimization problems. However, learning-based scheduling on unrelated parallel machines remains particularly difficult to design. Not only do the numbers of jobs and machines vary, but each job-machine pair has a unique processing time, dynamically altering feature dimensions. We propose a novel approach with a neural network tailored for offline deterministic scheduling of arbitrary sizes on unrelated machines. The goal is to minimize a complex objective function that includes the makespan and the weighted tardiness of jobs and machines. Unlike existing online approaches, which process jobs sequentially, our method generates a complete schedule considering the entire input at once. The key contribution of this work lies in the sophisticated architecture of our model. By leveraging various NLP-inspired architectures, it effectively processes any number of jobs and machines with varying feature dimensions imposed by unrelated processing times. Our approach enables supervised training on small problem instances while demonstrating strong generalization to much larger scheduling environments. Trained and tested on instances with 8 jobs and 4 machines, costs were only 2.51% above optimal. Across all tested configurations of up to 100 jobs and 10 machines, our network consistently outperformed an advanced dispatching rule, which incurred 22.22% higher costs on average. As our method allows fast retraining with simulated data and adaptation to various scheduling conditions, we believe it has the potential to become a standard approach for learning-based scheduling on unrelated machines and similar problem environments.