2023/11/19 by Wang, Zhaozi, Ying, Zhiwei, Zhang, Yuhao
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2311.11195
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 ≥ 3, no known algorithm has convincingly surpassed the long-standing 1.5 barrier. We propose a natural generalization of SLEEPY and show 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-(1)/(O(m2)), which beats the LPT algorithm (1.5-competitive) for every constant m.