Necessary and Sufficient Conditions for Feasible Neighbourhood Solutions in the Local Search of the Job-Shop Scheduling Problem

Abstract The meta-heuristic algorithm with local search is an excellent choice for the job-shop scheduling problem (JSP). However, due to the unique nature of the JSP, local search may generate infeasible neighbourhood solutions. In the existing literature, although some domain knowledge of the JSP can be used to avoid infeasible solutions, the constraint conditions in this domain knowledge are sufficient but not necessary. It may lose many feasible solutions and make the local search inadequate. By analysing the causes of infeasible neighbourhood solutions, this paper further explores the domain knowledge contained in the JSP and proposes the sufficient and necessary constraint conditions to find all feasible neighbourhood solutions, allowing the local search to be carried out thoroughly. With the proposed conditions, a new neighbourhood structure is designed in this paper. Then, a fast calculation method for all feasible neighbourhood solutions is provided, significantly reducing the calculation time compared with ordinary methods. A set of standard benchmark instances is used to evaluate the performance of the proposed neighbourhood structure and calculation method. The experimental results show that the calculation method is effective, and the new neighbourhood structure has more reliability and superiority than the other famous and influential neighbourhood structures, where 90% of the results are the best compared with three other well-known neighbourhood structures. Finally, the result from a tabu search algorithm with the new neighbourhood structure is compared with the current best results, demonstrating the superiority of the proposed neighbourhood structure.