# 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.