The constrained minimum weighted sum of job completion times problem

被引：0

作者：

Asaf Levin

Gerhard J. Woeginger

机构：

[1] The Hebrew University,Department of Statistics

[2] University of Twente,Department of Mathematics

[3] TU Eindhoven,Department of Mathematics and Computer Science

来源：

Mathematical Programming | 2006年 / 108卷

关键词：

Scheduling; Combinatorial optimization; Approximation scheme;

D O I：

暂无

中图分类号：

学科分类号：

摘要：

We consider the problem of minimizing the weighted sum of job completion times on a single machine (subject to certain job weights) with an additional side constraint on the weighted sum of job completion times (with respect to different job weights). This problem is NP-hard, and we provide a polynomial time approximation scheme for this problem. Our method is based on Lagrangian relaxation mixed with carefully guessing the positions of certain jobs in the schedule.

引用

页码：115 / 126

页数：11