# A Fast Algorithm to Generate Feasible Solution of Production Facilities Layout Based on Plane Segmentation

Authors: Shi-wang Hou; Zhibin Li; Hui Wang
Journal: Mathematical Problems in Engineering
 (2016)

---

## Abstract

For facility layout problem with continuous block and unequal area, it is key to generate feasible solution of facility layout with arbitrary space form in order to find the optimal arrangement scheme under a given goal. According to the given slicing position and slicing mode, the plane for arrangement was divided into many block areas by use of plane segmentation, which was consistent with the facilities in number. The precise coordinates of the lower-left corner and the top-right corner of each facility were calculated in light of its area, width, and length. The corresponding algorithm was designed in the form of pseudocode. The procedure proposed can provide a feasible facility layout solution. The running results of facilities layout instance containing 14 facilities show that the scheme can output facilities plane layout scheme quickly and provide decision support for the facilities planning.


---

## Body

## 1. Introduction

Layout design is an important content of facilities planning and design, mainly to deal with the relative position and area of various kinds of functional facilities (i.e., production or service units) as well as their relevant auxiliary facilities in order to make work flow (customers or materials) and information flow unblocked [1]. The concrete content includes the following two aspects: determination of relative position of all facilities and area of each facility. The former refers to the location relationship between different facilities and the latter refers to the size of each facility. Facilities layout solves the space allocation problem in production and operation and its purpose is to make effective combination of all facilities and obtain the maximum economic benefit. If the facility layout is unreasonable, that is, there are many invalid handling or moving or complex working sites and workshop channels, long distance and high cost handling, long time waiting, and poor production balance, the overall operating efficiency of the production system can be affected greatly [2].Suppose all facilities’ area is equal and only consider the location of the relationship between facilities; facilities layout problem (FLP) is ascribed to quadratic assignment problem (QAP) [3, 4]. By doing so, FLP is simplified to allocate n facilities to n discrete points without considering the location coordinates for multirow and multicolumn FLP. But this supposition is hard to meet in real production system and the application of this method is limited. A lot of FLPs are for multiple continuous blocks with unequal area as pointed out in [2]. As a special case, single row FLP considers one-dimensional linear array arrangement of rectangular facilities. In this case, all facilities are arranged in the same line in spite of the consideration of different area of every facility, so the generation of feasible solution and the implementation of algorithm are relatively easy [5–11].Double row layout is widely adapted in flexible manufacturing system [12–17] to facilitate automatic guided vehicles conveying material. The complexity on feasible solution generation was also greatly reduced by limiting the facilities to double line.Taking facility layout objective function as criterion, the optimal facility layout approach can be found by selecting the arrangement form freely rather than by limiting its form as single, double, or multiline artificially [18]. But that will greatly expand the feasible solution space of facilities layout. So the key to search the optimal layout approach combined with heuristic intelligent algorithm is to generate the feasible solution quickly.This paper is organized as follows. Section2 introduces the principle of plane segmentation method for facility layout. Section 3 describes the layout step of plane segmentation method and the pseudocode of the realizing algorithm. Section 4 describes an application case containing 14 facilities, verification test in Matlab environment, and some of the evaluation results of this method. Finally, Section 5 concludes with a discussion of the paper.


## 2. The Principle of Plane Segmentation Method for Facility Layout

Suppose vectorF
=
{
f
1
,
f
2
,
…
,
f
n
} is a collection of facilities waiting for layout; vector S
O
=
{
1,2
,
…
,
n
-
1
} is a collection of splitting positions for each plane splitting operation; vector S
P
=
{
s
1
,
s
2
,
…
,
s
n
-
1
} is a collection of splitting modes, where n denotes the facility number and s
i
=
0 or 1 (i
=
1,2
,
…
,
n
-
1).In each plane splitting operation, the relationship between vectorsF, S
O, and S
P is shown in Figure 1.Figure 1
Relationship between vectorsF, S
O, and S
P.In actual splitting operation, the element in vectorsF
,
S
O, and S
P can be any permutation within their respective values that an element may take. For a vector F with given element order, there is a splitting position between every two adjacent elements. From left to right, the splitting position randomly ranges from 1 to (n
-
1), respectively, and forms the splitting position vector S
O. For a vector S
O with given element order, there is a splitting mode for every element. From left to right, the splitting mode takes the value 1 or 0, respectively, and forms the splitting position vector S
P. According to the splitting position value of each element in S
P, vector F is partitioned into two parts, left and right. The value in vector S
P corresponding to the splitting position value determines the plane splitting mode, and 0 and 1 denote splitting vertically and horizontally, respectively.Taking a FLP with 6 facilities as an example, the above approach can be described in Figures2 and 3. Here, F
=
{
f
1
,
f
2
,
…
,
f
6
}, S
O
=
{
3,2
,
4,1
,
5
}, and S
P
=
{
1,0
,
1,1
,
0
}.Figure 2
Set partitioning diagram.Figure 3
Plane segmenting process including 6 facilities.


## 3. The Realization of Plane Partition Method of Facility Layout

### 3.1. Determination of Left Sets
e
t
L and Right Set s
e
t
R for Each Partitioning Operation

Step 1.
Find the maximum of existing splitting positionS
O
_
m
a
x.Step 2.
Find the minimum of existing splitting positionS
O
_
m
i
n.Step 3.
In accordance with the relationship between the current splitting positionS
O
_
c
u
r, S
O
_
m
a
x, and S
O
_
m
i
n, new left set s
e
t
L and right set s
e
t
R are determined as follows:(i)
IfS
O
_
c
u
r
<
S
O
_
m
i
n, in this case, the current splitting position S
O
_
c
u
r lies in existing s
e
t
L where S
O
_
m
i
n was found before. This operation partitions this s
e
t
L into two parts, that is, new s
e
t
L and s
e
t
R.
(ii)
IfS
O
_
c
u
r
>
S
O
_
m
a
x, the current splitting position S
O
_
c
u
r lies in the existing s
e
t
R where S
O
_
m
a
x was found before. This operation partitions this s
e
t
R into two parts, that is, new s
e
t
L and s
e
t
R.
(iii)
IfS
O
(
i
)
<
S
O
_
c
u
r
<
S
O
(
j
), here, S
O
(
i
) denotes the maximum of existing splitting position less than S
O
_
c
u
r and S
O
(
j
) denotes the minimum of existing splitting position greater than S
O
_
c
u
r. The completion order of splitting operation corresponding to the splitting positions S
O
(
i
) and S
O
(
j
) affects the object of this partition. If S
O
(
i
) splitting was carried out later than S
O
(
i
), that is, i
>
j, the right set resulting from S
O
(
i
) splitting was going to be partitioned. Similarly, if S
O
(
i
) splitting was carried out earlier than S
O
(
i
), that is, i
<
j, the left set resulting from S
O
(
j
) splitting was going to be partitioned.This paper defines two structures to record the information of splitting position and its results, setss
e
t
L and s
e
t
R; that is, s
e
t
L = struct(“splitting position”, {
}, “left set”, {
}) and s
e
t
R = struct(“splitting position”, {
}, “right set”, {
}).The process to determine the setss
e
t
L and s
e
t
R of every splitting operation is shown in Algorithm 1.Algorithm 1:Process to determine the left and right set for given splitting position.
Procedure  d
e
t
e
r
m
i
n
a
t
i
o
n
o
f
s
e
t
L
a
n
d
s
e
t
R  (N is the  cardinality of facility set F,  cso is position set that have been split)
(1)    s
e
t
L
(
1
)
←
s
t
r
u
c
t(“splitting position”, 0, “left set”, ); % Initialize the first left set with empty set
(2)    s
e
t
R
(
1
)
←
s
t
r
u
c
t(“splitting position”, 0, “right set”, F); % Initialize the first right set with set F
(3)    for i
←
1 To N
(4)      [
m
a
x
c
s
o
,
i
x
_
m
a
x
]
←
max
⁡
(
c
s
o
);
(5)      [
m
i
n
c
s
o
,
i
x
_
m
i
n
]
←
min
⁡
(
c
s
o
);
(6)      t
e
m
p
1
←
max
⁡
(
i
n
d
e
x
(
S
O
(
i
)
>
c
s
o
)
);
(7)      t
e
m
p
2
←
min
⁡
(
i
n
d
e
x
(
S
O
(
i
)
<
c
s
o
)
);
(8)      if  S
O
(
i
)
>
c
s
o
(
i
x
_
m
a
x
)
(9)       s
e
t
L
(
i
)
←
s
t
r
u
c
t(“splitting position”, S
O
(
i
), “left set”,
setR(i
x_max).right set(1: S
O
(
i
)-m
a
x
c
s
o));
(1
0)    s
e
t
R
(
i
)
←
s
t
r
u
c
t(“splitting position”, S
O
(
i
), “right set”,
setR(i
x_max).right set(S
O(i-m
a
x
c
s
o): end));
(11)   elseif S
O
(
i
)
<
c
s
o
(
i
x
_
m
i
n
)
(12)    s
e
t
L
(
i
)
←
s
t
r
u
c
t(“splitting position”,  S
O
(
i
),  “left set”,
setL(i
x_min).left set(1: S
O
(
i
)));
(13)    s
e
t
R
(
i
)
←
s
t
r
u
c
t(“splitting position”,  S
O
(
i
),  “right set”,
setL(i
x_min).left set((S
O
(
i
) + 1): end));
(14)   elseif c
s
o
(
t
e
m
p
1
)
<
s
(
i
)
<
c
s
o
(
t
e
m
p
2
)
(15)    if t
e
m
p
1
>
t
e
m
p
2
(16)     s
e
t
L
(
i
)
←
s
t
r
u
c
t(“splitting position”, S
O
(
i
), “left set”,
setR(temp1).right set(1:  S
O(i)-cso(temp1)));
(17)     s
e
t
R
(
i
)
←
s
t
r
u
c
t(“splitting position”, S
O
(
i
), “left set”,
setR(temp1).right set((s
(
i
)-cso(temp1) + 1): end));
(18)    elseif t
e
m
p
1
<
t
e
m
p
2
(19)     i
x
←
l
e
n
g
t
h(s
e
t
L(temp2).left set);
(20)     s
e
t
L
(
i
)
←
s
t
r
u
c
t(“splitting position”, S
O
(
i
), “left set”,
setL(temp2).left set(1: i
x-cso(temp2) + S
O
(
i
)));
(21)     s
e
t
R
(
i
)
←
s
t
r
u
c
t(“splitting position”, S
O
(
i
), “right set”,
setL(temp2).left set((i
x-cso(temp2) + S
O
(
i
) + 1): end));
(22)    end if
(23)   end if
(24)  end forThe partition task in Figure2 was completed using the above approach and the results are shown in Table 1. After repeating the operation 5 times, the facility set was partitioned into 5 sets, each of which contained only one element. At the same time, the plane was also partitioned into 5 blocks, each of which was for arranging a facility.Table 1
Results of set partitioning.
Splitting position
3
2
4
1
5
Left set
f
1
,
f
2
,
f
3
f
1
,
f
2
f
4
f
1
f
5
Right set
f
4
,
f
5
,
f
6
f
3
f
5
,
f
6
f
2
f
6


