ICS Theory Group

ICS 269, Fall 2004: Theory Seminar

5 Nov 2004:
Online Scheduling of Equal-Length Jobs:
Randomization and Restarts Help

Speaker: Marek Chrobak
(Department of Computer Science, University of California, Riverside, CA 92521)

We consider the following scheduling problem. The input is a set of jobs with equal processing times, where each job is specified by its release time and deadline. The goal is to determine a single-processor, non-preemptive schedule that maximizes the number of completed jobs. In the online version, each job arrives at its release time. We give two online algorithms with competitive ratios below 2 and show several lower bounds on the competitive ratios.

First, we give a barely random 5/3-competitive algorithm that uses only one random bit. We also show a lower bound of 3/2 for barely random algorithms that choose one of two deterministic algorithms.

Second, we give a deterministic 3/2-competitive algorithm in the model that allows restarts, and we show that in this model the ratio 3/2 is optimal. For randomized algorithms with restarts we show a lower bound of 6/5.

This is joint work with W.Jawor, J.Sgall, and T.Tichy.