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.
Year of publication: |
2009
|
---|---|
Authors: | Zhang, Liqi ; Lu, Lingfa ; Yuan, Jinjiang |
Published in: |
European Journal of Operational Research. - Elsevier, ISSN 0377-2217. - Vol. 198.2009, 3, p. 975-978
|
Publisher: |
Elsevier |
Keywords: | Scheduling Rejection penalty Fully polynomial-time approximation scheme |
Saved in:
Online Resource
Saved in favorites
Similar items by person
-
Bounded single-machine parallel-batch scheduling with release dates and rejection
Lu, Lingfa, (2009)
-
Single machine scheduling with release dates and rejection
Zhang, Liqi, (2009)
-
Two-machine open-shop scheduling with rejection to minimize the makespan
Zhang, Liqi, (2016)
- More ...