### 3.2. Coordinates Determination of the First Splitting Line

Before the first splitting operation, the layout area was empty and no facility was arranged. The coordinates of the lower-left corner and upper-right corner of the layout plane were denoted byO
(
0,0
) and O
′
(
∑
h
i
,
∑
v
i
), where h
i and v
i were the horizontal width and the vertical height of facility i, respectively. The coordinates of the upper-right corner were the extreme value when all the facilities were arranged side by side horizontally or vertically. The plane was firstly split according to the value of S
P
(
1
). The splitting line was denoted by L
i
1
L
i
2, where the first subscript i
=
1,2
,
…
,
n
-
1 shows the splitting position and the second subscript taking value of 1 or 2 means the start point or end point of splitting line. The line direction is from left to right for horizontal line and from bottom to top for vertical line.(i)
S
P
(
1
)
=
0. In this case, the first line is a horizontal one partitioning the layout area into two parts, upper and lower. The facilities of vector F on the left of splitting point S
O
(
1
), that is, s
e
t
L
(
1
)
.
leftset, were included in the lower part. The facilities of vector F on the right of S
O
(
1
), that is, s
e
t
R
(
1
)
.
rightset, were included in the upper part. The first line was denoted by L
S
O
(
1
)
1
(
0
,
∑
i
∈
s
e
t
L
(
1
)
.
l
e
f
t
s
e
t
v
i
), L
S
O
(
1
)
2
(
∑
h
i
,
∑
i
∈
s
e
t
L
(
1
)
.
l
e
f
t
s
e
t
v
i
).(ii)
S
P
(
1
)
=
1. When S
P
(
1
)
=
1, the first line L
S
O
(
1
)
1
L
S
O
(
1
)
2 is vertical and can be determined by L
S
O
(
1
)
1
(
∑
i
∈
s
e
t
L
(
1
)
.
l
e
f
t
s
e
t
h
i
,
0
), L
S
O
(
1
)
2
(
∑
i
∈
s
e
t
L
(
1
)
.
l
e
f
t
s
e
t
h
i
,
∑
v
i
).As shown in Algorithm2, the first line can be drawn by connecting the point (hlin_start(1), hlin_y(1)) and point (hlin_end(1), hlin_y(1)). As a result, the layout area was partitioned into two parts.Algorithm 2:Coordinate determination of the first line.
Procedure  D
r
a
w
i
n
g
t
h
e
f
i
r
s
t
s
p
l
i
t
t
i
n
g
l
i
n
e (F, S
P, s
e
t
L, s
e
t
R, L
W, L
H)
(1)    [
t
f
,
i
n
d
e
x
]
←
s
e
t
L
(
1
).elements and their index in F;
(2)    if  S
P
(
1
)
=
0
(3)     h
l
i
n
_
s
t
a
r
t
(
1
)
←
0;  %  x-coordinate of  horizontal line start point
(4)     h
l
i
n
_
e
n
d
(
1
)
←
s
u
m
(
L
W
); %  x-coordinate of  horizontal line end point
(5)     h
l
i
n
_
y
(
1
)
←
s
u
m
(
L
H
(
F
(
i
n
d
e
x
)
)
); %  y-coordinate of  horizontal line
(6)    elseif  S
P
(
1
)
=
1
(7)     v
l
i
n
_
s
t
a
r
t
(
1
)
←
0;
(8)     vlin_end(
1
)
←
s
u
m(L
H);
(9)     vlin_x
(
1
)
←
s
u
m(L
W(F(index)));;
(10)   end if
(11)   Connect point (hlin_start(1), hlin_y(1)) and (hlin_end(1), hlin_y(1))


### 3.3. Coordinates Determination of the Second and Subsequent Splitting Line

