Online Makespan Minimization: Beat LPT by Dynamic Locking

Zhaozi Wang, Zhiwei Ying, Yuhao ZhangWINE 2023

TL;DR

This paper tackles the online makespan minimization problem for identical machines with release times. The authors introduce a novel "dynamic locking" technique that allows their Generalized SLEEPY algorithm to achieve a competitive ratio of $1.5 - O(m^2)$ for $m \ge 4$, beating the long-standing $1.5$ bound of the LPT algorithm. For $m=3$, they achieve an even better $1.482$-competitive ratio without dynamic locking.

What Problem Does This Paper Address?

The problem of makespan minimization is about assigning jobs to machines to finish all jobs as quickly as possible. In the "online" version, jobs arrive over time, and decisions must be made without knowing future arrivals. Specifically, this paper focuses on the "over-time arrival formulation" where each job has a release time (when it becomes known) and a processing time. The goal is to schedule these jobs on $m$ identical machines to minimize the makespan (the time the last job finishes).

The classic Longest Processing Time First (LPT) algorithm is known to be $1.5$-competitive for this problem. While for two machines, a tighter $1.382$-competitive ratio was achieved, for $m \ge 3$, no algorithm had convincingly surpassed the $1.5$ barrier. This paper aims to break this $1.5$ barrier for general $m$, especially for constant values of $m$.

Methods

The core of the paper's contribution lies in a novel technique called dynamic locking, building upon the idea of "locking" machines from the SLEEPY algorithm.

  • Generalized SLEEPY Algorithm: This algorithm is an extension of the LPT strategy. When a job starts on a machine, other machines are "locked" for a certain period. This prevents other jobs from starting, potentially creating gaps that the optimal solution might not have.
  • Dynamic Locking: The key innovation is making the locking parameter dynamic. Instead of a fixed lock duration, the lock duration is adjusted based on the job's processing time and start time. This dynamic adjustment is crucial for achieving better competitive ratios, especially for larger $m$.
  • Analysis Framework: The authors employ standard competitive analysis techniques, including bin-packing arguments (limiting the number of large jobs) and efficiency arguments (bounding the total workload processed within a time interval). They also utilize a "left-over lemma" from previous work to bound the difference in workload between their algorithm and the optimal solution.
  • Case Analysis: The proofs involve intricate case analysis, particularly for the "last scheduling period" (after the release of the last job) and different types of "critical jobs" (jobs that are crucial to the analysis).

Datasets

Not discussed in the paper. The paper focuses on theoretical analysis and proves competitive ratios for arbitrary job instances.

Key Insights and Ideas

  • Breaking the 1.5 Barrier: The paper demonstrates that the $1.5$ competitive ratio of LPT is not optimal for the over-time makespan minimization problem, even for constant $m$.
  • Dynamic Locking is Key: The introduction of dynamic locking is the critical element that allows the algorithm to outperform LPT. This suggests that adaptive strategies can be more effective than static ones in online scheduling.
  • Trade-off between Locking and Efficiency: Locking machines can improve the competitive ratio by creating strategic gaps, but it can also lead to wasted machine capacity, potentially harming efficiency arguments. The dynamic locking strategy aims to balance these trade-offs.
  • Special Case for m=3: Interestingly, for $m=3$, the authors achieve a better competitive ratio ($1.482$) without needing the dynamic locking technique, highlighting that the optimal strategy can depend on the number of machines.
  • Hardness for Large m without Dynamic Locking: The paper proves that for $m \ge 6$, the Generalized SLEEPY algorithm without dynamic locking can be forced to have a competitive ratio of at least $1.5$, underscoring the necessity of the dynamic locking technique for achieving better bounds.

Key Results

  • Generalized SLEEPY with Dynamic Locking: Achieves a competitive ratio of $1.5 - O(m^2)$ for $m \ge 4$. This beats the LPT algorithm's $1.5$ ratio for any constant $m$.
  • Generalized SLEEPY without Dynamic Locking (m=3): Achieves a competitive ratio of $1.482$ for $m=3$.
  • Hardness Result: For $m \ge 6$, there exists a hard instance where Generalized SLEEPY without dynamic locking has a competitive ratio of at least $1.5$.

Limitations and Future Work

  • Complexity of Analysis: The analysis is highly technical and involves intricate case breakdowns and parameter tuning.
  • Practical Implementation: The paper focuses on theoretical guarantees. The practical implementation of dynamic locking and the optimal choice of parameters in real-world scenarios are not explored.
  • Open Question for Large m: While the paper beats $1.5$ for constant $m$, the question of whether $1.5$ is achievable for arbitrarily large $m$ (or if a constant competitive ratio better than $1.5$ exists for all $m$) remains open. The authors suggest that improving beyond $1.5$ for general $m$ would require addressing efficiency issues with locking and potentially more refined analysis techniques.
  • Dynamic Locking Strategy: The authors believe their dynamic locking strategy is not just a theoretical tool and suggest investigating practical ways to implement machine locking to enhance LPT's performance.

Summary updated

BibTeX
@inproceedings{wang2023online,
  author = {Zhaozi Wang and Zhiwei Ying and Yuhao Zhang},
  title = {{Online Makespan Minimization: Beat LPT by Dynamic Locking}},
  booktitle = {WINE},
  year = {2023},
}
Figure