Preemptive Online Scheduling with Reordering
György Dósa, Leah Epstein · SIAM Journal on Discrete Mathematics · 2011
We consider online preemptive scheduling of jobs, arriving one by one, on m identical parallel machines. A buffer of a fixed size $K>0$, which assists in partial reordering of the input, is available to be used for the storage of at most K unscheduled jobs. We study the effect of using a fixed-size buffer (of an arbitrary size) on the supremum competitive ratio over all numbers of machines (the overall competitive ratio), as well as the effect on the competitive ratio as a function of m. We find a tight bound on the competitive ratio for any m. This bound is $\frac{4}{3}$ for even values of m and slightly lower for odd values of m. We show that a buffer of size $\Theta(m)$ is sufficient to achieve this bound, but using $K=o(m)$ does not reduce the best overall competitive ratio that is known for the case without reordering, $\frac{e}{e-1}$. We further consider the semionline variant where jobs arrive sorted by nonincreasing processing time requirements. In this case it turns out to be possible to achieve a competitive ratio of 1. In addition, we find tight bounds as a function of the buffer size and the number of machines for this semionline variant. Related results for nonpreemptive scheduling were recently obtained by Englert, Özmen, and Westermann.