A new neighborhood structure for job shop scheduling problems
This is an incremental improvement for combinatorial optimization researchers and practitioners, addressing a specific bottleneck in job shop scheduling.
The paper tackled the job shop scheduling problem by proposing a new neighborhood structure (N8) that moves critical operations both within and outside critical blocks, and experimental results showed it is more effective and efficient than existing state-of-the-art structures on four benchmarks.
Job shop scheduling problem (JSP) is a widely studied NP-complete combinatorial optimization problem. Neighborhood structures play a critical role in solving JSP. At present, there are three state-of-the-art neighborhood structures, i.e., N5, N6, and N7. Improving the upper bounds of some famous benchmarks is inseparable from the role of these neighborhood structures. However, these existing neighborhood structures only consider the movement of critical operations within a critical block. According to our experiments, it is also possible to improve the makespan of a scheduling scheme by moving a critical operation outside its critical block. According to the above finding, this paper proposes a new N8 neighborhood structure considering the movement of critical operations within a critical block and the movement of critical operations outside the critical block. Besides, a neighborhood clipping method is designed to avoid invalid movement, reducing the computational time. Tabu search (TS) is a commonly used algorithm framework combined with neighborhood structures. This paper uses this framework to compare the N8 neighborhood structure with N5, N6, and N7 neighborhood structures on four famous benchmarks. The experimental results verify that the N8 neighborhood structure is more effective and efficient in solving JSP than the other state-of-the-art neighborhood structures.