A robust approach to design a single facility layout plan in dynamic manufacturing environments using a permutation-based genetic algorithm

Abstract

During the past few decades, developing efficient methods to solve dynamic facility layout problems has been focused on significantly by practitioners and researchers. More specifically meta-heuristic algorithms, especially genetic algorithm, have been proven to be increasingly helpful to generate sub-optimal solutions for large-scale dynamic facility layout problems. Nevertheless, the uncertainty of the manufacturing factors in addition to the scale of the layout problem calls for a mixed genetic algorithm–robust approach that could provide a single unlimited layout design. The present research aims to devise a customized permutation-based robust genetic algorithm in dynamic manufacturing environments that is expected to be generating a unique robust layout for all the manufacturing periods. The numerical outcomes of the proposed robust genetic algorithm indicate significant cost improvements compared to the conventional genetic algorithm methods and a selective number of other heuristic and meta-heuristic techniques.

Introduction

In competitive global markets, it is vital for a manufacturing firm to be able to adapt to the volatile demand conditions. The high capital that is invested in manufacturing systems requires an efficient order of machinery to meet consumers’ needs. Under these circumstances, it is critical to develop a flexible manufacturing line that is designed to be fulfilling the need for a variety of products, both under volatile demand conditions and with minimal changes in the initial machinery layout. Thus, a cost-efficient layout design could lead to increasing levels of productivity and profitability of the firm.

Dynamic facility layout problem

Cellular manufacturing systems (CMS) offer the means to plan for efficient facility layouts specifically for multi-production lines.^1,2 So far, CMS has been for long the most efficient approach being applied by firms to cope with the ever changing characteristics of the global competitive markets.^3,4 Singh ⁵ defined three stages for developing CMSs including (1) intra-cellular layout, (2) inter-cellular layout, and (3) categorizing parts into groups with similar manufacturing characteristics. However, considering the likelihood of frequent changes in the features of the products, cell layout could often be impracticable or uneconomical for the manufacturer. ⁶ Therefore, dynamic facility layouts became a popular method to eliminate the aforementioned issues.

Dynamic facility layout problem (DFLP) aims at minimizing costs of material handlings and machinery rearrangements for multiple periods of manufacturing and varying demand quantities.^7–9 In a given case, when there are considerable rearrangement costs for each manufacturing period and the differences in scales of machinery are negligible, one should investigate a single layout that is usually achieved by deploying quadratic assignment problem (QAP). ¹⁰ The QAP method is also used for solving DFLP or originally CMS layout problems.^11,12 Several articles have investigated the various aspects of QAPs^8,13,14 with their main focus being on minimizing a function related to the travel of parts including the total material handling cost, part travel duration, and part traveling distance. ⁸ Generally, QAP is considered as one of the most complex problems that is highly unlikely to be optimally solved in a reasonable time for more than 25 facilities/cells.^6,15 Hence, solution methods based on heuristic and meta-heuristic principles were proposed to address this issue.

Genetic algorithms for solving DFLPs

Since QAP was notoriously time-consuming and complicated even for smaller-sized problems (i.e. number of facilities less than or equal to 30), the development of alternative meta-heuristics and evolutionary solutions for DFLPs gained popularity among the researchers.^10,16,17Figure 1 outlines the meta-heuristic algorithms that have been applied to this date for minimizing intra-cellular and inter-cellular layout costs.^17,18

Figure 1.

Hierarchy of the meta-heuristics.

There have been fundamental improvements in solving DFLPs using meta-heuristics and hybrid algorithms that could be further investigated in excellent reviews presented by Ghosh et al., ¹³ Moslemipour et al., ¹⁴ and Kulturel-Konak. ¹⁹ Genetic algorithm (GA) for solving DFLPs has since long become a rather common method in solving facility layout problems. ²⁰ GA can explore the solution space by adopting the concept of natural genetics and evolution theory.^21–23 There indeed exists a variety of articles contributing to the concept of GA application in DFLPs (see Table 1). However, according to Table 1, a smaller percentage of these researches are dedicated to DFLPs where there is an uncertainty of demand for each period of manufacturing (i.e. robust GA). ³⁸

Table 1.

Review of different GA methods applied for cell formation problems (2000–2015).

