A new neighborhood structure for job shop scheduling problems

Jin Xie, Xinyu Li, Liang Gao, Lin GuiarXiv 2021 · arXiv

Introduction

The Job Shop Scheduling Problem (JSP) is a fundamental challenge in operations research and industrial engineering. It involves scheduling $n$ jobs across $m$ machines to minimize the total time taken, known as the makespan. Each job consists of a specific sequence of operations that must be performed on designated machines. Because JSP is NP-complete, finding optimal solutions for large-scale instances is computationally intensive, leading researchers to rely on meta-heuristics like Tabu Search.

To navigate the vast solution space of possible schedules, these algorithms use "neighborhood structures"—rules that define how to make small, iterative tweaks to a schedule. For decades, structures known as N5, N6, and N7 have been the industry standard. However, these traditional methods are often conservative, focusing only on moving "critical operations" within their immediate "critical blocks" (sequences of operations on the same machine that lie on the critical path).

A disjunctive graph representation showing the critical path (highlighted in pink) which determines the makespan.

The N8 Neighborhood Structure

This research introduces a novel neighborhood structure called N8, designed to overcome the limitations of local-only optimization. The core innovation of N8 is its ability to move an "inner" operation of a critical block to positions outside that block—specifically, before the first operation or after the last operation of the sequence on a given machine.

By allowing operations to "jump" over block boundaries, the N8 structure significantly expands the search space, enabling the algorithm to resolve complex bottlenecks that traditional local swaps cannot address.

The N8 structure allows inner operations to be moved to the beginning or end of a critical block, expanding the search space beyond traditional local moves.

Neighborhood Clipping and Efficiency

Expanding the search space typically results in slower computation. To maintain high performance, the authors developed a Neighborhood Clipping method. This approach is grounded in four mathematical propositions that identify moves guaranteed not to reduce the makespan. By pruning these "useless" moves before they are even calculated, the search remains efficient.

This logic was integrated into a Tabu Search framework (TS-N8) that utilizes a dynamic tabu list to prevent the search from falling into repetitive loops or local optima.

Experimental Results

The TS-N8 algorithm was rigorously tested against 110 well-known benchmark instances, including the classic FT10, Lawrence’s LA01–40, and the highly challenging Taillard (TA) sets.

Key findings include:

  • Superior Accuracy: TS-N8 achieved a lower Mean Relative Error (MRE) across nearly all benchmarks. On the difficult Taillard instances, N8 reached an MRE of 1.28%, outperforming N5 (1.74%) and N6 (1.67%).
  • New Benchmarks: The algorithm discovered improved solutions for several famous hard instances, such as LA29, LA40, and ABZ8.
  • Computational Speed: Despite the larger neighborhood, the clipping method ensured that TS-N8 was often faster than the previous state-of-the-art N7 structure. For example, on the SWV12 instance, TS-N8 found a superior solution in approximately half the time required by TS-N7.

Conclusion and Future Directions

The N8 neighborhood structure represents a significant advancement in JSP solving, proving that strategic "global" moves can outperform strictly local ones when paired with rigorous mathematical pruning. Future research will focus on refining the clipping techniques further and embedding the N8 structure into other meta-heuristic frameworks, such as Genetic Algorithms or Ant Colony Optimization, to push the boundaries of scheduling efficiency even further.

Summary updated

BibTeX
@misc{xie2021new,
  author = {Jin Xie and Xinyu Li and Liang Gao and Lin Gui},
  title = {{A new neighborhood structure for job shop scheduling problems}},
  year = {2021},
  eprint = {2109.02843},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2109.02843},
}
Figure