The Constrained Minimum Weighted Sum of Job Completion Times Problem

Asaf Levin; Gerhard J. Woeginger

doi:10.1007/978-3-540-25960-2_23

The Constrained Minimum Weighted Sum of Job Completion Times Problem

Asaf Levin, Gerhard J. Woeginger

Discrete Mathematics and Mathematical Programming

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

17 Downloads (Pure)

Abstract

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.

Original language	English
Title of host publication	Integer Programming and Combinatorial Optimization
Subtitle of host publication	10th International IPCO Conference, New York, NY, USA, June 7-11, 2004. Proceedings
Editors	Daniel Bienstock, Georg Nemhauser
Place of Publication	Heidelberg
Publisher	Springer
Pages	298-307
ISBN (Electronic)	978-3-540-25960-2
ISBN (Print)	978-3-540-22113-5
DOIs	https://doi.org/10.1007/978-3-540-25960-2_23
Publication status	Published - 2004
Event	10th Conference on Integer Programming and Combinatorial Optimization, IPCO 2004 - New York, United States Duration: 7 Jun 2004 → 11 Jun 2004 Conference number: 10

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer
Volume	3064
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	10th Conference on Integer Programming and Combinatorial Optimization, IPCO 2004
Abbreviated title	IPCO
Country/Territory	United States
City	New York
Period	7/06/04 → 11/06/04

Keywords

Scheduling
Bicriteria optimization
Approximation scheme

Access to Document

10.1007/978-3-540-25960-2_23

Cite this

Levin, A., & Woeginger, G. J. (2004). The Constrained Minimum Weighted Sum of Job Completion Times Problem. In D. Bienstock, & G. Nemhauser (Eds.), Integer Programming and Combinatorial Optimization: 10th International IPCO Conference, New York, NY, USA, June 7-11, 2004. Proceedings (pp. 298-307). (Lecture Notes in Computer Science; Vol. 3064). Springer. https://doi.org/10.1007/978-3-540-25960-2_23

@inproceedings{35297b19363449e48045f41df1e6379f,

title = "The Constrained Minimum Weighted Sum of Job Completion Times Problem",

abstract = "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.",

keywords = "Scheduling, Bicriteria optimization, Approximation scheme",

author = "Asaf Levin and Woeginger, \{Gerhard J.\}",

year = "2004",

doi = "10.1007/978-3-540-25960-2\_23",

language = "English",

isbn = "978-3-540-22113-5",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "298--307",

editor = "Daniel Bienstock and Georg Nemhauser",

booktitle = "Integer Programming and Combinatorial Optimization",

address = "Germany",

note = "10th Conference on Integer Programming and Combinatorial Optimization, IPCO 2004, IPCO ; Conference date: 07-06-2004 Through 11-06-2004",

}

Levin, A & Woeginger, GJ 2004, The Constrained Minimum Weighted Sum of Job Completion Times Problem. in D Bienstock & G Nemhauser (eds), Integer Programming and Combinatorial Optimization: 10th International IPCO Conference, New York, NY, USA, June 7-11, 2004. Proceedings. Lecture Notes in Computer Science, vol. 3064, Springer, Heidelberg, pp. 298-307, 10th Conference on Integer Programming and Combinatorial Optimization, IPCO 2004, New York, New York, United States, 7/06/04. https://doi.org/10.1007/978-3-540-25960-2_23

The Constrained Minimum Weighted Sum of Job Completion Times Problem. / Levin, Asaf; Woeginger, Gerhard J.
Integer Programming and Combinatorial Optimization: 10th International IPCO Conference, New York, NY, USA, June 7-11, 2004. Proceedings. ed. / Daniel Bienstock; Georg Nemhauser. Heidelberg: Springer, 2004. p. 298-307 (Lecture Notes in Computer Science; Vol. 3064).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - The Constrained Minimum Weighted Sum of Job Completion Times Problem

AU - Levin, Asaf

AU - Woeginger, Gerhard J.

N1 - Conference code: 10

PY - 2004

Y1 - 2004

N2 - 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.

AB - 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.

KW - Scheduling

KW - Bicriteria optimization

KW - Approximation scheme

U2 - 10.1007/978-3-540-25960-2_23

DO - 10.1007/978-3-540-25960-2_23

M3 - Conference contribution

SN - 978-3-540-22113-5

T3 - Lecture Notes in Computer Science

SP - 298

EP - 307

BT - Integer Programming and Combinatorial Optimization

A2 - Bienstock, Daniel

A2 - Nemhauser, Georg

PB - Springer

CY - Heidelberg

T2 - 10th Conference on Integer Programming and Combinatorial Optimization, IPCO 2004

Y2 - 7 June 2004 through 11 June 2004

ER -

Levin A, Woeginger GJ. The Constrained Minimum Weighted Sum of Job Completion Times Problem. In Bienstock D, Nemhauser G, editors, Integer Programming and Combinatorial Optimization: 10th International IPCO Conference, New York, NY, USA, June 7-11, 2004. Proceedings. Heidelberg: Springer. 2004. p. 298-307. (Lecture Notes in Computer Science). doi: 10.1007/978-3-540-25960-2_23

The Constrained Minimum Weighted Sum of Job Completion Times Problem

Abstract

Publication series

Conference

Keywords

Access to Document

Fingerprint

Cite this