(Acyclic) Job Shops are Hard to Approximate

For every euro > 0, we show that the (acyclic) job shop problem cannot be approximated within ratio O(log^1+euro lb), unless NP has quasi-polynomial Las-Vegas algorithms, and where lb denotes a trivial lower bound on the optimal value. This almost matches the best known results for acyclic job shops, since an O(log^1+euro lb)-approximate solution can be obtained in polynomial time for every euro > 0. Recently, a PTAS was given for the job shop problem, where the number of machines and the number of operations per job are assumed to be constant. Under P ne NP, and when the number mu of operations per job is a constant, we provide an inapproximability result whose value grows with mu to infinity. Moreover, we show that the problem with two machines and the preemptive variant with three machines have no PTAS, unless NP has quasi-polynomial algorithms. These results show that the restrictions on the number of machines and operations per job are necessary to obtain a PTAS.In summary, the presented results close many gaps in our understanding of the hardness of the job shop problem and resolve (negatively) several open problems in the literature.