Faster algorithms for single machine scheduling with release dates and rejection

Abstract

We consider the single machine scheduling problem with release dates and job rejection with an objective of minimizing the makespan of the job schedule plus the total rejection penalty of the rejected jobs. Zhang et al. [6] have presented a 2-approximation algorithm with an O(n2) complexity for this problem and an exact algorithm with an O(n3) complexity for the special case with identical job processing times. In this note, we show that the 2-approximation algorithm developed by Zhang et al. [6] can be implemented in O(nlogn) time. We also develop a new exact algorithm with an improved complexity of O(n2logn) for the special case with identical job processing times. The second algorithm can be easily extended to solve the parallel-machine case with the same running time complexity, which answers an open question recently raised by Zhang and Lu [5].