Article	Method	Description	Result
Zhao and Wu 24	Modified GA	A combination of multi-objectives and part routing of cell formation problems	Time-consuming Used for large-scale problems
Mak et al. 25	Applying an adaptive scheme for GA parameters	A genetic search technique for solving cell formation problems	Successful on benchmark problems
Ahuja et al. 26	Greedy GA	Including greedy principles in the GA formulation	Better quality of the results Used for combinatorial optimization problems
Brown and Sumichrast 27	Grouping GA (GGA)	A more accurate genetic algorithm solution for cell formation problems	More efficient solutions
Onwubolu and Mutingi 18	Competitive GA	Applying the objectives of intercell moves and cell load variation minimization	More accurate results than hybrid GA and TS
Zolfaghari and Liang 28	Tuned GA	Tuning the input parameters of GA by design of experiments (DOE) and analysis of variance (ANOVA)	Significant improvement of the results
Mansouri et al. 29	Multi-objective GA	Taking the chromosome as a decision variable vector and the fitness function as a vector of sub-objective functions	More efficient solutions than multi-objective cell formation techniques
Balakrishnan et al. 7	Hybrid GA	Applying an optimization-based crossover and a modified mutation	Used for large-scale problems More accurate results
El-Baz 21	GA	Considering different kinds of layouts	Minimizing the total material handling cost
Solimanpur et al. 30	Multi-fitness function GA	Solving a multi-objective mathematical programming and generating several near optimal solutions	Developing a decision support system for cell formation problems
Yasuda et al. 31	Multi-objective GGA (MOGGA)	The method is based on the cell formation, evaluation, and the similarity of products assigned to the machines	Cost-efficient and flexible layout design
Vila Gonçalves Filho and José Tiberti 32	New GGA	The proposed model includes new crossover, mutation operators, correction scheme, and a new codification scheme of chromosomes	The model is based on machine groups instead of individual machines A faster convergence
Boulif and Atif 33	Binary GA	Simultaneously using binary GA with branch and bound method	Outperforming classical GA
Defersha and Chen 34	Two-phase GA	Introducing several production factors and solving them by a two-phase GA	More flexible method More efficient results
Wu et al. 35	Hierarchical GA	Simultaneously solving cell formation and group layout problems	2%–20% better quality results
James et al. 36	Hybrid GGA (HGGA)	A combination of local search and grouping genetic algorithms (GGA)	Improving solution quality Reducing the variability of solutions
Tavakkoli-Moghaddam et al. 37	Integer coded GA	Assuming a dynamic and fuzzy demand environment and solving the problem with integer-coded GA	Used for large-scale problems
Pillai and Subbarao 38	Robust GA	Forecasting product mix and demand changes	The layout is not going to change over planning horizons
Defersha and Chen 39	Hybrid GA	Applying linear programming technique and hybrid GA for solving cell formation problems	Using the Simplex method to solve the problem that would generate global optimum solutions
Tunnukij and Hicks 40	Enhanced GGA (EnGGA)	The method applies rank-based roulette–elitist strategy for creating generations	More efficient output
Noktehdan et al. 41	Differential evolution GGA (DEGGA)	Combining features of DE and GGA to solve cell formation problems	Better grouping efficacy
Deljoo et al. 42	Modified GA	Solving dynamic product conditions with a modified GA	More efficient results
Datta et al. 43	Permutation-based GA	Using the permutation-based GA to solve single-row facility layout problems	Reaching global optimum solutions for large-scale problems
Junlin and Haizhou 44	Improved GA	Analyzing the layouts of irregular objects based on GA	Fast convergence More efficient layout plans
Javadi et al. 45	Hybrid electromagnetism GA algorithm	Using electromagnetism-like algorithm to improve solutions obtained by GA	Results show superiority of the algorithm to other similar algorithms
Pourvaziri and Naderi 46	Multi-population GA	Dividing the population into sub-populations and avoiding infeasible space	Saving on computation time. More efficient outcomes compared to conventional methods

According to McKendall and Hakobyan, ⁴⁷ when solving a DFLP with either mathematical models or the combined heuristic-mathematical approaches, material handling costs and rearrangement costs play a critical role in determining how to plan an efficient layout system for a manufacturing system. However, apart from the advantages of applying the proposed GA hybrid algorithms for solving DFLPs (Table 1) for single periods and for certain demands, the main concern here would be the rearrangement costs of different periods of manufacturing and for demand uncertainties. This could therefore call for an integrated heuristic–robust algorithm (i.e. robust genetic algorithm (RGA)) that can provide a single optimum solution for DFLPs and could be applicable especially in manufacturing environments with uncertain demand quantities. Needless to say, there are numerous manufacturing factors that could be applied to the layout problem depending on the manufacturing requirements. Most of these factors are reviewed in Saxena and Jain ⁶ and Liu et al. ³

Robust modeling

