Facility Layout Problem for Cellular Manufacturing Systems

Abstract

Good layout plan leads to in improve machine utilization, part demand quality, efficient setup time, less work-in-process inventory and material handling cost. Cellular Manufacturing (CM) is an application of GTCM is the combination of job shop and/or flow shop. Facility Layout Problem (FLP) for CMS includes both inter-cell layout and intra-cell layout. A bi-level mixed-integer non-linear programming continuous model has been formulated to fully define the problem and the relationship between intra-cell and inter-cell layout design. Facilities are assumed unequal size; operation sequences, part demands, overlap elimination, aisle are considered. The problem is NP-hard; hence, a simulated annealing meta-heuristic employing a novel constructive radial-based heuristic for initialization have been designed and implemented. For the first time, a novel heuristic algorithm has been designed to allocate and displace facilities in radial direction. In order to improve the search efficiency of the developed SA algorithm, the cell size used in the initialization heuristic algorithm is assumed twice as that of the original size of the cells. A real case study from the metal cutting inserts industry has been used. Results demonstrate the superiority of the developed SA algorithm against rival comparable meta-heuristics and algorithms from the literature.

1. Introduction

Facility layout problem (FLP) is the arrangement of a given number of non‐equal‐sized facilities within the given space. Good layout plan leads to improve machine utilization, part demand quality, efficient setup time, less work‐in‐process inventory and material handling cost. Generally speaking, efficient layout design provides two main advantages: (1) Reduction of between 30% to 70% in the total material handling cost (MHC) and (2) designing layout is the long term-plan, hence, any changes in layout impose some expenditure such as shutting down production or service line, losing process time and so on. Thus, designing proper facility layout plan would prevent lots of costs [1].

Several algorithms have been developed for FLP problem. The traditional approach to FLP called discrete representation often addressed by quadratic assignment problem (QAP) with the objective of minimizing a given function cost. There are two main assumptions in QAP: firstly, all facilities are equal size and shape; secondly, the location of facilities is known in a priori. However, these kinds of assumptions are not applicable in real‐world case studies. This approach to FLP is not suited to represent the exact location of facilities and cannot formulate FLP especially when facilities are unequal size and shape or if there are different clearances between the facilities. The more suitable approach to such a kind of cases is continuous representation rather than discrete. There are two ways to solve this problem. Chronologically, the first one attempts was to divide each facility into smaller size unit blocks, where the total area of those blocks is approximately equal to the area of the facility. There are two drawbacks to this method: firstly, the problem size is growing as the total number of blocks increase, and secondly, the exact shapes of facilities are ignored. The second approach to continuous problem assumes the exact shape and dimensions of the facilities (Table 1).

Approach	Plant site	Distance	Facilities	Mathematical formulation
Discrete	Divided in rectangular blocks with same size and shape; i.e., predetermined locations	Parameters Meller et al., [2]	Equal‐sized	QAP
Continuous	No predetermined location, i.e., no blocks	Variable	Unequal‐sized	MIP

Table 1.

FLP discrete approach versus FLP continuous approach.

The design of a cellular manufacturing system (CMS) includes: (1) cell formation (CF), (2) group layout, (3) group scheduling and (4) resource allocation. FLP to CMS is focusing on the second step of design of CMS which by itself is twofold: inter‐cell and intra‐cell layouts. The main objective of group layout is minimizing material handling cost (MHC) by arranging facilities in their corresponding cells and cells in floor. In this chapter, both demand and operation sequencing have been considered in optimizing the layout both at inter‐ and intra‐cellular levels. However, this was not the case with the literature; there is a dearth of papers that happened to take a discrete approach which really did address those factors. Moreover, in this chapter, a continuous approach has been adopted.

Here, a bi‐level mixed‐integer non‐linear programming continuous model has been developed for both intra‐cell and inter‐cell layout design sequentially. The problem is to arrange facilities that are machine tools in the leader problem and cells in the follower problem on the continual planar site. The objective function of leader and follower problems is minimizing the material handling cost at intra‐ and inter‐cellular levels, respectively. The developed mathematical model has some main novelties. Firstly, a continuous approach has been adopted; i.e., facilities take unequal size and their locations are not predetermined. Secondly, operation sequences and part demands are taken into consideration. Thirdly, the model has the ability to consider certain restrictions or preferences for cells and floors such as aisle. Finally, CMS design of disjoint cells is considered; hence, the overlapping elimination constraint is presented. Since the model is NP‐hard, a novel heuristic has been developed to solve the problem at two different levels (intra‐ and inter‐cellular) in a similar fashion to that used for developing the mathematical model. The developed heuristic is very different from its counterparts in the literature in the sense that it places the facilities radially, while dividing the production floor area into four quadrants. A real case study from the metal cutting industry has been used, where multiple families of inserts have been formed, each with its distinguished master plan.

2. Literature review

The block facility layout problem that was originally formulated by Armour and Buffa [3] is concerned with finding the most efficient arrangement of m indivisible departments with unequal area requirements within a facility [4]. As defined in the literature, the objective of the block layout design problem is to minimize the material handling costs by considering the following two sets of constraints: (a) department and floor area requirements; i.e. departments cannot overlap, must be placed within the facility, and some must be fixed to a location or cannot be placed in specific regions; see Refs. [1, 3, 5, 6].

Cellular layout is considered as one of the special cases of the general FLP. There is an increasing interest in solving the block layout problem by taking a continuous approach [6]. Alfa et al., [9] have developed a model to simultaneously solve group formation and intra-cell. The objective function is the summation of both inter‐cell and intra‐cell flow times based on distance. They develop SA/heuristic algorithm to solve their model. SA has been used to find the initial solution, and then a heuristic approach based on the penalty model developed to improve the solution. The main limitation of this model is that the cell locations are predetermined.

Bazargan‐Lari and Kaebernick published few papers about design of cellular manufacturing [10–13]. Bazargan-Lari and Kaebernick [11] present a continuous plane approach where different constraints such as cell boundaries, non‐overlapping, closeness relationships, location restrictions/preferences, orientation constraints and travelling distances have been considered. They develop a hybrid method which combined a non‐linear goal programming (NLGP) and simulated annealing for machine layout problem. They have combined all constraints as goals using goal programming (GP) formulas. Generally speaking, GP divides those constraints into two main categories such as absolute or hard and goal or soft constraints. Hard constraints are those that have to be satisfied absolutely. It means that violation of any of them would yield to infeasibility. However, soft constraints can be compromised and be offset from desired set goals. Those constraints are considered as three separate sets of objectives. The first priority level includes all set of absolute or hard objectives which have to be absolutely satisfied such as non‐overlapped and cell boundary constraints. The second and third priority levels are preferences. The second priority is devoted to minimizing the area of the cells/shop floor, satisfying closeness relationship and orientation. Finally, the third priority is to minimize the total travelling cost. Overall, the approach of Bazargan‐Lari and Kaebernick is a combination of the NLGP and SA. They use the pattern search to solve their NLGP based on those three priorities. Since a pattern search is finding the local minimum, then they have been using SA to exit from the trap of local minimum. The core of their model is that they are generating alternative layout design by changing the order of priority levels 2 and 3 in each outer loop of SA algorithm. In other words, the starting point of new outer loop of SA is generated by the patter search algorithm. By changing the goal priority levels, huge pools of efficient solutions are generating. To solve this issue, they used what they called the filtering process to choose which sets of solutions have more different with the other ones. The logic behind this is giving decision‐makers the chance to consider how changing preferences’ priorities would impact the solutions.

