期刊
JOURNAL OF ALGORITHMS
卷 49, 期 1, 页码 175-191出版社
ACADEMIC PRESS INC ELSEVIER SCIENCE
DOI: 10.1016/S0196-6774(03)00078-6
关键词
-
We consider the general problem of scheduling a set of jobs where we may choose not to schedule certain jobs. and thereby incur a penalty for each rejected job. More specifically, we focus on choosing a set of jobs to reject and constructing a schedule for the remaining jobs so as to optimize the sum of the weighted completion times of the jobs scheduled plus the sum of the penalties of the jobs rejected. We give several techniques for designing scheduling algorithms under this criterion. Many of these techniques show how to reduce a problem with rejection to a (potentially more complex) scheduling problem without rejection. Some of the reductions are based on general properties of certain kinds of linear-programming relaxations of optimization problems, and therefore are applicable to problems outside of scheduling; we demonstrate this by giving an approximation algorithm for a variant of the facility-location problem. (C) 2003 Elsevier Inc. All rights reserved.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据