The rate of convergence to optimality of the LPT rule
The LPT rule is a heuristic method to distribute jobs among identical machines so as to minimize the makespan of the resulting schedule. If the processing times of the jobs are assumed to be independent identically distributed random variables, then (under a mild condition on the distribution) the absolute error of this heuristic is known to converge to 0 almost surely. In this note we analyse the asymptotic behaviour of the absolute error and its first and higher moments to show that under quite general assumptions the speed of convergence is proportional to appropriate powers of (log log n)/n and 1/n. Thus, we simplify, strengthen and extend earlier results obtained for the uniform and exponential distribution.
Year of publication: |
1986-06-01
|
---|---|
Authors: | Frenk, Frenk, J.B.G. ; Rinnooy Kan, Rinnooy Kan, A.H.G. |
Institutions: | Faculteit der Economische Wetenschappen, Erasmus Universiteit Rotterdam |
Saved in:
freely available
Extent: | application/pdf |
---|---|
Series: | Econometric Institute Research Papers. - ISSN 1566-7294. |
Type of publication: | Book / Working Paper |
Notes: | The text is part of a series RePEc:ems:eureir |
Source: |
Persistent link: https://www.econbiz.de/10010731926
Saved in favorites
Similar items by person
-
Probabilistic analysis of algorithms for dual bin packing problems
Csirik, J., (1991)
-
A probabilistic analysis of the next fit decreasing bin packing heuristic
Csirik, J., (1986)
-
Order statistics and the linear assignment problem
Frenk, Frenk, J.B.G., (1987)
- More ...