The other important piece of research was written by Imam and Mir [14, 15]. Imam and Mir [14] introduce a heuristic algorithm to place unequal‐sized rectangular facilities in continuous plane by introducing the new concept of ‘controlled coverage’ by using ‘envelop blocks'. In the initial solution, facilities are randomly placed in plane in the envelop block the size of which is much larger than the actual size of facility and is calculated by multiplying magnification factor with the facilities’ actual dimensions. Afterwards, during the heuristic iterations, the sizes of envelop blocks are gradually decreased by decreasing the magnification factor until the dimensions of envelopes will became equal to the dimensions of their corresponding facilities. By this approach, they were controlling the coverage of facilities together. The improvement iteration is based on the univariate search method. In this method, only one of the $2n$ design variables where $n$ is the number of facilities is changing at time. This change means moving facility horizontally or vertically along the x‐axis or y‐axis, respectively. There are three drawbacks to their method. Firstly, each iteration cycle is repeated $2n$ times, $n$ times to move facilities horizontally and then another $n$ more times to move them vertically. The other drawback is that facilities are just allowed to move horizontally or vertically, there is no diagonal movement. Thirdly, there are no borders for the assumed continuous plane. However, in real world, there is no plane without borders. The last drawback is related to magnification factor, they have not specified how large this factor has to be originally and by which fraction it has to be reduced in each iteration cycle.

Mir and Imam [15] have mentioned the second drawback above is addressed and try to improve their primary procedure. They develop a hybrid model by using SA for gaining the sub‐optimal initial feasible solution and then they improved it using a steepest descent approach. As they also noted that the number of optimization iterations depends of the magnification factor by which the size of the envelope blocks reduces when the magnification factor was being reduced. The algorithm stopped when the magnification factor is equal to one. So it is obvious that the computational cost and time are quite dependent on magnification factor.

On the other hand, there are various papers that considered alternative as a discrete approach. QAP is an NP‐complete problem, which means that when the size of the problem is increasing it cannot be solved by exact algorithm [16]. Hence, lots of efforts have been made to develop and apply heuristic and meta‐heuristic algorithm for this kind of problem. Wilhelm and Ward [16] have applied simulated annealing (SA) to solve QAP. Their results have been compared with the computerized relative allocation of facilities technique (CRAFT), biased sampling and revised Hillier problem and showed better quality solutions.

Baykasoğlu and Gindy [17] have applied SA for dynamic layout problem, discrete approach. They claim their proposed algorithm finds better solution. They compared their proposed algorithm to the three works done [18–20]. In the first comparison, their SA approach found optimum solution and revealed better solution than dynamic programming algorithm of Rosenblatt [18]. The second comparison has two experiments: first one carried out with no shifting cost and the SA algorithm found optimum solution and outperforms that Conway and Venkataramanan [19] genetic algorithm. In this experiment, relocation costs are included. The optimum solution was not found; however, the results of SA showed a slight improvement over that of Rosenblatt [18]. Finally, in the third comparison the data set obtained from Balakrishnan and Cheng [20]. They develop non‐linear genetic algorithm (NLGA). The comparison between the SA‐based approach and NLGA reveals the superiority of SA algorithm when the size of the problems is large. Since they have taken discrete approach to FLP, the only operator has been used in neighbourhood generation algorithm is the swap operator.

Tavakkoli-Moghaddam et al., [21] are developed a non-linear mathematical modelling to solve the cell formation in dynamic environment in which demand varies in each time horizon. The strength point of their model is that it is a multi‐objective model, i.e. considering more than one objective such as machine cost, operating cost, inter‐cell material handling cost and machine relocation cost. Three meta‐heuristic models, such as genetic algorithm (GA), simulated annealing (SA) and tabu search (TS), have been used to solve this problem. The results show SA outperforms compare to the two meta‐heuristics.

Safaei et al., [22] have developed a mixed integer programming which tries to minimize machine constant and variable costs, inter‐ and intra‐material handling cost and reconfiguration costs. They present a hybrid model called mean field annealing and simulated annealing (MFA‐SA) to solve the problem. MFA stands for mean field annealing which used to find the feasible initial solution for SA. Most of the developed heuristics in the literature have taken a discrete approach to FLP than a continuous one. Developing heuristics for the discrete problem is easier, because locations are predetermineda priori; hence, the only operator that is usually used is the swap operator, to shuffle the different facilities locations. Moreover, in the discrete approach no overlap would happen between facilities. On the other hand, it is harder to design heuristics for the continuous formulation of FLP since overlap takes place. It is usually the case that repeated repairs and checks of validity of the generated solutions have to take place.

3. Mathematical modelling

The problem is to arrange facilities that are cells in the leader problem and machine tools in the follower problem in their respective space. The site has a rectangular shape with specified length (L) and width (W). Moreover, there is a horizontal aisle in the site by the same length as of site, however, with two different vertical dimensions ${\mathbf{Y}}_{\mathbf{VALU}}$ and ${\mathbf{Y}}_{\mathbf{VALL}}$. Aisle divides the site into two sections, upper and lower. No facilities are allocated to the aisles. The objective is to minimize the total travel‐flow cost by considering shape, size and geometric characteristic of the different facilities. Facilities have a rectangular shape. The position of each facility is determined by the coordinates of its centroid as well as its predetermined length and width. Facilities are not allowed to overlap each other and have to be assigned in their related boundary areas, which is the overall site's boundaries for the follower problem and that of the cell for the leader problem. The traditional Cartesian coordinate system, shown in Figure 1, represents the scheme used in this chapter. The following model has represented by Allahyari and Azab [7, 8] and Allahayri [7]. The problem is formulated under the following assumptions [6]:

Figure 1.

Scheme of shop.

The problem is formulated under the following assumptions:

1. CF is known in advanced.

2. Machines are not in the same size.

3. Machines must be located within a given area.

4. Machines are not allowed to overlap each other.

5. Cell's dimensions and orientation are predetermined.

6. Each part type has a number of operations that must be processed based on its operation sequence readily available from the route sheet of parts. It should be noted that the process sequence of each part is different.

7. The demand for each part type in known and is constant.

8. Material handling devices moving the one part between machines.

9. Inter‐ and intra‐cell movements related to the part types have different costs that are related to the distance travelled. We assume the rectangular distance between each pair of machines’ centroid.

10. In determining machine size and dimensions, the workspace required for operator usage and that needed to enforce between the different machines have been taken into account.

The mathematical formulation represented as below

Sets:

1. $P=\mathrm{\{}1,2,3,\dots ,P\mathrm{\}}$ Index set of part types

2. $M=\mathrm{\{}1,2,3,\dots ,M\mathrm{\}}$ Index set of machine types

3. $C=\mathrm{\{}1,2,3,\dots ,C\mathrm{\}}$ Index set of cell types

4. $O_p=\mathrm{\{}1,2,3,\dots ,O_p\mathrm{\}}$ Index set of operations indices for part p

Parameters:

1. L Horizontal dimension of shop floor

2. W Vertical dimension of shop floor

3. $Y_{\text{VALU}}$ Vertical dimension of upper side of aisle

4. $Y_{\text{VALL}}$ Vertical dimension of lower side of aisle

5. $X_{\text{HALLF}}$ Horizontal dimension of left side of aisle

6. $X_{\text{HALRT}}$ Horizontal dimension of right side of aisle

7. $l_i$ Length of machine i

8. $w_i$ Width of machine i

9. $l_c$ Length of cell c

10. $w_c$ Width of cell c

11. $\mathit{C}{\mathit{A}}_{\mathit{j}}$ Intra‐cellular transfer unit cost for part j

12. $\mathit{C}{\mathit{E}}_{\mathit{j}}$ Inter‐cellular transfer unit cost for part j

13. ${\mathit{D}}_{\mathit{j}}$ Demand quantity for part j

14. $U_{joi}$ 1, if operation o of part j is done by machine i, otherwise 0

15. ${U^{\prime }}_{joi}$ 1, if operation o of part j is done by machine i which is located in cell c, otherwise 0

16. $Q_{ic}$ 1, if machine i is assigned in cell c

Decision variables:

