A Sequence-Pair and Mixed Integer Programming Based Methodology for the Facility Layout Problem
MetadataShow full item record
As the first contribution of this dissertation, we present a genetic algorithm based heuristic, SEQUENCE, that combines the sequence-pair representation and the most recent MIPFLP model to solve the all-rectangular-department continuous-representation-based FLP. Numerical experiments based on different sized test problems from both the literature and industrial applications are provided and the solutions are compared with both the optimal solutions and the solutions from other heuristics to show the effectiveness and efficiency of our heuristic. For eleven data sets from the literature, we provide solutions better than those previously found.
For the FLP with fixed departments, many sequence-pairs become infeasible with respect to the fixed department location and dimension restrictions. As our second contribution, to address this difficulty, we present a repair operator to filter the infeasible sequence-pairs with respect to the fixed departments. This repair operator is integrated into SEQUENCE to solve the FLP with fixed departments more efficiently. The effectiveness of combining SEQUENCE and the repair operator for solving the FLP with fixed departments is illustrated through a series of numerical experiments where the SEQUENCE solutions are compared with other heuristics' solutions.
The third contribution of this dissertation is to formulate and solve the FLP with an existing aisle structure (FLPAL). In many industrial layout designs, the existing aisle structure must be taken into account. However, there is very little research that has been conducted in this area. We extend our research to further address the FLPAL. We first present an MIP model for the FLPAL (MIP-FLPAL) and run numerical experiments to test the performance of the MIP-FLPAL. These experiments illustrate that the MIP-FLPAL can only solve very limited sized FLPAL problems. Therefore, we present a genetic algorithm based heuristic, SEQUENCE-AL, to combine the sequence-pair representation and MIP-FLPAL to solve larger-sized FLPAL problems. Different sized data sets are solved by SEQUENCE-AL and the solutions are compared with both the optimal solutions and other heuristics' solutions to show the effectiveness of SEQUENCE-AL.
The fourth contribution of this dissertation is to formulate and solve the FLP with non-rectangular-shaped departments. Most FLP research focuses on layout design with all rectangular-shaped departments, while in industry there are many FLP applications with non-rectangular-shaped departments. We extend our research to solve the FLP with nonrectangular-shaped departments. We first formulate the FLP with non-rectangular-shaped departments (FLPNR) to a MIP model (MIP-FLPNR), where each non-rectangular department is partitioned into rectangular-shaped sub-departments and the sub-departments from the same department are connected according to the department's orientation. The effect of different factors on the performance of the MIP-FLPNR is explored through a series of numerical tests, which also shows that MIP-FLPNR can only solve limited-sized FLPNR problems. To solve larger-sized FLPNR problems, we present a genetic algorithm based heuristic, SEQUENCE-NR, along with two repair operators based on the mathematical properties of the MIP-FLPNR to solve the larger-sized FLPNR. A series of numerical tests are conducted on SEQUENCE-NR to compare the SEQUENCE-NR solutions with both the optimal solutions and another heuristic's solutions to illustrate the effectiveness of SEQUENCE-NR.
As the first systematic research study on a methodology that combines the sequence-pair representation and the MIP-based FLP, this dissertation addresses different types of continuous-representation based facility layout design problems: from block layout design with and without fixed departments to re-layout design with an existing aisle structure, and from layout design with all-rectangular-shaped departments to layout design with arbitrary non-rectangular-shaped departments. For each type of layout design problem, numerical experiments are conducted to illustrate the effectiveness of our specifically designed family of sequence-pair and MIP-based heuristics. As a result, better solutions than those previously found are provided for some widely used data sets from the literature and some new datasets based on both the literature and industrial applications are proposed for the first time. Furthermore, future research that continues to combine the sequence-pair representation and the MIP-FLP model to solve the FLP is also discussed, indicating the richness of this research domain.
- Doctoral Dissertations