Single machine scheduling with release dates and rejection

In this paper, we consider the single machine scheduling problem with release dates and rejection. A job is either rejected. in which case a rejection penalty has to be paid, or accepted and processed on the machine. The objective is to minimize the sum of the makespan of the accepted jobs and the total rejection penalty of the rejected jobs. We show that the problem is NP-hard in the ordinary sense. Then we provide two pseudo-polynomial-time algorithms. Consequently, two special cases can be solved in polynomial-time. Finally, a 2-approximation algorithm and a fully polynomial-time approximation scheme are given for the problem. (C) 2008 Published by Elsevier B.V.