1. ${\mathit{x}}_{\mathit{i}}$ Horizontal distance between centre of machine i and vertical reference line

2. ${\mathit{y}}_{\mathit{i}}$ Vertical distance between centre of machine i and horizontal reference line

3. ${{\mathit{x}}^{\prime }}_{\mathit{c}}$ Horizontal distance between centre of cell c and vertical reference line

4. ${{\mathit{y}}^{\prime }}_{\mathit{c}}$ Vertical distance between centre of cell c and horizontal reference line

5. $Z_{iu}$ 1, if machine u is arranged in the same horizontal level as machine i, and 0 otherwise

6. $W_{c{c}^{\prime }}$ 1, if cell $c$ is arranged in the same horizontal level as cell $c^{\prime }$ and 0 otherwise

7. $Z_c$ 1, if cell $c$ is arranged in out of aisle horizontal boundaries and 0 otherwise

8. $W_c$ 1, if cell $c$ is arranged in out of aisle vertical boundaries and 0 otherwise

The continuous bi‐level programming problem is defined as: the intra‐cell layout mathematical formulation to layout the different machines (machines here are the facilities) of every cell c at a time is as follows:

$\text{Min}{\displaystyle \sum }_{j=1}^P{\displaystyle \sum }_{o=1}^{o_p-1}{\displaystyle \sum }_{\begin{array}{c}i,u=1\\ i\ne u\end{array}}^M{U}_{joi} U_{jo+1u}\left(\left|x_i-x_u\right|+\left|y_i-y_u\right|\right)C{A}_j{D}_j$E1

s.t.

$x_i+\frac{l_i}{2}\le l_C\hspace{1em}\hspace{1em}i=1,\mathrm{..},M$E2

$x_i-\frac{l_i}{2} \ge 0\hspace{1em}\hspace{1em}i=1,\mathrm{..},M$E3

$y_i+\frac{w_i}{2}\le w_c\hspace{1em} i=1,\mathrm{..},M$E4

$y_i-\frac{w_i}{2}\ge 0\hspace{1em}\hspace{1em}i=1,\mathrm{..},M$E5

$\left|x_i-x_u\right|\ge Z_{iu}\left(l_i+l_u\right)/2\hspace{1em}\hspace{1em}i,u=1,\mathrm{..},M$E6

$\left|y_i-y_u\right|\ge (1-Z_{iu})\left(w_i+w_u\right)/2\hspace{1em}\hspace{1em}i,u=1,\mathrm{..},M$E7

$x_i, y_i\ge 0,Z_{iu}\text{are}\text{binary}\hspace{1em}\hspace{1em}i,u=1,\mathrm{..},M$E8

Equation (1) declares the objective function of leader problem, which is minimizes the total intra‐cell transportation cost of parts. Equations (2)–(5) are within site constraints that ensure each machine tool is assigned within the boundaries of its corresponding cell. Equations (6) and (7) force the overlap elimination for machine tools. Equation (8) represents the nature of the decision variables which are binary and non‐negative.

Finally, the inter‐cell layout problem tries to layout the different cells (cells here are the facilities) of the entire shop floor is as follows:

$\text{Min}{{\displaystyle \sum }}_{j=1}^P{\displaystyle \sum }_{o=1}^{o_p-1}{\displaystyle \sum }_{\begin{array}{c}c,c^{\prime }=1\\ c\ne c^{\prime }\end{array}}^C{U^{\prime }}_{joc} {U^{\prime }}_{jo+1c^{\prime }} \left(\left|{x^{\prime }}_c-{x^{\prime }}_{c^{\prime }}\right|+\left|{y^{\prime }}_c-{y^{\prime }}_{c^{\prime }}\right|\right)C{E}_j{D}_j$E9

s.t

${x^{\prime }}_c+\frac{{l^{\prime }}_c}{2}\le L\hspace{1em}\hspace{1em}c=1,\mathrm{..},C$E10

${x^{\prime }}_c-\frac{{l^{\prime }}_c}{2}\ge 0\hspace{1em}\hspace{1em}c=1,\mathrm{..},C$E11

${y^{\prime }}_c+\frac{{w^{\prime }}_c}{2}\le W\hspace{1em}c=1,\mathrm{..},C$E12

${y^{\prime }}_c-\frac{{w^{\prime }}_c}{2}\ge 0\hspace{1em}\hspace{0.5em}c=1,\mathrm{..},C$E13

$\left|{x^{\prime }}_c-{x^{\prime }}_{c^{\prime }}\right|\ge W_{c{c}^{\prime }}\left({l^{\prime }}_c+{l^{\prime }}_{c^{\prime }}\right)/2\hspace{1em}\hspace{1em}\hspace{1em} c,c^{\prime }=1,\mathrm{..},C$E14

$\left|{y^{\prime }}_c-{y^{\prime }}_{c^{\prime }}\right|\ge (1-W_{c{c}^{\prime }})\left({w^{\prime }}_c+{w^{\prime }}_{c^{\prime }}\right)/2\hspace{1em}c,c^{\prime }=1,\mathrm{..},C$E15

Aisle constraints:

Horizontal aisle:

$\left({{\mathit{y}}^{\prime }}_{\mathit{c}}+{{\mathit{w}}^{\prime }}_{\mathit{c}}/\mathbf{2}\right)-{\mathit{Y}}_{\mathit{\text{VALL}}}\le \text{M} {\mathit{Z}}_{\mathit{c}}$E16

${\mathit{Y}}_{\mathbf{\text{VALU}}}-\left({{\mathit{y}}^{\prime }}_{\mathit{c}}-{{\mathit{w}}^{\prime }}_{\mathit{c}}/\mathbf{2}\right)\le \text{M} (\mathbf{1}-{\mathit{Z}}_{\mathit{c}})$E17

Vertical aisle:

$\left({{\mathit{x}}^{\prime }}_{\mathit{c}}-{{\mathit{l}}^{\prime }}_{\mathit{c}}/\mathbf{2}\right)-{\mathit{X}}_{\mathbf{\text{HALRT}}}\le \mathit{M}{\mathit{W}}_{\mathit{c}}$E18

${\mathit{X}}_{\mathit{\text{HALLF}}}-\left({{\mathit{x}}^{\prime }}_{\mathit{c}}+{{\mathit{l}}^{\prime }}_{\mathit{c}}/\mathbf{2}\right)\le \mathit{M} (\mathbf{1}-{\mathit{W}}_{\mathit{c}})$E19

${{\mathit{x}}^{\prime }}_{\mathit{c}},{{\mathit{y}}^{\prime }}_{\mathit{c}}\ge \mathit{0},{\mathbf{W}}_{\mathit{c}{\mathit{c}}^{\prime }},{\mathit{Z}}_{\mathit{c}},{\mathit{W}}_{\mathit{c}} \mathrm{are} \mathrm{binary}\mathit{c}=\mathit{1},\mathrm{..},\mathit{C}$E20

Equation (9) represents the objective function of follower program. The objective function minimizes the inter‐cell transportation cost of parts. The within‐site constraints are enforced by the set of constraints 10–13; i.e. these constraints ensure that cells are assigned within the boundaries of shop floor. Moreover, overlap elimination constraints are defined by constraints (14) and (15) which enforce the overlap elimination among cells. Equations (16) and (19) in the follower problem ensure that no cells would be assigned in the aisle boundaries. Finally, Eq. (20) specifies that the decision variables are binary and positive.

4. Simulated annealing

Simulated annealing is a stochastic neighbourhood search technique, which was initially developed by Metropolis and applied to combinatorial problems by Kirkpatrich et al. [25] for the first time.

