Minimizing makespan in no-wait job shops

N. Bansal, M. Mahdian, M. Sviridenko

    Research output: Contribution to journalArticleAcademicpeer-review

    24 Citations (Scopus)
    1 Downloads (Pure)

    Abstract

    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
    Volume30
    Issue number4
    DOIs
    Publication statusPublished - 2005

    Fingerprint

    No-wait
    Job Shop
    Polynomials
    Polynomial Time Approximation Scheme
    Job Shop Scheduling Problem
    Objective function
    Job shop scheduling
    Makespan
    Job shop
    Approximation
    Factors

    Cite this

    Bansal, N. ; Mahdian, M. ; Sviridenko, M. / Minimizing makespan in no-wait job shops. In: Mathematics of Operations Research. 2005 ; Vol. 30, No. 4. pp. 817-831.
    @article{4373c8372bc44a3b954eb2071b2ac423,
    title = "Minimizing makespan in no-wait job shops",
    abstract = "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.",
    author = "N. Bansal and M. Mahdian and M. Sviridenko",
    year = "2005",
    doi = "10.1287/moor.1050.0155",
    language = "English",
    volume = "30",
    pages = "817--831",
    journal = "Mathematics of Operations Research",
    issn = "0364-765X",
    publisher = "INFORMS Institute for Operations Research and the Management Sciences",
    number = "4",

    }

    Minimizing makespan in no-wait job shops. / Bansal, N.; Mahdian, M.; Sviridenko, M.

    In: Mathematics of Operations Research, Vol. 30, No. 4, 2005, p. 817-831.

    Research output: Contribution to journalArticleAcademicpeer-review

    TY - JOUR

    T1 - Minimizing makespan in no-wait job shops

    AU - Bansal, N.

    AU - Mahdian, M.

    AU - Sviridenko, M.

    PY - 2005

    Y1 - 2005

    N2 - 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.

    AB - 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.

    U2 - 10.1287/moor.1050.0155

    DO - 10.1287/moor.1050.0155

    M3 - Article

    VL - 30

    SP - 817

    EP - 831

    JO - Mathematics of Operations Research

    JF - Mathematics of Operations Research

    SN - 0364-765X

    IS - 4

    ER -