Online Multiprocessor Scheduling

Steve Seiden
Technische Universität Graz
Institut für Mathematik B
Graz, Austria

Optimization problems are at the very heart of computer science. Given a problem and a cost function over the set of possible solutions, our goal as computer scientists is to find an algorithm which produces an optimal or near-optimal cost solution. We call such algorithms optimization algorithms. An online algorithm is an optimization algorithm which works under the handicap of an uncertain future. The problem is revealed to the algorithm incrementally, and the algorithm's solution must be produced incrementally. Many fundamental problems arising in computer science are online. In order to contrast them with online algorithms, algorithms which are not restricted in this way are called offline algorithms.

In competitive analysis, the cost of an online algorithm's solution is compared to the cost of the optimal offline solution. The measure of performance used is the competitive ratio. An online algorithm for a given problem is said to be c-competitive if for all problem instances the cost of the algorithm's solution is at most c times the cost of the optimal solution on that same problem instance.

This talk focuses on online scheduling, in which jobs must be scheduled without the knowledge of jobs which will arrive in the future. Three problems are examined.

The first is the scheduling of 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 discuss a randomized algorithm for , and outline a proof of its competitiveness. This algorithm is the first randomized algorithm for , and provides the best known competitive ratios for .

The second is the scheduling of independent jobs on m machines when rejection is allowed. I discuss the first randomized algorithms for this problem, and outline the analysis of one of these algorithms.

The third is the preemptive scheduling of independent jobs on m machines with rejection. I briefly describe the first deterministic and randomized algorithms for this problem.

Philip Chan,
Last modified: Tue Apr 7 13:31:07 EDT 1998