Optimal algorithms for single-machine scheduling with rejection to minimize the makespan
In this paper we consider the single-machine scheduling problem with rejection. Each job has an arrival time, a processing time and a rejection penalty. The objective is to minimize the sum of the makespan of the accepted jobs and the total rejection penalty of the rejected jobs. First, we present a polynomial-time algorithm for the off-line problem when split is allowed. Second, for the on-line problem with arbitrary arrival times, we provide a determined on-line algorithm with the best-possible competitive ratio 2. Finally, for the on-line problem with at most two distinct arrival times, we provide a determined on-line algorithm with the best-possible competitive ratio .
Year of publication: |
2011
|
---|---|
Authors: | Lu, Lingfa ; Ng, C.T. ; Zhang, Liqi |
Published in: |
International Journal of Production Economics. - Elsevier, ISSN 0925-5273. - Vol. 130.2011, 2, p. 153-158
|
Publisher: |
Elsevier |
Keywords: | Scheduling Rejection penalty On-line algorithm Competitive ratio |
Saved in:
Online Resource
Saved in favorites
Similar items by person
-
Optimal algorithms for single-machine scheduling with rejection to minimize the makespan
Lu, Lingfa, (2011)
-
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)
- More ...