Title page for ETD etd-11292004-160311


Type of Document Dissertation
Author Liu, Qi
Author's Email Address qliu@vt.edu
URN etd-11292004-160311
Title A Sequence-Pair and Mixed Integer Programming Based Methodology for the Facility Layout Problem
Degree PhD
Department Industrial and Systems Engineering
Advisory Committee
Advisor Name Title
Meller, Russell D. Committee Chair
Barkhi, Reza Committee Member
Chen, Fengshan Frank Committee Member
Deisenroth, Michael P. Committee Member
Fraticelli, Barbara M. P. Committee Member
Keywords
  • Mixed Integer Programming
  • Sequence-Pair Representation
  • Facility Layout Problem
Date of Defense 2004-11-22
Availability unrestricted
Abstract
The facility layout problem (FLP) is one of the most important and challenging problems in both the operations research and industrial engineering research domains. In FLP research, the continuous-representation-based FLP can consider all possible all-rectangular department solutions. Given this flexibility, this representation has become the representation of-choice in FLP research. Much of this research is based on a methodology of mixed integer programming (MIP) models. However, these MIP-FLP models can only solve problems with a limited number of departments to optimality due to a large number of binary variables used in the models to prevent departments from overlapping. Our research centers around the sequence-pair representation, a concept that originated in the Very Large Scale Integration (VLSI) design literature. We show that an exhaustive search of the sequence-pair solution space will result in finding the optimal layout of the MIP-FLP and that every sequence-pair solution is binary-feasible in the MIP-FLP. Based on this fact, we propose a methodology that combines the sequence-pair and MIP-FLP model to efficiently solve large continuous-representation-based FLPs. Our heuristic approach searches the sequence-pair solution space and then use the sequence-pair representation to simplify and solve the MIPFLP model. Based on this methodology, we systematically study the different aspects of the FLP throughout this dissertation.

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.

Files
  Filename       Size       Approximate Download Time (Hours:Minutes:Seconds) 
 
 28.8 Modem   56K Modem   ISDN (64 Kb)   ISDN (128 Kb)   Higher-speed Access 
  Dissertation.pdf 971.23 Kb 00:04:29 00:02:18 00:02:01 00:01:00 00:00:05

Browse All Available ETDs by ( Author | Department )

dla home
etds imagebase journals news ereserve special collections
virgnia tech home contact dla university libraries

If you have questions or technical problems, please Contact DLA.