Bicriteria job sequencing with release dates

Yaoguang Wang
Additional contact information
Yaoguang Wang: Max-Planck-Institut für Informatik, Saarbrücken, Germany

No 1996058, LIDAM Discussion Papers CORE from Université catholique de Louvain, Center for Operations Research and Econometrics (CORE)

Abstract: We consider the single machine job sequencing problem with release dates. The main purpose of this paper is to investigate efficient and effective approximation algorithms with a bicriteria performance guarantee. That is, for some (p1,p2), they find schedules simultaneously within a factor of p1 of the minimum total weighted completion times and within a factor of p2 of the minimum makespan. The main results of the paper are summarized as follows. First, we present a new O(n logn) algoritbm with the performance guarantee [(1+1/(Bêta), 1 + ( beta)] for any [bêta] E [0, 1]. For the problem with integer processing times and release dates, the algorithm has the bicriteria performance guarantee [(2-1/Pmax, 2 - 1/Pmax], where Pma:r: is the maximum processing time. Next, we study an elegant approximation algorithm introduced recently by Goemans. We show that its randomized version has expected bicriteria performance guarantee (1.7735, 1.51) and the derandomized version has the guarantee (1.7735, 2 - 1/Pmax). To establish the performance guarantee, we also use two LP relaxations and some randomization techniques as Goemans does, but take a different approach in the analysis, based on a decomposition theorem. Finally, we present a family of bad instances showing that it is impossible to achieve p1 [less than or equal] 1.5 with this LP lower bound.

Date: 1996-11-01
References: Add references at CitEc
Citations:

Downloads: (external link)
https://sites.uclouvain.be/core/publications/coredp/coredp1996.html (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:cor:louvco:1996058

Access Statistics for this paper

More papers in LIDAM Discussion Papers CORE from Université catholique de Louvain, Center for Operations Research and Econometrics (CORE) Voie du Roman Pays 34, 1348 Louvain-la-Neuve (Belgium). Contact information at EDIRC.
Bibliographic data for series maintained by Alain GILLIS ().