LLMs can Schedule

Henrik Abgaryan, Ararat Harutyunyan, Tristan CazenavearXiv 2024 · OpenReview

Abstract

The job shop scheduling problem (JSSP) remains a significant hurdle in optimizing production processes. This challenge involves efficiently allocating jobs to a limited number of machines while minimizing factors like total processing time or job delays. While recent advancements in artificial intelligence have yielded promising solutions, such as reinforcement learning and graph neural networks, this paper explores the potential of Large Language Models (LLMs) for JSSP. We introduce the very first supervised 120k dataset specifically designed to train LLMs for JSSP. Surprisingly, our findings demonstrate that LLM-based scheduling can achieve performance comparable to other neural approaches. Furthermore, we propose a sampling method that enhances the effectiveness of LLMs in tackling JSSP.

Introduction

The Job Shop Scheduling Problem (JSSP) is a fundamental hurdle in manufacturing and logistics. It involves processing $N$ jobs on $M$ different machines, where each job has a specific sequence of operations with varying durations. The objective is to minimize the makespan—the total time required to complete all jobs. As an NP-hard problem, JSSP is computationally intensive for large-scale instances. Traditional approaches rely on mathematical programming or Priority Dispatching Rules (PDRs). While Deep Reinforcement Learning (DRL) and Graph Neural Networks (GNNs) have emerged as modern alternatives, this research investigates whether the reasoning capabilities of Large Language Models (LLMs) can be directly applied to solve these combinatorial optimization problems.

Methodology

The researchers framed scheduling as a translation task, converting a natural language description of a problem into a valid schedule description.

Problem Representation

Two primary descriptive formats were explored:

  • Job-Centric: Detailing the operation sequence for each job.
  • Machine-Centric: Detailing the operations assigned to each machine. The machine-centric approach was selected for training as it better highlights resource conflicts.

Model and Fine-Tuning

The study utilized Phi-3-Mini-128K-Instruct, a 3.8 billion parameter model. To ensure computational efficiency, the team employed LoRA (Low-Rank Adaptation) and 4-bit quantization, enabling fine-tuning on a single GPU.

Sampling Strategy

To improve solution quality, a sampling method was implemented. Instead of a single greedy output, the model generates 10 candidate schedules per problem, with the one yielding the lowest makespan being selected. This approach leverages the model's ability to explore the solution space.

Training and evaluation metrics over time, showing loss and gradient norm convergence.

The JSSP-120k Dataset

A major contribution of this work is the JSSP-120k dataset, the first large-scale natural language dataset for scheduling.

  • Scale: 120,000 instances ranging from 2x2 to 20x20.
  • Generation: Problems were generated randomly, with "ground truth" solutions provided by Google’s OR-Tools classical solver.
  • Format: All data is presented in human-readable natural language, moving away from traditional matrix-based representations.

Results and Discussion

The fine-tuned Phi-3 model was benchmarked against state-of-the-art neural approaches, including L2D (Learning to Dispatch) and SLJ (Self-Labeling JSSP).

  • Performance: The LLM achieved an 8.92% average gap from the optimal makespan, significantly outperforming the original L2D method (13.01% gap). While it slightly trailed the most advanced pointer networks (2-3% gap), it established LLMs as a competitive alternative.
  • Constraint Satisfaction: Post-fine-tuning, the model consistently generated feasible schedules respecting all machine and precedence constraints, a task it could not perform zero-shot.
  • Model Efficiency: The success of a 3.8B parameter model suggests that high-quality, domain-specific data is more critical than sheer model size for complex logical tasks.

Conclusion and Future Work

This research demonstrates that LLMs can internalize complex optimization constraints through text-based fine-tuning. However, challenges remain regarding computational overhead compared to specialized GNNs and scalability to industrial-scale problems (e.g., 100x100). Future research will explore hybrid approaches combining LLMs with Reinforcement Learning to develop self-improving schedulers and address the "black box" nature of neural decision-making in industrial contexts.

Summary updated

Abstract

The job shop scheduling problem (JSSP) remains a significant hurdle in optimizing production processes. This challenge involves efficiently allocating jobs to a limited number of machines while minimizing factors like total processing time or job delays. While recent advancements in artificial intelligence have yielded promising solutions, such as reinforcement learning and graph neural networks, this paper explores the potential of Large Language Models (LLMs) for JSSP. We introduce the very first supervised 120k dataset specifically designed to train LLMs for JSSP. Surprisingly, our findings demonstrate that LLM-based scheduling can achieve performance comparable to other neural approaches. Furthermore, we propose a sampling method that enhances the effectiveness of LLMs in tackling JSSP.
BibTeX
@misc{abgaryan2024llms,
  author = {Henrik Abgaryan and Ararat Harutyunyan and Tristan Cazenave},
  title = {{LLMs can Schedule}},
  year = {2024},
  eprint = {2408.06993},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2408.06993},
}
Figure