Optimal job insertion in the no‐wait job shop

The no‐wait job shop (NWJS) considered here is a version of the job shop scheduling problem where, for any two operations of a job, a fixed time lag between their starting times is given. Also, sequence‐dependent set‐up times between consecutive operations on a machine can be present. The NWJS problem consists in finding a schedule that minimizes the makespan. We address here the so‐called optimal job insertion problem (OJI) in the NWJS. While the OJI is NP‐hard in the classical job shop, it was shown by Gröflin & Klinkert to be solvable in polynomial time in the NWJS. We present a highly efficient algorithm with running time $𝒪(n^2\cdot \max \{n,m\})$ for this problem. The algorithm is based on a compact formulation of the NWJS problem and a characterization of all feasible insertions as the stable sets (of prescribed cardinality) in a derived comparability graph. As an application of our algorithm, we propose a heuristic for the NWJS problem based on optimal job insertion and present numerical results that compare favorably with current benchmarks.