From the second splitting operation, inclusion relations between the left set obtained in current operation and the left set and right set obtained before were determined. For the set including the current left set, its maximum of the structure attribute SO is recorded. LetJ
1 be the index of maximum SO in left set and let J
2 be the index of maximum SO in right set.(I) If the current splitting mode is horizontal, that is,S
P
(
i
)
=
0
,
i
≥
2, the splitting line of current operation has the following cases according to the value of J
1 and J
2.(i) ConsiderJ
1
≠
0, J
2
=
0. In this case, the left set obtained in current operation was included by only one existing left set. The determination of splitting line according to the value of S
P
(
J
1
) was as shown in Figure 4.Figure 4
Case of current left set only belonging to some existing left set.
(a)
S
P
(
J
1
)
=
0
(b)
S
P
(
J
1
)
=
1As shown in Figure4(a), when S
P
(
J
1
)
=
0, the corresponding existing splitting line was a horizontal line L
S
O
(
J
1
)
1
L
S
O
(
J
1
)
2, below which the current line L
S
O
(
i
)
1
L
S
O
(
i
)
2 was drawn horizontally, where L
S
O
(
i
)
1
(
x
_
L
S
O
(
J
1
)
1
,
∑
j
∈
s
e
t
L
(
i
)
.
l
e
f
t
s
e
t
v
j
), L
S
O
(
i
)
2
(
x
_
L
S
O
(
i
)
2
,
y
_
L
S
O
(
i
)
1
); Figure 4(b) shows the other case of S
P
(
J
1
)
=
1. The corresponding existing splitting line L
S
O
(
J
1
)
1
L
S
O
(
J
1
)
2 was vertical, on the left side of which the current line L
S
O
(
i
)
1
L
S
O
(
i
)
2 was drawn, where L
S
O
(
i
)
1
(
0
,
∑
j
∈
s
e
t
L
(
i
)
.
l
e
f
t
s
e
t
v
j
), L
S
O
(
i
)
2
(
x
_
L
S
O
(
J
1
)
1
,
y
_
L
S
O
(
i
)
1
).(ii) ConsiderJ
1
=
0, J
2
≠
0. In this case, the left set obtained in current operation was included by only one existing right set. The determination of splitting line according to the value of S
P
(
J
2
) was as shown in Figure 5.Figure 5
Case of current left set only belonging to some existing right set.
(a)
S
P
(
J
2
)
=
0
(b)
S
P
(
J
2
)
=
1As shown in Figure5(a), when S
P
(
J
2
)
=
0, the corresponding existing splitting line was a horizontal line L
S
O
(
J
2
)
1
L
S
O
(
J
2
)
2, above which the current line L
S
O
(
i
)
1
L
S
O
(
i
)
2 was drawn, where L
S
O
(
i
)
1
(
x
_
L
S
O
(
J
2
)
1
,
y
_
L
S
O
(
J
2
)
1
+
∑
j
∈
s
e
t
L
(
i
)
.
l
e
f
t
s
e
t
v
j
), L
S
O
(
i
)
2
(
x
_
L
S
O
(
J
2
)
2
,
y
_
L
S
O
(
i
)
1
); Figure 5(b) shows the other case of S
P
(
J
2
)
=
1. The corresponding existing splitting line L
S
O
(
J
1
)
1
L
S
O
(
J
1
)
2 was vertical, on the right side of which the current line L
S
O
(
i
)
1
L
S
O
(
i
)
2 was drawn, where L
S
O
(
i
)
1
(
x
_
L
S
O
(
J
2
)
1
,
∑
j
∈
s
e
t
L
(
i
)
.
l
e
f
t
s
e
t
v
j
), L
S
O
(
i
)
2
(
∑
h
i
,
y
_
L
S
O
(
i
)
1
).(iii) ConsiderJ
1
≠
0, J
2
≠
0. In this case, the left set obtained in current operation belonged to both some existing right set and some existing left set. The determination of splitting line according to the value of S
P
(
J
2
) and S
P
(
J
1
) was as shown in Figure 6.Figure 6
Case of current left set belonging to both some existing right set and some existing left set.
(a)
S
P
(
J
1
)
=
0, S
P
(
J
2
)
=
0
(b)
S
P
(
J
1
)
=
1, S
P
(
J
2
)
=
0
(c)
S
P
(
J
1
)
=
0, S
P
(
J
2
)
=
1
(d)
S
P
(
J
1
)
=
1, S
P
(
J
2
)
=
1As shown in Figure6(a), when S
P
(
J
1
)
=
0 and S
P
(
J
2
)
=
0, the corresponding two existing splitting lines were L
S
O
(
J
1
)
1
L
S
O
(
J
1
)
2 and L
S
O
(
J
2
)
1
L
S
O
(
J
2
)
2, and they were horizontal. The current line L
S
O
(
i
)
1
L
S
O
(
i
)
2 was drawn above the line L
S
P
(
J
2
)
1
L
S
P
(
J
2
)
2 and below the line L
S
O
(
J
1
)
1
L
S
O
(
J
1
)
2, where L
S
O
(
i
)
1
(
x
_
L
S
O
(
J
2
)
1
,
y
_
L
S
O
(
J
2
)
1
+
∑
j
∈
s
e
t
L
(
i
)
.
l
e
f
t
s
e
t
v
j
), L
S
O
(
i
)
2
(
x
_
L
S
O
(
J
2
)
2
,
y
_
L
S
O
(
i
)
1
); in Figure 6(b), when  S
P
(
J
1
)
=
1 and S
P
(
J
2
)
=
0, L
S
O
(
i
)
1
L
S
O
(
i
)
2 was drawn above the existing horizontal line L
S
O
(
J
1
)
1
L
S
O
(
J
1
)
2 and on the left side of existing vertical line L
S
O
(
J
2
)
1
L
S
O
(
J
2
)
2, where L
S
O
(
i
)
1
(
x
_
L
S
O
(
J
2
)
1
,
y
_
L
S
O
(
J
2
)
1
+
∑
j
∈
s
e
t
L
(
i
)
.
l
e
f
t
s
e
t
v
j
), L
S
O
(
i
)
2
(
x
_
L
S
O
(
J
2
)
2
,
y
_
L
S
O
(
J
1
)
1
); in Figure 6(c), when  S
P
(
J
1
)
=
0 and S
P
(
J
2
)
=
1, L
S
O
(
i
)
1
L
S
O
(
i
)
2 was drawn below the existing horizontal line L
S
O
(
J
1
)
1
L
S
O
(
J
1
)
2 and on the right side of existing vertical line L
S
O
(
J
2
)
1
L
S
O
(
J
2
)
2, where L
S
O
(
i
)
1
(
x
_
L
S
O
(
J
2
)
1
,
y
_
L
S
O
(
J
2
)
1
+
∑
j
∈
s
e
t
L
(
i
)
.
l
e
f
t
s
e
t
v
j
), L
S
O
(
i
)
2
(
x
_
L
S
O
(
J
1
)
2
,
y
_
L
S
O
(
i
)
1
); in Figure 6(d), when  S
P
(
J
1
)
=
1 and S
P
(
J
2
)
=
1, L
S
O
(
i
)
1
L
S
O
(
i
)
2 was drawn between the left side of the existing vertical line L
S
O
(
J
1
)
1
L
S
O
(
J
1
)
2 and the right side of existing vertical line L
S
O
(
J
2
)
1
L
S
O
(
J
2
)
2, where L
S
O
(
i
)
1
(
x
_
L
S
O
(
J
2
)
1
,
y
_
L
S
O
(
J
2
)
1
+
∑
j
∈
s
e
t
L
(
i
)
.
l
e
f
t
s
e
t
v
j
), L
S
O
(
i
)
2
(
x
_
L
S
O
(
J
1
)
1
,
y
_
L
S
O
(
i
)
1
).The above approach to determine the line coordinates and to draw the line was shown as the pseudocode in Algorithm3.Algorithm 3:Process of line coordinates determination.
Procedure  D
r
a
w
i
n
g
t
h
e
s
e
c
o
n
d
a
n
d
s
u
b
s
e
q
u
e
n
t
s
p
l
i
t
t
i
n
g
l
i
n
e  (F, S
P, s
e
t
L, s
e
t
R, L
W, L
H)
(1)    for i
←
2 TO N
-
1
(2)     J
1
←
0; J
2
←
0;
(3)     for  j
=
1 TO i
-
1
(4)      if s
e
t
L
(
i
).left s
e
t
⊂
s
e
t
L
(
j
).left set  &  j
>
J
1
(5)       J
1
←
j
(6)      elseif s
e
t
L
(
i
).left  s
e
t
⊂
s
e
t
L
(
j
).right set  &  j
>
J
2
(7)       J
2
←
j
(8)      end if
(9)     end for
(10)  [
t
f
,
i
n
d
e
x
]
←
s
e
t
L
(
i
).elements and their index in F;
(11)  if  J
1
~
=
0
&
J
2
=
0
(12)   if S
P
(
J
1
)
=
0
(13)    h
l
i
n
_
s
t
a
r
t
(
i
)
←
h
l
i
n
_
s
t
a
r
t
(
J
1
);    h
l
i
n
_
e
n
d
(
i
)
←
h
l
i
n
_
e
n
d
(
J
1
);
(14)    h
l
i
n
_
y
(
i
)
←
s
u
m(L
H(F(index)));
(15)   elseif S
P
(
J
1
)
=
1
(16)    h
l
i
n
_
s
t
a
r
t
(
i
)
←
0;   h
l
i
n
_
e
n
d
(
i
)
←
v
l
i
n
_
x
(
J
1
);
(17)    h
l
i
n
_
y
(
i
)
←
s
u
m(L
H(F(index)));
(18)   end if
(19)  elseif J
1
=
0
&
J
2
~
=
0
(20)   if S
P
(
J
2
)
=
0
(21)    hlin_start(
i
)
←
hlin_start(J
2);   hlin_end(
i
)
←
hlin_end(J
2);  hlin_y
(
i
)
←
hlin_y
(
J
2
) + sum(L
H(F(index)));
(2
2)   elseif S
P
(
J
2
)
=
1
(2
3)    hlin_start(
i
)
←
vlin_x
(
J
2
);    hlin_end(
i
)
←
s
u
m(L
W);       hlin_y
(
i
)
←
vlin_start(J
2) + sum(L
H(F(index)));
(2
4)   end if
(2
5)  elseif J
1
~
=
0  &  J
2
~
=
0
(2
6)   if S
P
(
J
1
)
=
0  &  S
P
(
J
2
)
=
0
(2
7)    hlin_start(
i
)
←
hlin_start(J
2);    hlin_end(
i
)
←
hlin_end(J
2);  hlin_y
(
i
)
←
hlin_y
(
J
2
) + sum(L
H(F(index)));
(28)   elseif S
P(J
1) = 1  &  S
P(J
2) = 0
(29)    hlin_start(
i
)
←
hlin_start(J
2);   hlin_end(
i
)
←
vlin_end(J
1);  hlin_y
(
i
)
←
hlin_y
(
J
2
) + sum(L
H(F(index)));
(30)   elseif S
P(J
1) = 0  &  S
P(J
2) = 1
(3
1)    hlin_start(
i
)
←
vlin_x(J
2);     hlin_end(
i
)
←
hlin_end(J
1);  hlin_y
(
i
)
←
vlin_start(J
2) + sum(L
H(F(index)));
(3
2)   elseif S
P(J
1) = 1  &  S
P(J
2) = 1
(3
3)    hlin_start(
i
)
←
vlin_x(J
2);    hlin_end(
i
)
←
vlin_x
(
J
1
);      hlin_y
(
i
)
←
vlin_start(J
2) + sum(L
H(F(index)));
(3
4)   end if
(3
5)  end if
(3
6)  Connect point (hlin_start(i), hlin_y(i)) and point (hlin_end(i), hlin_y(i))
(3
7)      end for(II) If the current splitting mode is horizontal, that is,S
P
(
i
)
=
1
,
i
≥
2, the splitting line of current operation has the following cases according to the value of J
1 and J
2.(i) ConsiderJ
1
≠
0, J
2
=
0. In this case, the left set obtained in current operation belonged to only one existing left set. The determination of splitting line according to the value of S
P
(
J
1
) was as shown in Figure 7.Figure 7
Case of current left set only belonging to some existing left set whenS
P
(
i
)
=
1
,
i
≥
2.
(a)
S
P
(
J
1
)
=
0
(b)
S
P
(
J
1
)
=
1As shown in Figure7(a), when S
P
(
J
1
)
=
0, the corresponding existing splitting line was a horizontal line L
S
O
(
J
1
)
1
L
S
O
(
J
1
)
2, below which the current line L
S
O
(
i
)
1
L
S
O
(
i
)
2 was drawn vertically, where L
S
O
(
i
)
1
(
x
_
L
S
O
(
J
1
)
1
+
∑
j
∈
s
e
t
L
(
i
)
.
l
e
f
t
s
e
t
v
j
,
0
), L
S
O
(
i
)
2
(
x
_
L
S
O
(
i
)
1
,
y
_
L
S
O
(
J
1
)
1
); Figure 7(b) showed the other case of S
P
(
J
1
)
=
1. The corresponding existing splitting line L
S
O
(
J
1
)
1
L
S
O
(
J
1
)
2 was vertical, on the left side of which the current line L
S
O
(
i
)
1
L
S
O
(
i
)
2 was drawn, where L
S
O
(
i
)
1
(
∑
j
∈
s
e
t
L
(
i
)
.
l
e
f
t
s
e
t
v
j
,
y
_
L
S
O
(
J
1
)
1
),     L
S
O
(
i
)
2
(
x
_
L
S
O
(
i
)
1
,
y
_
L
S
O
(
J
1
)
2
).(ii) ConsiderJ
1
=
0
,
J
2
≠
0. In this case, the left set obtained in current operation belonged to only one existing right set. The determination of splitting line according to the value of S
P
(
J
2
) was as shown in Figure 8.Figure 8
Case of current left set only belonging to some existing right set whenS
P
(
i
)
=
1
,
i
≥
2.
(a)
S
P
(
J
2
)
=
0
(b)
S
P
(
J
2
)
=
1As shown in Figure8(a), when S
P
(
J
2
)
=
0, the corresponding existing splitting line was a horizontal line L
S
O
(
J
2
)
1
L
S
O
(
J
2
)
2, above which the current line L
S
O
(
i
)
1
L
S
O
(
i
)
2 was drawn vertically, where L
S
O
(
i
)
1
(
x
_
L
S
O
(
J
2
)
1
+
∑
j
∈
s
e
t
L
(
i
)
.
l
e
f
t
s
e
t
v
j
,
0
), L
S
O
(
i
)
2
(
x
_
L
S
O
(
i
)
1
,
∑
v
i
); Figure 8(b) showed the other case of S
P
(
J
2
)
=
1. The corresponding existing splitting line L
S
O
(
J
2
)
1
L
S
O
(
J
2
)
2 was vertical, on the left side of which the current line L
S
O
(
i
)
1
L
S
O
(
i
)
2 was drawn, where L
S
O
(
i
)
1
(
x
_
L
S
O
(
J
2
)
1
+
∑
j
∈
s
e
t
L
(
i
)
.
l
e
f
t
s
e
t
v
j
,
y
_
L
S
O
(
J
2
)
1
), L
S
O
(
i
)
2
(
x
_
L
S
O
(
i
)
1
,
y
_
L
S
O
(
J
1
)
2
).(iii) ConsiderJ
1
≠
0, J
2
≠
0. In this case, the left set obtained in current operation belonged to both one existing right set and one existing left set. The determination of splitting line according to the value of S
P
(
J
1
) and S
P
(
J
2
) was as shown in Figure 9.Figure 9
Case of current left set belonging to both some existing right set and some existing left set,S
P
(
i
)
=
1
,
i
≥
2.
(a)
S
P
(
J
1
)
=
0, S
P
(
J
2
)
=
0
(b)
S
P
(
J
1
)
=
1, S
P
(
J
2
)
=
0
(c)
S
P
(
J
1
)
=
0, S
P
(
J
2
)
=
1
(d)
S
P
(
J
1
)
=
1, S
P
(
J
2
)
=
1As shown in Figure9(a), when S
P
(
J
1
)
=
0 and S
P
(
J
2
)
=
0, the corresponding two existing splitting lines were L
S
O
(
J
1
)
1
L
S
O
(
J
1
)
2 and L
S
O
(
J
2
)
1
L
S
O
(
J
2
)
2, and they were horizontal. The current line L
S
O
(
i
)
1
L
S
O
(
i
)
2 was drawn between line L
S
P
(
J
2
)
1
L
S
P
(
J
2
)
2 and line L
S
O
(
J
1
)
1
L
S
O
(
J
1
)
2, where L
S
O
(
i
)
1
(
x
_
L
S
O
(
J
2
)
1
+
∑
j
∈
s
e
t
L
(
i
)
.
l
e
f
t
s
e
t
h
j
,
y
_
L
S
O
(
J
2
)
1
), L
S
O
(
i
)
2
(
x
_
L
S
O
(
i
)
1
,
y
_
L
S
O
(
J
1
)
1
); in Figure 9(b), when  S
P
(
J
1
)
=
1 and S
P
(
J
2
)
=
0, L
S
O
(
i
)
1
L
S
O
(
i
)
2 was drawn above the existing horizontal line L
S
O
(
J
1
)
1
L
S
O
(
J
1
)
2 and on the left side of existing vertical line L
S
O
(
J
2
)
1
L
S
O
(
J
2
)
2, where L
S
O
(
i
)
1
(
x
_
L
S
O
(
J
2
)
1
+
∑
j
∈
s
e
t
L
(
i
)
.
l
e
f
t
s
e
t
h
j
,
y
_
L
S
O
(
J
2
)
1
), L
S
O
(
i
)
2
(
x
_
L
S
O
(
i
)
1
,
y
_
L
S
O
(
J
1
)
2
); in Figure 9(c),  when  S
P
(
J
1
)
=
0 and S
P
(
J
2
)
=
1, L
S
O
(
i
)
1
L
S
O
(
i
)
2 was drawn below the existing horizontal line L
S
O
(
J
1
)
1
L
S
O
(
J
1
)
2 and on the right side of existing vertical line L
S
O
(
J
2
)
1
L
S
O
(
J
2
)
2, where L
S
O
(
i
)
1
(
x
_
L
S
O
(
J
2
)
1
+
∑
j
∈
s
e
t
L
(
i
)
.
l
e
f
t
s
e
t
h
j
,
y
_
L
S
O
(
J
2
)
1
), L
S
O
(
i
)
2
(
x
_
L
S
O
(
i
)
1
,
y
_
L
S
O
(
J
1
)
1
); in Figure 9(d), when   S
P
(
J
1
)
=
1 and S
P
(
J
2
)
=
1, L
S
O
(
i
)
1
L
S
O
(
i
)
2 was drawn between the left side of the existing vertical line L
S
O
(
J
1
)
1
L
S
O
(
J
1
)
2 and the right side of existing vertical line L
S
O
(
J
2
)
1
L
S
O
(
J
2
)
2, where L
S
O
(
i
)
1
(
x
_
L
S
O
(
J
2
)
1
+
∑
j
∈
s
e
t
L
(
i
)
.
l
e
f
t
s
e
t
h
j
,
y
_
L
S
O
(
J
2
)
1
), L
S
O
(
i
)
2
(
x
_
L
S
O
(
i
)
1
,
y
_
L
S
O
(
J
1
)
2
).For the case ofS
P
(
i
)
=
1
,
i
≥
2, the pseudocode to realize the above approach can be achieved by replacing hlin_start(
i
), hlin_end(
i
), and hlin_y
(
i
) in Figure 5 with vlin_start(
i
), vlin_end(
i
), and vlin_x
(
i
), respectively. The coordinate values of each splitting line can be determined according to Figures 7~9.Plane segmentation process is to determine facilities relative position in the layout area. For the aforementioned FLP with 6 facilities (as shown in Figure3), the process of plane splitting and splitting line coordinate determining can be described as follows.The initial layout area was a plane determined by the lower-left cornerO
(
0,0
) and top-right corner O
′
(
∑
h
i
,
∑
v
i
). For the first splitting operation, the vertical splitting line L
31
L
32, L
31
(
∑
i
=
1,2
,
3
h
i
,
0
), L
32
(
∑
i
=
1,2
,
3
h
i
,
∑
v
i
), divided the initial layout area into two parts, left and right side. The left was for facilities 1, 2, and 3, and the right was for facilities 4, 5, and 6. The second splitting line L
21
L
22, L
21
(
0
,
∑
i
=
1,2
v
i
), L
22
(
∑
i
=
1,2
,
3
h
i
,
∑
i
=
1,2
v
i
), was horizontal and partitioned the left side of the first time into two parts, lower and upper part. The lower area was for facilities 1 and 2, and the upper part was for facility 3. The third splitting line L
41
L
42, L
41
(
∑
i
=
1,2
,
3
h
i
,
v
4
), L
42
(
∑
h
i
,
v
4
), was horizontal and partitioned the right side of the first time into two parts, lower and upper. The upper area was for facilities 5 and 6, and the lower part was for facility 4. The fourth vertical splitting line L
11
L
12, L
11
(
v
1
,
0
), L
12
(
h
1
,
∑
i
=
1,2
v
i
), divided the lower part of the second time into two sides, left and right. The left was for facility 1 and the right was for facility 2. The fifth horizontal splitting line L
51
L
52, L
51
(
∑
i
=
1,2
,
3
h
i
,
v
4
+
v
5
), L
52
(
∑
h
i
,
v
4
+
v
5
), divided the upper part of the third time into two sides, upper and lower. The upper one was for facility 6 and the lower one was for facility 5. So far, the plane was divided into blocks whose amount was equal to the facility number. Each block was for a special facility. The position of the above 6 facilities can be located by a point pair of the lower-left corner and the upper-right corner of the 6 blocks as follows: f
1
O
,
L
12, f
2
L
11
,
L
22, f
3
L
21
,
L
32, f
4
L
31
,
L
42, f
5
L
41
,
L
52, and f
6
{
L
51
,
O
′
}. So a feasible facility layout solution was obtained.


