Back to Search
Start Over
Single-machine scheduling under the job rejection constraint
- Source :
-
Theoretical Computer Science . Mar2010, Vol. 411 Issue 16-18, p1877-1882. 6p. - Publication Year :
- 2010
-
Abstract
- Abstract: In this paper, we consider single-machine scheduling problems under the job rejection constraint. A job is either rejected, in which case a rejection penalty has to be paid, or accepted and processed on the single machine. However, the total rejection penalty of the rejected jobs cannot exceed a given upper bound. The objective is to find a schedule such that a given criterion is minimized, where is a non-decreasing function on the completion times of the accepted jobs. We analyze the computational complexities of the problems for distinct objective functions and present pseudo-polynomial-time algorithms. In addition, we provide a fully polynomial-time approximation scheme for the makespan problem with release dates. For other objective functions related to due dates, we point out that there is no approximation algorithm with a bounded approximation ratio. [Copyright &y& Elsevier]
Details
- Language :
- English
- ISSN :
- 03043975
- Volume :
- 411
- Issue :
- 16-18
- Database :
- Academic Search Index
- Journal :
- Theoretical Computer Science
- Publication Type :
- Academic Journal
- Accession number :
- 48605660
- Full Text :
- https://doi.org/10.1016/j.tcs.2010.02.006