The Constrained Minimum Weighted Sum of Job Completion Times Problem

Asaf Levin, Gerhard J. Woeginger

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

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 languageEnglish
Title of host publicationInteger Programming and Combinatorial Optimization
Subtitle of host publication10th International IPCO Conference, New York, NY, USA, June 7-11, 2004. Proceedings
EditorsDaniel Bienstock, Georg Nemhauser
Place of PublicationHeidelberg
PublisherSpringer
Pages298-307
ISBN (Electronic)978-3-540-25960-2
ISBN (Print)978-3-540-22113-5
DOIs
Publication statusPublished - 2004
Event10th Conference on Integer Programming and Combinatorial Optimization, IPCO 2004 - New York, United States
Duration: 7 Jun 200411 Jun 2004
Conference number: 10

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume3064
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference10th Conference on Integer Programming and Combinatorial Optimization, IPCO 2004
Abbreviated titleIPCO
CountryUnited States
CityNew York
Period7/06/0411/06/04

Keywords

  • Scheduling
  • Bicriteria optimization
  • Approximation scheme

Fingerprint Dive into the research topics of 'The Constrained Minimum Weighted Sum of Job Completion Times Problem'. Together they form a unique fingerprint.

  • 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). Heidelberg: Springer. https://doi.org/10.1007/978-3-540-25960-2_23