To begin with, the basic of SA is based on statistical mechanics and comes from the similarity between the annealing of solids process and the solving method of combinatorial problem. If each feasible solution to the combinatorial optimization problem as a configuration of atoms and the objective function value of corresponding feasible solution as the energy of the system, then the optimal solution of combinatorial optimization problem is as like as the lowest energy state of the physical system [23]. The core of heuristic algorithms for solving the combinatorial problem is based on continual improvement, moving from one solution to another one in order to decrease the objective function from one iteration to next one. The same procedure is taking in quenching the system from high to low temperature in order to reach the required quality.

4.1. The elements of an SA algorithm

The core of SA algorithm is Metropolis algorithm, which allows uphill moves sometimes. Metropolis algorithm has four main elements [24, 25]. Figure 2 represents the simulated annealing steps.

1. Initial solution and description of system configuration

   It is the starting point of SA algorithm. There are two main approaches for generating initial solution. One is generating initial solution randomly; by taking this approach feasibility of initial solution has to be considered. The second approach is getting feasible initial solution by adapting greedy algorithms or another heuristic algorithm. It has to be noted that initial solution should not be too good because escaping from its local optimum is hard.

2. Configuration changes

   By moving from one configuration to another one, new neighbourhood solution is generated. These changes occurred by defining some operators which are responsible to make changes in the current solution.

3. Objective function that represent the quantitative measurement of goodness of a system

   After finding any neighbour, the difference between objective value of new solution ($E_{n+1}$) and of the current solution $(E_n)$ is calculated. If $(\mathrm{∆}E<0)$, it means that the objective value of neighbourhood solution is showing improvement in comparison to the objective value of the current solution found so far $(\mathrm{∆}E<0)$. Hence, the current one will be accepted as the new best solution. On the other hand, if $(\mathrm{∆}E\ge 0)$ the new solution is accepted with a certain probability. Using this approach, SA tries to exit from the local optima region in which it trap. The probability is based on the so‐called Boltzmann probability distribution

   $\mathit{\text{Prob}}\left(\mathrm{∆}E\right)~\mathit{\text{exp}}\left(-\mathrm{∆}E/k_{b}T\right)$E21

   where $T$ is the parameter and $k_b$ is the Boltzmann's constant which is not required when Metropolis algorithm is applying to combinatorial problems [16]. The acceptance probability of new solution depends on two factors, one is how large is this difference. The bigger the difference, the lesser the chance of accepting this new solution. The second criterion is a control parameter (temperature). It should be noted if the initial temperature is not large enough or it decreases dramatically the chances that the algorithm traps at local optima is high.

4. Annealing schedule/cooling schedule

Figure 2.

Flowchart of simulated annealing.

The annealing schedule determines four rules:

1. Initial temperature: Since the annealing of solids is the basic of the SA approach, initial temperature is the melting point of SA algorithm and it should be defined in such a way that the solutions generated by high acceptance probability approximately close to one. Kirkpatrick et al. [25] noted that the initial temperature has to be large enough that 80% of generated solutions are accepted. Kia et al., [26] and Baykasoğlu and Gindy [17] defined initial solution high enough in such a way that 95% of generated candidates can be accepted using the following equation:

$T_0=\frac{\text{Obj}{v}_j-\text{Obj}{v}_i}{\text{ln}\left(0.95\right)}$E22

1. $\text{Obj}{v}_j$ and $\text{Obj}{v}_i$ are the objective values of two random solution i and j, respectively. It should be noted initial solution $T_0$ is generated once at the beginning of SA algorithm.

2. Temperature length

3. Termination: There are different approaches for stopping criteria such as

• A specific number of iteration

• Exact final temperature

• No improvement for a number of iteration

Based on the literature review, there are different approaches for choosing SA parameters as explained briefly in Table 2.

Author	Initial temperature (T0)	Cooling rate (α)	Temperature reduction	Loop length
				Inner	Outer
Bazargan-Lari and Kaebernick [11]	10	0.9	$t_i=10{(0.9)}^{i-1}$	$N^{\prime }\times n$	$K$
Baykasoğlu and Gindy [17]	$T_{\text{in}}=\frac{f_{\text{min}}-f_{\text{max}}}{ln{P}_c=\text{ln}(0.95)}$	$\propto ={\left(\frac{\text{ln}{P}_c}{\text{ln}{P}_f}\right)}^{\raisebox{1ex}{$1$}\!\left/ \!\raisebox{-1ex}{$(e{L}_{max}{}^{-1})$}\right.}$	$T_{el+1}=\alpha T_{e1}$	$I_L$>LMC	$e{l}_{\text{max}}$ calculated
Heragu and Alfa [27]	999	0.90	$T=rT$	Epoch concept; $N^{\prime }\times n$	$K$
Wilhelm and Ward [16]	10	0.9	$t_i=10{(0.9)}^{i-1}$	Epoch concept; $N^{\prime }\times n$	$K$

Table 2.

SA parameters.

Epoch: Predetermined specific number of successful pairwise interchanges at each temperature.

$N^{\prime }:$ Predetermined integer.

$n:$ Total number of facilities.

$K:$ Predetermined integer‐ the total number of temperature steps.

4.2. Developed simulated annealing for FLP

4.2.1. Initialization

A unique heuristic is used to generate a feasible initial solution for SA algorithm [7, 8]. The explanation of the developed heuristic is provided in Section 4.2.1.1.

4.2.1.1. Initialization heuristic

The mechanics of the developed algorithm are very different than any of the available heuristics in the literature. The whole idea behind our algorithm is to place facilities radially along vectors $\overrightarrow{r_f}$ that are originated from the centroid of the space considered, where all facilities are to be placed as shown in Figure 3. The radial vectors along which all facilities are to be placed are distant radially by an angle $\theta =\frac{{360}^0}{M}$.

At the start of the heuristic method, at first the given area is first divided into four equal size quadrants; i.e. ${\text{Q}}_1, {\text{Q}}_2, {\text{Q}}_3, \text{and} {\text{Q}}_4$. Afterwards, all facilities are placed on top of each other in the middle of the given area. The developed heuristic algorithm consists of the two nested loops.

4.2.1.1.1. Outer loop

For each iteration of the outer loop, one random facility (called target facility) $f_G$ is chosen and located radially along the radius $(r_f)$, which is making an angle ${\theta }^{\prime }$ with the abscissa, as shown in Figure 3.

$\acute{\theta }=i\times \theta i=1,2,\dots ,M$E23

Facilities are permitted to be placed within the boundaries of the given area. In order to satisfy this constraint, vector $\overrightarrow{a}$, which is a vector of random magnitude along vector's $\overrightarrow{r_f}$ direction, is taken, and facility, $f_G$, is placed at the end of this vector. The length of vector $\overrightarrow{a}$ is a random number between $\left[0,\left|\overrightarrow{r_f}\right|-r\right]$, where $r$ is the length of the diagonal of facility $f_G$. The next step is checking the possibilities for overlap between all facilities. If any overlap occurs between the target facility $f_G$ and the given area's boundaries or between target facility $f_G$ and the previously placed facilities, the inner loop is triggered. It should be noted that the facility coordinates for each is calculated based on an origin that is located at the bottom‐left corner of the site as shown in Figure 3.

4.2.1.1.2. Inner loop

Different repair functions based on the type of overlap are being developed to eliminate overlap. Repair functions guarantee the elimination of overlap between facilities and allocation of the facility within the boundaries of its corresponding quadrant. However, if the corresponding quadrant is too congested, the overlapped facility can be placed partially in a different quadrant. Nevertheless, no facilities are allowed to violate the given area boundaries. The inner loop has two main steps: in the first step, the overlap between facility $f_G$ and the overlapped facility $f_j$ is repaired. Afterwards, overlap checking is performed for all facilities starting from the last placed facility to the first one to see if repair done in previous step has caused further overlaps or not. If no overlap takes place, the inner loop is ended and algorithm goes back to the outer loop to place another facility, given a facility is still left to be placed. However, if overlap is detected when checking for overlap between all the facilities, the second step of the inner loop is enacted.

