Faster algorithms for single machine scheduling with release dates and rejection

Jinwen Ou, Xueling Zhong, Chung Lun Li

Research output: Journal article publicationJournal articleAcademic researchpeer-review

13 Citations (Scopus)


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].
Original languageEnglish
Pages (from-to)503-507
Number of pages5
JournalInformation Processing Letters
Issue number8
Publication statusPublished - 1 Aug 2016


  • Algorithms
  • Rejection penalty
  • Release dates
  • Scheduling
  • Worst-case analysis

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Signal Processing
  • Information Systems
  • Computer Science Applications

Cite this