| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 427068 | Information Processing Letters | 2016 | 4 Pages |
Abstract
•An algorithm with the best possible competitive ratio.•An algorithm that defines its own parameter.•One algorithm for the preemptive and the non-preemptive variants.
We design an algorithm of the best possible competitive ratio for preemptive and non-preemptive scheduling of unit size jobs with rejection on three identical machines. The algorithm does not use preemption even for the preemptive variant, and it has the interesting feature that one of its parameters is not fixed in advance, and it is defined based on the properties of the first input job having a sufficiently large rejection penalty.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Leah Epstein, Hanan Zebedat-Haider,