# Obtaining an Initial Solution for Facility Layout Problem

Authors: Ali Shoja Sangchooli; Mohammad Reza Akbari Jokar
Journal: Journal of Industrial Mathematics
 (2013)

---

## Abstract

The facility layout approaches can generally be classified into two groups, constructive approaches and improvement approaches. All improvement procedures require an initial solution which has a significant impact on final solution. In this paper, we introduce a new technique for accruing an initial placement of facilities on extended plane. It is obtained by graph theoretic facility layout approaches and graph drawing algorithms. To evaluate the performance, this initial solution is applied to rectangular facility layout problem. The solution is improved using an analytical method. The approach is then tested on five instances from the literature. Test problems include three large size problems of 50, 100, and 125 facilities. The results demonstrate effectiveness of the technique especially for large size problems.


---

## Body

## 1. Introduction

The facility layout problem seeks the best positions of facilities to optimize some objective. The common objective is to reduce material handling costs between the facilities. The problem has been modeled by a variety of approaches. A detailed review of the different problem formulations can be found in Singh and Sharma [1]. The facility layout problem is an optimization problem which arises in a variety of problems such as placing machines on a factory floor, VLSI design, and layout design of hospitals, schools.The facility layout approaches can generally be classified into two groups, constructive methods and improvement methods. In this paper, we consider the placement of facilities on an extended plane. Many improvement approaches have been proposed for this problem. All improvement procedures require an initial solution. Some approaches start from a good but infeasible solution [2–4]. These models contain a penalty component in their objective function. Hence, these approaches minimize objective function value for feasible solutions. But some approaches require a feasible initial solution. These approaches use a randomly generated initial solution [5, 6]. Mir and Imam [7] have proposed simulated annealing for a better initial solution. They have shown that a good initial solution has a significant impact on final solution.In this paper, we introduce a new technique for accruing an initial placement of facilities on an extended plane. The technique consists of two stages. In the first stage, a maximal planar graph (MPG) is obtained. In the second stage, the vertices of MPG are drawn on the plane by graph drawing algorithms. Then, vertices are replaced by facilities. Hence, an initial solution is obtained.In an MPG, the facilities with larger flows are adjacent together. Hence, drawing the MPG on the plane can be a good idea for obtaining an initial solution. To evaluate the performance of the idea, this initial solution is applied in rectangular facility layout problem. The solution is improved by an analytical method by Mir and Imam [7]. The approach is then tested on five instances from the literature.The remaining parts of the paper are organized as follows. The next section describes the formulation of the facility layout problem chosen for our work. Section3 describes accruing an initial placement. In Section 4, the analytical method is described, and the approach is compared to other approaches in the literature. In Section 5, the proposed initial solution is compared with random initial solution. Finally, Section 6 provides a summary and conclusion.


## 2. Problem Formulation

