The constrained minimum weighted sum of job completion times problem

A. Levin, G.J. Woeginger

Research output: Contribution to journalArticleAcademicpeer-review

4 Citations (Scopus)

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
Pages (from-to)115-126
Number of pages12
JournalMathematical Programming
Volume108
Issue number1
DOIs
Publication statusPublished - 2006

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