用Transformer加速调度问题列生成，省时且保优。
All You Need is an Improving Column: Enhancing Column Generation for Parallel Machine Scheduling via Transformers
- 用Transformer预测负缩减成本的作业序列以生成新列
- 小中规模实例平均提速45%，大规模实例500秒内目标值提升80%
- 模型可泛化到不同分布的新问题，适合大规模调度场景
我们提出一种基于神经网络增强的列生成（CG）方法，用于并行机调度问题。该方法采用编码器-解码器注意力结构（即Transformer与指针网络），生成具有负缩减成本的作业序列，从而向主问题添加新列。通过离线训练神经网络并在推理模式下预测负缩减成本列，相比动态规划（DP）显著节省计算时间。由于在终止时仍使用精确的DP过程验证是否还能发现负缩减成本列，原列生成方法的最优性保证得以保留。对于小至中等规模实例，本方法平均减少45%的计算时间；此外，模型不仅能泛化到同分布但更大的未见实例，还可适应训练时未出现的概率分布。对于大规模实例，该方法在500秒内实现目标值80%的提升，展现出良好的可扩展性与效率。
原文摘要 · Abstract (English)
We present a neural network-enhanced column generation (CG) approach for a parallel machine scheduling problem. The proposed approach utilizes an encoder-decoder attention model, namely the transformer and pointer architectures, to develop job sequences with negative reduced cost and thus generate columns to add to the master problem. By training the neural network offline and using it in inference mode to predict negative reduced costs columns, we achieve significant computational time savings compared to dynamic programming (DP). Since the exact DP procedure is used to verify that no further columns with negative reduced cost can be identified at termination, the optimality guarantee of the original CG procedure is preserved. For small to medium-sized instances, our approach achieves an average 45% reduction in computation time compared to solving the subproblems with DP. Furthermore, the model generalizes not only to unseen, larger problem instances from the same probability distribution but also to instances from different probability distributions than those presented at training time. For large-sized instances, the proposed approach achieves an 80% improvement in the objective value in under 500 seconds, demonstrating both its scalability and efficiency.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。