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 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 to that 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 uniformly related machines, where the machine 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; and (4) Several upper and lower bounds for variations on these models.
Document Details
- Document Type
- Technical Report
- Publication Date
- Nov 01, 1990
- Accession Number
- ADA230070
Entities
People
- David P. Williamson
- Joel Wein
Organizations
- Massachusetts Institute of Technology