Online Scheduling

scheduled without the knowledge of jobs which will arrive in
the future. I discuss several different scheduling problems on
which I have worked.

I then go into more detail on the problem of scheduling
independent jobs on $m$ machines, considered to be a
classical problem in computer science. While the deterministic
case of this problem has been studied extensively, starting
with Graham in 1966, little work has been done on the randomized
case. For $m= 2$, a randomized $4/3$-competitive algorithm was
found by Bartal, Fiat, Karloff and Vohra. In this talk, I
present a randomized algorithm for $m \geq 3$, and outline a
proof of its competitiveness. This algorithm is the first
randomized algorithm for $m \geq 3$, and provides the best
known competitive ratios for $m=3, \ldots, 7$.