Please use this identifier to cite or link to this item: https://doi.org/10.1109/TAC.2004.825984
Title: Asymptotic performance ratio of an online algorithm for the single machine scheduling with release dates
Authors: Chou, C.-F.M. 
Keywords: Algorithms
Mathematical programming
Scheduling
Issue Date: 2004
Citation: Chou, C.-F.M. (2004). Asymptotic performance ratio of an online algorithm for the single machine scheduling with release dates. IEEE Transactions on Automatic Control 49 (5) : 772-776. ScholarBank@NUS Repository. https://doi.org/10.1109/TAC.2004.825984
Abstract: We analyze the single machine weighted completion time problem with release dates and prove that the asymptotic performance ratio of a simple online algorithm is one. This implies that this algorithm generates a solution whose relative error decreases to zero as the number of jobs increases. Our proof does not require any probabilistic assumption on the job parameters and relies heavily on properties of optimal solutions to a linear programming relaxation of the problem.
Source Title: IEEE Transactions on Automatic Control
URI: http://scholarbank.nus.edu.sg/handle/10635/44045
ISSN: 00189286
DOI: 10.1109/TAC.2004.825984
Appears in Collections:Staff Publications

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

SCOPUSTM   
Citations

4
checked on Aug 10, 2018

WEB OF SCIENCETM
Citations

3
checked on Jul 16, 2018

Page view(s)

52
checked on Jul 27, 2018

Google ScholarTM

Check

Altmetric


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