The nature of uncertainty is often not clear and there is not much information about the behavior of the noise in this environment. In this article, a robust approach proposed by Bertsimas et al. ⁴⁸ and Bertsimas and Sim ⁴⁹ is applied to develop the proposed RGA and to solve the DFLP with uncertain demand conditions. In many robust optimization techniques, it is essential to assume that the uncertain data have a symmetric unknown distribution. The main consideration in this kind of programming is the effect of deviated data from their nominal values on the final results of the model. Ben-Tal and Nemirovski ⁵⁰ proved that a perturbation on some benchmark linear programming problems could lead to infeasible solutions. They also introduced a technique which could immune the output results from the infeasibility. Ben-Tal and Nemirovski ⁵⁰ used a counterpart, which is mapped inside the feasible region. They also developed another robust approach where the structure of the robust problem remains similar to the original one.

Considering the above mentioned, this study presents a method for solving DFLP by robust GA (RGA) for five manufacturing periods with no limitations in the number of machines or operational sequences. This method is mostly beneficial when the rearrangement costs are significant. The authors have intentionally referred to the numerical example presented by Pillai et al. ⁵¹ and Chan et al. ⁵² in order to highlight the superiority of the proposed approach to conventional GA and other heuristics.

The rest of this article is organized as follows. In the next section, the QAP model is introduced with some minor alternations in its original format. Next, the aforementioned robust technique developed by Bertsimas et al. ⁴⁸ and Bertsimas and Sim ⁴⁹ is presented. The QAP model is accordingly transformed to comply with the format of the proposed robust formulation. Subsequently, the RGA is introduced to the numerical example proposed and commonly shared in Pillai et al. ⁵¹ and Chan et al. ⁵² Finally, the numerical results are compared and the advantages of the RGA are outlined, the conclusions are made and some implications for further studies are proposed, respectively.

Problem statement

The notations used in the model are as follows:

$\mathrm{x}\in {\mathrm{R}}^{\mathrm{n}\times 1}$	Vector of unknown variables
a	Vector of uncertain data
${\Gamma }_i$	Degree of uncertainty within ith constraint parameters
${\overline{a}}_{ij}$	Nominal value of ${\mathrm{a}}_{\mathrm{ij}}$
${\widehat{a}}_{ij}$	Precision of estimation of ${\mathrm{a}}_{\mathrm{ij}}$
${\mathrm{q}}_{\mathrm{i}}$	Some auxiliary variable related to the robust counterpart denoting the cost of robustness in each constraints
${\mathrm{r}}_{\mathrm{ij}}$	Some auxiliary variable related to the robust counterpart counting the number of uncertain parameters in each constraints
y	Decision variable for making the absolute term $(|{\mathrm{x}}_{\mathrm{j}}|)$ to linear one
$\mathrm{\psi }$	Total traveling cost for average demand scenario
${\mathrm{d}}_{\mathrm{rs}}$	Rectilinear distance between location r and location s
${\mathrm{x}}_{\mathrm{jr}}$	A binary variable, which is 1 when machine j is assigned to location r, otherwise it is 0
${\mathrm{x}}_{\mathrm{ks}}$	A binary variable, which is 1 when machine k is assigned to location s, otherwise it is 0
${\mathrm{\chi }}_{\mathrm{jrks}}$	A binary variable, which is 1 when machines j and k are both assigned to locations r and s, otherwise it is 0
${\mathrm{\beta }}_{\mathrm{ijk}}$	Number of part i per transportation when transported from machine j to machine k
p	Number of periods in planning horizon
${\mathrm{D}}_{\mathrm{pi}}$	Demand of part i in period p
${\overline{\mathrm{D}}}_{\mathrm{i}}$	Average demand of part i in the given periods, it is used as a nominal value of demand in robust QAP
${\tilde{\mathrm{D}}}_{\mathrm{pi}}$	Uncertainty of demand of part i in period p
${\mathrm{\gamma }}_{\mathrm{ijk}}$	Part handling factor of part i when transported between machines j and k

The QAP model

There are several presumptions for the QAP model that should be considered before developing the formulation:

1. Equal area departments are considered which include enough space for each machine so that no overlap would occur.

2. The rearrangement costs are included after obtaining the optimum layout in order to compare the computational results with alternative methods. ⁵²

3. Part demands in time periods have unknown symmetric distribution.

4. Cells or machines are equal in size.

The objective function for modeling the QAP is as follows

