Scheduling Seminar: The Benefit of Preemption


Datum / čas
Date(s) - 29.09.
15:00 - 17:00

Kategorie ne Kategorie

Leah Epstein (University of Haifa): The Benefit of Preemption

Abstract: Given an input of a scheduling problem, any non-preemptive solution for it can be used as a preemptive solution. Thus, the optimal cost of a preemptive solution is not larger than that of an optimal non-preemptive solution. As preemption comes at a cost in real-life applications, it is of interest to find the worst-case ratio between the two costs. For a given problem, the supremum ratio over all possible inputs of the ratio between the two costs (of an optimal solution without preemption and an optimal solution that possibly uses preemption) is called the power or benefit of preemption. While many scheduling variants can be studied with respect to this measure, we will focus on the cases of a single machine, parallel identical machines, and uniformly related machines, and we will discuss the objectives of makespan and total (weighted) completion time. We will exhibit how one can benefit from preemption, and we will analyze the resulting worst case ratios for several basic models.

Watch online:

More information: