Publication

Asymptotic performance ratio of an online algorithm for the single machine scheduling with release dates

Citations
Altmetric:
Alternative Title
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.
Keywords
Algorithms, Mathematical programming, Scheduling
Source Title
IEEE Transactions on Automatic Control
Publisher
Series/Report No.
Organizational Units
Organizational Unit
DECISION SCIENCES
dept
Rights
Date
2004
DOI
10.1109/TAC.2004.825984
Type
Article
Related Datasets
Related Publications