Facility Layout Planning

Introduction

Facility layout design is one the most important problems to be addressed in facilities planning problem. The facility layout problem deals with laying out the physical set of facilities, such as machines or more generally, departments, in manufacturing plants, hospitals, etc. In fact, the facilities layout design is to yield the location of the facilities which are to be laid with respect to optimizing some objective function(s) in the system. Typical measures broadly appearing in the literature are: the sum of trip distance of materials and workers, the total summation of the closeness rating among facilities adjacent to each other, etc.

The Weighted Maximal Planar Graph (WMPG) appears in many applications. It is currently used to design facilities layout in manufacturing plants. Given an edge-weighted complete simple graph G, the WMPG involves finding a sub-graph of G that is planar in the sense that it could be embedded on the plane such that none of its edges intersect, and is maximal in the sense that no more edges can be added to it unless its planarity is violated. Finally, it is optimal in the sense that the resulting maximal planar graph holds the maximum sum of edge weights.

The WMPG approach to design the facility layout involves three major steps (Osman, 2006). First, the adjacency graph, in which the vertices stand for facilities, is built. Also the outer space of the layout is represented by an artificial vertex in the WMPG (as shown in Figure 1). An edge connects a couple of vertices if the corresponding two facilities are adjacent in the layout, and the edge weights indicate the benefit of adjacency between facilities (solid lines and related vertices in Figure 1). Secondly, using common procedures and algorithms, the WMPG of the adjacency graph is obtained (The graph in solid edges in Figure 1). Since the resulting block plan, which is the dual of the obtained WMPG, may not meet the size or shape requirements imposed on each of its areas, the designer must draw an appropriate block layout. Figure 1 exemplifies a WMPG in solid lines with its corresponding dual graph in dashed lines. Since the graph in dashed line cannot be considered as a block layout, the designer has to manipulate it such that the block layout represented by the dashed lines in Figure 2 is obtained. Among these steps, finding the WMPG is computationally the most difficult one since the WMPG is an NP-complete problem in terms of computational complexity (Giffin, 1984). It should be noted that a planar graph may have several plane embeddings, thus there may be alternative block layout plans that meet the adjacency requirements.

Figure 1.

A WMPG and its corresponding dual graph

Figure 2.

A WMPG and the corresponding block layout

It should be emphasized that constructing a block layout given a planar adjacency graph that meets the size and shape requirements of the blocks is a nontrivial task. Researchers have confirmed that a block plan that meets the adjacency requirements and shape constraints often cannot be drawn. Researchers such as Muther (1955) and Hales (1984) have suggested heuristics for accomplishing this task. Giffin and Foulds (1987) also presented a method which achieves part of the aim of the drawing of a block plan. Giffin et al. (1995) presented a linear time algorithm to construct a block layout plan which is dual to an adjacency graph, and must meet all the adjacency requirements and shape restrictions of facilities.

Mathematical Models

In this section the mathematical models jointed with the algorithms which have ever been developed to obtain the WMPG are explained.