On the rate of convergence to optimality of the LPT rule

J.B.G. Frenk, A.H.G. Rinnooy Kan

    Research output: Book/ReportReportAcademic

    64 Downloads (Pure)


    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 strengthen and extend earlier results obtained for the uniform and exponential distribution.
    Original languageEnglish
    Place of PublicationEindhoven
    PublisherTechnische Hogeschool Eindhoven
    Number of pages12
    Publication statusPublished - 1985

    Publication series

    NameMemorandum COSOR
    ISSN (Print)0926-4493


    Dive into the research topics of 'On the rate of convergence to optimality of the LPT rule'. Together they form a unique fingerprint.

    Cite this