The constrained minimum weighted sum of job completion times problem

A. Levin, G.J. Woeginger

Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer review

4 Citaten (Scopus)

Samenvatting

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.
Originele taal-2Engels
Pagina's (van-tot)115-126
Aantal pagina's12
TijdschriftMathematical Programming
Volume108
Nummer van het tijdschrift1
DOI's
StatusGepubliceerd - 2006

Vingerafdruk

Duik in de onderzoeksthema's van 'The constrained minimum weighted sum of job completion times problem'. Samen vormen ze een unieke vingerafdruk.

Citeer dit