Great Deluge-Based Metaheuristic Incorporating Integer Nonlinear Programming for Modeling and Solving Dynamic Capability-Based Machine Layout Problem

Abstract

This paper introduces a novel Dynamic Capability-Based Machine Layout (DCB-ML) problem by integrating the Quadratic Assignment Problem (QAP) formulation with a Dynamic Capability-Based Part Flow Assignment (DCB-PFA) problem. This integration enables the simultaneous consideration of machines' processing capabilities, routing flexibility, dynamic flow assignment, and machine capacity utilization. First, a new Integer Nonlinear Programming (INLP) model is developed. The dynamic part flows are determined via the DCB-PFA sub-problem, while machine-location assignments are obtained by solving QAP. To address the complex nature of this problem, a hybrid solution approach is proposed that combines a Great Deluge Algorithm (GDA) with a Mixed-Integer Linear Programming (MILP) model, complemented by local search procedures. Since the problem has a decomposable structure, the proposed approach allows each sub-problem to be addressed independently, while the overall solution quality is jointly evaluated. Decomposition reduces the size of the resulting MILP model, as several binary variables and assignment constraints are eliminated. The proposed hybrid approach is also compared with the INLP and its linearized equivalent on several test problems. For large-scale problems with medium to high capability overlaps, nonlinear and MIP solvers fail to obtain feasible solutions, whereas the proposed approach can efficiently generate high-quality solutions within reasonable times. Moreover, when the effects of different machine-capability overlaps are investigated, it is observed that the solution of the problem will be more complex in the case of higher machine-capability overlaps. However, considering machine capabilities improves overall layout scores and eliminates the necessity of frequent reconfigurations, which is costly and time-consuming.