## 3.1. Determination of Left Sets
e
t
L and Right Set s
e
t
R for Each Partitioning Operation

Step 1.
Find the maximum of existing splitting positionS
O
_
m
a
x.Step 2.
Find the minimum of existing splitting positionS
O
_
m
i
n.Step 3.
In accordance with the relationship between the current splitting positionS
O
_
c
u
r, S
O
_
m
a
x, and S
O
_
m
i
n, new left set s
e
t
L and right set s
e
t
R are determined as follows:(i)
IfS
O
_
c
u
r
<
S
O
_
m
i
n, in this case, the current splitting position S
O
_
c
u
r lies in existing s
e
t
L where S
O
_
m
i
n was found before. This operation partitions this s
e
t
L into two parts, that is, new s
e
t
L and s
e
t
R.
(ii)
IfS
O
_
c
u
r
>
S
O
_
m
a
x, the current splitting position S
O
_
c
u
r lies in the existing s
e
t
R where S
O
_
m
a
x was found before. This operation partitions this s
e
t
R into two parts, that is, new s
e
t
L and s
e
t
R.
(iii)
IfS
O
(
i
)
<
S
O
_
c
u
r
<
S
O
(
j
), here, S
O
(
i
) denotes the maximum of existing splitting position less than S
O
_
c
u
r and S
O
(
j
) denotes the minimum of existing splitting position greater than S
O
_
c
u
r. The completion order of splitting operation corresponding to the splitting positions S
O
(
i
) and S
O
(
j
) affects the object of this partition. If S
O
(
i
) splitting was carried out later than S
O
(
i
), that is, i
>
j, the right set resulting from S
O
(
i
) splitting was going to be partitioned. Similarly, if S
O
(
i
) splitting was carried out earlier than S
O
(
i
), that is, i
<
j, the left set resulting from S
O
(
j
) splitting was going to be partitioned.This paper defines two structures to record the information of splitting position and its results, setss
e
t
L and s
e
t
R; that is, s
e
t
L = struct(“splitting position”, {
}, “left set”, {
}) and s
e
t
R = struct(“splitting position”, {
}, “right set”, {
}).The process to determine the setss
e
t
L and s
e
t
R of every splitting operation is shown in Algorithm 1.Algorithm 1:Process to determine the left and right set for given splitting position.
Procedure  d
e
t
e
r
m
i
n
a
t
i
o
n
o
f
s
e
t
L
a
n
d
s
e
t
R  (N is the  cardinality of facility set F,  cso is position set that have been split)
(1)    s
e
t
L
(
1
)
←
s
t
r
u
c
t(“splitting position”, 0, “left set”, ); % Initialize the first left set with empty set
(2)    s
e
t
R
(
1
)
←
s
t
r
u
c
t(“splitting position”, 0, “right set”, F); % Initialize the first right set with set F
(3)    for i
←
1 To N
(4)      [
m
a
x
c
s
o
,
i
x
_
m
a
x
]
←
max
⁡
(
c
s
o
);
(5)      [
m
i
n
c
s
o
,
i
x
_
m
i
n
]
←
min
⁡
(
c
s
o
);
(6)      t
e
m
p
1
←
max
⁡
(
i
n
d
e
x
(
S
O
(
i
)
>
c
s
o
)
);
(7)      t
e
m
p
2
←
min
⁡
(
i
n
d
e
x
(
S
O
(
i
)
<
c
s
o
)
);
(8)      if  S
O
(
i
)
>
c
s
o
(
i
x
_
m
a
x
)
(9)       s
e
t
L
(
i
)
←
s
t
r
u
c
t(“splitting position”, S
O
(
i
), “left set”,
setR(i
x_max).right set(1: S
O
(
i
)-m
a
x
c
s
o));
(1
0)    s
e
t
R
(
i
)
←
s
t
r
u
c
t(“splitting position”, S
O
(
i
), “right set”,
setR(i
x_max).right set(S
O(i-m
a
x
c
s
o): end));
(11)   elseif S
O
(
i
)
<
c
s
o
(
i
x
_
m
i
n
)
(12)    s
e
t
L
(
i
)
←
s
t
r
u
c
t(“splitting position”,  S
O
(
i
),  “left set”,
setL(i
x_min).left set(1: S
O
(
i
)));
(13)    s
e
t
R
(
i
)
←
s
t
r
u
c
t(“splitting position”,  S
O
(
i
),  “right set”,
setL(i
x_min).left set((S
O
(
i
) + 1): end));
(14)   elseif c
s
o
(
t
e
m
p
1
)
<
s
(
i
)
<
c
s
o
(
t
e
m
p
2
)
(15)    if t
e
m
p
1
>
t
e
m
p
2
(16)     s
e
t
L
(
i
)
←
s
t
r
u
c
t(“splitting position”, S
O
(
i
), “left set”,
setR(temp1).right set(1:  S
O(i)-cso(temp1)));
(17)     s
e
t
R
(
i
)
←
s
t
r
u
c
t(“splitting position”, S
O
(
i
), “left set”,
setR(temp1).right set((s
(
i
)-cso(temp1) + 1): end));
(18)    elseif t
e
m
p
1
<
t
e
m
p
2
(19)     i
x
←
l
e
n
g
t
h(s
e
t
L(temp2).left set);
(20)     s
e
t
L
(
i
)
←
s
t
r
u
c
t(“splitting position”, S
O
(
i
), “left set”,
setL(temp2).left set(1: i
x-cso(temp2) + S
O
(
i
)));
(21)     s
e
t
R
(
i
)
←
s
t
r
u
c
t(“splitting position”, S
O
(
i
), “right set”,
setL(temp2).left set((i
x-cso(temp2) + S
O
(
i
) + 1): end));
(22)    end if
(23)   end if
(24)  end forThe partition task in Figure2 was completed using the above approach and the results are shown in Table 1. After repeating the operation 5 times, the facility set was partitioned into 5 sets, each of which contained only one element. At the same time, the plane was also partitioned into 5 blocks, each of which was for arranging a facility.Table 1
Results of set partitioning.
Splitting position
3
2
4
1
5
Left set
f
1
,
f
2
,
f
3
f
1
,
f
2
f
4
f
1
f
5
Right set
f
4
,
f
5
,
f
6
f
3
f
5
,
f
6
f
2
f
6


