Online scheduling of unit jobs on three machines with rejection: A tight result

• 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.