Efficient parallel tabu search for the blocking job shop scheduling problem

The Blocking Job Shop Scheduling (BJSS) is an NP-hard scheduling problem. It is obtained from the classical job shop scheduling problem by replacing the infinite buffer capacity constraint by a zero buffer capacity which introduces the blocking constraint. This constraint affects deeply the ability of meta-heuristics to find good solutions due to the low ratio of feasible to explored solutions. In this paper, we discuss the parallelization of the Tabu Search algorithm (TS) which represents one of the most widely used heuristics. Applying the classical TS neighborhood to the BJSS problem produces infeasible solutions in 98% of cases which leads to waste a valuable time in exploring infeasible solutions. For this reason, the use of a feasibility recovery strategy is unavoidable; however, the recovery step slows down considerably the TS algorithm. Therefore, incurring a huge time to explore a small area in the search space. To overcome this drawback and to accelerate the TS algorithm, we propose in this paper parallel multi-start TS approaches where several processes explore simultaneously the search space. Our parallelization exploits a cluster-based architecture with 512 CPU-cores. The obtained results show the positive impact of our proposed parallelization on the solution quality. Moreover, combining both the parallelism and the recovery strategy allowed us to improve the best result in the literature for a large number of known benchmarks.