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.
Collections
Rights
Date
2004
DOI
10.1109/TAC.2004.825984
Type
Article