$$min\psi =\sum _{\mathrm{j}=1}^{\mathrm{m}}\sum _{\mathrm{k}=1}^{\mathrm{m}}\sum _{\mathrm{r}=1}^{\mathrm{m}}\sum _{\mathrm{s}=1}^{\mathrm{m}}\sum _{\mathrm{i}=1}^{\mathrm{n}}\frac{{\tilde{\mathrm{D}}}_{\mathrm{pi}}*{\gamma }_{\mathrm{ijk}}}{{\beta }_{\mathrm{ijk}}}*{\mathrm{d}}_{\mathrm{rs}}*{\mathrm{x}}_{\mathrm{jr}}*{\mathrm{x}}_{\mathrm{ks}}$$

(1)

subject to

$$\sum _{\mathrm{r}=1}^{\mathrm{m}}{\mathrm{x}}_{\mathrm{jr}}=1,\forall \mathrm{j}$$

(2)

$$\sum _{\mathrm{j}=1}^{\mathrm{m}}{\mathrm{x}}_{\mathrm{jr}}=1,\forall \mathrm{r}$$

(3)

$${\mathrm{x}}_{\mathrm{jr}},{\mathrm{x}}_{\mathrm{ks}}\in \{0,1\}.\forall \mathrm{j},\mathrm{r}$$

(4)

In quadratic assignment, the objective function contains the product pairs of location decision variables, hence the quadratic form. Also, the constraints are similar to classical assignment problem. Constraints (2) and (3) ensure that each facility is assigned to exactly one location and each location is assigned to one facility.

Since QAP is a nonlinear problem and a global optimum solution is rarely available, an auxiliary variable is required, which encompasses both ${\mathrm{x}}_{\mathrm{jr}}$ and ${\mathrm{x}}_{\mathrm{ks}}$ and makes the formulation a linear one. Here, the objective function (1) is nonlinear. As a result, two more constraints presented by Tavakkoli-Moghaddain and Shayan ²² and Tavakkoli-Moghaddam et al. ³⁷ are included in the formulas to ensure the linearity of the model. The formulation could be further expressed as follows

$$min\psi =\sum _{\mathrm{j}=1}^{\mathrm{m}}\sum _{\mathrm{k}=1}^{\mathrm{m}}\sum _{\mathrm{r}=1}^{\mathrm{m}}\sum _{\mathrm{s}=1}^{\mathrm{m}}\sum _{\mathrm{i}=1}^{\mathrm{n}}\frac{{\tilde{\mathrm{D}}}_{\mathrm{pi}}*{\gamma }_{\mathrm{ijk}}}{{\beta }_{\mathrm{ijk}}}*{\mathrm{d}}_{\mathrm{rs}}*{\chi }_{\mathrm{jrks}}$$

(5)

subject to

$$\sum _{\mathrm{r}=1}^{\mathrm{m}}{\mathrm{x}}_{\mathrm{jr}}=1,\forall \mathrm{j}$$

(6)

$$\sum _{\mathrm{j}=1}^{\mathrm{m}}{\mathrm{x}}_{\mathrm{jr}}=1,\forall \mathrm{r}$$

(7)

$$1.5{\chi }_{\mathrm{jrks}}⩽{\mathrm{x}}_{\mathrm{jr}}+{\mathrm{x}}_{\mathrm{ks}},\forall \mathrm{jrks}$$

(8)

$${\chi }_{\mathrm{jrks}}+1.5>{\mathrm{x}}_{\mathrm{jr}}+{\mathrm{x}}_{\mathrm{ks}},\forall \mathrm{jrks}$$

(9)

$${\mathrm{x}}_{\mathrm{jr}},{\mathrm{x}}_{\mathrm{ks}},{\mathrm{x}}_{\mathrm{jrks}}\in \{0,1\}.\forall \mathrm{j},\mathrm{r},\mathrm{k},\mathrm{s}$$

(10)

where ${\tilde{\mathrm{D}}}_{\mathrm{pi}}$ denotes the uncertain demand in different manufacturing periods that is going to be solved by the robust modeling proposed by Bertsimas et al. ⁴⁸ and Bertsimas and Sim. ⁴⁹

Robust optimization model

The aim of the robust optimization under uncertainty is to develop immune models. Prior to robust optimizations, stochastic programming and sensitivity analysis were considered to be appropriate tools to deal with uncertainty; however, robust modeling could be a more efficient alternative to replace these methods.^53,54 For a better understanding of a robust method developed by Bertsimas et al. ⁴⁸ and Bertsimas and Sim, ⁴⁹ consider linear program (11) as follows

$$max\mathrm{cx}$$

(11)

subject to

$$\sum _{\mathrm{j}=1}^{\mathrm{n}}{\tilde{\mathrm{a}}}_{\mathrm{ij}}{\mathrm{x}}_{\mathrm{j}}⩽{\mathrm{b}}_{\mathrm{i}},\forall \mathrm{i}$$

(12)

