Makespan minimization in preemptive two machine job shops

S.V. Sevastianov, G.J. Woeginger

    Research output: Contribution to journalArticleAcademicpeer-review

    11 Citations (Scopus)
    1 Downloads (Pure)

    Abstract

    In this note we investigate the NP-complete problem of minimizing the makespan in a preemptive two machine job shop. We present a polynomial time approximation algorithm with worst case ratio 3/2 for this problem, and we also argue that this is the best possible result that can be derived via our line of approach.
    Original languageEnglish
    Pages (from-to)73-79
    Number of pages7
    JournalComputing
    Volume60
    Issue number1
    DOIs
    Publication statusPublished - 1998

    Fingerprint

    Dive into the research topics of 'Makespan minimization in preemptive two machine job shops'. Together they form a unique fingerprint.

    Cite this