| Article ID: | iaor201530631 |
| Volume: | 116 |
| Issue: | 3 |
| Start Page Number: | 252 |
| End Page Number: | 255 |
| Publication Date: | Mar 2016 |
| Journal: | Information Processing Letters |
| Authors: | Epstein Leah, Zebedat-Haider Hanan |
| Keywords: | manufacturing industries, combinatorial optimization, scheduling |
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.