Efficient primal heuristic updates for the blocking job shop problem

The blocking job shop problem is a variant of the classical job shop problem, where a job continues to block a machine after being serviced, until the downstream machine needed by the job becomes available. Many real world problems have been modeled as blocking job shop problems, and local search heuristics have been shown to produce good quality solutions. Existing literature shows that the computational complexity of these local search algorithms is very high, severely limiting their practical performance. In this work, we present new theoretical results for blocking job shop and show how these results can be used to significantly improve the computational efficiency of existing local search procedures. We empirically evaluate the proposed algorithm updates on existing benchmarks. The results demonstrate that our approach outperforms the current state-of-the-art, by consistently matching or improving previous best known results, usually within a fraction of the time reported for blocking job shop benchmarks. Due to the efficiency in neighborhood computations, our approach scales up to larger size problems than have been considered in prior studies. In particular, for the first time for blocking job shop, we show results for the 100 x 20 instances in Taillard’s benchmark.