## 3.2. Coordinates Determination of the First Splitting Line

Before the first splitting operation, the layout area was empty and no facility was arranged. The coordinates of the lower-left corner and upper-right corner of the layout plane were denoted byO
(
0,0
) and O
′
(
∑
h
i
,
∑
v
i
), where h
i and v
i were the horizontal width and the vertical height of facility i, respectively. The coordinates of the upper-right corner were the extreme value when all the facilities were arranged side by side horizontally or vertically. The plane was firstly split according to the value of S
P
(
1
). The splitting line was denoted by L
i
1
L
i
2, where the first subscript i
=
1,2
,
…
,
n
-
1 shows the splitting position and the second subscript taking value of 1 or 2 means the start point or end point of splitting line. The line direction is from left to right for horizontal line and from bottom to top for vertical line.(i)
S
P
(
1
)
=
0. In this case, the first line is a horizontal one partitioning the layout area into two parts, upper and lower. The facilities of vector F on the left of splitting point S
O
(
1
), that is, s
e
t
L
(
1
)
.
leftset, were included in the lower part. The facilities of vector F on the right of S
O
(
1
), that is, s
e
t
R
(
1
)
.
rightset, were included in the upper part. The first line was denoted by L
S
O
(
1
)
1
(
0
,
∑
i
∈
s
e
t
L
(
1
)
.
l
e
f
t
s
e
t
v
i
), L
S
O
(
1
)
2
(
∑
h
i
,
∑
i
∈
s
e
t
L
(
1
)
.
l
e
f
t
s
e
t
v
i
).(ii)
S
P
(
1
)
=
1. When S
P
(
1
)
=
1, the first line L
S
O
(
1
)
1
L
S
O
(
1
)
2 is vertical and can be determined by L
S
O
(
1
)
1
(
∑
i
∈
s
e
t
L
(
1
)
.
l
e
f
t
s
e
t
h
i
,
0
), L
S
O
(
1
)
2
(
∑
i
∈
s
e
t
L
(
1
)
.
l
e
f
t
s
e
t
h
i
,
∑
v
i
).As shown in Algorithm2, the first line can be drawn by connecting the point (hlin_start(1), hlin_y(1)) and point (hlin_end(1), hlin_y(1)). As a result, the layout area was partitioned into two parts.Algorithm 2:Coordinate determination of the first line.
Procedure  D
r
a
w
i
n
g
t
h
e
f
i
r
s
t
s
p
l
i
t
t
i
n
g
l
i
n
e (F, S
P, s
e
t
L, s
e
t
R, L
W, L
H)
(1)    [
t
f
,
i
n
d
e
x
]
←
s
e
t
L
(
1
).elements and their index in F;
(2)    if  S
P
(
1
)
=
0
(3)     h
l
i
n
_
s
t
a
r
t
(
1
)
←
0;  %  x-coordinate of  horizontal line start point
(4)     h
l
i
n
_
e
n
d
(
1
)
←
s
u
m
(
L
W
); %  x-coordinate of  horizontal line end point
(5)     h
l
i
n
_
y
(
1
)
←
s
u
m
(
L
H
(
F
(
i
n
d
e
x
)
)
); %  y-coordinate of  horizontal line
(6)    elseif  S
P
(
1
)
=
1
(7)     v
l
i
n
_
s
t
a
r
t
(
1
)
←
0;
(8)     vlin_end(
1
)
←
s
u
m(L
H);
(9)     vlin_x
(
1
)
←
s
u
m(L
W(F(index)));;
(10)   end if
(11)   Connect point (hlin_start(1), hlin_y(1)) and (hlin_end(1), hlin_y(1))


## 3.3. Coordinates Determination of the Second and Subsequent Splitting Line

