Genetic neighborhood algorithm based on flexible blocks and idle space for flexible job-shop scheduling problem with sequencing flexibility

The Flexible Job-Shop Scheduling Problem with Sequencing Flexibility (FJSPSF) presents a significant challenge in job-shop environments, where operations within a job can be processed in multiple feasible precedence orders rather than a single sequence. However, traditional methods used to model precedence relationships, i.e., directed acyclic graphs (DAGs), struggle to accurately capture precedence constraints as flexibility increases. Moreover, given the NP-hard nature of FJSPSF, developing more efficient and high-quality algorithms remains essential. To address these challenges, this paper proposes a Genetic Neighborhood Algorithm based on Flexible Blocks and Idle Space (GNA-FBIS). GNA-FBIS introduces a flexible-block-based matrix representation (FMR) method instead of DAGs, enabling the efficient integration of complex precedence constraints into the optimization algorithm. Building upon this representation, we develop a novel three-segment encoding scheme that integrates flexible blocks, operations sequences, and machine selections, while ensuring that genetic operations such as crossover and mutation align with these structural characteristics. A neighborhood search strategy focusing on critical operational space and idle space is incorporated to enhance solution quality. This strategy strategically relocates critical operations to (relatively) effective idle spaces by evaluating operational spaces and differentiating between flexible and non-flexible critical operations. Extensive experiments on both standard and extended FJSPSF instances demonstrate the superior performance of GNA-FBIS over existing methods.