$${\mathrm{x}}_{\mathrm{j}}⩾0$$

where $\mathrm{a}\in {\mathrm{R}}^{\mathrm{m}\times \mathrm{n}}$ and $\mathrm{b}\in {\mathrm{R}}^{\mathrm{m}\times 1}$ and $\mathrm{c}\in {\mathrm{R}}^{\mathrm{n}\times 1}$ and ∼ shows levels of uncertainty associate with ${\tilde{\mathrm{a}}}_{\mathrm{ij}}$ . The uncertainty of ${\tilde{\mathrm{a}}}_{\mathrm{ij}}$ indicates that a particular row of i and a set of j coefficients in that row are uncertain. ${\tilde{\mathrm{a}}}_{\mathrm{ij}}$ is therefore modeled as a symmetric variable in $[{\overline{a}}_{ij}-{\widehat{a}}_{ij},{\overline{a}}_{ij}+{\widehat{a}}_{ij}]$ . The robust optimization approach converts this linear model into:

$$max\mathrm{cx}$$

(13)

subject to

$$\sum _{\mathrm{j}=1}^{\mathrm{n}}{\overline{\mathrm{a}}}_{\mathrm{ij}}{\mathrm{x}}_{\mathrm{j}}+{\mathrm{q}}_{\mathrm{i}}{\Gamma }_{\mathrm{i}}+\sum _{\mathrm{j}\in {\mathrm{J}}_{\mathrm{i}}}{\mathrm{r}}_{\mathrm{ij}}⩽{\mathrm{b}}_{\mathrm{i}},\forall \mathrm{i}$$

(14)

$${\mathrm{q}}_{\mathrm{i}}+{\mathrm{r}}_{\mathrm{ij}}⩾{\hat{\mathrm{a}}}_{\mathrm{ij}}{\mathrm{y}}_{\mathrm{j}},\forall \mathrm{i},\mathrm{j}\in {\mathrm{J}}_{\mathrm{i}}$$

(15)

$$-{\mathrm{y}}_{\mathrm{j}}⩽{\mathrm{x}}_{\mathrm{j}}⩽{\mathrm{y}}_{\mathrm{j}},\forall \mathrm{j}$$

(16)

$$\mathrm{x},\mathrm{y},\mathrm{r},\mathrm{q}⩾0.$$

In equations (13–16), ${\Gamma }_{\mathrm{i}}$ decreases when the extent of uncertainty decreases and vice versa.

The robust model

Based on equations (13–16), the proposed robust approach to solve the QAP (5–10) is formulated as follows

$$max-\psi$$

(17)

subject to

$$\begin{array}{l}\mathrm{\psi }-{\displaystyle \sum }_{\mathrm{j}=1}^{\mathrm{m}}{\displaystyle \sum }_{\mathrm{k}=1}^{\mathrm{m}}{\displaystyle \sum }_{\mathrm{r}=1}^{\mathrm{m}}{\displaystyle \sum }_{\mathrm{s}=1}^{\mathrm{m}}{\displaystyle \sum }_{\mathrm{i}=1}^{\mathrm{n}}\frac{{\overline{\mathrm{D}}}_{\mathrm{i}}{*\mathrm{\gamma }}_{\mathrm{ijk}}}{{\mathrm{\beta }}_{\mathrm{ijk}}}*{\mathrm{d}}_{\mathrm{rs}}*{\mathrm{\chi }}_{\mathrm{jrks}}\\ +{\mathrm{q}}_{\mathrm{i}}*{\mathrm{Г}}_{\mathrm{i}}+{\displaystyle \sum }_{\mathrm{j}=1}^{\mathrm{m}}{\displaystyle \sum }_{\mathrm{k}=1}^{\mathrm{m}}{\displaystyle \sum }_{\mathrm{r}=1}^{\mathrm{m}}{\displaystyle \sum }_{\mathrm{s}=1}^{\mathrm{m}}{\mathrm{r}}_{\mathrm{jrks}}⩽0\end{array}$$

(18)

$$\begin{array}{l}{\mathrm{q}}_{\mathrm{i}}+{\mathrm{r}}_{\mathrm{jrks}}⩾\\ \left({\displaystyle \sum }_{\mathrm{j}=1}^{\mathrm{m}}{\displaystyle \sum }_{\mathrm{k}=1}^{\mathrm{m}}{\displaystyle \sum }_{\mathrm{r}=1}^{\mathrm{m}}{\displaystyle \sum }_{\mathrm{s}=1}^{\mathrm{m}}{\displaystyle \sum }_{\mathrm{i}=1}^{\mathrm{n}}\frac{{\overline{\mathrm{D}}}_{\mathrm{i}}{*\mathrm{\gamma }}_{\mathrm{ijk}}}{{\mathrm{\beta }}_{\mathrm{ijk}}}{*\mathrm{d}}_{\mathrm{rs}}\right)*{\mathrm{y}}_{\mathrm{jrks}},\forall \mathrm{j},\mathrm{r},\mathrm{k},\mathrm{s}\end{array}$$

