论文标题
针对非律师安排的竞争性杀戮和先发制人策略
Competitive Kill-and-Restart and Preemptive Strategies for Non-Clairvoyant Scheduling
论文作者
论文摘要
我们研究了基本调度问题的杀戮和先发制策略，这些问题是最大程度地减少非顾客环境中一台机器上加权完成时间的总和。首先，对于任何确定的非顾客杀人和现场策略，我们显示了〜$ 3 $的下限。然后，我们给出任何$ b> 1 $的紧密分析，对天然$ b $尺度的杀伤和现实策略以及它的随机变体。特别是，我们通过使用Toeplitz Matrix的最大特征值来显示，确定性的竞争比为$（1+3 \ sqrt {3}）\大约6.197 $，而随机策略的竞争比率约为$ 6.197 $，而随机策略的竞争比率约为$ 6.197 $。此外，我们表明，当在线发布作业时，先发制人加权最短的时间（WSETF）规则是$ 2 $竞争，与单位权重情况下的下限匹配，与任何非智力算法的琐事释放日期相匹配。使用此结果以及向旋转机器对多台计算机的竞争力，我们证明性能保证了$ b $ scaling策略在线发布日期和相同平行机上未加权的工作的适应性$ 10 $。
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\sqrt{3})\approx 6.197$ for the deterministic and of $\approx 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.
