Bicriteria job sequencing with release dates

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.