(19)

$$-{\mathrm{y}}_{\mathrm{jrks}}⩽{\chi }_{\mathrm{jrks}}⩽{\mathrm{y}}_{\mathrm{jrks}},\forall \mathrm{j},\mathrm{r},\mathrm{k},\mathrm{s}$$

(20)

$$\sum _{\mathrm{r}=1}^{\mathrm{m}}{\mathrm{x}}_{\mathrm{jr}}=1,\forall \mathrm{j}$$

(21)

$$\sum _{\mathrm{j}=1}^{\mathrm{m}}{\mathrm{x}}_{\mathrm{jr}}=1,\forall \mathrm{r}$$

(22)

$$1.5{\chi }_{\mathrm{jrks}}⩽{\mathrm{x}}_{\mathrm{jr}}+{\mathrm{x}}_{\mathrm{ks}},\forall \mathrm{jrks}$$

(23)

$${\chi }_{\mathrm{jrks}}+1.5>{\mathrm{x}}_{\mathrm{jr}}+{\mathrm{x}}_{\mathrm{ks}},\forall \mathrm{jrks}$$

(24)

$${\mathrm{y}}_{\mathrm{jrks}}⩾0,\forall \mathrm{j},\mathrm{r},\mathrm{k},\mathrm{s}$$

(25)

$${\mathrm{r}}_{\mathrm{jrks}}⩾0,\forall \mathrm{j},\mathrm{r},\mathrm{k},\mathrm{s}$$

(26)

$$\mathrm{q}⩾0$$

(27)

$${\mathrm{x}}_{\mathrm{jr}},{\mathrm{x}}_{\mathrm{ks}},{\mathrm{x}}_{\mathrm{jrks}}\in \{0,1\}.\forall \mathrm{j},\mathrm{r},\mathrm{k},\mathrm{s}$$

(28)

where ${\overline{\mathrm{D}}}_{\mathrm{i}}$ is the nominal value of the demand of part i, which is equal to the average demand of part i in all the manufacturing periods. q and ${\mathrm{r}}_{\mathrm{jkrs}}$ are non-negative variables associated with uncertain parameters (here ${\tilde{\mathrm{D}}}_{\mathrm{pi}}$ ).

Permutation-based GA for solving robust DFLPs

As it is mentioned in the previous sections, during the past few years, there have been significant attempts to use meta-heuristics to provide a solution for NP-hard problems. GA is believed to be one of the promising methods for this purpose. ⁵⁵ In this article, we have considered a permutation of nine locations to develop chromosomes in GA as it is a natural representation of solutions in many optimization problems that involve sequencing or ordering. A permutation is a vector $\sigma =({\sigma }_1,{\sigma }_2,\dots ,{\sigma }_{\mathrm{n}})$ of indexes {1, 2, …, n} such that ${\sigma }_{\mathrm{i}}\ne {\sigma }_{\mathrm{j}}$ for all $\mathrm{i}\ne \mathrm{j}$ (i.e. index j is in position i in $\sigma$ when ${\sigma }_{\mathrm{i}}=1$ ). ⁵⁶ A possible solution to a problem with nine machines and nine locations is presented in Figure 2.

Figure 2.

Representation scheme of the chromosome structure.

The permutation-based GA is as follows:

Initialize: Set population size (nPop), Maximum iteration (MaxIt), Crossover percentage (pc), mutation percentage (pm), Tournament size (TournamentSize), Roulette Wheel Selection Pressure (beta).

Calculate number of offspring in crossover (nc) and number of mutants (nm). Create a random starting population (size=nPop). Initialize position of each population member and evaluate bu cost function. Sort population and save best solution ever found. Choose Roulette Wheel Selection (RWS) or Tournament Selection randomly (TS).

for it=1:MaxIt

Create crossover population with size nc (popc)

For k=1:nc/2

Choose parents by RWS or TS

Apply permutation crossover

Evaluate offspring

End

Save popc

Create mutation population with size nm (popm)

For k=1:nm

Select parent randomly

Apply (Swap, Reversion or Insertion) permutation mutation randomly

Evaluate mutant

End

Save popm

Merge pop, popc and popm

Sort new population considering costs

Truncate extra members

Update best solution ever

