Competitive kill-and-restart and preemptive strategies for non-clairvoyant scheduling
研究了非明悉环境下单机最小化加权完成时间之和的杀重启与抢占策略，给出了确定性策略的竞争比下界3，并分析了b-缩放策略的竞争比，同时证明了抢占式WSETF规则在在线释放时是2-竞争的。
Abstract 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$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>b</mml:mi> <mml:mo>></mml:mo> <mml:mn>1</mml:mn> </mml:mrow> </mml:math> 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\sqrt{3})\approx 6.197$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mo>(</mml:mo> <mml:mn>1</mml:mn> <mml:mo>+</mml:mo> <mml:mn>3</mml:mn> <mml:msqrt> <mml:mn>3</mml:mn> </mml:msqrt> <mml:mo>)</mml:mo> <mml:mo>≈</mml:mo> <mml:mn>6.197</mml:mn> </mml:mrow> </mml:math> for the deterministic and of $$\approx 3.032$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mo>≈</mml:mo> <mml:mn>3.032</mml:mn> </mml:mrow> </mml:math> 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.