教务员Graph Theoretic Bad Heuristics
For the Facility Layout Design Problems
Louis Caccetta and Yaya S. Kusumah
公司愿景School of Mathematics and Statistics
Curtin University of Technology
Perth 6001
Australia
Abstract
The facility layout problem is concerned with determining the location of a number of facilities which optimizes a prescribed objective such as profit, cost, or distance. This problem aris in many applications; for example, in design of buildings and in plant layout design. The facility layout problem has been modeled as: a quadratic assignment problem; a quadratic t covering problem; a linear inte
ger programming problem; a graph theoretic problem. Since this problem is NP-complete, most approaches are heuristic in nature and bad on graph theoretic concepts. Graph theoretically, when the objective is to maximize profit, the facility layout problem is to determine, in a given edge weighted graph G, a maximum weight planar subgraph. In this paper, we discuss a number of heuristics for this problem. The performance of the heuristics is established through a comparative analysis bad on an extensive t of random test problems.
1.Introduction
寒包火Typically the facility layout design problems involve the lection of the most effective arrangement of physical facilities to obtain greatest efficiency with the combination of available resources. The objective is to produce a product or rvice that optimizes a prescribed objective such as total benefit; production cost; material-handling cost; or traffic flow. The facility layout problem aris in many industrial applications as detailed below.
In industry, facility layout design can be ud for designing the layout of a system of facilities including buildings on a plant site or machines on a manufacturing floor. In the manufacturing context, the facility layout problem may be defined as the process of obtaining the optimal location of
plant equipment (workstations). The solution of the facility layout problem is very important since it can increa the flexibility of a production plant and there are significant cost implications which directly impacts on the competitiveness of products produced.
In material handling, the facility layout problem deals with the physical arrangement of a given t of facilities so that the total cost to move the required material between the facilities is minimized. The material handling cost can compri between 30 and 70% of the total manufacturing costs, depending on whether the facility is planned on a product or process basis.晶莹意思
In solving management problems, the facility layout problem techniques have been ud for hospital organizations to reduce nursing staff effort and improve the patient perceive environment. Nowadays facility layout design is ud not only in industrial plants, but also in other institutions, such as airports, office buildings, civic complexes, sport centres, police stations, and aircraft’s instrumentation panel.
Sahni and Gonzalez [22], and Giffin et. al. [12] have shown that the facility layout design problem is NP-complete. Therefore, even though a number of exact algorithms have been propod, computational difficulties ari in large applications. This problem has led rearchers to consider su
boptimal solutions generated by heuristic approaches. Graph theoretic bad heuristics for solving the facility layout problem have been devid by Seppanen and Moore [24], Foulds and Robinson [10], Green-Al Hakim [13], Eades et al. [8], Kim and Kim [17], Leung [21], and Boswell [5]. Most heuristic approaches utilize graph theoretic concepts. The advantage of this is that there is no need to u a planarity test.
The existing graph theoretic bad heuristics are constructive methods in which a solution is generated systematically by adding a vertex or a t of vertices into an existing face. The drawback of the methods, however, is that there are some edges, that contribute a poor weight and conquently a poor solution may be generated. The heuristic developed in this paper alleviates this problem by allowing bad edges to be removed. Testing on 600 randomly generated problems with 10 to 100 vertices provides good support for our methods.
2. Models for the Facility Layout Design Problem
As described by Kusiak and Heragu [19], the facility layout problem has been modeled as a quadratic assignment problem, a quadratic t covering problem, a linear integer programming problem, a mixed integer programming problem, and a graph theoretic problem. Koopmans and Bec
kman [18] have modeled facility layout location plants with material flow between them as a quadratic assignment problem (QAP). It is called a quadratic assignment problem becau its objective function is a cond degree function of the variables and the constraints are linear functions of the variables.
One of the early exact algorithms was devid by Koopmans and Beckman [18]. Their algorithm is bad on the Quadratic Assignment Problem (QAP). A suggestion to linearize this model was given by Lawler [20], and Kaufman and Broeckx [16]. Foulds and Robinson [9] suggested a branch and bound method and ud the Kuratowski criterion for planarity testing. Another suggestion is a cutting plane method, which was devid by Bazaraa and Sherali [3]. There are also veral other integer programming formulations suggested by Lawler [20], Kaufmann and Broeckx [16], Heragu and Kusiak [22]. Bazaraa [2] modeled the problem as a quadratic t covering problem (QSP). Using this formulation, the total area occupied by all the facilities is divided into a number of blocks. Each facility is assigned to exactly one location and each block is occupied by at most one facility. It should be noted that in the total area occupied by all the facilities is divided into smaller blocks, the problem size increas.
Using graph theory the facility layout can be modeled as an edge-weight maximal planar graph, in w
hich the vertices reprent the facilities and the edges reprent the “adjacencies”. The edge weight reprents either the cost or the benefit of having two facilities adjacent. When the edge weight reprent cost (benefit) the problem is to find an arrangement which minimizes (maximizes) the total cost (benefit). The layout of a facility
can be obtained by constructing the dual of a maximal planar subgraph. In graph theoretic formulation it is assumed that the desirability of locating each pair of facilities adjacent to each other is given.
3. Graph Theoretic Bad Heuristics
For our purpos, G = (V,E) is a finite simple graph with vertex t V and edge t E. K n denotes the complete graph on n vertices. A graph is said to be planar if it can be drawn in the plane so that its edges interct only at their vertices. A maximal planar graph is a planar graph with the property that adding an edge between any two non adjacent vertices results in a nonplanar graph. For convenience, let V = {1, 2, . . . , n} and denote an edge as an unordered pair (i,j); the weight of edge (i,j) is denoted by w ij . Without loss of generality we can assume that our graph is complete and the edge weight w ij reprents the benefit of locating facilities i and j adjacent. For a general discussion of graph theoretic concepts we refer to the book of Bondy and Murty [4].赵孟頫楷书字帖
Given a weighted graph G, the facility layout problem is to find a maximum weighted spanning subgraph G ′ of G that is planar. Mathematically the problem is:
E j)(i,x w = B(G) Maximize ij ij ∑′
∈ subject to
x ij =0,1, for all i,j,
and G ′=(V,E ′), where E ′= {(i,j): x ij = 1}, is a planar graph.
As noted in the introduction, a number of constructive heuristics that generate a maximal planar graph have been propod. Typically, the heuristics start with a K 3 or K 4 and build up the solution through vertex inrtion, maintaining planarity at every stage. A major advantage of such methods is that there is no need to u planarity test at any stage of the inrtion process. Once the final graph is obtained, the corresponding block plan can be easily drawn by converting a dual graph to a block layout, using procedures devid by Al-Hakim [1], Hasan and Hogg [14], or Green and Al-Hakim [13].By using a new matrix reprentation of a planar graph, a floor plan as a dual graph can be easily constructed. Below is an example of a block plan together with the corresponding maximal planar graph.
Figure 1. A graph and its corresponding block layout
Some of the heuristics incorporate an improvement procedure. The main graph theoretic bad heuristics developed to date are tho of: Foulds and Robinson [9](Deltahedron Method), Green and Al-Hakim [13], Leung [21], Kim and Kim [17], Eades et al. [8] (Wheel Expansion Method), and Boswell [5] (TESSA).
In this paper, we prent a new constructive heuristic. Computational results bad on 600 randomly generated problems demonstrates the superiority of our heuristic over the ven literature heuristics mentioned above. A brief description of the literature heuristic is given below.
(i) The Deltahedron Method (Foulds and Robinson [9])
The application of graph theory to facility layout design was initiated by Foulds and Robinson [9] with the publication of the Deltahedron Method in 1976. The method involves simple inrtion. Starting with an initial K4, vertices are inrted one by one according to a benefit criteria. At each step, the maximum benefit of inrting each unud vertex is calculated and the vertex yielding the highest benefit is lected and inrted into the current generated subgraph. The initial K4 can be determined (S-Construction) by lecting the four highest weighted vertices (the weight of a vertex is the sum of the weights of the edges incident to it); an alternative method (R-construction) is to generate the entire list of K4’s and lect the best. Using the S-construction, a solution can be generated in O(n2). The algorithm was tested on 6 small graphs ranging from 8 to 26 vertices.
(ii) The Green-Al Hakim Algorithm [13]
This algorithm is a slight variation of the Deltahedron Method. Here we start with a maximum weight K3 instead of a K4 and vertices are inrted as in (i). A simple format is ud to allow easy generation of the block layout plan corresponding to the solution. The complexity of this algorithm is O(n3).
(iii) The Constructive Heuristic (Leung [21])
This Heuristic can be viewed as the generalization of (i) in that at each step either one or three vertices are inrted. The single inrtion option is evaluated as in (i). The triple vertex inrtion involves 9 new edges, the benefit of the inrtion is evaluated by dividing the sum of the weights of the 9 edges by 3. The method usually generates a better solution than (i), but the processing time is considerably longer. The complexity of the algorithm is O(n5).
This algorithm was tested using a t of 90 problems; values of n ud were 20, 30, and 40. The edge weights were taken from a normal distribution with mean 100 and standard deviation 5, 10, 15, 20, 25, and 30.
(iv) The Wheel Expansion Algorithm (Eades et al. [8])
Here the initial K4 is obtained by lecting an edge having the highest weight and then applying two successive vertex inrtion according to the benefit criteria. The algorithm then proceeds with an inrtion process, called the wheel expansion procedure. A wheel on n vertices is defined as a cycle on (n-1) vertices (termed the rim), such that each vertex is adjacent to one additional vertex (termed the hub).
Let W be a wheel having the hub x. Select two vertices k and l, which are the rims of this cycle. A ver
tex y from the t of unud vertices is then inrted to this wheel in the current partial subgraph such that y is a hub of the new wheel W′ containing k, l and x as its rims, and all rims in W are now adjacent to vertex x or vertex y. By inrting each unud vertex successively using the above fashion, the final maximal planar subgraph is obtained. The complexity of this algorithm is O(n4).
(v) The Kim-Kim Algorithm [17]
八上地理复习提纲
This algorithm is only a slight variation of (iii). Here instead of considering 1 vertex or 3 vertices in each iteration to obtain the highest weight inrtion, only 3-vertex inrtions are considered until there are two vertices or one vertex left in the t of unud vertices. This process is devoted to avoid an umbrella effect, a situation where a vertex is adjacent to all other vertices. The complexity of this algorithm is O(n4).
(vi) Tessa (Boswell [5])
This algorithm starts with an initial K3 , chon according to weight, and adds faces. It considers only triangular faces and at each step a list of available triangles is maintained. The lected face is chon according to weight and must have at least one edge in common with the boundary of the current partial subgraph. Note that each step either a single edge or a vertex and two edges are add
ed.
Tessa was implemented and tested using randomly generated data for each of n=10, 20, 30, and 40. The edge weights are normally distributed with a mean of 100 and standard deviations of 5, 10, 15, 20, 25, and 30. Though no computational (time) analysis is given, this algorithm requires significantly more computational time than the others. The complexity of this algorithm is O(n5).
王替夫
4. A New Graph Theoretic Bad Heuristic
Basically, the edge removal step as the main idea introduced in Caccetta and Kusumah [7], is ud in our new algorithm. The inrtion procedure in our algorithm, however, implements veral new inrtion types. The option of inrtion can accommodate some possible high-weighted subgraphs, constructed by vertices having degree 3, 4, or 5; including octahedron or icosahedron. So, this construction technique does not restrict the type of MPG produced.
Four vertices are lected as an initial solution. This step is started by making a list of all possible subgraphs consisting of 4 vertices. Bad on the sum of each weight, the best 4 vertices having the highest weight are lected as an initial subgraph K4.
Additional vertices are inrted to the existing partial solution until all of the vertices are ud. In each iteration we inrt 1 or 2 vertices at a time to a face or a pair of faces in the current partial solution. We may drop a poor-weighted edge in the existing partial solution, and replace it with a better-weighted edge. An inrtion of 1 vertex or 2 vertices to a pair of faces drops an edge, particularly when this edge has a poor weight and does not give a good contribution to the current partial solution.
The construction technique compris 1-vertex and 2-vertex inrtion. In 1-vertex inrtions we inrt a vertex to a face or to a pair of faces. When this vertex is inrted to a face, a vertex having degree 3 is added. It also constructs 3 new faces and removes 1 face. If this vertex is inrted to a pair of faces, we have a vertex having degree 4, but at the same time we also remove an existing edge from the current partial solution. There are 4 new faces constructed and 2 faces removed by this technique.
The application of 2-vertex inrtion into a face gives 2 new vertices, each of which has degree 3 and 4 respectively. It also yields 5 new faces and removes 1 face. No edges are removed from the current subgraph by using this technique. If two vertices are inrted into a pair of faces, we obtain either 2 new vertices all of which have degree 4, or 2 new vertices one with degree 3 and the other
with degree 5. This type of inrtion gives us 6 new faces and removes 1 edge and 2 faces from the current partial subgraph.
Since a triangulation process is ud at each step in this inrtion technique and some new faces are constructed in each iteration, this algorithm does not need a planarity testing routine and thus is time efficient. The detailed algorithm is described below.
a. Initialization
Select 4 vertices from the list of unud vertices to form a complete graph K4, which has the highest benefit.
Figure 2. A complete graph K4
b. Generation of candidates
Consider all the following possible inrtions to all pair of faces having a common
1. Remove the common edge from the pair of faces, to obtain a cycle of 4 vertices.
Inrt vertex x from the t of unud vertices into the cycle such that x is adjacent to all vertices in the cycle.
2. Remove the common edge from the pair of faces to obtain a cycle of 4 vertices.
Inrt vertices x and y from the t of unud vertices into the cycle such that deg(x)=deg(y)=4, x is adjacent to y, and each of x and y is adjacent to 3 vertices in the cycle.
3. Remove the common edge from the pair of faces to obtain a cycle of 4 vertices.
Inrt vertices x and y from the t of unud vertices into the cycle such that deg(x)=3, deg(y)=5, x and y are adjacent and each is adjacent to two vertices in the cycle.
4. Inrt vertex x from the t of unud vertices into a face in the pair of faces,
such that deg(x)=3, and vertex x is adjacent to all vertices in the face.
5. Inrt vertices x and y from the t of unud vertices into a face in the pair of
faces, such that deg(x)=4, deg(y)=3, x is adjacent to y and all vertices in the face, and y is also adjacent to 2 vertices in the face.
c. Construction
Choo the highest-weight inrtion, and construct a new partial subgraph bad on the corresponding type of inrtion. The weight resulted from 2-vertex inrtion has to be divided by 2 before compared to the weight resulted from any other inrtions.
Repeat until all unud vertices are inrted to the current partial subgraph.第一次拥抱
