The Taub Faculty of Computer Science Events and Talks

In the online preemptive scheduling problem, a computing system (e.g., a server) receives job processing requests throughout time, each request characterized by an arrival time, deadline, size and value. The goal of the scheduler is to maximize the total value of fully-completed jobs. Job preemption is allowed, i.e., jobs may be paused and resumed from the point at which they were preempted.

In its most general form, the problem admits a polylogarithmic lower bound on the competitive ratio of any randomized algorithm, and no upper bound on the competitive ratio of any deterministic algorithm. Constant competitive ratios are only known for special cases, e.g., when job values are either identical or equal to job sizes; yet, both cases do not encompass realistic settings. A natural goal, then, is to develop constant-factor approximations under reasonable assumptions that hold in practice for realistic input pro?les.

We circumvent known lower bounds for this problem by assuming that the input has slack, meaning that any job could be delayed and still ?nish by its deadline. Under the slackness assumption, we design a deterministic preemptive scheduler with a constant-factor worst-case performance guarantee. Along the way, we pay close attention to practical aspects, such as runtime e?ciency, data locality, demand uncertainty, provider commitments and user truthfulness.