Starjob: Dataset for LLM-Driven Job Shop Scheduling

📄 arXiv: 2503.01877v2 📥 PDF

作者: Henrik Abgaryan, Tristan Cazenave, Ararat Harutyunyan

分类: cs.LG, cs.AI

发布日期: 2025-02-26 (更新: 2025-03-27)

备注: arXiv admin note: substantial text overlap with arXiv:2408.06993

💡 一句话要点

提出Starjob数据集，利用LLM解决Job Shop调度问题

🎯 匹配领域: 支柱九：具身大模型 (Embodied Foundation Models)

关键词: Job Shop调度 大型语言模型 组合优化 数据集 微调 LLaMA LoRA

📋 核心要点

  1. 现有Job Shop调度方法在复杂场景下难以达到最优解，且泛化能力有限，需要更强大的模型。
  2. 论文提出利用LLM的强大建模能力，直接学习Job Shop调度策略，无需人工设计启发式规则。
  3. 实验表明，基于Starjob数据集微调的LLM模型，在标准benchmark上显著超越传统方法和现有神经方法。

📝 摘要（中文）

大型语言模型（LLM）在各个领域都展现了卓越的能力，但它们在解决组合优化问题方面的潜力仍未被充分探索。本文研究了LLM在Job Shop调度问题（JSSP）中的适用性，这是一个经典的组合优化挑战，需要有效地将作业分配给机器以最小化完工时间。为此，我们引入了Starjob，这是第一个用于JSSP的监督数据集，包含13万个专门为训练LLM而设计的实例。利用该数据集，我们使用LoRA方法对LLaMA 8B 4-bit量化模型进行微调，以开发端到端的调度方法。在标准基准测试上的评估表明，所提出的基于LLM的方法不仅超越了传统的优先级调度规则（PDR），而且在DMU和Taillard基准测试上分别实现了15.36%和7.85%的平均改进，优于最先进的神经方法（如L2D）。这些结果突出了LLM在解决组合优化问题方面的未开发潜力，为该领域未来的发展铺平了道路。

🔬 方法详解

问题定义：论文旨在解决Job Shop调度问题（JSSP），目标是找到最优的作业调度方案，以最小化完工时间。现有方法，如优先级调度规则（PDR）和基于神经网络的方法（如L2D），在面对大规模和复杂的JSSP实例时，往往难以获得高质量的解决方案，并且泛化能力有限。

核心思路：论文的核心思路是利用大型语言模型（LLM）强大的序列建模能力，将JSSP视为一个序列生成问题。通过训练LLM直接预测作业的调度顺序，从而避免了手动设计复杂的启发式规则或训练专门的神经网络模型。这种方法旨在提高求解效率和泛化能力。

技术框架：整体框架包括数据集构建和模型训练两个主要阶段。首先，构建了大规模的JSSP数据集Starjob，包含13万个实例。然后，使用LoRA方法对LLaMA 8B 4-bit量化模型进行微调，使其能够根据JSSP实例生成调度方案。模型输入是JSSP实例的描述，输出是作业的调度顺序。

关键创新：最重要的技术创新点在于将LLM应用于JSSP问题，并构建了专门的训练数据集Starjob。与传统的基于规则或神经网络的方法不同，该方法利用LLM的预训练知识和强大的建模能力，直接学习调度策略，无需人工干预。

关键设计：关键设计包括：1) Starjob数据集的构建，保证了数据规模和多样性；2) 使用LoRA方法进行模型微调，降低了训练成本；3) 采用LLaMA 8B 4-bit量化模型，减小了模型体积，提高了推理速度；4) 将JSSP实例编码为LLM可以理解的文本格式，例如，将机器和作业信息转换为自然语言描述。

🖼️ 关键图片

fig_0
fig_1
fig_2

📊 实验亮点

实验结果表明，基于Starjob数据集微调的LLaMA模型在DMU和Taillard基准测试上分别实现了15.36%和7.85%的平均改进，显著优于传统的优先级调度规则（PDR）和最先进的神经方法（如L2D）。这些结果验证了LLM在解决JSSP问题上的有效性和潜力。

🎯 应用场景

该研究成果可应用于智能制造、物流管理、资源调度等领域，通过优化生产流程和资源分配，提高生产效率、降低成本。未来，可进一步探索LLM在更复杂的组合优化问题中的应用，例如车辆路径问题、旅行商问题等，推动相关领域的智能化发展。

📄 摘要（原文）

Large Language Models (LLMs) have shown remarkable capabilities across various domains, but their potential for solving combinatorial optimization problems remains largely unexplored. In this paper, we investigate the applicability of LLMs to the Job Shop Scheduling Problem (JSSP), a classic challenge in combinatorial optimization that requires efficient job allocation to machines to minimize makespan. To this end, we introduce Starjob, the first supervised dataset for JSSP, comprising 130k instances specifically designed for training LLMs. Leveraging this dataset, we fine-tune the LLaMA 8B 4-bit quantized model with the LoRA method to develop an end-to-end scheduling approach. Our evaluation on standard benchmarks demonstrates that the proposed LLM-based method not only surpasses traditional Priority Dispatching Rules (PDRs) but also achieves notable improvements over state-of-the-art neural approaches like L2D, with an average improvement of 15.36% on DMU and 7.85% on Taillard benchmarks. These results highlight the untapped potential of LLMs in tackling combinatorial optimization problems, paving the way for future advancements in this area.