Complexity of machine scheduling problems

J.K. Lenstra, A.H.G. Rinnooy Kan, P. Brucker

    Research output: Contribution to journalArticleAcademicpeer-review

    1628 Citations (Scopus)
    30 Downloads (Pure)


    We survey and extend the results on the complexity of machine scheduling problems. After a brief review of the central concept of NP-completeness we give a classification of scheduling problems on single, different and identical machines and study the influence of various parameters on their complexity. The problems for which a polynomial-bounded algorithm is available are listed and NP-completeness is established for a large number of other machine scheduling problems. We finally discuss some questions that remain unanswered.
    Original languageEnglish
    Pages (from-to)343-362
    JournalAnnals of Discrete Mathematics
    Publication statusPublished - 1977


    Dive into the research topics of 'Complexity of machine scheduling problems'. Together they form a unique fingerprint.

    Cite this