In this paper, we label the facilities1,2,…,N, where N is the total number of facilities. Facilities are assumed to be rectangles with fixed shape. The notation is given as follows: (xi,yi) coordinates of the center of facility iLi length of facility iWi width of facility ifij the total cost of flow per unit distance between two facilities i and jdij distance between the centers of the facilities i and j. dij could be one of the following three distance norms.
(1)
Euclidean distance:(1)dij=((xi-xj)2+(yi-yj)2)1/2.(2)
Squared Euclidean distance:(2)dij=(xi-xj)2+(yi-yj)2.(3)
Rectilinear distance:(3)dij=|yi-yj|+|xi-xj|.The requirement for problem is that the facilities must not overlap each other. The area of overlap is defined as follows:
(4)Aij=λij(ΔXij)(ΔYij),
where
(5)ΔXij=Li+Lj2-|xi-xj|,ΔYij=Wi+Wj2-|yi-yj|,λij={1,forΔXij≥0,ΔYij≥0,0,otherwise.
The value of overlap area Aij is a nonnegative number. Aij will be zero only if there is no overlapping between facilities i and j. The objective is to minimize material handling costs. So, the problem can be stated as follows:
(6)minimizing  cost=∑i=1N-1∑j=i+1NfijdijsubjecttoAij=0∀i,j,i<j.
The constraint ensures that facilities do not overlap. A similar formulation also can be found in [7].


## 3. Obtaining an Initial Solution

The initial solution is obtained by graph theoretic facility layout approaches (GTFLP) and graph drawing algorithms. The following subsection describes obtaining an MPG. Section3.2 describes the drawing of the MPG on the plane.


### 3.1. Generating a Maximal Planar Graph

In GTFLP, facilities are represented by vertices, and flow (adjacency desirability) between them is represented by weighted edges. Created graph is called adjacency graph. Graph theory is particularly useful for the facility layout problems, because graphs easily enable us to capture the adjacency information and model the problem. A review of graph theory applications to the facility layout problem can be found in [9, 10]. GTFLP consists of two stages. At the first stage, the adjacency graph is converted to a maximal planar graph (MPG). In the second stage, a block layout is constructed from the MPG. The second stage is not our concern here. For more details, we refer to [11–15]. Figure 1 shows an MPG and its correspondent block layout.Figure 1
An MPG (solid lines) and its correspondent block layout (dashed lines).Many heuristic and metaheuristic methods for obtaining an MPG have been suggested [16–21]. In this paper, we use from the greedy heuristic [16]. It is conceptually simple and creates high weighted MPGs [16]. This heuristic has a simple instruction: the edges are sorted in nonincreasing order of weight. Each edge is tested in turn and accepted as part of the MPG unless it makes the graph nonplanar. So, the heuristic needs planarity testing. Boyer and Myrvold [22] developed a simplified O(n) planarity testing algorithm. We use this algorithm for planarity testing. In the worst case, O(n2) edges are considered, and for each edge, the Boyer and Myrvold test is called. Hence, the approach results in a complexity of O(n3).


### 3.2. Drawing Maximal Planar Graph on the Plane

Graph drawing, as a branch of graph theory, applies topology and geometry to derive two-dimensional representations of graphs. A graph drawing algorithm reads as input a combinatorial description of a graph G and produces as output a drawing of G. A graph has infinitely many different drawings. For a review of various graphs drawing algorithms, refer to [23]. We use algorithm of Chrobak and Payne [24] to form a straight line drawing, of the MPG. In such a drawing, each edge is drawn using a straight line segment. The algorithm draws vertices in an MPG to integer coordinates in a (2N-4)×(N-2) grid. Figure 2 shows an example of straight line drawing.Figure 2
An example of straight line drawing.For acquiring an initial solution, each vertex is replaced by its correspondent facility. In a feasible solution, facilities have no overlaps. For this reason, the coordinates of facilities can be multiplied by maximum dimensions of all facilities (width and length). This operation increases distance between facilities and makes the solution feasible. For the case of circular facilities, the diameter of circle can be considered as maximum dimensions.


## 3.1. Generating a Maximal Planar Graph

In GTFLP, facilities are represented by vertices, and flow (adjacency desirability) between them is represented by weighted edges. Created graph is called adjacency graph. Graph theory is particularly useful for the facility layout problems, because graphs easily enable us to capture the adjacency information and model the problem. A review of graph theory applications to the facility layout problem can be found in [9, 10]. GTFLP consists of two stages. At the first stage, the adjacency graph is converted to a maximal planar graph (MPG). In the second stage, a block layout is constructed from the MPG. The second stage is not our concern here. For more details, we refer to [11–15]. Figure 1 shows an MPG and its correspondent block layout.Figure 1
An MPG (solid lines) and its correspondent block layout (dashed lines).Many heuristic and metaheuristic methods for obtaining an MPG have been suggested [16–21]. In this paper, we use from the greedy heuristic [16]. It is conceptually simple and creates high weighted MPGs [16]. This heuristic has a simple instruction: the edges are sorted in nonincreasing order of weight. Each edge is tested in turn and accepted as part of the MPG unless it makes the graph nonplanar. So, the heuristic needs planarity testing. Boyer and Myrvold [22] developed a simplified O(n) planarity testing algorithm. We use this algorithm for planarity testing. In the worst case, O(n2) edges are considered, and for each edge, the Boyer and Myrvold test is called. Hence, the approach results in a complexity of O(n3).


## 3.2. Drawing Maximal Planar Graph on the Plane

Graph drawing, as a branch of graph theory, applies topology and geometry to derive two-dimensional representations of graphs. A graph drawing algorithm reads as input a combinatorial description of a graph G and produces as output a drawing of G. A graph has infinitely many different drawings. For a review of various graphs drawing algorithms, refer to [23]. We use algorithm of Chrobak and Payne [24] to form a straight line drawing, of the MPG. In such a drawing, each edge is drawn using a straight line segment. The algorithm draws vertices in an MPG to integer coordinates in a (2N-4)×(N-2) grid. Figure 2 shows an example of straight line drawing.Figure 2
An example of straight line drawing.For acquiring an initial solution, each vertex is replaced by its correspondent facility. In a feasible solution, facilities have no overlaps. For this reason, the coordinates of facilities can be multiplied by maximum dimensions of all facilities (width and length). This operation increases distance between facilities and makes the solution feasible. For the case of circular facilities, the diameter of circle can be considered as maximum dimensions.


## 4. Improving Initial Solution and  Comparing

To evaluate the performance, the initial solution is improved by an analytical method by Mir and Imam [7]. In this method, the convergence is controlled by carrying out the optimization using concept of “magnified envelop blocks.” The dimensions of the blocks are determined by multiplying the dimensions of the facilities with a “magnification factor.” The optimization is then carried out for these envelop blocks rather than the actual facilities. The analytical method searches the optimum placements of each envelop block in the direction of steepest descent which is opposite to the gradient direction. The sizes of the envelop blocks are then reduced, and the optimization process is repeated for the second phase. The number of optimization phases is equal to the magnification factor number for the envelop blocks. In the last optimization phase, the dimensions of the envelop blocks become equal to the actual facilities. For more detail, we refer to Mir and Imam [7].So, the proposed approach for solving a facility layout problem can be summarized as follows.Step 1: encapsulating facilities in envelop blocks (multiplying the dimensions of facilities by a magnification factor).Step 2: obtaining an MPG.Step 3: drawing the MPG on the plane and obtaining an initial solution.Step 4: improving initial solution by analytical method.Figure 3 shows summary of these steps.Figure 3
Steps of the proposed approach.The proposed approach was coded using the VB.NET programming language in a program named GOT (Graph optimization technique). Five test problems were run. For all test problems, results were obtained on a PC with Intel T5470 processor. The results were compared with the previously published papers and commercial software VIP-PLANOPT 2006. VIP-PLANOPT is a useful layout software package that can generate near-optimal layout [25]. For more details about VIP-PLANOPT, see Engineering Optimization Software [8]. VIP-PLANOPT results were obtained from the software user’s manual. The results are presented in the following sections.


### 4.1. Test Problem #1

This problem of 8 facilities was introduced by Imam and Mir [5]. Figure 4 shows the steps for accruing the initial solution. Figure 4(a) shows the flow matrix and dimension of facilities. All dimensions and cost matrix elements are integer-valued numbers ranging between 1 and 6. There are several pairs of facilities with no flow between them. Distance norm is squared Euclidean. The greedy heuristic generates the edges lists of MPG as shown in Figure 4(b).Obtaining an initial solution for test problem #1.
(a)
The raw facilities layout data
(b)
MPG
(c)
Straight line drawing of the MPG
(d)
Initial solutionThe straight line drawing algorithm gives the coordinates of vertices. The drawing is shown in Figure4(c). Then, each vertex is replaced by its correspondent facility. The coordinates are multiplied by maximum dimensions of facilities (width and length), and finally, the initial layout design is shown in Figure 4(d).The solution is improved by the analytical technique. Figure5 shows the final layout. The cost function value for this layout is 752.7, and the running time is 0.4 second. Table 1 shows the results obtained by the other approaches. The best solution for this problem is obtained by VIP-PLANOPT 2006.Table 1
Results for test problem #1.
Program
Cost function value
TOPOPT (Imam and Mir, 1989) [5]
794
VIP-PLANOPT (2006) [8]
692
GOT
752.7Figure 5
Final layout for test problem #1.


### 4.2. Test Problem #2

This problem of 20 unequal area facilities was introduced by Imam and Mir [6]. The data consist of only integer values. The dimensions of the facilities are between 1 and 3. The elements of the cost matrix are integers between 0 and 5. The distance norm is rectilinear. The final layout obtained by GOT is shown in Figure 6. The layout cost is 1302, and the running time is 0.6 second. Table 2 compares the results obtained by GOT with the results available in the literature. VIP-PLANOPT 2006 has the lowest value of the cost function.Table 2
Results for test problem #2.
Program
Best design
Topopt (Mir and Imam, 1989) [5]
1320.72
FLOAT (Imam and Mir, 1993) [6]
1264.94
HOT (Imam and Mir, 2001) [7]
1225.40
VIP-PLANOPT (2006) [8]
1157
GOT
1302Figure 6
Final layout for test problem #2.


### 4.3. Test Problem #3

This is a problem of 50 facilities randomly generated by VIP-PLANOPT 2006. The dimensions of the facilities are decimal numbers between 1 to 6. The elements of the cost matrix are all integers between 1 and 10. The distance norm is Euclidean. The results are shown in Table3. The best published result has a cost of 78224.7, whereas GOT produces a final layout with a cost of 76882.3 only in 15.1 seconds. Figure 7 shows the final layout.Table 3
Results for test problem #3.
Program
Cost function value
HOT (Mir and Imam, 2001) [7]
80794.24
VIP-PLANOPT (2006) [8]
78224.7
GOT
76882.3Figure 7
Final layout for test problem #3.


### 4.4. Test Problem #4

This is a randomly generated large size problem of 100 facilities. The dimensions of the facilities are decimal numbers between 1 and 6. The cost matrix elements are integers between 1 and 10. The distance norm is rectilinear. The results are shown in Table4. GOT obtained the cost function value of 527094.1 in 74.3 seconds. This value is about 2% below the cost function value of VIP-PLANOPT 2006. The coordinates of the facilities for the layout obtained by GOT are given in  Table 5.Table 4
Results for test problem #4.
Program
Cost function value
HOT (Mir and Imam, 2001) [7]
558556.2
VIP-PLANOPT (2006) [8]
538193.1
GOT
527094.1Table 5
For test problem #4, the coordinates of facilities obtained by GOT are given below. The value of the cost function for this layout is 527094.1.
Facility
X
Y
1
17.599
22.158
2
18.514
32.933
3
29.485
18.634
4
35.526
20.582
5
14.798
22.65
6
26.425
25.388
7
12.213
13.282
8
19.435
27.466
9
32.119
15.319
10
24.743
8.862
11
16.231
2.711
12
25.533
17.621
13
14.274
20.352
14
22.791
3.889
15
14.467
14.812
16
38.012
16.94
17
9.735
11.276
18
24.609
27.663
19
20.685
20.578
20
19.866
22.579
21
15.832
8.421
22
8.866
31.495
23
22.402
17.335
24
35.551
9.125
25
16.95
19.378
26
36.104
25.31
27
16.328
21.843
28
13.208
26.161
29
22.439
14.732
30
14.052
13.065
31
28.21
21.934
32
16.436
12.282
33
24.467
11.365
34
23.103
32.489
35
23.283
24.968
36
19.444
14.708
37
32.927
16.699
38
11.708
28.857
39
15.14
29.793
40
28.164
5.174
41
32.08
8.476
42
29.636
13.049
43
26.373
31.127
44
8.693
15.785
45
16.05
26.859
46
31.965
26.099
47
29.361
9.586
48
33.822
12.885
49
19.394
25.043
50
25.902
21.954
51
4.234
16.534
52
19.539
30.211
53
5.587
11.801
54
13.399
32.831
55
28.771
16.071
56
30.974
22.774
57
22.453
22.117
58
12.35
23.138
59
21.725
18.944
60
30.419
31.854
61
24.388
18.897
62
19.587
36.974
63
19.943
12.839
64
24.632
15.019
65
5.951
32.233
66
16.918
14.346
67
23.818
6.408
68
19.581
18.447
69
35.191
31.263
70
0.927
21.347
71
32.644
19.464
72
9.487
20.325
73
39.749
21.788
74
18.485
16.27
75
15.581
36.344
76
6.345
20.203
77
13.484
23.21
78
18.527
20.734
79
11.773
20.295
80
19.329
2.663
81
4.471
22.79
82
4.788
27.961
83
27.51
36.612
84
26.306
15.776
85
4.545
25.257
86
23.545
35.892
87
10.746
37.712
88
7.405
6.656
89
12.021
6.684
90
29.14
27.123
91
23.367
29.856
92
14.87
16.629
93
11.961
17.137
94
16.126
18.34
95
22.426
16.075
96
19.729
10.752
97
19.707
7.63
98
23.824
21.511
99
8.257
27.817
100
9.179
24.151


### 4.5. Test Problem #5

This is a large size problem of 125 facilities randomly generated by VIP-PLANOPT 2006. The dimensions of facilities are real numbers between 1 and 6, and elements of the cost matrix are integers between 1 and 10. The distance norm is rectilinear. The results are shown in Table6. GOT obtained the cost function value of 1062080 in 129.6 seconds. This value is about 2% below the cost function value of VIP-PLANOPT 2006. The coordinates of the facilities for the layout obtained by GOT are given in Table 7.Table 6
Results for test problem #5.
Program
Cost function value
VIP-PLANOPT (2006) [8]
1084451
GOT
1062080Table 7
For test problem #5, the coordinates of facilities obtained by GOT are given below. The layout cost is 1062080.
Facility
X
Y
1
28.617
19.513
2
25.371
22.082
3
27.683
32.088
4
6.488
13.531
5
17.53
34.357
6
10.131
16.929
7
29.906
25.226
8
28.243
36.473
9
14.372
31.298
10
37.502
22.299
11
32.586
4.846
12
19.349
13.249
13
3.314
23.588
14
46.96
19.354
15
21.953
8.539
16
34.13
25.537
17
33.636
32.8
18
37.21
17.564
19
12.603
23.713
20
21.763
21.428
21
16.261
37.283
22
27.453
25.185
23
25.213
15.36
24
27.111
41.844
25
21.208
24.959
26
33.287
38.471
27
25.882
19.125
28
43.87
14.147
29
27.342
6.265
30
2.831
26.3
31
18.328
31.432
32
38.33
7.761
33
22.131
27.038
34
7.166
26.77
35
18.909
46.302
36
15.123
34.383
37
28.974
22.602
38
18.728
4.656
39
33.526
8.657
40
12.176
32.318
41
16.539
39.732
42
28.383
39.485
43
15.09
23.899
44
32.571
12.559
45
41.221
40.78
46
24.335
27.843
47
2.516
30.62
48
37.452
25.455
49
40.189
36.294
50
12.672
36.825
51
34.282
27.349
52
19.126
15.005
53
36.395
41.322
54
31.473
40.034
55
30.991
34.983
56
38.702
27.03
57
28.176
12.73
58
29.219
45.218
59
25.113
10.766
60
11.021
27.029
61
22.158
14.239
62
22.543
17.582
63
12.348
21.322
64
13.684
43.96
65
8.569
36.149
66
8.828
33.239
67
10.933
12.373
68
24.203
26.047
69
12.647
7.071
70
29.789
27.362
71
6.492
38.642
72
18.394
17.993
73
4.815
17.754
74
24.465
45.646
75
24.704
24.448
76
48.912
31.164
77
19.063
11.088
78
27.843
16.379
79
35.271
29.217
80
21.659
35.429
81
15.303
28.087
82
32.599
31.07
83
3.311
20.836
84
44.02
33.76
85
43.843
9.862
86
16.694
23.899
87
20.628
17.23
88
19.088
35.563
89
48.998
25.308
90
33.559
46.176
91
31.162
30.86
92
24.82
36.607
93
44.673
24.381
94
18.385
27.694
95
30.086
10.858
96
33.289
15.156
97
30.399
17.188
98
15.52
19.071
99
36.518
32.041
100
19.439
40.84
101
22.932
4.334
102
27.279
28.155
103
31.849
19.046
104
11.48
19.243
105
7.31
21.826
106
38.088
12.744
107
22.892
30.522
108
14.917
13.713
109
6.995
30.065
110
40.466
30.376
111
41.964
19.47
112
30.3
14.954
113
19.953
27.768
114
27.316
2.155
115
35.983
36.293
116
44.374
28.853
117
22.621
41.026
118
31.99
20.775
119
11.309
39.88
120
41.379
24.172
121
31.589
26.996
122
18.031
8.178
123
18.549
22.682
124
31.64
23.551
125
33.452
23.294


## 4.1. Test Problem #1

This problem of 8 facilities was introduced by Imam and Mir [5]. Figure 4 shows the steps for accruing the initial solution. Figure 4(a) shows the flow matrix and dimension of facilities. All dimensions and cost matrix elements are integer-valued numbers ranging between 1 and 6. There are several pairs of facilities with no flow between them. Distance norm is squared Euclidean. The greedy heuristic generates the edges lists of MPG as shown in Figure 4(b).Obtaining an initial solution for test problem #1.
(a)
The raw facilities layout data
(b)
MPG
(c)
Straight line drawing of the MPG
(d)
Initial solutionThe straight line drawing algorithm gives the coordinates of vertices. The drawing is shown in Figure4(c). Then, each vertex is replaced by its correspondent facility. The coordinates are multiplied by maximum dimensions of facilities (width and length), and finally, the initial layout design is shown in Figure 4(d).The solution is improved by the analytical technique. Figure5 shows the final layout. The cost function value for this layout is 752.7, and the running time is 0.4 second. Table 1 shows the results obtained by the other approaches. The best solution for this problem is obtained by VIP-PLANOPT 2006.Table 1
Results for test problem #1.
Program
Cost function value
TOPOPT (Imam and Mir, 1989) [5]
794
VIP-PLANOPT (2006) [8]
692
GOT
752.7Figure 5
Final layout for test problem #1.


## 4.2. Test Problem #2

This problem of 20 unequal area facilities was introduced by Imam and Mir [6]. The data consist of only integer values. The dimensions of the facilities are between 1 and 3. The elements of the cost matrix are integers between 0 and 5. The distance norm is rectilinear. The final layout obtained by GOT is shown in Figure 6. The layout cost is 1302, and the running time is 0.6 second. Table 2 compares the results obtained by GOT with the results available in the literature. VIP-PLANOPT 2006 has the lowest value of the cost function.Table 2
Results for test problem #2.
Program
Best design
Topopt (Mir and Imam, 1989) [5]
1320.72
FLOAT (Imam and Mir, 1993) [6]
1264.94
HOT (Imam and Mir, 2001) [7]
1225.40
VIP-PLANOPT (2006) [8]
1157
GOT
1302Figure 6
Final layout for test problem #2.


## 4.3. Test Problem #3

This is a problem of 50 facilities randomly generated by VIP-PLANOPT 2006. The dimensions of the facilities are decimal numbers between 1 to 6. The elements of the cost matrix are all integers between 1 and 10. The distance norm is Euclidean. The results are shown in Table3. The best published result has a cost of 78224.7, whereas GOT produces a final layout with a cost of 76882.3 only in 15.1 seconds. Figure 7 shows the final layout.Table 3
Results for test problem #3.
Program
Cost function value
HOT (Mir and Imam, 2001) [7]
80794.24
VIP-PLANOPT (2006) [8]
78224.7
GOT
76882.3Figure 7
Final layout for test problem #3.


## 4.4. Test Problem #4

This is a randomly generated large size problem of 100 facilities. The dimensions of the facilities are decimal numbers between 1 and 6. The cost matrix elements are integers between 1 and 10. The distance norm is rectilinear. The results are shown in Table4. GOT obtained the cost function value of 527094.1 in 74.3 seconds. This value is about 2% below the cost function value of VIP-PLANOPT 2006. The coordinates of the facilities for the layout obtained by GOT are given in  Table 5.Table 4
Results for test problem #4.
Program
Cost function value
HOT (Mir and Imam, 2001) [7]
558556.2
VIP-PLANOPT (2006) [8]
538193.1
GOT
527094.1Table 5
For test problem #4, the coordinates of facilities obtained by GOT are given below. The value of the cost function for this layout is 527094.1.
Facility
X
Y
1
17.599
22.158
2
18.514
32.933
3
29.485
18.634
4
35.526
20.582
5
14.798
22.65
6
26.425
25.388
7
12.213
13.282
8
19.435
27.466
9
32.119
15.319
10
24.743
8.862
11
16.231
2.711
12
25.533
17.621
13
14.274
20.352
14
22.791
3.889
15
14.467
14.812
16
38.012
16.94
17
9.735
11.276
18
24.609
27.663
19
20.685
20.578
20
19.866
22.579
21
15.832
8.421
22
8.866
31.495
23
22.402
17.335
24
35.551
9.125
25
16.95
19.378
26
36.104
25.31
27
16.328
21.843
28
13.208
26.161
29
22.439
14.732
30
14.052
13.065
31
28.21
21.934
32
16.436
12.282
33
24.467
11.365
34
23.103
32.489
35
23.283
24.968
36
19.444
14.708
37
32.927
16.699
38
11.708
28.857
39
15.14
29.793
40
28.164
5.174
41
32.08
8.476
42
29.636
13.049
43
26.373
31.127
44
8.693
15.785
45
16.05
26.859
46
31.965
26.099
47
29.361
9.586
48
33.822
12.885
49
19.394
25.043
50
25.902
21.954
51
4.234
16.534
52
19.539
30.211
53
5.587
11.801
54
13.399
32.831
55
28.771
16.071
56
30.974
22.774
57
22.453
22.117
58
12.35
23.138
59
21.725
18.944
60
30.419
31.854
61
24.388
18.897
62
19.587
36.974
63
19.943
12.839
64
24.632
15.019
65
5.951
32.233
66
16.918
14.346
67
23.818
6.408
68
19.581
18.447
69
35.191
31.263
70
0.927
21.347
71
32.644
19.464
72
9.487
20.325
73
39.749
21.788
74
18.485
16.27
75
15.581
36.344
76
6.345
20.203
77
13.484
23.21
78
18.527
20.734
79
11.773
20.295
80
19.329
2.663
81
4.471
22.79
82
4.788
27.961
83
27.51
36.612
84
26.306
15.776
85
4.545
25.257
86
23.545
35.892
87
10.746
37.712
88
7.405
6.656
89
12.021
6.684
90
29.14
27.123
91
23.367
29.856
92
14.87
16.629
93
11.961
17.137
94
16.126
18.34
95
22.426
16.075
96
19.729
10.752
97
19.707
7.63
98
23.824
21.511
99
8.257
27.817
100
9.179
24.151


## 4.5. Test Problem #5

This is a large size problem of 125 facilities randomly generated by VIP-PLANOPT 2006. The dimensions of facilities are real numbers between 1 and 6, and elements of the cost matrix are integers between 1 and 10. The distance norm is rectilinear. The results are shown in Table6. GOT obtained the cost function value of 1062080 in 129.6 seconds. This value is about 2% below the cost function value of VIP-PLANOPT 2006. The coordinates of the facilities for the layout obtained by GOT are given in Table 7.Table 6
Results for test problem #5.
Program
Cost function value
VIP-PLANOPT (2006) [8]
1084451
GOT
1062080Table 7
For test problem #5, the coordinates of facilities obtained by GOT are given below. The layout cost is 1062080.
Facility
X
Y
1
28.617
19.513
2
25.371
22.082
3
27.683
32.088
4
6.488
13.531
5
17.53
34.357
6
10.131
16.929
7
29.906
25.226
8
28.243
36.473
9
14.372
31.298
10
37.502
22.299
11
32.586
4.846
12
19.349
13.249
13
3.314
23.588
14
46.96
19.354
15
21.953
8.539
16
34.13
25.537
17
33.636
32.8
18
37.21
17.564
19
12.603
23.713
20
21.763
21.428
21
16.261
37.283
22
27.453
25.185
23
25.213
15.36
24
27.111
41.844
25
21.208
24.959
26
33.287
38.471
27
25.882
19.125
28
43.87
14.147
29
27.342
6.265
30
2.831
26.3
31
18.328
31.432
32
38.33
7.761
33
22.131
27.038
34
7.166
26.77
35
18.909
46.302
36
15.123
34.383
37
28.974
22.602
38
18.728
4.656
39
33.526
8.657
40
12.176
32.318
41
16.539
39.732
42
28.383
39.485
43
15.09
23.899
44
32.571
12.559
45
41.221
40.78
46
24.335
27.843
47
2.516
30.62
48
37.452
25.455
49
40.189
36.294
50
12.672
36.825
51
34.282
27.349
52
19.126
15.005
53
36.395
41.322
54
31.473
40.034
55
30.991
34.983
56
38.702
27.03
57
28.176
12.73
58
29.219
45.218
59
25.113
10.766
60
11.021
27.029
61
22.158
14.239
62
22.543
17.582
63
12.348
21.322
64
13.684
43.96
65
8.569
36.149
66
8.828
33.239
67
10.933
12.373
68
24.203
26.047
69
12.647
7.071
70
29.789
27.362
71
6.492
38.642
72
18.394
17.993
73
4.815
17.754
74
24.465
45.646
75
24.704
24.448
76
48.912
31.164
77
19.063
11.088
78
27.843
16.379
79
35.271
29.217
80
21.659
35.429
81
15.303
28.087
82
32.599
31.07
83
3.311
20.836
84
44.02
33.76
85
43.843
9.862
86
16.694
23.899
87
20.628
17.23
88
19.088
35.563
89
48.998
25.308
90
33.559
46.176
91
31.162
30.86
92
24.82
36.607
93
44.673
24.381
94
18.385
27.694
95
30.086
10.858
96
33.289
15.156
97
30.399
17.188
98
15.52
19.071
99
36.518
32.041
100
19.439
40.84
101
22.932
4.334
102
27.279
28.155
103
31.849
19.046
104
11.48
19.243
105
7.31
21.826
106
38.088
12.744
107
22.892
30.522
108
14.917
13.713
109
6.995
30.065
110
40.466
30.376
111
41.964
19.47
112
30.3
14.954
113
19.953
27.768
114
27.316
2.155
115
35.983
36.293
116
44.374
28.853
117
22.621
41.026
118
31.99
20.775
119
11.309
39.88
120
41.379
24.172
121
31.589
26.996
122
18.031
8.178
123
18.549
22.682
124
31.64
23.551
125
33.452
23.294


## 5. Comparing GOT Initial Solution with Random Initial Solution

To compare the proposed initial solution (GOT initial solution) with random initial solution, a set of test problems(n=10,11,12,…,100) were generated. The facilities dimensions were 1×1, and flow matrices were randomly generated between 0 and 10. For acquiring a random initial solution, facilities were randomly placed in a (2n − 4) × (n − 2) integer grid. For each test problem, 20 random placements were found. Table 8 shows the value of cost function in GOT initial solution and the best value found by random placements. Figures 8 and 9 shows these results graphically. The results demonstrated significant improvement in cost function.Table 8
The value of cost function in GOT initial solution and the best value of random placements.
n
GOT initial solution
The best random initial solution
10
1945
2437.3
11
2122
2758.5
12
2368
3531.7
13
4919
5764
14
5514
7024
15
5538
7449
16
8116
10287.7
17
8468
12207.5
18
10648
15304
19
13943
19119.3
20
14265
20094
21
17199
22491.2
22
16610
26370
23
22128
30749.2
24
25533
35508
25
27585
37968.4
26
29929
43803.6
27
36255
51850
28
41483
57050.5
29
47543
65109.2
30
57830
73705.8
31
61408
82058.4
32
63687
86436
33
59970
94066.4
34
82721
110195.2
35
76220
104940
36
92426
124186.1
37
95386
125468
38
87532
150060
39
93708
146793.8
40
118266
180538
41
141363
183911
42
104263
195458.7
43
152188
204207.3
44
163529
239253
45
166360
237051.8
46
167002
251049.3
47
189027
290085
48
226097
305900
49
234811
324500.3
50
238855
337198.9
51
264842
358480.5
52
251009
358666.7
53
233805
370262.4
54
298806
404104.4
55
284543
431091.9
56
344755
481656.9
57
371962
493986.4
58
344044
510976
59
375321
503358.9
60
373118
538554.9
61
370817
573555.9
62
457275
628602.9
63
544350
688184.6
64
530408
708518.3
65
502322
690275.2
66
526230
741481.1
67
556568
773325.9
68
639735
867242.4
69
578533
860229.8
70
643592
914437.3
71
589557
893978.8
72
670866
950592.5
73
736669
1058290.5
74
660395
1039023
75
749795
1115704.6
76
835418
1180300
77
727648
1157821.9
78
852689
1147676
79
971135
1273329.8
80
920522
1294614.8
81
882645
1420567
82
1084711
1500037.8
83
1072241
1436365.1
84
1072132
1606669.3
85
1154018
1552139.2
86
1150925
1756302.3
87
1164220
1608156.3
88
1230008
1726587.4
89
1379479
1913688.3
90
1351210
1970899.3
91
1275975
1895126.4
92
1360771
2114230
93
1520228
1969614.1
94
1542740
2125200
95
1581145
2230222.7
96
1640792
2305569.3
97
1486796
2362639.4
98
1645889
2365109.3
99
1607866
2490733.7
100
2073979
2635666.4Figure 8
Comparisons of cost function value in GOT initial solution with the best value of random placements.Figure 9
Cost reduction by using GOT.


## 6. Summary and Conclusion

An initial solution has been presented for the layout design of facilities on a continuous plane. The technique consists of two stages. In the first stage, a maximal planar graph (MPG) is obtained. In the second stage, the vertices of MPG are drawn on the plane by graph drawing algorithms. Then, vertices are replaced by facilities. Hence, an initial solution is obtained. To evaluate the performance, this initial solution has been applied in rectangular facility layout problem and improved by an analytical method by Mir and Imam [7].The approach has been tested on five instances from the literature. Table6 shows the Summary of the results, and Figure 8 shows the cost reduction by the technique. For the large size problems involving 50, 100, and 125 facilities, the layout costs values are better than those obtained by the previously published techniques. As shown in Table 9, the results demonstrate effectiveness of the technique, especially for large size problems.Table 9
Summary of the results.
Problem
Number of facilities
Best result by other methods
GOT
Cost reduction
#1
8
692.5
752.7
−60.2
#2
20
1157
1302
−145
#3
50
78224.7
76882.3
1342.4
#4
100
538193.1
527094.1
11099
#5
125
1084451
1062080
22371This paper introduced a simple technique for obtaining a good initial solution. The technique, with some modification, can be applied in facility layout approaches that use a randomly generated initial solution. In future researches, it would be interesting to analyze the influence of MPG and graph drawing algorithm on the solution. The results can be further improved by using a metaheuristic such as GRASP [21] and Tabu search [20] for generating a high weighted MPG.



---

*Source: 130251-2013-10-24.xml*