Probabilistic analysis of the minimum weighted flowtime scheduling problem

A. Marchetti Spaccamela, W.S. Rhee, L. Stougie, S.A. van de Geer

    Research output: Contribution to JournalArticleAcademicpeer-review


    The minimum weighted flow time scheduling problem is studied from a probabilistic point of view. A probability distribution is specified over its problem instances, and the asymptotics of the optimal solution value are derived. Rewriting this value as a U-statistic perturbed by a small term allows us to use results from the well-established theory on these statistics. We derive a law of large numbers, a law of the iterated logarithm and a central limit theorem. As a byproduct we obtain a proof of asymptotic optimality almost surely of a greedy heuristic (the shortest weighted processing time first rule) for the solution of the NP-complete problem with more than one machine
    Original languageEnglish
    Pages (from-to)67-71
    JournalOperations Research Letters
    Issue number2
    Publication statusPublished - 1992

    Bibliographical note



    Dive into the research topics of 'Probabilistic analysis of the minimum weighted flowtime scheduling problem'. Together they form a unique fingerprint.

    Cite this