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.