The second step of the inner loop consists of few iterations. In each iteration, as explained one facility $f_i$ is selected as target facility, and then the possibility of overlap between the target facility and rest of previously placed facilities is checked. If there is overlap between the target facility $f_i$ and facility $f_j$, overlap elimination algorithms are enacted. The overlap has two main projections: one in the x‐direction, $\mathrm{∆}x,$ and another in the y‐direction, $\mathrm{∆}y$.$\mathrm{∆}x$ represents the horizontal overlap between the two facilities $f_i$ and $f_j$. In a similar fashion, $\mathrm{∆}y$ shows the vertical overlap between the two overlapped facilities as demonstrated in Figure 4. If $\mathrm{∆}x\le \mathrm{∆}y,$ the overlap is fixed by removing overlap in the $x$‐projection direction; otherwise, it does that in the y‐direction. The repair mechanism starts by moving target facility $f_i$ by the overlap distance $\mathrm{∆}$ in appropriate direction.

Since no facility is allowed to violate the given area's boundaries, there is a need to know how much distance left between facility $f_i$ and cell/floor (or quarter) boundaries. If the distance left is less than overlap $\mathrm{∆}$, then overlap elimination is carried out for the facility $f_j$. Moreover, if the distance left between the facility $f_j$ and site (or quarter) boundaries is not less than overlap $\mathrm{∆}$, the overlap distance $\mathrm{∆}$ should be applied to both facilities $f_i$ and $f_j$. At the end of each iteration, the overlap is checked once again to tackle any possibility of newly occurred overlap. This loop is repeated until all overlap and intersection between facilities are repaired. The summary of the developed initialization heuristic is represented in Figure 5.

4.2.2. Neighbourhood solution scheme

In order to generate new neighbourhood solution, two main operators, namely, move operator and swap operator, have been developed. The move operator tries to make facilities close to each other and also the swap operator switches the location of the two facilities. The details about these two operators explained below.

4.2.2.1. Move operator

The developed move operator tries to reduce distances between the facilities. The logic behind this algorithm is decreasing the distance between one facility called in‐context facility, which is chosen randomly and the closest facility towards that. By moving the in‐context facility towards its closest facility, the possibility of overlap between in‐context facility and the rest of facilities is decreased. Main point here is that how much the maximum_movable_ distance is. Maximum_movable_ distance is the maximum length which if in‐context facility moved towards its closest facility no overlap will happen between them. The steps of move operator algorithm are explained below:

1. Randomly choose one facility, called in‐context facility $f_G$.

2. The Euclidean distance between the centroid of in‐context facility $f_G$ and the rest of facilities is calculated.

   ${\text{Dis}}_{Gi}=\sqrt{{\left(X_G-X_i\right)}^2-{\left(Y_G-Y_i\right)}^2} \forall i=1,2,\dots ,M \text{and} i\ne G$E24

3. Facilities are sorted based on the distances found in step 2 in the descending order. The first one among the above set would be the closest facility $f_C$ to the in‐context facility $f_G$.

4. Divide the in‐context facility $f_G$ into four equal‐sized quadrants by the origin of its centroid.

5. Find in which quadrant of in‐context facility $f_G$ the closest facility $f_C$ is located.

6. At this point the maximum _movable_ distance $\left|\overrightarrow{C{C}^{\prime }}\right|$ is calculated. For finding this distance, two points $C$ and $C^{\prime }$ have to be found. $C$ is the conjunction of vector $\overrightarrow{r^{\prime }}$ and the closest boundary of in‐context facility $f_G$ to the closest facility $f_C$; and $C^{\prime }$ is the conjunction of vector $\overrightarrow{r^{\prime \prime }}$ and the closest boundary of closest facility to in‐context facility. To do this, these concepts are defined:

   1. $\overrightarrow{O^{\prime }{O}^{\prime \prime }}$: Vector between centroids of in‐context facility $f_G$ and closest facility $f_C$.

   2. $\left|\overrightarrow{C{C}^{\prime }}\right|$: Maximum_movable_distance

   3. ${\theta }_1$: The angle between vector $\overrightarrow{O^{\prime }{O}^{\prime \prime }}$ and horizontal line

   4. ${\theta }_2$: The angle between vector $\overrightarrow{O^{\prime }{O}^{\prime \prime }}$ and vertical line

   5. $\overrightarrow{r^{\prime }}:$ Vector from centroid of in‐context facility $O^{\prime }$ to the closest boundary of in‐context facility $f_G$ towards the closet facility $f_C.$

   6. $\overrightarrow{r^{\prime \prime }}:$ Vector from centroid of the closest facility $O^{\prime \prime }$ to the closet boundary of the closest facility $f_C$ toward the in‐context facility $f_G$.

${\theta }_1={\text{tan}}^{-1}\frac{\left|\text{Opposite side}\right|}{\left|\text{Adjacent side}\right|}={\text{tan}}^{-1}\frac{\left|Y_G-Y_C\right|}{\left|X_G-X_C\right|}$E25

${\theta }_2={\text{tan}}^{-1}\frac{\left|\text{Opposite side}\right|}{\left|\text{Adjacent side}\right|}={\text{tan}}^{-1}\frac{\left|X_G-X_C\right|}{\left|Y_G-Y_C\right|}$E26

Also: ${\theta }_2=90-{\theta }_1$

where $X_G$ and $Y_G$ are vertical and horizontal coordinates of centroid of in‐context facility $f_G$, respectively. Similarly, $X_C$ and $Y_C$ are vertical and horizontal coordinates of centroid of in‐context facility $f_C,$ respectively.

