Graph theoretic based heuristics for the facility layout design problem

Abstract

The facility layout design problem is concerned with determining the arrangement and configuration of facilities, which optimizes a prescribed objective such as profit, cost, or distance, and which satisfies various prescribed constraints pertaining to available resources. In industry, facility layout design problems arise in manufacturing, in warehousing, and in various assignment type situations. The solution of these problems impacts on the viability of the industry. For example, material-handling costs which can comprise between 30 and 75% of the total manufacturing costs, can be reduced by using the optimization methods associated with the facility layout design. In the service industries, facility layout design problems arise in the location of emergency facilities (such as ambulance, fire stations) and in the allocation of space. The solution of these location problems impacts on the well being of the community. Mathematically, the facility layout problem has been modelled as: a quadratic assignment problem, a quadratic set covering problem, a linear integer programming problem, a mixed integer programming problem, and a graph theoretic problem. The problem has been shown to be NP-complete. This computational difficulty has led researchers to consider suboptimal solutions generated by heuristic approaches. There are a number of heuristic procedures that have been proposed for solving the facility layout design problem, including Simulated Annealing, Tabu Search, Expert Systems, and Graph Theoretic Algorithms. The most successful heuristic approaches are based on graph theoretic concepts. In this thesis we focus our study on constructive graph theoretic based heuristics for determining an optimal arrangement and configuration of facilities with the objective of maximizing the total benefit.We are particularly interested in constructive heuristics, which can produce a maximum-weighted planar graph as a final solution. Our contribution is the development, implementation, and testing of three new algorithms. Computational results, based on 4200 randomly (uniform and normal distribution) generated problems, demonstrate the value of our methods. We also present the performance of each algorithm when various initial solutions are applied. Chapter 1 provides the background of the facility layout design, including the notation, terminology and general concepts as well as a summary of the thesis. Chapter 2 provides a comprehensive survey of the facility layout design problem. This includes models and methods of solution based on exact algorithms (including the branch and bound method and the cutting plane method), as well as heuristic algorithms. We detail the main constructive graph theoretic based heuristics in the literature: the Deltahedron Method, the Green-Al Hakim Algorithm, the Leung’s Constructive Heuristic, the Kim-Kim Algorithm, the Wheel Expansion Method, TESSA and the String Processing Algorithm. We also briefly discuss the non-graph theoretic heuristics including simulated annealing, tabu search, and expert systems. In Chapter 3 we present three new graph theoretic based heuristics. These heuristics are constructive and the solution is built up, starting with an initial layout of four facilities, by an insertion process. Our algorithms have two important features. Firstly, they allow for previously chosen edges to be removed at each insertion step. Secondly, they do not restrict the type of maximal planar graph produced. Computational results and a comparative analysis of the main graph theoretic based heuristics are provided. The analysis is based on 4200 randomly generated test problems (from uniform and normal distribution).The test problems consist of 30 data sets with the number of facilities ranging from 5 to 100 in increments of 5. Chapter 4 is devoted to the performance of graph theoretic based heuristics when different types of initial solutions are applied. Examples show that the final solution is sensitive to the initial solution. Computational results indicate that for most algorithms, the best type of initial solution is the selection of four facilities which yield the best objective function value contribution. However, this does not always coincide with that proposed in the original description of the algorithms. We conclude this thesis by discussing some future research that can be carried out on the facility layout design problem, particularly in graph theoretic based heuristics.