The rate of convergence to optimality of the LPT rule (Q1087469)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | The rate of convergence to optimality of the LPT rule |
scientific article |
Statements
The rate of convergence to optimality of the LPT rule (English)
0 references
1986
0 references
The problem in which each of n jobs is to be processed on one of m uniform parallel machines is considered. The objective is to minimize the maximum completion time. The LPT rule is a heuristic method where jobs are assigned to the first available machine in non-increasing order of processing times. If processing times are independent identically distributed random variables, then (under a mild condition on the distribution) the absolute deviation of the maximum completion time of the heuristic schedule from the optimum is known to converge to 0 almost surely. The asymptotic behaviour of the absolute deviation is analyzed, and its first and higher moments show that under quite general assumptions the speed of convergence is proportional to appropriate powers of (log log n)/n and 1/n respectively.
0 references
probabilistic analysis
0 references
uniform parallel machines
0 references
maximum completion time
0 references
heuristic method
0 references
asymptotic behaviour
0 references
speed of convergence
0 references