Minimizing the Total Completion Time On-line on a Single Machine, Using Restarts

Minimizing the Total Completion Time On-line on a Single Machine, Using Restarts
复制标题

DOI：
10.1007/3-540-45749-6_75
复制
发表时间：
2002-09
期刊：
--
影响因子：
--
通讯作者：
R. V. Stee;H. L. Poutré
R. V. Stee;H. L. Poutré
中科院分区：
其他
文献类型：
--
作者：
R. V. Stee;H. L. Poutré

文献摘要

被引文献

相似文献

我们给出了一个算法，以最小化总完成时间在线单机上，使用重新启动，与3/2的竞争比。在不使用重启的情况下，确定性算法的最优竞争比为2，随机算法的最优竞争比为de/（e-1）= 1.582。这是第一个重新启动算法，以最大限度地减少总完成时间，被证明是优于一个算法，不重新启动。
We give an algorithm to minimize the total completion time on-line on a single machine, using restarts, with a competitive ratio of 3/2. The optimal competitive ratio without using restarts is 2 for deterministic algorithms ande/(e—1)≈ 1.582 for randomized algorithms. This is the first restarting algorithm to minimize the total completion time that is proved to be better than an algorithm that does not restart.