Minimizing makespan in no-wait job shops

N. Bansal, M. Mahdian, M. Sviridenko

    Research output: Contribution to journalArticleAcademicpeer-review

    28 Citations (Scopus)
    1 Downloads (Pure)


    In this paper, we study polynomial time approximation schemes (PTASes) for the no-wait job shop scheduling problem with the makespan objective function. It is known that the problem is MaxSNP-hard in the case when each job is allowed to have three operations or more. We show that if each job has at most two operations, the problem admits a PTAS if the number of machines is a constant (i.e., not part of the input). If the number of machines is not a constant, we show that the problem is hard to approximate within a factor better than 5/4.
    Original languageEnglish
    Pages (from-to)817-831
    JournalMathematics of Operations Research
    Issue number4
    Publication statusPublished - 2005


    Dive into the research topics of 'Minimizing makespan in no-wait job shops'. Together they form a unique fingerprint.

    Cite this