期刊
MATHEMATICAL PROGRAMMING
卷 94, 期 2-3, 页码 361-374出版社
SPRINGER HEIDELBERG
DOI: 10.1007/s10107-002-0324-z
关键词
scheduling; preemption; approximation algorithm; worst case ratio; computational complexity; in-approximability
We consider the problem of preemptively scheduling a set of n jobs on in (identical, uniformly related, or unrelated) parallel machines. The scheduler may reject a subset of the jobs and thereby incur job-dependent penalties for each rejected job, and he must construct a schedule for the remaining jobs so as to optimize the preemptive makespan on the in machines plus the sum of the penalties of the jobs rejected. We provide a complete classification of these scheduling problems with respect to complexity and approximability. Our main results are on the variant with an arbitrary number of unrelated machines. This variant is APX-hard, and we design a 1.58-approximation algorithm for it. All other considered variants are weakly NP-hard, and we provide fully polynomial time approximation schemes for them. Finally, we argue that our results for unrelated machines can be carried over to the corresponding preemptive open shop scheduling problem with rejection.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据