Online Makespan Minimization: Beat LPT by Dynamic Locking
摘要
Online makespan minimization is a fundamental problem in scheduling. In this paper, we investigate its over-time formulation, where each job has a release time and a processing time. A job becomes known only at its release time and must be scheduled on a machine thereafter. The Longest Processing Time First (LPT) algorithm, established by Chen and Vestjens (1997), achieves a competitive ratio of 1.5. For the special case of two machines, Noga and Seiden introduced the SLEEPY algorithm, which achieves a tight competitive ratio of 1.382. However, for \(m \ge 3\) , no known algorithm has convincingly surpassed the long-standing 1.5 barrier. We propose a natural generalization of SLEEPY and show that this simple approach can beat the 1.5 barrier and achieve 1.482-competitive when \(m=3\) . However, when m becomes large, we prove this simple generalization fails to beat 1.5. Meanwhile, we introduce a novel technique called dynamic locking to overcome this new challenge. As a result, we achieve a competitive ratio of \(1.5-\frac{1}{O(m^2)}\) , which beats the LPT algorithm (1.5-competitive) for every constant m.