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.
Introduction
The Job-Shop Scheduling Problem (JSP) is a classic NP-complete optimization challenge where $n$ jobs must be processed on $m$ machines in a predefined sequence to minimize the makespan. Local search algorithms are frequently employed to solve JSP by iteratively exploring "neighborhoods"—sets of schedules reachable by small modifications, such as swapping the order of operations on a machine.
A significant hurdle in JSP local search is the generation of infeasible schedules. A simple swap can introduce circular dependencies, creating a cycle in the schedule's precedence graph. Historically, researchers relied on "sufficient" conditions to avoid these cycles. While safe, these conditions are overly restrictive, often pruning valid, high-quality solutions from the search space. This paper identifies the "necessary and sufficient" conditions for feasibility, enabling a more exhaustive search.
Methodology: The Disjunctive Graph and NNS
The research utilizes the Disjunctive Graph model to represent JSP. In this model, nodes represent operations, directed edges represent job sequences, and undirected (disjunctive) edges represent potential machine processing orders.
Necessary and Sufficient Conditions
The authors mathematically proved that a neighborhood move (swapping operations) is infeasible if and only if it creates a cycle. By focusing on path existence between operations rather than just numerical processing times, they established the exact boundary for feasibility.
New Neighbourhood Structure (NNS)
Based on these proofs, the authors developed the New Neighbourhood Structure (NNS). Unlike established structures like N5, N6, or N7, which use restrictive numerical heuristics, NNS employs path-based logic to evaluate every possible feasible move.
To handle the computational overhead of path detection in large graphs, the authors introduced a Fast Calculation Method. This "mixed method" combines simple numerical checks with targeted graph searches, maintaining competitive execution speeds even when exploring a significantly larger solution space.
Experimental Evaluation
The NNS was evaluated against 152 standard benchmark instances, including LA, TA, ORB, and FT sets. These datasets are widely recognized in the scheduling community and are publicly available.
Key Findings
- Search Depth: NNS consistently finds more feasible neighbors than traditional methods. For large-scale "tall" problems (high job-to-machine ratio), NNS generated over 20 times more feasible solutions per iteration than the N5 structure.
- Performance: The NNS structure achieved the best results in 90% of the tested cases compared to N5, N6, and N7.
- Efficiency: The Fast Calculation Method successfully mitigated the complexity of exhaustive feasibility checking, making the thorough search practical for large $100 \times 20$ problems.
Conclusion
By defining the necessary and sufficient conditions for feasibility in JSP, this work removes artificial constraints that have limited local search algorithms for decades. The resulting NNS structure provides a more reliable and superior search mechanism. Future work will focus on "clipping" strategies to filter out feasible but non-improving moves and extending these conditions to Flexible Job-Shop Scheduling (FJSP).
Reference: Gui, L., Li, X., Gao, L. et al. Necessary and Sufficient Conditions for Feasible Neighbourhood Solutions in the Local Search of the Job-Shop Scheduling Problem. Chin. J. Mech. Eng. 36, 87 (2023). https://doi.org/10.1186/s10033-023-00911-8
Summary updated