Jonathan Yaniv (CS, Technion)
Wednesday, 10.4.2013, 12:30
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
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.