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)


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
Issue number1
Publication statusPublished - 1998


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

Cite this