End.

Crossover

For applying the partially mapped crossover, two parents are selected by Roulette Wheel Selection (RWS) or Tournament Selection (TS). In this method, two crossover points are selected randomly on each chromosome. Then, the substrings are exchanged, mapped, and legalized as shown in Figure 3.

Figure 3.

Partially mapped crossover method.

Mutation

We have used three of the most common mutation operators for permutation-based GAs as follows:

• Swap. Swap mutation exchanges the positions of two randomly selected genes from the permutation.

• Insertion. Insertion mutation removes a randomly selected gene from a chromosome and inserts it into a randomly different position of the same chromosome.

• Reversion. Reversion mutation selects two random genes on a chromosome and reverses the sub-permutation.

Computational results

This section describes the performance of RGA when applied to a numerical example commonly shared by Chan et al. ⁵² and Pillai et al. ⁵¹ These numerical data present a 3 × 3 grid to locate machines. There are five parts in five periods to manufacture. The operational sequences of parts consist of nine machines with certain values for their part handling factors (Table 2). The volatile demands of each part in each period of manufacturing are presented in Table 3 for five periods of manufacturing. The data in Tables 2 and 3 are used as inputs to the proposed RGA algorithm.

Table 2.

Input parameters including machine operational sequence and part handling factor ( ${\mathrm{\gamma }}_{\mathrm{ijk}}$ ).

Part	Machine operational sequence	Part handling factor ( ${\mathrm{\gamma }}_{\mathrm{ijk}}$ )
1	01-03-05-07-02-07-09	6-5-4-3-2-1
2	01-04-02-05-06-08-09	1-2-3-4-5-6
3	01-05-07-08-05-06-02-09	6-5-4-4-3-2-1
4	01-02-04-06-07-08-02-03-09	1-1-2-2-2-3-3-4
5	01-07-06-04-02-08-03-05-06	1-2-3-4-5-5-5-5-6

Table 3.

Demand profiles in five periods in Chan et al. ⁵²

Part	Period					Mean	Maximum perturbation (%)
	1	2	3	4	5
1	10	35	90	40	55	46	95
2	30	50	25	65	20	38	71
3	45	15	40	70	15	37	89
4	70	80	55	90	85	76	28
5	85	60	70	20	30	53	43

Chan et al. ⁵² have included some rearrangement costs (Table 4) that encompass both costs for machine relocation and costs per unit of machine movement. Machine relocation costs encompass setup cost and costs of facility transportation and labor force. Also, for robust model, expected demand of the parts has been used according to Table 5. A better performing layout is the one which minimizes all the above-mentioned costs over the planning horizon.

Table 4.

Machine rearrangement costs in Chan et al. ⁵²

Machine	01	02	03	04	05	06	07	08	09
Basic cost for machine relocation
($)	150	100	200	320	180	90	240	130	90
Cost per unit machine movement
($)	15	10	20	32	18	9	24	13	9

Table 5.

Expected demand of the parts.

Part	1	2	3	4	5
Average demand	46	38	37	76	53

After developing the permutation-based GA for QAP and inserting the required inputs (i.e. Tables 2–5), the layouts for each manufacturing period considering ${\gamma }_{\mathrm{ijk}}=1$ are illustrated in Table 6. Table 6 also encompasses the layouts proposed by Chan et al. ⁵² Overall, the cost of applying the proposed GA model for each period is less compared to the cost of heuristic model proposed by Chan et al. ⁵²

Table 6.

Optimum permutations obtained for five periods by QAP and Chan et al. ⁵² models where ${\mathrm{\beta }}_{\mathrm{ijk}}=1$ .

Models	Period	Objective value ( $\mathrm{\psi }$ )	Permutation of the machines
QAP	1	2675	3 9 7 2 5 4 6 1 8
	2	2470	1 7 9 8 5 6 4 3 2
	3	2875	7 9 3 8 5 6 4 1 2
	4	2835	9 6 5 7 1 2 3 8 4
	5	2080	2 7 9 5 6 8 1 3 4
Chan et al. 52	1	2850	2 4 1 8 6 7 3 5 9
	2	2790	2 4 1 8 6 7 3 5 9
	3	3160	1 8 3 2 7 5 4 9 6
	4	3165	1 2 4 9 8 6 3 7 5
	5	2275	1 2 4 9 8 6 3 5 7

In addition, Table 7 compares the total traveling costs obtained from RGA and robust simulated annealing model proposed by Pillai et al. ⁵¹ with both varying and constant part handling factors. The results in Table 7 indicate that in terms of total traveling costs, the proposed RGA model outperforms the model developed by Pillai et al. ⁵¹ by 10%. It is also worth mentioning that both models excluded relocation costs using a robust modeling approach.

