MAKESPAN MINIMIZATION IN PREEMPTIVE 2 MACHINE JOB SHOPS

Authors
SEVASTIANOV SV WOEGINGER GJ
Citation
Sv. Sevastianov et Gj. Woeginger, MAKESPAN MINIMIZATION IN PREEMPTIVE 2 MACHINE JOB SHOPS, Computing, 60(1), 1998, pp. 73-79
Citations number
10
Categorie Soggetti
Computer Science Theory & Methods","Computer Science Theory & Methods
Journal title
Computing → ACNP
ISSN journal
0010485X
Volume
60
Issue
1
Year of publication
1998
Pages
73 - 79
Database
ISI
SICI code
0010-485X(1998)60:1<73:MMIP2M>2.0.ZU;2-6
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 probl em, and we also argue that this is the best possible result that can b e derived via our line of approach.