.png){kind=icon}
.png){kind=icon}
Return
Single machine scheduling with release dates and rejection
.png){kind=icon}
PRE
AI
DOI：10.1016/j.ejor.2008.10.006.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
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.
Keywords:
Scheduling
Rejection penalty
Fully polynomial-time approximation scheme
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
IF:
6
Papers:
2.2W
Citations:
6.4W