A linear time approximation scheme for the job shop scheduling problem

We study the preemptive and non-preemptive versions of the job shop scheduling pr oblem when the number of machines and the number of operations per job are fixed. We present linear time approximation schemes for both problems. These algorithms are the best possible for such problems in two regards: they achieve the best po ssible performance ratio since both problems are known to be strongly NP-hard; an d they have optimum asymptotic time complexity