用深度学习一次性生成任意规模的机器调度方案,效果接近最优。
Deep Learning for Unrelated-Machines Scheduling: Handling Variable Dimensions
- 设计可处理变维特征的神经网络,一次生成完整调度
- 8×4小规模下误差仅2.51%,100×10时比先进规则低22.22%成本
- 适合需要快速适应新调度场景的工业应用
深度学习在离散优化中已取得成效,但针对异构并行机的调度仍具挑战。因工件与机器数量可变,且每对组合处理时间不同,导致特征维度动态变化。本文提出一种新型神经网络方法,用于异构机上离线确定性调度,目标是最小化包含完工时间和加权延迟的复杂目标函数。不同于现有在线逐个处理的方法,本方法一次性考虑全部输入生成完整调度。模型融合多种受NLP启发的架构,能有效处理任意规模的工件与机器,且特征维度可变。在8工件4机器的小规模实例上训练后,可泛化至最多100工件10机器的大规模场景。测试显示,成本仅比最优值高2.51%;相较先进派发规则,平均成本降低22.22%。该方法支持通过模拟数据快速重训练,适应不同调度条件,有望成为异构机调度的通用学习范式。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。