# ICS 269, Spring 1997: Theory Seminar

## 14 November 1997:

Better Bounds for Online Scheduling

Joseph Wang, ICS, UC Irvine

A sequence of jobs must be scheduled on m identical parallel
machines. As each job arrives, its processing time is known. The
goal is to minimize the makespan. Bartal, Fiat, Karloff and Vohra
gave a deterministic online algorithm that is 1.986-competitive.
Karger, Phillips and Torng generalized the algorithm and proved an
upper bound of 1.945. The best lower bound currently known on the
competitive ratio that can be achieved by deterministic online
algorithms is equal to 1.837. In this paper we present an improved
deterministic online scheduling algorithm that is
1.923-competitive, for all m >= 2. The algorithm is based on a
new scheduling strategy, i.e., it is not a generalization of the
approach by Bartal et al. Also, the algorithm has a simple
structure. Furthermore, we develop a better lower bound. We prove
that, for general m, no deterministic online scheduling algorithm
can be bettern than 1.852-competitive.

(From a STOC '97 paper by Susanne Albers)