From the second splitting operation, inclusion relations between the left set obtained in current operation and the left set and right set obtained before were determined. For the set including the current left set, its maximum of the structure attribute SO is recorded. LetJ
1 be the index of maximum SO in left set and let J
2 be the index of maximum SO in right set.(I) If the current splitting mode is horizontal, that is,S
P
(
i
)
=
0
,
i
≥
2, the splitting line of current operation has the following cases according to the value of J
1 and J
2.(i) ConsiderJ
1
≠
0, J
2
=
0. In this case, the left set obtained in current operation was included by only one existing left set. The determination of splitting line according to the value of S
P
(
J
1
) was as shown in Figure 4.Figure 4
Case of current left set only belonging to some existing left set.
(a)
S
P
(
J
1
)
=
0
(b)
S
P
(
J
1
)
=
1As shown in Figure4(a), when S
P
(
J
1
)
=
0, the corresponding existing splitting line was a horizontal line L
S
O
(
J
1
)
1
L
S
O
(
J
1
)
2, below which the current line L
S
O
(
i
)
1
L
S
O
(
i
)
2 was drawn horizontally, where L
S
O
(
i
)
1
(
x
_
L
S
O
(
J
1
)
1
,
∑
j
∈
s
e
t
L
(
i
)
.
l
e
f
t
s
e
t
v
j
), L
S
O
(
i
)
2
(
x
_
L
S
O
(
i
)
2
,
y
_
L
S
O
(
i
)
1
); Figure 4(b) shows the other case of S
P
(
J
1
)
=
1. The corresponding existing splitting line L
S
O
(
J
1
)
1
L
S
O
(
J
1
)
2 was vertical, on the left side of which the current line L
S
O
(
i
)
1
L
S
O
(
i
)
2 was drawn, where L
S
O
(
i
)
1
(
0
,
∑
j
∈
s
e
t
L
(
i
)
.
l
e
f
t
s
e
t
v
j
), L
S
O
(
i
)
2
(
x
_
L
S
O
(
J
1
)
1
,
y
_
L
S
O
(
i
)
1
).(ii) ConsiderJ
1
=
0, J
2
≠
0. In this case, the left set obtained in current operation was included by only one existing right set. The determination of splitting line according to the value of S
P
(
J
2
) was as shown in Figure 5.Figure 5
Case of current left set only belonging to some existing right set.
(a)
S
P
(
J
2
)
=
0
(b)
S
P
(
J
2
)
=
1As shown in Figure5(a), when S
P
(
J
2
)
=
0, the corresponding existing splitting line was a horizontal line L
S
O
(
J
2
)
1
L
S
O
(
J
2
)
2, above which the current line L
S
O
(
i
)
1
L
S
O
(
i
)
2 was drawn, where L
S
O
(
i
)
1
(
x
_
L
S
O
(
J
2
)
1
,
y
_
L
S
O
(
J
2
)
1
+
∑
j
∈
s
e
t
L
(
i
)
.
l
e
f
t
s
e
t
v
j
), L
S
O
(
i
)
2
(
x
_
L
S
O
(
J
2
)
2
,
y
_
L
S
O
(
i
)
1
); Figure 5(b) shows the other case of S
P
(
J
2
)
=
1. The corresponding existing splitting line L
S
O
(
J
1
)
1
L
S
O
(
J
1
)
2 was vertical, on the right side of which the current line L
S
O
(
i
)
1
L
S
O
(
i
)
2 was drawn, where L
S
O
(
i
)
1
(
x
_
L
S
O
(
J
2
)
1
,
∑
j
∈
s
e
t
L
(
i
)
.
l
e
f
t
s
e
t
v
j
), L
S
O
(
i
)
2
(
∑
h
i
,
y
_
L
S
O
(
i
)
1
).(iii) ConsiderJ
1
≠
0, J
2
≠
0. In this case, the left set obtained in current operation belonged to both some existing right set and some existing left set. The determination of splitting line according to the value of S
P
(
J
2
) and S
P
(
J
1
) was as shown in Figure 6.Figure 6
Case of current left set belonging to both some existing right set and some existing left set.
(a)
S
P
(
J
1
)
=
0, S
P
(
J
2
)
=
0
(b)
S
P
(
J
1
)
=
1, S
P
(
J
2
)
=
0
(c)
S
P
(
J
1
)
=
0, S
P
(
J
2
)
=
1
(d)
S
P
(
J
1
)
=
1, S
P
(
J
2
)
=
1As shown in Figure6(a), when S
P
(
J
1
)
=
0 and S
P
(
J
2
)
=
0, the corresponding two existing splitting lines were L
S
O
(
J
1
)
1
L
S
O
(
J
1
)
2 and L
S
O
(
J
2
)
1
L
S
O
(
J
2
)
2, and they were horizontal. The current line L
S
O
(
i
)
1
L
S
O
(
i
)
2 was drawn above the line L
S
P
(
J
2
)
1
L
S
P
(
J
2
)
2 and below the line L
S
O
(
J
1
)
1
L
S
O
(
J
1
)
2, where L
S
O
(
i
)
1
(
x
_
L
S
O
(
J
2
)
1
,
y
_
L
S
O
(
J
2
)
1
+
∑
j
∈
s
e
t
L
(
i
)
.
l
e
f
t
s
e
t
v
j
), L
S
O
(
i
)
2
(
x
_
L
S
O
(
J
2
)
2
,
y
_
L
S
O
(
i
)
1
); in Figure 6(b), when  S
P
(
J
1
)
=
1 and S
P
(
J
2
)
=
0, L
S
O
(
i
)
1
L
S
O
(
i
)
2 was drawn above the existing horizontal line L
S
O
(
J
1
)
1
L
S
O
(
J
1
)
2 and on the left side of existing vertical line L
S
O
(
J
2
)
1
L
S
O
(
J
2
)
2, where L
S
O
(
i
)
1
(
x
_
L
S
O
(
J
2
)
1
,
y
_
L
S
O
(
J
2
)
1
+
∑
j
∈
s
e
t
L
(
i
)
.
l
e
f
t
s
e
t
v
j
), L
S
O
(
i
)
2
(
x
_
L
S
O
(
J
2
)
2
,
y
_
L
S
O
(
J
1
)
1
); in Figure 6(c), when  S
P
(
J
1
)
=
0 and S
P
(
J
2
)
=
1, L
S
O
(
i
)
1
L
S
O
(
i
)
2 was drawn below the existing horizontal line L
S
O
(
J
1
)
1
L
S
O
(
J
1
)
2 and on the right side of existing vertical line L
S
O
(
J
2
)
1
L
S
O
(
J
2
)
2, where L
S
O
(
i
)
1
(
x
_
L
S
O
(
J
2
)
1
,
y
_
L
S
O
(
J
2
)
1
+
∑
j
∈
s
e
t
L
(
i
)
.
l
e
f
t
s
e
t
v
j
), L
S
O
(
i
)
2
(
x
_
L
S
O
(
J
1
)
2
,
y
_
L
S
O
(
i
)
1
); in Figure 6(d), when  S
P
(
J
1
)
=
1 and S
P
(
J
2
)
=
1, L
S
O
(
i
)
1
L
S
O
(
i
)
2 was drawn between the left side of the existing vertical line L
S
O
(
J
1
)
1
L
S
O
(
J
1
)
2 and the right side of existing vertical line L
S
O
(
J
2
)
1
L
S
O
(
J
2
)
2, where L
S
O
(
i
)
1
(
x
_
L
S
O
(
J
2
)
1
,
y
_
L
S
O
(
J
2
)
1
+
∑
j
∈
s
e
t
L
(
i
)
.
l
e
f
t
s
e
t
v
j
), L
S
O
(
i
)
2
(
x
_
L
S
O
(
J
1
)
1
,
y
_
L
S
O
(
i
)
1
).The above approach to determine the line coordinates and to draw the line was shown as the pseudocode in Algorithm3.Algorithm 3:Process of line coordinates determination.
Procedure  D
r
a
w
i
n
g
t
h
e
s
e
c
o
n
d
a
n
d
s
u
b
s
e
q
u
e
n
t
s
p
l
i
t
t
i
n
g
l
i
n
e  (F, S
P, s
e
t
L, s
e
t
R, L
W, L
H)
(1)    for i
←
2 TO N
-
1
(2)     J
1
←
0; J
2
←
0;
(3)     for  j
=
1 TO i
-
1
(4)      if s
e
t
L
(
i
).left s
e
t
⊂
s
e
t
L
(
j
).left set  &  j
>
J
1
(5)       J
1
←
j
(6)      elseif s
e
t
L
(
i
).left  s
e
t
⊂
s
e
t
L
(
j
).right set  &  j
>
J
2
(7)       J
2
←
j
(8)      end if
(9)     end for
(10)  [
t
f
,
i
n
d
e
x
]
←
s
e
t
L
(
i
).elements and their index in F;
(11)  if  J
1
~
=
0
&
J
2
=
0
(12)   if S
P
(
J
1
)
=
0
(13)    h
l
i
n
_
s
t
a
r
t
(
i
)
←
h
l
i
n
_
s
t
a
r
t
(
J
1
);    h
l
i
n
_
e
n
d
(
i
)
←
h
l
i
n
_
e
n
d
(
J
1
);
(14)    h
l
i
n
_
y
(
i
)
←
s
u
m(L
H(F(index)));
(15)   elseif S
P
(
J
1
)
=
1
(16)    h
l
i
n
_
s
t
a
r
t
(
i
)
←
0;   h
l
i
n
_
e
n
d
(
i
)
←
v
l
i
n
_
x
(
J
1
);
(17)    h
l
i
n
_
y
(
i
)
←
s
u
m(L
H(F(index)));
(18)   end if
(19)  elseif J
1
=
0
&
J
2
~
=
0
(20)   if S
P
(
J
2
)
=
0
(21)    hlin_start(
i
)
←
hlin_start(J
2);   hlin_end(
i
)
←
hlin_end(J
2);  hlin_y
(
i
)
←
hlin_y
(
J
2
) + sum(L
H(F(index)));
(2
2)   elseif S
P
(
J
2
)
=
1
(2
3)    hlin_start(
i
)
←
vlin_x
(
J
2
);    hlin_end(
i
)
←
s
u
m(L
W);       hlin_y
(
i
)
←
vlin_start(J
2) + sum(L
H(F(index)));
(2
4)   end if
(2
5)  elseif J
1
~
=
0  &  J
2
~
=
0
(2
6)   if S
P
(
J
1
)
=
0  &  S
P
(
J
2
)
=
0
(2
7)    hlin_start(
i
)
←
hlin_start(J
2);    hlin_end(
i
)
←
hlin_end(J
2);  hlin_y
(
i
)
←
hlin_y
(
J
2
) + sum(L
H(F(index)));
(28)   elseif S
P(J
1) = 1  &  S
P(J
2) = 0
(29)    hlin_start(
i
)
←
hlin_start(J
2);   hlin_end(
i
)
←
vlin_end(J
1);  hlin_y
(
i
)
←
hlin_y
(
J
2
) + sum(L
H(F(index)));
(30)   elseif S
P(J
1) = 0  &  S
P(J
2) = 1
(3
1)    hlin_start(
i
)
←
vlin_x(J
2);     hlin_end(
i
)
←
hlin_end(J
1);  hlin_y
(
i
)
←
vlin_start(J
2) + sum(L
H(F(index)));
(3
2)   elseif S
P(J
1) = 1  &  S
P(J
2) = 1
(3
3)    hlin_start(
i
)
←
vlin_x(J
2);    hlin_end(
i
)
←
vlin_x
(
J
1
);      hlin_y
(
i
)
←
vlin_start(J
2) + sum(L
H(F(index)));
(3
4)   end if
(3
5)  end if
(3
6)  Connect point (hlin_start(i), hlin_y(i)) and point (hlin_end(i), hlin_y(i))
(3
7)      end for(II) If the current splitting mode is horizontal, that is,S
P
(
i
)
=
1
,
i
≥
2, the splitting line of current operation has the following cases according to the value of J
1 and J
2.(i) ConsiderJ
1
≠
0, J
2
=
0. In this case, the left set obtained in current operation belonged to only one existing left set. The determination of splitting line according to the value of S
P
(
J
1
) was as shown in Figure 7.Figure 7
Case of current left set only belonging to some existing left set whenS
P
(
i
)
=
1
,
i
≥
2.
(a)
S
P
(
J
1
)
=
0
(b)
S
P
(
J
1
)
=
1As shown in Figure7(a), when S
P
(
J
1
)
=
0, the corresponding existing splitting line was a horizontal line L
S
O
(
J
1
)
1
L
S
O
(
J
1
)
2, below which the current line L
S
O
(
i
)
1
L
S
O
(
i
)
2 was drawn vertically, where L
S
O
(
i
)
1
(
x
_
L
S
O
(
J
1
)
1
+
∑
j
∈
s
e
t
L
(
i
)
.
l
e
f
t
s
e
t
v
j
,
0
), L
S
O
(
i
)
2
(
x
_
L
S
O
(
i
)
1
,
y
_
L
S
O
(
J
1
)
1
); Figure 7(b) showed the other case of S
P
(
J
1
)
=
1. The corresponding existing splitting line L
S
O
(
J
1
)
1
L
S
O
(
J
1
)
2 was vertical, on the left side of which the current line L
S
O
(
i
)
1
L
S
O
(
i
)
2 was drawn, where L
S
O
(
i
)
1
(
∑
j
∈
s
e
t
L
(
i
)
.
l
e
f
t
s
e
t
v
j
,
y
_
L
S
O
(
J
1
)
1
),     L
S
O
(
i
)
2
(
x
_
L
S
O
(
i
)
1
,
y
_
L
S
O
(
J
1
)
2
).(ii) ConsiderJ
1
=
0
,
J
2
≠
0. In this case, the left set obtained in current operation belonged to only one existing right set. The determination of splitting line according to the value of S
P
(
J
2
) was as shown in Figure 8.Figure 8
Case of current left set only belonging to some existing right set whenS
P
(
i
)
=
1
,
i
≥
2.
(a)
S
P
(
J
2
)
=
0
(b)
S
P
(
J
2
)
=
1As shown in Figure8(a), when S
P
(
J
2
)
=
0, the corresponding existing splitting line was a horizontal line L
S
O
(
J
2
)
1
L
S
O
(
J
2
)
2, above which the current line L
S
O
(
i
)
1
L
S
O
(
i
)
2 was drawn vertically, where L
S
O
(
i
)
1
(
x
_
L
S
O
(
J
2
)
1
+
∑
j
∈
s
e
t
L
(
i
)
.
l
e
f
t
s
e
t
v
j
,
0
), L
S
O
(
i
)
2
(
x
_
L
S
O
(
i
)
1
,
∑
v
i
); Figure 8(b) showed the other case of S
P
(
J
2
)
=
1. The corresponding existing splitting line L
S
O
(
J
2
)
1
L
S
O
(
J
2
)
2 was vertical, on the left side of which the current line L
S
O
(
i
)
1
L
S
O
(
i
)
2 was drawn, where L
S
O
(
i
)
1
(
x
_
L
S
O
(
J
2
)
1
+
∑
j
∈
s
e
t
L
(
i
)
.
l
e
f
t
s
e
t
v
j
,
y
_
L
S
O
(
J
2
)
1
), L
S
O
(
i
)
2
(
x
_
L
S
O
(
i
)
1
,
y
_
L
S
O
(
J
1
)
2
).(iii) ConsiderJ
1
≠
0, J
2
≠
0. In this case, the left set obtained in current operation belonged to both one existing right set and one existing left set. The determination of splitting line according to the value of S
P
(
J
1
) and S
P
(
J
2
) was as shown in Figure 9.Figure 9
Case of current left set belonging to both some existing right set and some existing left set,S
P
(
i
)
=
1
,
i
≥
2.
(a)
S
P
(
J
1
)
=
0, S
P
(
J
2
)
=
0
(b)
S
P
(
J
1
)
=
1, S
P
(
J
2
)
=
0
(c)
S
P
(
J
1
)
=
0, S
P
(
J
2
)
=
1
(d)
S
P
(
J
1
)
=
1, S
P
(
J
2
)
=
1As shown in Figure9(a), when S
P
(
J
1
)
=
0 and S
P
(
J
2
)
=
0, the corresponding two existing splitting lines were L
S
O
(
J
1
)
1
L
S
O
(
J
1
)
2 and L
S
O
(
J
2
)
1
L
S
O
(
J
2
)
2, and they were horizontal. The current line L
S
O
(
i
)
1
L
S
O
(
i
)
2 was drawn between line L
S
P
(
J
2
)
1
L
S
P
(
J
2
)
2 and line L
S
O
(
J
1
)
1
L
S
O
(
J
1
)
2, where L
S
O
(
i
)
1
(
x
_
L
S
O
(
J
2
)
1
+
∑
j
∈
s
e
t
L
(
i
)
.
l
e
f
t
s
e
t
h
j
,
y
_
L
S
O
(
J
2
)
1
), L
S
O
(
i
)
2
(
x
_
L
S
O
(
i
)
1
,
y
_
L
S
O
(
J
1
)
1
); in Figure 9(b), when  S
P
(
J
1
)
=
1 and S
P
(
J
2
)
=
0, L
S
O
(
i
)
1
L
S
O
(
i
)
2 was drawn above the existing horizontal line L
S
O
(
J
1
)
1
L
S
O
(
J
1
)
2 and on the left side of existing vertical line L
S
O
(
J
2
)
1
L
S
O
(
J
2
)
2, where L
S
O
(
i
)
1
(
x
_
L
S
O
(
J
2
)
1
+
∑
j
∈
s
e
t
L
(
i
)
.
l
e
f
t
s
e
t
h
j
,
y
_
L
S
O
(
J
2
)
1
), L
S
O
(
i
)
2
(
x
_
L
S
O
(
i
)
1
,
y
_
L
S
O
(
J
1
)
2
); in Figure 9(c),  when  S
P
(
J
1
)
=
0 and S
P
(
J
2
)
=
1, L
S
O
(
i
)
1
L
S
O
(
i
)
2 was drawn below the existing horizontal line L
S
O
(
J
1
)
1
L
S
O
(
J
1
)
2 and on the right side of existing vertical line L
S
O
(
J
2
)
1
L
S
O
(
J
2
)
2, where L
S
O
(
i
)
1
(
x
_
L
S
O
(
J
2
)
1
+
∑
j
∈
s
e
t
L
(
i
)
.
l
e
f
t
s
e
t
h
j
,
y
_
L
S
O
(
J
2
)
1
), L
S
O
(
i
)
2
(
x
_
L
S
O
(
i
)
1
,
y
_
L
S
O
(
J
1
)
1
); in Figure 9(d), when   S
P
(
J
1
)
=
1 and S
P
(
J
2
)
=
1, L
S
O
(
i
)
1
L
S
O
(
i
)
2 was drawn between the left side of the existing vertical line L
S
O
(
J
1
)
1
L
S
O
(
J
1
)
2 and the right side of existing vertical line L
S
O
(
J
2
)
1
L
S
O
(
J
2
)
2, where L
S
O
(
i
)
1
(
x
_
L
S
O
(
J
2
)
1
+
∑
j
∈
s
e
t
L
(
i
)
.
l
e
f
t
s
e
t
h
j
,
y
_
L
S
O
(
J
2
)
1
), L
S
O
(
i
)
2
(
x
_
L
S
O
(
i
)
1
,
y
_
L
S
O
(
J
1
)
2
).For the case ofS
P
(
i
)
=
1
,
i
≥
2, the pseudocode to realize the above approach can be achieved by replacing hlin_start(
i
), hlin_end(
i
), and hlin_y
(
i
) in Figure 5 with vlin_start(
i
), vlin_end(
i
), and vlin_x
(
i
), respectively. The coordinate values of each splitting line can be determined according to Figures 7~9.Plane segmentation process is to determine facilities relative position in the layout area. For the aforementioned FLP with 6 facilities (as shown in Figure3), the process of plane splitting and splitting line coordinate determining can be described as follows.The initial layout area was a plane determined by the lower-left cornerO
(
0,0
) and top-right corner O
′
(
∑
h
i
,
∑
v
i
). For the first splitting operation, the vertical splitting line L
31
L
32, L
31
(
∑
i
=
1,2
,
3
h
i
,
0
), L
32
(
∑
i
=
1,2
,
3
h
i
,
∑
v
i
), divided the initial layout area into two parts, left and right side. The left was for facilities 1, 2, and 3, and the right was for facilities 4, 5, and 6. The second splitting line L
21
L
22, L
21
(
0
,
∑
i
=
1,2
v
i
), L
22
(
∑
i
=
1,2
,
3
h
i
,
∑
i
=
1,2
v
i
), was horizontal and partitioned the left side of the first time into two parts, lower and upper part. The lower area was for facilities 1 and 2, and the upper part was for facility 3. The third splitting line L
41
L
42, L
41
(
∑
i
=
1,2
,
3
h
i
,
v
4
), L
42
(
∑
h
i
,
v
4
), was horizontal and partitioned the right side of the first time into two parts, lower and upper. The upper area was for facilities 5 and 6, and the lower part was for facility 4. The fourth vertical splitting line L
11
L
12, L
11
(
v
1
,
0
), L
12
(
h
1
,
∑
i
=
1,2
v
i
), divided the lower part of the second time into two sides, left and right. The left was for facility 1 and the right was for facility 2. The fifth horizontal splitting line L
51
L
52, L
51
(
∑
i
=
1,2
,
3
h
i
,
v
4
+
v
5
), L
52
(
∑
h
i
,
v
4
+
v
5
), divided the upper part of the third time into two sides, upper and lower. The upper one was for facility 6 and the lower one was for facility 5. So far, the plane was divided into blocks whose amount was equal to the facility number. Each block was for a special facility. The position of the above 6 facilities can be located by a point pair of the lower-left corner and the upper-right corner of the 6 blocks as follows: f
1
O
,
L
12, f
2
L
11
,
L
22, f
3
L
21
,
L
32, f
4
L
31
,
L
42, f
5
L
41
,
L
52, and f
6
{
L
51
,
O
′
}. So a feasible facility layout solution was obtained.


