User Manual Privacy Policy Disclaimer Contact us
  Advanced SearchBrowse





Bicriteria job sequencing with release dates


Wang,  Yaoguang
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

External Ressource
No external resources are shared
Fulltext (public)

(Any fulltext), 11KB

Supplementary Material (public)
There is no public supplementary material available

Wang, Y.(1997). Bicriteria job sequencing with release dates (MPI-I-1997-1-005). Saarbrücken: Max-Planck-Institut für Informatik.

Cite as: http://hdl.handle.net/11858/00-001M-0000-0014-9F79-B
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 $(\rho_1, \rho_2)$, they find schedules simultaneously within a factor of $\rho_1$ of the minimum total weighted completion times and within a factor of $\rho_2$ of the minimum makespan. The main results of the paper are summarized as follows. First, we present a new $O(n\log n)$ algorithm with the performance guarantee $\left(1+\frac{1}{\beta}, 1+\beta\right)$ for any $\beta \in [0,1]$. For the problem with integer processing times and release dates, the algorithm has the bicriteria performance guarantee $\left(2-\frac{1}{p_{max}}, 2-\frac{1}{p_{max}}\right)$, where $p_{max}$ 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-\frac{1}{p_{max}})$. 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 $\rho_1\leq 1.5$ with this LP lower bound.