A hierarchical scheduling problem with a well-solvable second stage

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

    Research output: Contribution to JournalArticleAcademicpeer-review


    In the hierarchical scheduling model to be considered, the decision at the aggregate level to acquire a number of identical machines has to be based on probabilistic information about the jobs that have to be scheduled on these machines at the detailed level. The objective is to minimize the sum of the acquisition costs and the expected average completion time of the jobs. In contrast to previous models of this type, the second part of this objective function corresponds to a well-solvable scheduling problem that can be solved to optimality by a simple priority rule. A heuristic method to solve the entire problem is described, for which strong asymptotic optimality results can be established
    Original languageEnglish
    Pages (from-to)43-58
    JournalAnnals of Operations Research
    Issue number1
    Publication statusPublished - 1984

    Bibliographical note



    Dive into the research topics of 'A hierarchical scheduling problem with a well-solvable second stage'. Together they form a unique fingerprint.

    Cite this