Strong LP formulations for scheduling splittable jobs on unrelated machines

José Correa, Alberto Marchetti-Spaccamela, Jannik Matuschke, Leen Stougie, Ola Svensson, Víctor Verdugo, José VerschaeMath. Program 2015 · DOI

Introduction

In classical scheduling theory, the problem of unrelated machine scheduling ($R||C_{max}$) involves assigning $n$ jobs to $m$ machines to minimize the makespan, where each job has a machine-dependent processing time. This paper investigates a more complex and realistic extension: splittable jobs with setup times ($R|split, setup|C_{max}$). In this model, jobs can be processed by multiple machines simultaneously, but each machine must perform a fixed-duration setup whenever it handles any portion of a job. This scenario is prevalent in high-overhead industries such as semiconductor manufacturing and disaster relief logistics.

Problem Formulation and Challenges

The core challenge in $R|split, setup|C_{max}$ is the inherent tension between splitting jobs to balance machine loads and the overhead incurred by setup times. Excessive splitting can lead to an accumulation of setup times that paradoxically increases the total makespan. The authors aim to bridge the gap between simple heuristics and optimal solutions using advanced Linear Programming (LP) techniques.

Hierarchical LP Relaxations

The research develops a progression of LP formulations to tighten the approximation bounds:

  1. The Basic LP (LST): A natural generalization of the classic Lenstra-Shmoys-Tardos LP. The authors prove this formulation has an integrality gap of 3 and provide a corresponding 3-approximation rounding algorithm.
  2. Lift-and-Project (LST_strong): By applying a lift-and-project procedure, the authors add valid inequalities that more accurately capture the relationship between fractional job assignments and the binary nature of setup times.
  3. Job Configuration LP: Moving beyond standard machine-based configurations, the authors propose a novel "job-based" configuration LP. This approach considers the infinite continuum of ways a single job can be distributed across the machine fleet. They demonstrate that this can be solved in polynomial time through discretization and dual separation.

Rounding and the Pseudotree Structure

A key insight of the paper is the structural property of the LP's extreme points. The authors show that these points correspond to graphs where each connected component is a "pseudotree"—a tree structure containing at most one cycle. This structural regularity allows for a sophisticated rounding algorithm that assigns fractional jobs to machines while maintaining a low approximation ratio.

The structure of extreme points in the LP relaxation, forming a collection of pseudotrees, which facilitates the rounding process.

Theoretical Bounds and Hardness

The authors establish that the approximation ratio for machine-based formulations is fundamentally tied to the golden ratio ($\phi \approx 1.618$), hitting a barrier at $1 + \phi \approx 2.618$. Furthermore, they prove that allowing jobs to be split with setups makes the problem strictly harder than the non-splittable version. Using a reduction from the Max $k$-Cover problem, they establish a new hardness lower bound of $e/(e-1) \approx 1.582$.

A specific mathematical instance (gadget) used to prove the integrality gaps of the LP formulations and the NP-hardness of the problem.

Key Results and Conclusion

The paper provides several significant contributions to scheduling theory:

  • An improved $(1 + \phi + \epsilon)$-approximation (approximately 2.618) for the general case.
  • A $(2 + \epsilon)$-approximation for the restricted assignment case.
  • A proof that all proposed algorithms produce schedules where at most one split job is processed per machine, a desirable property for minimizing labor costs in manufacturing.

While the Job Configuration LP is exceptionally strong, finding a rounding algorithm that fully exploits its potential to beat the $1 + \phi$ ratio remains an open question for future research.

Summary updated

BibTeX
@article{correa2015strong,
  author = {José Correa and Alberto Marchetti-Spaccamela and Jannik Matuschke and Leen Stougie and Ola Svensson and Víctor Verdugo and José Verschae},
  title = {{Strong LP formulations for scheduling splittable jobs on unrelated machines}},
  journal = {Math. Program.},
  year = {2015},
  doi = {10.1007/s10107-014-0831-8},
}
Figure