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, J.B.G. ; Rinnooy Kan, A.H.G. |
Institutions: | Erasmus University Rotterdam, Econometric Institute |
Saved in:
freely available
Extent: | application/pdf |
---|---|
Series: | Econometric Institute Report. - ISSN 1566-7294. |
Type of publication: | Book / Working Paper |
Notes: | The text is part of a series RePEc:dgr:eureir Number 1765011698 |
Source: |
Persistent link: https://www.econbiz.de/10004998898
Saved in favorites
Similar items by person
-
Order statistics and the linear assignment problem
Frenk, J.B.G., (1987)
-
The asymptotic behaviour of a distributive sorting method
Dam, W.B. van, (1983)
-
A probabilistic analysis of the next fit decreasing bin packing heuristic
Csirik, J., (1986)
- More ...