Learning to solve the single machine scheduling problem with release times and sum of completion times

Axel Parmentier, Vincent T'kindtarXiv 2021 · arXiv

Introduction

The single machine scheduling problem with release times and the sum of completion times ($1|r_j|\sum C_j$) is a fundamental challenge in operations research. While the version without release dates is solvable in polynomial time using the Shortest Processing Time (SPT) rule, the introduction of release dates $r_j$ renders the problem NP-hard. This paper proposes a novel framework that leverages machine learning (ML) to transform these hard instances into simpler "proxy" problems that can be solved near-instantaneously.

The Learning-to-Solve Framework

The core of the proposed approach is a three-stage pipeline: Encoding, Solving, and Decoding. This framework allows an ML model to act as a "translator," mapping the constraints of a hard problem instance into a simplified space where a greedy algorithm can find high-quality solutions.

The general Learning-to-Solve framework for NP-hard problems.

1. Encoding (The ML Predictor)

A machine learning predictor $\phi_\theta$ calculates "pseudo-processing times" $\hat{p}_j$ for each job. These values are not the actual processing times but are derived from a linear combination of 27 features, including job positions in various heuristic sequences and release date statistics. The model is trained using Structured Learning with Fenchel-Young loss, ensuring that the optimal solution of the simplified problem corresponds to a strong solution for the original NP-hard instance.

2. Solving (The Proxy Problem)

The "easy" version of the problem ignores release dates. Using the predicted pseudo-times $\hat{p}_j$, the system applies the Shortest Processing Time (SPT) rule. This step is computationally efficient, requiring only $O(n \log n)$ time.

3. Decoding

The sequence generated in the solving stage is mapped back to the original problem. The authors explore three decoding variants:

  • PMLH (Pure ML): Directly uses the sequence from the proxy solver.
  • IMLH (Improved ML): Enhances the sequence with a fast local search and the RDI refinement heuristic.
  • itMLH (Iterative ML): Generates multiple candidate schedules by perturbing learned parameters and selects the best one.
The Iterative ML Heuristic (itMLH) architecture.

Experimental Results and Insights

The framework was evaluated on synthetic benchmarks ranging from 50 to 2,500 jobs.

Performance and Speed

The iterative variant, itMLH, demonstrated superior performance compared to standard heuristics on large-scale instances. While complex matheuristics (MATH) can achieve slightly higher accuracy, they are significantly slower. For instance, on problems with 300 jobs, MATH required approximately 214 seconds, whereas itMLH reached a solution in just 2.37 seconds.

Scalability

A key finding is the effectiveness of the "Pure" ML heuristic (PMLH). Even without local search, PMLH maintained an average deviation of only ~1% from best-known solutions on large instances. This suggests that the ML predictor successfully captures the underlying structure of the scheduling problem, allowing simple greedy rules to perform exceptionally well.

Conclusion

This research demonstrates that ML can be integrated into operations research not just as a standalone solver, but as a sophisticated pre-processor that simplifies problem complexity. By learning to "warp" problem parameters, the framework enables near-optimal scheduling at speeds suitable for real-time applications. Future work will explore applying this paradigm to other combinatorial optimization problems like the Traveling Salesperson Problem (TSP).

Summary updated

Abstract

In this paper, we focus on the solution of a hard single machine scheduling problem by new heuristic algorithms embedding techniques from machine learning field and scheduling theory. These heuristics transform an instance of the hard problem into an instance of a simpler one solved to optimality. The obtained schedule is then transposed to the original problem. Computational experiments show that they are competitive with state-of-the-art heuristics, notably on large instances.
BibTeX
@misc{parmentier2021learning,
  author = {Axel Parmentier and Vincent T'kindt},
  title = {{Learning to solve the single machine scheduling problem with release times and sum of completion times}},
  year = {2021},
  eprint = {2101.01082},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2101.01082},
}
Figure