Accession Number:

ADA230070

Title:

On-Line Scheduling of Parallel Machines

Descriptive Note:

Technical rept.

Corporate Author:

MASSACHUSETTS INST OF TECH CAMBRIDGE LAB FOR COMPUTER SCIENCE

Personal Author(s):

• Wein, Joel
• Williamson, David P.

Report Date:

1990-11-01

Pagination or Media Count:

19.0

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.

Descriptors:

• *REQUIREMENTS
• JOBS
• COMPETITION
• DETERMINANTS(MATHEMATICS)
• PARALLEL PROCESSORS
• SCHEDULING
• ONLINE SYSTEMS
• RATIONS
• RATIOS
• PROCESSING

Subject Categories:

• Operations Research
• Computer Hardware

Distribution Statement:

APPROVED FOR PUBLIC RELEASE