Please use this identifier to cite or link to this item: https://doi.org/10.1007/s10107-005-0588-1
Title: The asymptotic performance ratio of an on-line algorithm for uniform parallel machine scheduling with release dates
Authors: Chou, M.C. 
Queyranne, M.
Simchi-Levi, D.
Keywords: Analysis of Heuristics
Asymptotic Performance Ratio
On-line algorithms
Scheduling
Issue Date: 2006
Source: Chou, M.C., Queyranne, M., Simchi-Levi, D. (2006). The asymptotic performance ratio of an on-line algorithm for uniform parallel machine scheduling with release dates. Mathematical Programming 106 (1) : 137-157. ScholarBank@NUS Repository. https://doi.org/10.1007/s10107-005-0588-1
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.
Source Title: Mathematical Programming
URI: http://scholarbank.nus.edu.sg/handle/10635/44065
ISSN: 00255610
DOI: 10.1007/s10107-005-0588-1
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

SCOPUSTM   
Citations

20
checked on Dec 7, 2017

WEB OF SCIENCETM
Citations

17
checked on Nov 23, 2017

Page view(s)

40
checked on Dec 11, 2017

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.