## 4. Case Study

### 4.1. Basic Information of Facilities

This paper took the FLP of a toolkit manufacturer as a case to validate the approach mentioned above. The area and aspect ratio of every facility were shown in Table2.Table 2
Facility information of a toolkit manufacturer.
Symbol
Name of facility
Facility function
Length (m)
Width (m)
f
1
Machining workshop
Blanking and punching
36
24
f
2
Welding workshop
Welding body parts
24
24
f
3
Painting workshop
Painting the  body
12
6
f
4
Assembly workshop
Riveting the handle, lock, and hinge
24
12
f
5
Cargo-receiving areas
Receiving the supplied materials
6
6
f
6
Storage areas
Storing the rough parts
5
6
f
7
Warehouse
Storing the finished products
48
36
f
8
Shipping areas
Shipping the finished products
8
8
f
9
Lounge
For break
6
6
f
10
Maintenance area
Maintaining the equipment
6
6
f
11
Tool room
Storing the production tools
12
6
f
12
Changing room
Changing work clothes
5
4
f
13
Restaurant
Life services
72
18
f
14
Office
Office space
36
8


### 4.2. Run Settings of Plane Segmentation Algorithm and the Results

According to the layout approach of plane splitting proposed in Section3, the input information for this case is as follows: F
=
{
f
1
,
f
2
,
…
,
f
14
}, S
O
=
{
6,3
,
11,7
,
8,5
,
1,2
,
4,13,9
,
10,12
},  and  S
P
=
{
0,1
,
1,0
,
0,1
,
0,1
,
1,0
,
0,1
,
0
}, and size matrix of facility A
e
r
a is as follows: (1)
A
e
r
a
=
36
24
12
24
6
5
48
8
6
6
12
5
72
36
24
24
6
12
6
6
36
8
6
6
6
4
18
8
.InA
e
r
a, the data in the first and second row denoted the length and width of each facility, respectively. By running the algorithm in Matlab, a feasible layout approach was obtained as in Figure 10. The Arabic numerals labeled in Figure 10 denoted the facility number, and the block that was labeled with a numeral was the layout area of the corresponding facility. Each block was located by the coordinates of lower-left corner and upper-right corner. The red point in each block denoted the centroid position of each facility.Figure 10
A feasible layout approach of FLP with 14 facilities using plane splitting method.From the layout scheme of Figure10, it can be seen that facility 1 was in the lower-left corner of the plane, and, for facilities adjacent to facility 1, the facility with smaller number was located in the left and lower side and the facility with larger number was located in the right and upper side. This result was related to the order given by the input set. By changing the element order of F, S
O, and S
P, different feasible layout approaches can be obtained and then be further combined with heuristic intelligent algorithms to search the optimum. Figure 11 showed the different schemes of different F, S
O, and S
P.Figure 11
Feasible layout scheme corresponding to different element order of input set.
(a)
F
=
f
13
,
f
12
,
f
7
,
f
2
,
f
10
,
f
1
,
f
14
,
f
5
,
f
11
,
f
4
,
f
9
,
f
8
,
f
3
,
f
6, S
O
=
6,3
,
8,12,10,7
,
5,11,4
,
13,1
,
9,2, and S
P
=
{
0,1
,
1,0
,
0,0
,
0,1
,
1,0
,
0,1
,
1
}
(b)
F
=
f
12
,
f
13
,
f
6
,
f
3
,
f
14
,
f
5
,
f
9
,
f
11
,
f
10
,
f
2
,
f
1
,
f
4
,
f
8
,
f
7, S
O
=
5,11,3
,
4,6
,
1,8
,
10,7
,
2,12,9
,
13, and  S
P
=
{
1,0
,
1,1
,
1,0
,
1,0
,
0,0
,
0,0
,
1
}
(c)
F
=
f
2
,
f
10
,
f
1
,
f
6
,
f
14
,
f
7
,
f
13
,
f
8
,
f
3
,
f
12
,
f
5
,
f
11
,
f
4
,
f
9, S
O
=
3,5
,
8,11,9
,
6,1
,
2,7
,
4,10,12,13, and S
P
=
{
0,0
,
0,1
,
1,1
,
0,1
,
1,0
,
0,1
,
0
}
(d)
F
=
f
9
,
f
10
,
f
3
,
f
1
,
f
11
,
f
14
,
f
2
,
f
5
,
f
12
,
f
4
,
f
8
,
f
13
,
f
6
,
f
7, S
O
=
10,6
,
12,11,13,5
,
9,4
,
7,2
,
8,1
,
3, and S
P
=
{
1,0
,
0,1
,
0,1
,
0,1
,
0,0
,
0,1
,
1
}


