The asymptotic performance ratio of an on-line algorithm for uniform parallel machine scheduling with release dates |
| |
Authors: | Mabel C Chou Maurice Queyranne David Simchi-Levi |
| |
Institution: | (1) Dept. of Decision Sciences, National University of Singapore, Singapore;(2) Faculty of Commerce and Business Administration, University of British Columbia, Canada;(3) Dept. of Civil and Environmental Engineering, Massachusetts Institute of Technology, USA |
| |
Abstract: | Jobs arriving over time must be non-preemptively processed on one of m parallel machines, each running at its own speed, so as to minimize a weighted sum of the job completion times. In this on-line
environment, the processing requirement and weight of a job are not known before the job arrives. The Weighted Shortest Processing
Requirement (WSPR) heuristic is a simple extension of the well known WSPT heuristic, which is optimal for the single machine
problem without release dates. According to WSPR, whenever a machine completes a job, the next job assigned to it is the one
with the least ratio of processing requirement to weight among all jobs available for processing at this point in time. We
analyze the performance of this heuristic and prove that its asymptotic competitive ratio is one for all instances with bounded job processing requirements and weights. This implies that the WSPR algorithm generates a
solution whose relative error approaches zero as the number of jobs increases. Our proof does not require any probabilistic
assumption on the job parameters and relies extensively on properties of optimal solutions to a single machine relaxation
of the problem.
Research supported in part by ONR Contracts N00014-90-J-1649 and N00014-95-1-0232, NSF Contracts DDM-9322828, DMI-9732795,
DMI-0085683 and DMI-0245352, NUS Academic Research Grant R314-000-046-112, and a research grant from the Natural Sciences
and Research Council of Canada (NSERC). |
| |
Keywords: | Scheduling Asymptotic Performance Ratio On-line algorithms Analysis of Heuristics |
本文献已被 SpringerLink 等数据库收录! |
|