Competitive kill-and-restart and preemptive strategies for non-clairvoyant scheduling

• 成果类型: Article
• 署名作者: Jaeger, Sven; Sagnol, Guillaume; Waldschmidt, Daniel Schmidt genannt; Warode, Philipp
• 署名单位: Technical University of Berlin; Humboldt University of Berlin
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-024-02118-8
• 发表日期: 2025
• 页码: 457-509
• 关键词: completion-time; single-machine; minimize; bounds

摘要

We study kill-and-restart and preemptive strategies for the fundamental scheduling problem of minimizing the sum of weighted completion times on a single machine in the non-clairvoyant setting. First, we show a lower bound of 3 for any deterministic non-clairvoyant kill-and-restart strategy. Then, we give for any b > 1 a tight analysis for the natural b-scaling kill-and-restart strategy as well as for a randomized variant of it. In particular, we show a competitive ratio of(1+3 root 3) approximate to 6.197 for the deterministic and of approximate to 3.032 for the randomized strategy, by making use of the largest eigenvalue of a Toeplitz matrix. In addition, we show that the preemptive Weighted Shortest Elapsed Time First (WSETF) rule is 2-competitive when jobs are released online, matching the lower bound for the unit weight case with trivial release dates for any non-clairvoyant algorithm. Using this result as well as the competitiveness of round-robin for multiple machines, we prove performance guarantees smaller than 10 for adaptions of the b-scaling strategy to online release dates and unweighted jobs on identical parallel machines.