It has to be noted, the length of both vectors $\overrightarrow{r^{\text{'}}}$ and $\overrightarrow{r^{\text{'}\text{'}}}$ depends on their corresponding angles ${\theta }_1$ and ${\theta }_2$. Figures 6 and 7 illustrate this topic.

$\left|\overrightarrow{r^{\prime }}\right|=\{\begin{array}{c}\frac{Adjacent side}{Cos{\theta }_1}=\frac{\raisebox{1ex}{$L_G$}\!\left/ \!\raisebox{-1ex}{$2$}\right.}{Cos{\theta }_1} if 0\le {\theta }_1\le {45}^0\\ \frac{Opposite side}{Sin{\theta }_1}=\frac{\raisebox{1ex}{$W_G$}\!\left/ \!\raisebox{-1ex}{$2$}\right.}{Sin{\theta }_1} if {45}^0\le {\theta }_1\le {90}^0\end{array}$E27

$\left|\overrightarrow{r^{″}}\right|=\{\begin{array}{c}\frac{Adjacent side}{Cos{\theta }_2}=\frac{\raisebox{1ex}{$W_C$}\!\left/ \!\raisebox{-1ex}{$2$}\right.}{Cos{\theta }_1} if 0\le {\theta }_2\le {45}^0\\ \frac{Opposite side}{Sin{\theta }_2}=\frac{\raisebox{1ex}{$L_C$}\!\left/ \!\raisebox{-1ex}{$2$}\right.}{Sin{\theta }_1} if {45}^0\le {\theta }_2\le {90}^0\end{array}$E28

where $L_G$ and $W_G$ are length and width of in‐context facility $f_G,$ respectively. Similarly, $L_C$ and $W_C$ are length and width of in‐context facility $f_C,$ respectively.

Based on in which quadrant closing facility is located, $C$ and $C^{\prime }$ coordinates are calculating by equations shown in Table 3.

	Coordinates
Quadrant	$c$	$c^{\prime }$
1	$(X_G+r^{\prime }Cos{\theta }_1, Y_G+r^{\prime }Sin{\theta }_1)$	$(X_i-r^{\prime \prime }Cos{\theta }_2, Y_i-r^{\prime \prime }Sin{\theta }_2)$
2	$(X_G-r^{\prime }Cos{\theta }_1, Y_G+r^{\prime }Sin{\theta }_1)$	$(X_i+r^{\prime \prime }Cos{\theta }_2, Y_i-r^{\prime \prime }Sin{\theta }_2)$
3	$(X_G-r^{\prime }Cos{\theta }_1, Y_G-r^{\prime }Sin{\theta }_1)$	$(X_i+r^{\prime \prime }Cos{\theta }_2, Y_i+r^{\prime \prime }Sin{\theta }_2)$
4	$(X_G+r^{\prime }Cos{\theta }_1, Y_G-r^{\prime }Sin{\theta }_1)$	$(X_i-r^{\prime \prime }Cos{\theta }_2, Y_i+r^{\prime \prime }Sin{\theta }_2)$

Table 3.

$C$ and $C^{\prime }$ coordinates.

Hence, the length of vector $\left|\overrightarrow{C{C}^{\prime }}\right|$ is

$\left|\overrightarrow{C{C}^{\prime }}\right|=\sqrt{{\left(X_C-X_{C^{\prime }}\right)}^2-{\left(Y_C-Y_{C^{\prime }}\right)}^2}$E29

7. At this point the length of the movement, called $ml$ is the random number in interval $(0,\left|\overrightarrow{C{C}^{\prime }}\right|].$ Furthermore, the direction of movement is along the vector $\overrightarrow{C{C}^{\prime }}$.

8. If the closest facility is adjacent to the facility $f_G$, find the other closest facility and go to step 5, otherwise go to step 9.

9. Finally, new coordinates of in‐context facility $f_G$ are calculated and shown in Table 4.

	New coordinates of target facility
Direction	$X_G$	$Y_G$
Quadrant 1	$X_G+ml*\text{Cos}{\theta }_1$	$Y_G+ml*\text{Sin}{\theta }_1$
Quadrant 2	$X_G-ml*\text{Cos}{\theta }_1$	$Y_G+ml*\text{Sin}{\theta }_1$
Quadrant 3	$X_G-ml*\text{Cos}{\theta }_1$	$Y_G-ml*\text{Sin}{\theta }_1$
Quadrant 4	$X_G+ml*\text{Cos}{\theta }_1$	$Y_G-ml*\text{Sin}{\theta }_1$

Table 4.

New coordinate of $f_G$ after move.

4.2.2.2. Swap operator

The second operator of the developed SA is the swap operator which is switching positions of two facilities. The point here is how swap two facilities together that with the minimum possibility of overlap. To do that, the new concepts called free zone is defined. To apply this concept, a random facility called $f_G$ is chosen and the available free space around this facility called $F{Z}_G$ is determined by applying the maximum_movable_distance concept introduced in move operator. It has to be noted the centroid of free zone $F{Z}_G$ is the same as centroid of the facility $f_G$. If there is any facility whose area is greater than the area of the facility $f_G$ and less than the area of free zone $F{Z}_G$ then that facility is qualified for swapping. By swapping this facility with facility $f_G$ the possibility of occurrence of overlap is minimized. Moreover, if there is more than one facility which are qualified to swap with the facility $f_G$, one facility is chosen randomly. Figure 8 shows the scheme of free zone concept. The algorithm below explained swap operator's steps in detail:

1. One facility is chosen randomly, called facility $f_G$.

2. The closest facility to the $f_G$ is determined‐details mentioned in move operator.

3. Maximum_movable_distance is calculated.

4. Free zone $F{Z}_G$ of facility $f_G$ is determined.

5. Areas of facility $f_G$ and $F{Z}_G$ are calculated.

6. Among the rest of facilities those ones whose areas are greater than the area of facility $f_G$ and less than the area of free zone $F{Z}_G$ are found.

7. Randomly one facility among those facilities is found in step 6 is chosen, call it $f_i$.

8. Swap facility $f_G$ to the facility $f_i$.

9. Calculated the new coordinates of both $f_G$ and $f_i$.

10. End

Assume:

1. $L_G$: Length of the $f_G$

2. $W_G$: Width of the $f_G$

3. $ml$: Maximum movable distance

4. LFZ: Length of the FZ

5. WFZ: Width of the FZ

6. AFZ: Area of FZ

$AC=\text{min}\left(\left(X_G-\raisebox{1ex}{$L_G$}\!\left/ \!\raisebox{-1ex}{$2$}\right.\right),ml\times \text{Cos}{\theta }_1\right)$E30

$A{C}^{\prime }=\text{min}\left(\left(Y_G-\raisebox{1ex}{$W_G$}\!\left/ \!\raisebox{-1ex}{$2$}\right.\right),ml\times \text{Sin}{\theta }_1\right)$E31

$LFZ=L_G+2AC$E32

$WFZ=W_G+2A{C}^{\prime }$E33

$\text{AFZ}=\text{LFZ}\times \text{WFZ}$E34

4.2.3. Aisle constraints

In case of aisle, the operators move and swap vary. The details are presented in the below section.

4.2.3.1. Move operator

The move operator has the same procedure as the move operator developed in case of no aisle. Hence, in case of aisle one facility is chosen randomly $f_G$ and moves to its closest facility $f_C$. Afterwards, the possibility of overlap between aisle and new position of facility $f_G$ called ${\acute{f}}_G$ is considering. If any overlap happened, it has to be fixed. To do that, two repair functions have been developed.

4.2.3.2. Before‐aisle repair function

The idea behind this function is if there is any overlap between ${\acute{f}}_G$ and aisle happens, the facility ${\acute{f}}_G$ moves back exactly before the aisle. To illustrate, ${\acute{f}}_G$ backs to the back of boundary of aisle which it passed over. Figures 9 and 10 represent the overlap conditions in both cases of vertical and horizontal aisle.

The steps of the move operator with aisle constraints are explained as follows:

1. Step 1. Move facility $f_G$ towards its closest facility. Calculate new coordinates of facility $f_G$ and call it facility ${\acute{f}}_G$.

2. Step 2. Check overlaps possibility between ${\acute{f}}_G$ and aisle.

3. Step 3. If there is any overlap, take appropriate repair function.

4. Step 4. Find the coordinates of ${\acute{f}}_G$‐ —details are shown in Tables 5 and 6.

5. Step 5. End

Horizontal Aisle	${\mathit{x}}_{{\mathit{f}}_{\mathit{G}}}<{\mathit{x}}_{{\acute{\mathit{f}}}_{\mathit{G}}}$	${\mathit{x}}_{{\mathit{f}}_{\mathit{G}}}\ge {\mathit{x}}_{{\acute{\mathit{f}}}_{\mathit{G}}}$
$y_{f_G}<Y_L$	$x_{{\acute{f}}_G}=x_{{\acute{f}}_G}-\text{Rep}\times \text{cos}\theta$ $x_{{\acute{f}}_G}=x_{{\acute{f}}_G}-\text{Rep}\times \text{sin}\theta$	$x_{{\acute{f}}_G}=x_{{\acute{f}}_G}+\text{Rep}\times \text{cos}\theta$ $x_{{\acute{f}}_G}=x_{{\acute{f}}_G}-\text{Rep}\times \text{sin}\theta$
$y_{f_G}>Y_L$	$x_{{\acute{f}}_G}=x_{{\acute{f}}_G}-\text{Rep}\times \text{cos}\theta$ $x_{{\acute{f}}_G}=x_{{\acute{f}}_G}+\text{Rep}\times \text{sin}\theta$	$x_{{\acute{f}}_G}=x_{{\acute{f}}_G}+\text{Rep}\times \text{cos}\theta$ $x_{{\acute{f}}_G}=x_{{\acute{f}}_G}+\text{Rep}\times \text{sin}\theta$

Table 5.

Revised coordinate based on before‐aisle repair function‐horizontal aisle.

Vertical Aisle	${\mathit{y}}_{{\mathit{f}}_{\mathit{G}}}<{\mathit{y}}_{{\acute{\mathit{f}}}_{\mathit{G}}}$	${\mathit{y}}_{{\mathit{f}}_{\mathit{G}}}\ge {\mathit{y}}_{{\acute{\mathit{f}}}_{\mathit{G}}}$
$x_{f_G}<X_L$	$x_{{\acute{f}}_G}=x_{{\acute{f}}_G}-\text{Rep}\times \text{cos}\theta$$x_{{\acute{f}}_G}=x_{{\acute{f}}_G}-\text{Rep}\times \text{sin}\theta$	$x_{{\acute{f}}_G}=x_{{\acute{f}}_G}-\text{Rep}\times \text{cos}\theta$$x_{{\acute{f}}_G}=x_{{\acute{f}}_G}+\text{Rep}\times \text{sin}\theta$
$x_{f_G}>X_L$	$x_{{\acute{f}}_G}=x_{{\acute{f}}_G}+\text{Rep}\times \text{cos}\theta$$x_{{\acute{f}}_G}=x_{{\acute{f}}_G}-\text{Rep}\times \text{sin}\theta$	$x_{{\acute{f}}_G}=x_{{\acute{f}}_G}+\text{Rep}\times \text{cos}\theta$$x_{{\acute{f}}_G}=x_{{\acute{f}}_G}+\text{Rep}\times \text{sin}\theta$

Table 6.

Revised coordinate based on before‐aisle repair function‐vertical aisle.

Repair function‐horizontal aisle

• Facility $f_G$ is lower side of the aisle is

  $\text{Rep}=\raisebox{1ex}{$\left(\left({ý}_G+\raisebox{1ex}{$W_G$}\!\left/ \!\raisebox{-1ex}{$2$}\right.\right)-\left(Y_A-\raisebox{1ex}{$w_A$}\!\left/ \!\raisebox{-1ex}{$2$}\right.\right)\right)$}\!\left/ \!\raisebox{-1ex}{$\text{Sin}\theta $}\right.$E35

• Facility $f_G$ is upper side of the aisle:

$\text{Rep}=\raisebox{1ex}{$\left(\left(Y_A+\raisebox{1ex}{$W_A$}\!\left/ \!\raisebox{-1ex}{$2$}\right.\right)-\left({ý}_G-\raisebox{1ex}{$w_G$}\!\left/ \!\raisebox{-1ex}{$2$}\right.\right)\right)$}\!\left/ \!\raisebox{-1ex}{$\text{Sin}\theta $}\right.$E36

Repair function‐vertical aisle

• Facility $f_G$ is in the left side of the aisle:

  $\text{Rep}=\raisebox{1ex}{$\left(\left({\acute{x}}_G+\raisebox{1ex}{$l_G$}\!\left/ \!\raisebox{-1ex}{$2$}\right.\right)-\left(X_A-\raisebox{1ex}{$L_A$}\!\left/ \!\raisebox{-1ex}{$2$}\right.\right)\right)$}\!\left/ \!\raisebox{-1ex}{$\text{Cos}\theta $}\right.$E37

• Facility $f_G$ is in the right side of the aisle:

$\text{Rep}=\raisebox{1ex}{$\left(\left(X_A+\raisebox{1ex}{$L_A$}\!\left/ \!\raisebox{-1ex}{$2$}\right.\right)-\left({\acute{x}}_G-\raisebox{1ex}{$l_G$}\!\left/ \!\raisebox{-1ex}{$2$}\right.\right)\right)$}\!\left/ \!\raisebox{-1ex}{$\text{Cos}\theta $}\right.$E38

4.2.4. Developed SA algorithm

In this chapter, the parameters taken by Bazargan‐Lari and Kaebernick [10] have been used in the developed SA algorithm:

1. Initial temperature: 10

2. Cooling rate: 0.9

3. Temperature reduction: $t_i=10{\left(0.9\right)}^{i-1}$

4. Outer loop: 25

5. Inner loop: $100\times M$, $M$ is the total number of facilities

Figure 3.

The mechanics of developed heuristics.

Figure 4.

Scheme of overlap between two facilities $f_i$ and $f_j$.

Figure 5.

Summary of developed initialization heuristic algorithm.

Figure 6.

Angle calculation in move operator (I).

Figure 7.

Concept of angle in move operator (II).

Figure 8.

Free zone concept.

Figure 9.

Before‐aisle move operator for horizontal aisle.

Figure 10.

Before‐aisle move operator for vertical aisle.

5. Case study

Carbide Tool Inc. manufactures and distributes metalworking tools. The company is dedicated to developing specialized carbide, polycrystalline diamond (PCD) and cubic boron nitride (CBN) inserts, as well as multi‐task tooling for the aerospace, automotive and mould‐die industries. The company currently has a process layout configuration. Five different kinds of family cutting insert tools are produced. Each part has specific monthly demand. There are different kinds of unequal sized grinding machine tools. Some of the machine tools have identical copies on the shop floor to increase productivity. Therefore, the demand is being shared among the different copies of those machine tools. Different operations are performed on inserts with different sequences. The list of operations of each insert and the machine tools used for those operations are shown in Table 7.

ID	Machine	Dimension		Cutting insert tools
		Length	Width	Dog bone	S Shape	Triangular	Top notch	Diamond type 1	Diamond type 2	Diamond type 3
M1	Double disk (1)	12.67	5		O1	O2
M2	Blanchard (2)	6	9.07			O1	O1	O1	O1
M3	Wendt (3)	8.5; 6.8	6.1; 9.45	O1	O2	O4	O2	O2	O2
M4	Polish (1)	6	5			O3
M5	EWAG (1)	4.3	7.3					O7		O3
M6	Surface grinding (2)	7	6	O4	O5	O5	O3
M7	Surface grinding (1)	6	7.54					O3	O3
M8	Swing fixture (1)	8	6	O2	O3
M9	V‐bottom (1)	7	6	O3	O4
M10	Wire cutting (2)	7.8; 7.4	6.7; 5.7					O4	O4
M11	Laser M/C (1)	7.6	9.74						O6
M12	Brazing (1)	4	1.8					O6	O5	O1
M13	ETCH (1)	3	4	O5	O5	O6	O4	O8	O7	O3
ST1	Inspection (1)	4	3	O6	O6	O7	O5	O9	O8	O4
ST2	Wash (1)	5	3	O7	O7	O8	O6	O10	O9	O5
ST3	Packing (1)	16	8	O8	O8	O9	O7	O11	O10	O6
		Part demand		1200	900	500	500	600	600	200

Table 7.

Machine tool characterizations and parts’ operations sequence.

The company's shop floor has a rectangular shape. There is no special material handling device for transforming unfinished products among machine tools. As demonstrated in Table 7, it is obvious that the number of operations performed on each part insert tool is large enough; hence, the amount of travel taking place every day on the production floor is quite significant. Additionally, as per their original layout, all the raw materials are transported from the back side of the shop to the front to start operation. This causes extra unnecessary travel, and hence extra material handling cost. The inspection and shipping stations which are two of the last steps as per the sequence of operations are not properly positioned in the current layout, because they are located in front of the floor. Since the current layout is process layout, similar machine tools are grouped together and located on one side of the floor. The original layout is causing too much traffic, since it is not taking into account the sequence of processing of parts. For an example, the primary operations of all insert tools are performed by the combination of three machine tools: Double Disk, Blanchard and Wendt. All Wendt machines are located in upper side of hall, while Blanchard and Double Disk machines are arranged in the lower side. Therefore, it could be concluded that there are too much back and forth travel being done between the two sides of the floor just for performing the first couple of operations.

Cell name	Machine tools/work station
Primary	M1 (1)	M2 (2)	M4 (1)	M3 (3)
Grinding	M6 (2)	M8 (2)	M9 (1)
Diamond	M10 (2)	M7 (1)	M5 (1)	M12 (1)	M11 (1)
Final	M13 (1)	ST1 (1)	ST2 (1)	ST3 (1)

Table 8.

GF results.

After having several meetings with the plant manager and executive board of the company, cellular layout was chosen as the best layout plan. Group formation was performed by the plant manager. Four cells with specific types of machine tools were designed as given in Table 8. The problem was solved using both the developed mathematical model and heuristic [7].

Cells	Dimension		Centroid		MHC (material handling cost)
	Length	Width	$\mathit{X}$	$\mathit{Y}$
Primary	35	25	42.5	13.5	$1191.550
Grinding	26	20	74	50	$520.588
Diamond	30	20	45	59.22	$764.580
Final	30	20	75	8	$1056.350
Aisle	90	60	45	32.5

Table 9.

Intra‐cell material handling costs and inter‐cell dimensions of cells.

5.1. Mathematical model

5.1.1. Intra‐cellular layout

For the leader problem the layout of the different machine tools and work stations in their respective cells are being solved. The intra‐cellular travel cost per unit distance per one unit of each respective part are ¢10, ¢10, ¢15, ¢12 and ¢20, respectively for Dog Bone, S Shape, Triangular, Top Notch and all types of Diamond. The results for intra‐cellular layout are summarized in Table 9.

5.1.2. Inter‐cellular layout

In the follower problem, the four cells with exact dimensions are located on the 90” × 60” shop floor. The inter‐cellular travel cost per unit distance for each unit of Dog Bone, S shape, Triangular, Top Notch, and Diamond are ¢12, ¢12, ¢18, ¢15, and ¢20, respectively. Material handling cost for the inter‐cellular layout is $7520.42. Table 11 shows the coordinates of cells based on inter‐cellular layout plan. The final sketch of inter‐cellular and intra‐cellular layout is shown in Figure 11.

Cell	Machine	Coordinates
		X	Y
Primary	Blanchard	14.5	18.30
	Blanchard	21.27	17.16
	Polish	14.5	5.98
	Wendt	6.58	7.64
	Wendt	23.34	4.45
	Double Disc	23.83	10
	Wendt	7.25	17.72
	MHC	$734.581
Grinding	Surface grinding	16.79	4
	Surface grinding	21.05	16
	Swing fixture	18.97	10
	Swing fixture	5.72	15.26
	V‐bottom	8.55	6.76
	MHC	$669.480
Diamond	Wire cutting	10.39	3.8
	Wire cutting	5.50	10
	Surface grinding	18	5.64
	Brazing	26	10
	Ewag	11.53	16.31
	Laser M/c	18.8	14.87
	MHC	$808.640
Final	ETCH	26.19	9
	Wash	15	12.42
	Inspection	4.89	9
	Packing	15	5
	MHC	$2410.760

Table 10.

Machine coordinates based on heuristic.

5.2. Heuristic

The heuristic is applied to solve the intra‐cellular layout problems for each respective cell. The results obtained are provided in Table 10 and plotted in Figure 12. The material handling cost for the inter‐cellular layout is $6134.50 [6].

Method	Leader problem				Follower problem
	Primary cell	Grinding cell	Diamond cell	Final cell	Shop
NLMIP	$ 1191.550	$520.588	$764.580	$1056.350	$7520.420
LMIP	$503.024	$399.750	$360.800	$685.200	$2838.6
SA	$701.592	$526.004	$787.940	$856.508	$6167.6

Table 11.

Comparisons between mathematical modelling and simulate annealing.

Figure 11.

Inter‐cell and intra‐cell layout plan.

5.3. Simulated annealing (SA)

5.3.1. To validate the proof of the efficiency of the developed SA algorithm, the developed SA was applied for 10 runs for each cells [8]

5.4. Discussion

The comparison between the solutions provided non‐linear, linear model and simulated annealing is represented in Table 11. The linear model gives the exact optimum solution, however simulated annealing provides near optimum solution. The results also prove this fact. In both leader and follower problem, i.e. intra‐ and inter‐cell, respectively, the total material handling cost is less than costs provided by non‐linear mixed integer programming and simulated annealing.

The follower problem solved by simulated annealing has just assumed aisle.

Generally speaking, the linearized model obviously has yielded exact optimal results which proved to be better than those obtained by both the simulated annealing and the original non‐linear model. This was quite expected; in most cases simulated annealing resulted in better solutions than the non‐linear model; however, there were cases where the non‐linear model results were slightly better than those obtained by simulated annealing. The exception was for grinding cell and diamond cell where the non‐linear model outperformed slightly than simulated annealing.

Table 12 summarizes the results from both leader and follower problems. Both mean and SDV from the performed 10 runs are being provided. Standard deviation is good except for inter‐cell layout problem. For inter‐cell, we believe the algorithm is yet to be improved, and variance as shown in Table 12 is relatively high.

Cell	Average	SDV
Primary	$633.86	$11.19
Grinding	$492.44	$15.63
Diamond	$759.790	$22.315
Final	$902.62	$32.23
Inter‐cell	$5474.61	$423.97

Table 12.

Mean and standard deviation of SA solutions.

Figure 12.

Heuristic results showing layout presented at intra‐cell level for different cells (note: quadrant have been plotted demonstrating how facilities were spread around the different quadrants as per the working of the algorithm).

6. Conclusion

Cellular manufacturing system (CMS) layout has recently begun to receive heightened attention worldwide. The design of a CMS includes: (1) cell formation (CF), (2) group layout, (3) group and (4) resource allocation. An effective CMS implementation help any company improve machine utilization and quality; it also makes reduction in setup time, work‐in‐process inventory, material handling cost, part makespan and expediting costs.

There are two main approaches to FLP such as the discrete and continuous approaches. The discrete approach holds two main assumptions: one is all facilities are equal size and shape; the other one is predetermined locations of facilities. However, these kinds of assumptions are not realistic. The discrete approach is not suited to represent the exact locations of facilities. Moreover, this approach is not applicable for FLP with unequal size and shape facilities. The appropriate approach to this kind of FLP is continuous representation.

Generally speaking, the design of layout cannot be efficient if manufacturing attributes are not being considered in it. To illustrate, operation sequencing and parts’ demand are the two factors that have significant impacts on the flow rate which minimizes the main objective of FLP. The majority of literature studies have not considered these factors in the design of layout plan. Besides those manufacturing attributes, the available area of the shop that can be used for locating facilities is the other factor that has to be considered.

The facility layout problem for cellular manufacturing system in both inter‐ and intra‐cellular levels is considered in this chapter. The problem is to arrange facilities that are cells in the leader problem and machine tools in the follower problem in the continual planar site. Operation sequence and parts’ demand are the two main manufacturing attributes considered in the developed model. The MIP has been presented for both leader and follower problems. The novel aisle constraints have been presented in the mathematical formulation. Since the model is non‐linear, the linearized model has been developed. Additionally, a novel mathematical modelling has been developed for considering block constraints such as fixed departments and facilities. Since the FLP is an NP‐hard problem, novel heuristics presented in this chapter.

A novel heuristic model developed for finding feasible initial solution for designed meta‐heuristic algorithm, simulated annealing. The initial solution is based on the radial movement. In other words, the algorithm placed facilities along the specific radius with certain angle within site. The algorithm starts with dividing site into four equal‐sized quadrants, start placing facilities into first quadrant to the fourth one. After placing any new facility, the overlap's possibility between facilities and between facility and site boundaries is being checked. The different repair functions have been designed for different cases.

The SA algorithm developed for both inter‐ and intra‐cellular problem. The results of heuristic have used to initialize the developed SA algorithm. However, in order to have more efficient SA, the cell size used in heuristic algorithm is assumed two times of the original size of the cells. The two main operators used are move and swap operators. The move operator decreases the distance between facilities by moving the target facility towards the closest facility to it. Furthermore, the swap operator developed by defining the concept of the free zone.