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

共 13 条

[1]

Cole undefined(1987)undefined J. ACM 34 200-undefined

[2]

Goemans undefined(2000)undefined SIAM J. Discrete Math. 13 281-undefined

[3]

Horn undefined(1972)undefined SIAM J. Appl. Math. 23 189-undefined

[4]

Hassin undefined(1992)undefined Math. Oper. Res. 17 36-undefined

[5]

Levin undefined(2004)undefined Oper. Res. Lett. 32 530-undefined

[6]

Marathe undefined(1998)undefined J. Algorithms 28 142-undefined

[7]

McCormick undefined(1995)undefined ORSA J. Comput. 7 63-undefined

[8]

Megiddo undefined(1979)undefined Math. Oper. Res. 4 414-undefined

[9]

Queyranne undefined(1993)undefined Math. Program. 58 263-undefined

[10]

Queyranne undefined(1991)undefined Math. Oper. Res. 16 1-undefined

← 1 2 →