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
    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

    Identifiers