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]. © 2016 Elsevier B.V. All rights reserved.
| Original language | English |
|---|---|
| Pages (from-to) | 503-507 |
| Journal | Information Processing Letters |
| Volume | 116 |
| Issue number | 8 |
| DOIs | |
| Publication status | Published - 1 Aug 2016 |
| Externally published | Yes |
Bibliographical note
Publication details (e.g. title, author(s), publication statuses and dates) are captured on an “AS IS” and “AS AVAILABLE” basis at the time of record harvesting from the data source. Suggestions for further amendments or supplementary information can be sent to [email protected].Research Keywords
- Algorithms
- Rejection penalty
- Release dates
- Scheduling
- Worst-case analysis