Improved Scheduling Algorithms for Minsum Criteria
Improved Scheduling Algorithms for Minsum Criteria
复制标题
DOI：
10.1007/3-540-61440-0_166
复制
发表时间：
1996-07
期刊：
影响因子：
--
通讯作者：
Soumen Chakrabarti;C. Phillips;Andreas S. Schulz;D. Shmoys;C. Stein;J. Wein
中科院分区：
文献类型：
--
作者：
Soumen Chakrabarti;C. Phillips;Andreas S. Schulz;D. Shmoys;C. Stein;J. Wein
本文研究了一类以最小化总加权完工时间为目标的np -hard调度问题的近最优解问题。最近的工作导致了几种技术的发展，这些技术在许多情况下产生恒定的最坏情况边界。我们通过为几个最基本的调度模型提供改进的性能保证，并为许多更现实的约束调度问题提供第一个恒定的性能保证，来继续这条研究路线。例如，我们给出了一个改进的性能保证，使单个机器上受发布日期约束的总加权完成时间最小化，并在相同的并行机器上受发布日期和/或优先级约束。我们还改进了在并行机器上调度具有发布日期的作业时的抢占能力的界限。我们给出了许多更现实的调度模型的改进在线算法，包括具有并行作业的环境，争夺共享资源的作业，树优先级约束的作业，以及车间调度模型。在其中一些情况下，我们给出了在线实现的第一个恒定性能保证。最后，我们工作的结果之一是令人惊讶的结构特性，即存在同时逼近最佳完工时间和最佳加权完成时间的时间表，且这些时间表在很小的常数范围内。这样的时间表不仅存在，而且我们可以用在线算法找到它们的近似值。
We consider the problem of finding near-optimal solutions for a variety ofNP-hard scheduling problems for which the objective is to minimize the total weighted completion time. Recent work has led to the development of several techniques that yield constant worst-case bounds in a number of settings. We continue this line of research by providing improved performance guarantees for several of the most basic scheduling models, and by giving the first constant performance guarantee for a number of more realistically constrained scheduling problems. For example, we give an improved performance guarantee for minimizing the total weighted completion time subject to release dates on a single machine, and subject to release dates and/or precedence constraints on identical parallel machines. We also give improved bounds on the power of preemption in scheduling jobs with release dates on parallel machines.We give improved on-line algorithms for many more realistic scheduling models, including environments with parallelizable jobs, jobs contending for shared resources, tree precedence-constrained jobs, as well as shop scheduling models. In several of these cases, we give the first constant performance guarantee achieved on-line. Finally, one of the consequences of our work is the surprising structural property that there are schedules that simultaneously approximate the optimal makespan and the optimal weighted completion time to within small constants. Not only do such schedules exist, but we can find approximations to them with an on-line algorithm.