A novel two stage neighborhood search for flexible job shop scheduling problem considering reconfigurable machine tools - Yanjun Shi; Chengjia Yu; Shiduo Ning (Complex & Intelligent Systems)
Abstract The rapid changes in market demand are driving a transition from traditional mass production to high-mix, low-volume production, emphasizing the need for customization and rapid response. Reconfigurable Manufacturing Systems (RMS) are crucial in this shift, providing a flexible platform to meet diverse production requirements, and forming an essential component of next-generation manufacturing. Reconfigurable Machine Tools (RMTs), the core of RMS, enable dynamic configuration adjustments through auxiliary modules (AMs), enhancing both flexibility and efficiency. However, optimizing the allocation of limited AMs, considering non-negligible assembly and disassembly times, remains a significant challenge. This paper focuses on the flexible job shop scheduling problem with machine reconfigurations (FJSP-MR) and proposes an improved genetic algorithm with a two-stage neighborhood search (IGA-TNS) to minimize total weighted tardiness (TWT). Initially, a mixed-integer linear programming (MILP) model is formulated to comprehensively represent the problem. To enhance search efficiency, a two-stage neighborhood search strategy is developed: the first stage extends the k-insertion search to facilitate operation movement across different machine configurations, while the second stage refines operations within the same configuration. Furthermore, a trend-detection-based neighborhood search activation strategy is introduced to accelerate convergence and reduce computational costs. Experimental results on extended benchmark instances demonstrate that the proposed IGA-TNS effectively addresses the FJSP-MR, outperforming other algorithms in solution quality and computational efficiency. Finally, a industrial FJSP-MR case is studied, demonstrating that the proposed IGA-TNS is applicable to large-scale problems.