b'@techreport{Wang1997,'b'\nTITLE = {Bicriteria job sequencing with release dates},\nAUTHOR = {Wang, Yaoguang},\nLANGUAGE = {eng},\nURL = {http://domino.mpi-inf.mpg.de/internet/reports.nsf/NumberView/1997-1-005},\nNUMBER = {MPI-I-1997-1-005},\nINSTITUTION = {Max-Planck-Institut f{\\"u}r Informatik},\nADDRESS = {Saarbr{\\"u}cken},\nYEAR = {1997},\nDATE = {1997},\nABSTRACT = {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.},\nTYPE = {Research Report / Max-Planck-Institut f\xc3\xbcr Informatik},\n}\n'