On the rate of convergence to optimality of the LPT rule

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

    Research output: Book/ReportReportAcademic

    54 Downloads (Pure)


    The LPT rule is a heuristic method to distribute jobs among identical machines so as to minimize the makes pan 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 show that the speed of convergence is proportional to logn/n, thus extending earlier results obtained for the uniform and exponential distribution.
    Original languageEnglish
    Place of PublicationEindhoven
    PublisherTechnische Hogeschool Eindhoven
    Number of pages8
    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