Table 7.

RGA and Pillai et al. ⁵¹ layouts and their total traveling costs for expected demand profile when ${\mathrm{\gamma }}_{\mathrm{ijk}}=1\mathrm{and\; varying}$ , ${\mathrm{\beta }}_{\mathrm{ijk}}=1$ , and $\mathrm{\Gamma }=5$ .

Models	${\mathrm{\gamma }}_{\mathrm{ijk}}$	Total traveling cost	Permutation of the machines
RGA	1	2497.5	4 3 7 5 2 1 8 6 9
	Varying	7690.5	7 9 3 4 5 8 1 2 6
Pillai et al. 51	1	2740	1 5 3 2 7 8 4 6 9
	Varying	8752	3 8 9 5 7 6 1 2 4

RGA: robust genetic algorithm.

Table 7 also suggests that the proposed robust layout in this article can perform well in a dynamic environment with volatile demand. Subsequently, layouts in Table 7 have been applied to the demand profile of different manufacturing periods for robust and non-robust models, and the results are depicted in Figure 4. Figure 4 illustrates the comparisons made between the results of different models used in this article. It can be observed that the proposed permutation-based RGA model yields optimal solution values for traveling costs among the four models, mentioned above, except for the 4th and 5th periods where QAP outperforms RGA by only 5% and 2%, respectively (Figure 4). Moreover, in their article, Pillai et al. ⁵¹ showed that the results obtained from their model are more efficient than a number of other meta-heuristic approaches with the same set of data. In a similar vein, the superiority of the results obtained from our proposed permutation-based RGA to Pillai et al. ⁵¹ reveals that our model outperforms those other meta-heuristic models as well.

Figure 4.

Comparison of total traveling costs where ${\mathrm{\gamma }}_{\mathrm{ijk}}=1$ , ${\mathrm{\beta }}_{\mathrm{ijk}}=1$ , and $\mathrm{\Gamma }=5$ .

The material handling costs of each period of the planning horizon are illustrated in Table 8. Again, the RGA model presents better solutions compared to the other aforementioned studies. Additionally, the material handling costs are at their lowest in every period for this size of problem (9-size).

Table 8.

Material handling costs of manufacturing periods for various layouts when ${\mathrm{\gamma }}_{\mathrm{ijk}}=1$ , ${\mathrm{\beta }}_{\mathrm{ijk}}=1$ , and $\mathrm{\Gamma }=5$ .

Period	1	2	3	4	5	Planning horizon
Pillai et al. 51	27,800	26,400	29,500	31,300	22,000	137,000
Chan et al. 52	28,500	27,900	31,600	31,650	22,750	142,400
RGA	25,000	24,125	28,125	29,800	21,200	128,250

Finally, Figure 5 provides the changes in total traveling costs for RGA model against varying amounts of gamma. This figure shows that for $\Gamma <6$ , the RGA model performs better than the model proposed by Pillai et al. ⁵¹ As the gamma increases more than 6, the gap between the two lines begins to grow. This is due to the fact that the higher amounts of gamma lead to higher degrees of uncertainty, hence increasing total costs. The latter suggests that based on the degree of uncertainty that the user prefers to apply, the costs can be decreased using the RGA model.

Figure 5.

RGA and Pillai et al. ⁵¹ total traveling costs for expected demand profile when ${\mathrm{\gamma }}_{\mathrm{ijk}}$ and Γ are varying and ${\mathrm{\beta }}_{\mathrm{ijk}}=1$ .

Conclusion and discussion

This article develops a method for the integration of GA and robust optimization techniques for solving DFLPs and generating a single layout considering demand uncertainties in successive periods of manufacturing. The advantages of this approach are first, the ability of permutation-based RGA to solve DFLP in larger scales than just a grid with a limited number of machinery and manufacturing criteria included in the main formulation; second, the generation of global optimum solution by choosing the right number of population and regeneration; third, obtaining a unique layout for all the manufacturing periods considering uncertain demand conditions, and finally the elimination of rearrangement costs due to this uniqueness of the layout. The outcomes have also proven to be more efficient than similar studies that have used both heuristic and meta-heuristic approaches with the same set of data. The results, however, indicate that the proposed RGA model is most efficient up to a certain amount of uncertainty in the model’s parameters. Further investigations could be carried out to improve this aspect of the permutation-based RGA model. The proposed permutation-based RGA could encompass various other manufacturing variables to comply more with manufacturing environments. Future studies could also alter the proposed model to be used as an inter-cellular layout solution.