A coupled spiking neural P system integrated with two-level neighborhood search for solving flexible job shop scheduling problems.

Abstract

The Flexible Job Shop Scheduling Problem (FJSP) is an Non-deterministic Polynomial (NP)-hard combinatorial optimization problem whose large-scale and highly flexible instances expose limitations of many existing metaheuristics: serial search structures, redundant neighborhood moves, and poor balance between global exploration and local exploitation, which together limit scalability and stability. To address these issues, we propose a Coupled Spiking Neural P system (CSN P) that embeds a genetic-operator module and a two-level neighborhood search (inter-machine moves based on non-overlapping critical operations, and intra-machine reverse-order critical-block moves) within a parallel membrane-computing framework. Across 49 benchmark instances the method attains current best-known solutions for 47 instances and improves 16 historical best solutions. The ablation study shows the total gain from a baseline without the genetic algorithm (GA) core and move synergies is 7.85 %; the GA contributes  ≈ 56.4 % of that gain, while inter- and intra-machine moves contribute  ≈ 18.6 % and  ≈ 16.8 %, respectively, demonstrating both module effectiveness and synergy. Convergence and box-plot analyses further confirm fast, stable search behavior.