### 4.3. Analysis on the Influence of Facilities Quantity on the Algorithm

In order to analyze the sensitivity of the proposed solutions to the quantity of the facilities, this paper selected 40 kinds of data with every 5th number from 5 to 200 to test. The machine parameters to run the algorithm were as follows: Intel Celeron CPU E3300, dual core, 2.5 GHz, 2 GB memory. The test results were displayed in Figure12.Figure 12
The relation curve between the facilities quantity and running time and memory usage.Figure12 showed the running time and memory usage of algorithm to generate a feasible layout scheme under different facility quantity. It can be seen that facility quantity has a great influence on the algorithm performance, and the facility quantity was nearly linear with the running time and memory usage. When facility quantity was 20 and 100, the running time was 0.0506 s and 0.7871 s and the memory usage was 74.419 Kb and 118.035 Kb, respectively. Supposing that this method was combined with genetic algorithm (GA) for iterative optimization, the population size of genetic algorithm was 50 and the iteration number was 100, the running time of GA was 0.0506
∗
50
∗
100
=
253 s and 0.7871
∗
50
∗
100
=
3935.5 s, and the memory usage was 74.419
K
b
∗
50
∗
100
=
372.095
M
b and 118.035
K
b
∗
50
∗
100
=
590.175
M
b for the above two cases. So the proposed approach is suitable for the FLP of limited facility quantity.


## 4.1. Basic Information of Facilities

This paper took the FLP of a toolkit manufacturer as a case to validate the approach mentioned above. The area and aspect ratio of every facility were shown in Table2.Table 2
Facility information of a toolkit manufacturer.
Symbol
Name of facility
Facility function
Length (m)
Width (m)
f
1
Machining workshop
Blanking and punching
36
24
f
2
Welding workshop
Welding body parts
24
24
f
3
Painting workshop
Painting the  body
12
6
f
4
Assembly workshop
Riveting the handle, lock, and hinge
24
12
f
5
Cargo-receiving areas
Receiving the supplied materials
6
6
f
6
Storage areas
Storing the rough parts
5
6
f
7
Warehouse
Storing the finished products
48
36
f
8
Shipping areas
Shipping the finished products
8
8
f
9
Lounge
For break
6
6
f
10
Maintenance area
Maintaining the equipment
6
6
f
11
Tool room
Storing the production tools
12
6
f
12
Changing room
Changing work clothes
5
4
f
13
Restaurant
Life services
72
18
f
14
Office
Office space
36
8


## 4.2. Run Settings of Plane Segmentation Algorithm and the Results

According to the layout approach of plane splitting proposed in Section3, the input information for this case is as follows: F
=
{
f
1
,
f
2
,
…
,
f
14
}, S
O
=
{
6,3
,
11,7
,
8,5
,
1,2
,
4,13,9
,
10,12
},  and  S
P
=
{
0,1
,
1,0
,
0,1
,
0,1
,
1,0
,
0,1
,
0
}, and size matrix of facility A
e
r
a is as follows: (1)
A
e
r
a
=
36
24
12
24
6
5
48
8
6
6
12
5
72
36
24
24
6
12
6
6
36
8
6
6
6
4
18
8
.InA
e
r
a, the data in the first and second row denoted the length and width of each facility, respectively. By running the algorithm in Matlab, a feasible layout approach was obtained as in Figure 10. The Arabic numerals labeled in Figure 10 denoted the facility number, and the block that was labeled with a numeral was the layout area of the corresponding facility. Each block was located by the coordinates of lower-left corner and upper-right corner. The red point in each block denoted the centroid position of each facility.Figure 10
A feasible layout approach of FLP with 14 facilities using plane splitting method.From the layout scheme of Figure10, it can be seen that facility 1 was in the lower-left corner of the plane, and, for facilities adjacent to facility 1, the facility with smaller number was located in the left and lower side and the facility with larger number was located in the right and upper side. This result was related to the order given by the input set. By changing the element order of F, S
O, and S
P, different feasible layout approaches can be obtained and then be further combined with heuristic intelligent algorithms to search the optimum. Figure 11 showed the different schemes of different F, S
O, and S
P.Figure 11
Feasible layout scheme corresponding to different element order of input set.
(a)
F
=
f
13
,
f
12
,
f
7
,
f
2
,
f
10
,
f
1
,
f
14
,
f
5
,
f
11
,
f
4
,
f
9
,
f
8
,
f
3
,
f
6, S
O
=
6,3
,
8,12,10,7
,
5,11,4
,
13,1
,
9,2, and S
P
=
{
0,1
,
1,0
,
0,0
,
0,1
,
1,0
,
0,1
,
1
}
(b)
F
=
f
12
,
f
13
,
f
6
,
f
3
,
f
14
,
f
5
,
f
9
,
f
11
,
f
10
,
f
2
,
f
1
,
f
4
,
f
8
,
f
7, S
O
=
5,11,3
,
4,6
,
1,8
,
10,7
,
2,12,9
,
13, and  S
P
=
{
1,0
,
1,1
,
1,0
,
1,0
,
0,0
,
0,0
,
1
}
(c)
F
=
f
2
,
f
10
,
f
1
,
f
6
,
f
14
,
f
7
,
f
13
,
f
8
,
f
3
,
f
12
,
f
5
,
f
11
,
f
4
,
f
9, S
O
=
3,5
,
8,11,9
,
6,1
,
2,7
,
4,10,12,13, and S
P
=
{
0,0
,
0,1
,
1,1
,
0,1
,
1,0
,
0,1
,
0
}
(d)
F
=
f
9
,
f
10
,
f
3
,
f
1
,
f
11
,
f
14
,
f
2
,
f
5
,
f
12
,
f
4
,
f
8
,
f
13
,
f
6
,
f
7, S
O
=
10,6
,
12,11,13,5
,
9,4
,
7,2
,
8,1
,
3, and S
P
=
{
1,0
,
0,1
,
0,1
,
0,1
,
0,0
,
0,1
,
1
}


## 4.3. Analysis on the Influence of Facilities Quantity on the Algorithm

In order to analyze the sensitivity of the proposed solutions to the quantity of the facilities, this paper selected 40 kinds of data with every 5th number from 5 to 200 to test. The machine parameters to run the algorithm were as follows: Intel Celeron CPU E3300, dual core, 2.5 GHz, 2 GB memory. The test results were displayed in Figure12.Figure 12
The relation curve between the facilities quantity and running time and memory usage.Figure12 showed the running time and memory usage of algorithm to generate a feasible layout scheme under different facility quantity. It can be seen that facility quantity has a great influence on the algorithm performance, and the facility quantity was nearly linear with the running time and memory usage. When facility quantity was 20 and 100, the running time was 0.0506 s and 0.7871 s and the memory usage was 74.419 Kb and 118.035 Kb, respectively. Supposing that this method was combined with genetic algorithm (GA) for iterative optimization, the population size of genetic algorithm was 50 and the iteration number was 100, the running time of GA was 0.0506
∗
50
∗
100
=
253 s and 0.7871
∗
50
∗
100
=
3935.5 s, and the memory usage was 74.419
K
b
∗
50
∗
100
=
372.095
M
b and 118.035
K
b
∗
50
∗
100
=
590.175
M
b for the above two cases. So the proposed approach is suitable for the FLP of limited facility quantity.


## 5. Conclusions and Prospects

According to the characteristics of FLP with continuous block and unequal area facilities, this paper proposed plane splitting method to divide the layout area into the same number of blocks with the facility quantity and also developed the algorithm pseudocode to realize the method. The splitting process and the corresponding results were recorded in a data structure. Based on this and the splitting mode of each operation, the splitting line coordinates were determined. The results of case study show the effectiveness and the reliability of the proposed method.The following conclusions are drawn from the above study:(i)
It is reasonable and effective to solve FLP with continuous block and unequal area facilities by use of plane segmentation method, which can divide the layout area into the same number of blocks with the facility quantity and so generate feasible layout scheme.
(ii)
The proposed plane segmentation algorithm can provide support to CAFP (computer aided facilities planning), generate feasible solution fast, and search the optimal layout approach combined with intelligent optimization algorithm.
(iii)
The encapsulated parameters of the proposed algorithm make it easy to solve different FLPs. When the FLP changed, the values ofF, S
O, and S
P can be passed to the algorithm as parameters without changing the algorithm itself.For particular facility layout goals, the combination of the proposed method with different heuristic intelligent optimization algorithm and the best combination scheme should be studied further. The proposed approach only considered the dimensions of facilities and did not analyze the impact of existing constraints within the layout area, which is common for FLP in renovated or expanded engineering. So it is worthy of further research.



---

*Source: 1712376-2016-03-29.xml*