On-line Scheduling of Parallel Machines

Abstract

We study the problem of scheduling jobs on parallel machines in an on-line fashion, where the processing requirement of a job is not known until the job is completed. Despite this lack of knowledge of the future, we wish to schedule so as to minimize the completion time of the entire set of jobs. In general, the performance of an on-line algorithm is measured by its competitive ratio: the worst case ratio of its performance of an optimal algorithm with total prior knowledge. We study two fundamental models for this problem, that of identical machines, where all the machines run at the same speed, and uniformaly related machines, where the machines run at different speeds. Our results include: 1) Matching upper and lower bounds on the competitive ratio for the case of identical machines. 2) Upper and lower bounds that differ by a constant factor for uniformly related machines. 3) A lower bound for randomized algorithms for identical machines that nearly matches the deterministic upper bound. 4) Several upper and lower bounds for variations on these models.