Makespan Minimization in Preemptive Two Machine Job Shops

摘要

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 results that can be derived via our line of approach.