Makespan minimization in preemptive two machine job shops |
| |
| Authors: | S. V. Sevastianov G. J. Woeginger |
| |
| Affiliation: | (1) Institute of Mathematics, Siberian Branch of the Russian Academy of Sciences, Universitetskii pr. 4, 630090 Novosibirsk-90, Russia;(2) Institut für Mathematik, Graz University of Technology, Steyrergasse 30, A-8010 Graz, Austria |
| |
| 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. |
| |
| Keywords: | 68Q25 68C15 90B35 |
| 本文献已被 SpringerLink 等数据库收录！ |
|
