The asymptotic optimality of the LPT rule

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

    Research output: Book/ReportReportAcademic

    95 Downloads (Pure)


    For the problem of minimizing makes pan on parallel machines of different speed, the behaviour of list scheduling rules is subjected to a probabilistic analysis under the assumption that the processing requirements of the jobs are independent, identically distributed nonnegative random variables. Under mild conditions on the probability distribution, we obtain strong asymptotic optimality results for arbitrary list scheduling and even stronger ones for the LPT (Longest Processing Time) rule, in which the jobs are assigned to the machines in order of nonincreasing processing requirements. Keywords: scheduling, parallel machines, list scheduling, LPT rule, probabilistic analysis, asymptotic optimality.
    Original languageEnglish
    Place of PublicationEindhoven
    PublisherTechnische Hogeschool Eindhoven
    Number of pages27
    Publication statusPublished - 1985

    Publication series

    NameMemorandum COSOR
    ISSN (Print)0926-4493


    Dive into the research topics of 'The asymptotic optimality of the LPT rule'. Together they form a unique fingerprint.

    Cite this