A graph-pair representation and linear programming embedded genetic algorithm for unequal-sized layout of cellular manufacturing systems

Abstract

Purpose

This paper aims to deal with intra and inter-cell layout problems in cellular manufacturing systems. The model is organized to minimize the total handling cost, i.e. intra and inter-cell handling costs in a continuous environment.

Design/methodology/approach

The research was conducted by developing a mixed integer mathematical model. Due to the complexity and NP-hard nature of the cellular manufacturing layout problem, which mostly originated from binary variables, a “graph-pair” representation is used for every machine set and cells each of which manipulates the relative locations of the machines and cells both in left-right and below-up direction. This approach results in a linear model as the binary variables are eliminated and the relative locations of the machines and cells are determined. Moreover, a genetic algorithm as an efficient meta-heuristic algorithm is embedded in the resulting linear programming model after graph-pair construction.

Findings

Various numerical examples in both small and large sizes are implemented to verify the efficiency of the linear programming embedded genetic algorithm.

Originality/value

Considering the machine and cell layout problem simultaneously within the shop floor under a static environment enabled managers to use this concept to develop the models with high efficiency.

Full text

Translate

Turn on search term navigation

Nomenclature Indices

= Index for operations of part p (j = 1,…,O_p);

= Index for parts (p = 1,…,P);

m, n

= Indices for machines (m,n = 1,…, M); and

c, k

= Indices for manufacturing cells (c, k = 1,…,C).

Input data

= Number of parts;

O_p

= Number of operations of part P;

= Number of machines;

= Number of manufacturing cells;

B_p

= Bach size of the part P;

γ₀

= Per batch, the movement cost for each unit of distance;

L_max

= Length of the shop floor;

W_max

= Width of the shop floor;

L_m

= Length of machine type m;

W_m

= Width of machine type m;

Hd_mn

= Horizontal allowable distance between machine types m and n;

Hd_ck

= Horizontal allowable distance between cells c and k;

Vd_mn

= Vertical allowable distance between machine types m and n;

Vd_ck

= Vertical allowable distance between cells c and k; and

= Allowable distance between machines and cell boundary.

Data resulted from the cell formation stage

D_p

= Demand for part type P;

α_jpm

= 1; If the operation j of part p is assigned to the machine m, 0; Otherwise; and

β_mc

= 1; If the machine m is assigned to a cell c, 0; Otherwise.

Variables Continuous

(x_m, y_m)

= Centroid coordinates of machine type m;

(xlc_c, ylc_c)

= Lower left-hand corner coordinates of cell c;

(xuc_c, yuc_c)

= Upper right-hand corner coordinates of cell c; and

d_mn

= Rectilinear distance between the centroid of machines m and n.

Binary

$a_{m n}^{x}$ , $a_{m n}^{y}$

= 1; If the machine m is located to the left/below of machine n, 0; Otherwise (right/up); and

b_{c k}^{x}

b_{c k}^{y}

= 1; If the cell c is located to the left/below of cell k, 0; Otherwise (right/up).

1. Introduction

Cellular manufacturing (CM) is an application of group technology (GT) that involves the formation of part families, based on their similarities in processing requirements, and the grouping of the machines to allocate into manufacturing cells to produce the parts (Wemmerlöv and Vakharia, 1991). Manufacturing systems (CMSs) design consists of three major steps as follows:

Cell formation (CF) (i.e. grouping parts into part families and machines into machine cells);
Intra-cell layout (i.e. arranging the layout of machines within each cell); and
Inter-cell layout (i.e. arranging the layout of cells within shop floor) (Singh, 1993).

Ideally, to reach the best results, these decisions should be addressed simultaneously. However, due to the complexity and NP-complete nature of the problem, most researchers have only covered one step in their study (Jolai et al., 2011). Since the layout problem has not received as much attention as the cell formation problem, this paper studies the layout aspects of CMSs to determine intra and inter-cell layout concurrently.

Facilities layout problems (FLPs) can be divided into equal-sized FLPs (EFLPs) and unequal-sized FLPs (UFLPs) based on the size of the facilities (Kim and Kim, 1995). In our proposed model, the UFLP has a higher possibility of implementation than the EFLP since different kinds of machines with different sizes are used in CMS. A mixed integer programming (MIP) is used to model the UAFLP, abbreviated as M-FLP, where binary variables are defined to determine the relative location (RL) of each machine within cells and each cell in the shop floor to prevent the probable overlapping between the machines of each cell and the cells over the entire floor (i.e. machines within cell and cells in the shop floor must be separated at least in left-right direction or down-up direction). The objective of the model proposed in this paper is to minimize the intra and inter-cell material handling costs, which are expressed as the multiplication of the flow between machine pairs and the rectilinear distance between the machine centroids as well as the multiplication of the flow between each pair of cells and the rectilinear distance between the cell centroids, respectively, and also maximize the adjacency between machine sets in a cell as a secondary objective. Due to the NP-complete nature of the model, attaining an optimal solution is difficult for real-size problems. Hence, a linear programming embedded genetic algorithm (LPEGA) heuristic is developed to tackle the problem and explore the solution. The proposed GA sub-algorithm is a procedure based on “graph-pair representation,” which is used effectively to specify the RL of the machines and cells by eliminating the binary variables of the MIP model and resulting in a linear programming (LP) subproblem. Then, the acquired LP subproblem is solved optimally to obtain the objective function value as well as continuous variables of the proposed MIP model according to the RLs of the facilities specified by “graph-pair representation” and GA procedure. The proposed LPEGA is implemented by creating a linkage between MATLAB software in which the proposed GA sub-algorithm is codded and GAMS software for obtaining the solution of the LP subproblem in different iterations of the algorithm to obtain the near-optimum solution. The proposed LPEGA will more likely fulfill the near optimum solution than pure GA since part of the algorithm is solved optimally, which reduces the possibility of capturing in local optima.

The remainder of this study is organized as follows: In Section 2, the literature on the concept of CMS and layout problems is reviewed. Assumptions and formulation of the model are detailed in Section 3. The graph pair representation approach is presented in Section 4. The proposed LPEGA is clarified in Section 5. In Section 6, numerical example is given to clarify the model. Finally, Section 7 concludes the paper.

2. Literature review

There is a considerable amount of literature devoted to layout design in CMS, specifically. Jolai et al. (2011) presented a new mathematical model for both intra and inter-cell layout problems in CMSs. A binary particle swarm algorithm (BPSO) was developed to solve the model because of the NP-hardness of the problem. Javadi et al. (2014) developed a mathematical model devoted to intra and inter-cell layout problems under dynamic situations. An electromagnetism-like (EM-like) algorithm, a GA, and a hybrid algorithm based on the EM-like algorithm and GA were separately adopted to minimize the total costs of rearrangement, and intra and inter-cell material flows. Rabbani et al. (2017) presented a comprehensive quadratic assignment problem for the assignment of machines of each part manufacturing cell, subassembly tasks of each subassembly cell as well as the assignment of different cells and final assembly tasks within the shop floor in their relevant predetermined locations. Forghani and Ghomi (2020) addressed cell formation, cell scheduling and group layout (GL) problems in designing and configuring a cellular manufacturing system (CMS). Depending on the type of cell, which is either classical or virtual, an encoding scheme is proposed to effectively represent candidate solutions, which demonstrates that the flexibility achieved by the virtual cell configuration allows for better solutions than the classical cell configuration. Motahari et al. (2023) designed a CMS that involves three major decisions: CF, GL and group scheduling (GS) simultaneously. Accordingly, a multi-objective linear programming (MOLP) model is proposed to optimize weighted completion time, transportation cost and machine idle time for a multiproduct system. The proposed model was solved with a nondominated sorting genetic algorithm II (NSGA-II).

There is also research performed on solving concurrent decisions of CMSs. In this regard, Al‐Zuheri et al. (2022) presented an innovative heuristic approach to rearrange machines, enabling the minimization of inter/intracellular movements and the cost of material handling between machines, increasing group efficiency and efficacy. The heuristic approach, which is based on GT, genetic algorithms and desirability function, determines the optimal solution for flexible cell formation and machine layout within each cell. Chang et al. (2013) formulated a two-stage mathematical programming model to tackle CF, cell layout and intra-cellular machine sequence simultaneously. Then they developed an efficient TS algorithm to solve the proposed combinatorial problem. Mansour et al. (2022) presented a novel heuristic-based two-stage approach to tackle CMS-related problems. In the first stage, a mathematical model is developed to concurrently solve cell formation and workers’ assignment problems. The model’s objective is to minimize the weighted sum of the total inter- and intra-cell movements, operation and defect costs. In the second stage, a heuristic algorithm is developed to solve the problem related to the layout design of the cellular manufacturing system. Wu et al. (2023) stated that the main challenge with CMS is not only the generation of cells but also the optimal arrangement of machines in each cell. The proposed paper objectives are therefore twofold: cell formation and optimal placement of machines within cells. A genetic algorithm (GA) and encoding system are used in the cell to shape the cells and position the machines.

Unequal-sized facility layout problem (UFLP) has been considered in many types of research. Castillo et al. (2005) presented a new modeling framework for UFLP to effectively find global optimal solutions for block layout design problems. They also compared different mixed-integer linear and mixed-integer nonlinear optimization methods. Hunagund et al. (2018) propose the SA heuristic to solve the unequal area dynamic facility layout problem (FBS) with flexible bay structure (UA-DFLPs with FBS to determine the facilities’ dimensions and their location coordinates with flexible bay formation in the layout for various periods of the planning horizon. Salimpour et al. (2021) presented the problems of cell formation (CF) and cellular layout (CL) encountered in the design of a CMS, and they used a semi-robust approach to find the optimum number of cells, CF and CL, with both inter and intra-cellular layout of unequal-area facilities. Graph theoretic heuristic has been widely used in FLP, in which cell layout and UFLP are incorporated as well. An early graph theoretic procedure was given by Kim and Kim (1995) to minimize total transportation distance. In the first step, an initial layout was obtained by constructing a planar adjacency graph. In the second step, the constructed layout was improved by changing the adjacency graph. Bozer and Wang (2012) proposed a heuristic procedure to tackle UFLP using graph-pair representation together with the SA algorithm to construct and improve facility locations, respectively.

Motivation and research gaps

In the following, by reviewing the summary of literature proposed in Table 1, only three works have considered simultaneously cell formation, inter and intra-cell layout problems in continuous layout type to the real- world. However, these three papers ignore a strong need for heuristic procedures that can identify good solutions to real-world unequal inter and intra-cell layout problems. Obtaining an optimal solution to the mixed integer unequal, inter and intra-cell layout formulation is difficult, and in these research works, only problems with a limited number of machines and cells can be solved to optimality. Motivated to fill the mentioned gaps, we developed a heuristic procedure that uses a “graph pair” representation to determine and manipulate the relative location of the machines in cells and the location of the cells on the shop floor layout. A proposed heuristic procedure uses graph-pair representation together with the linear programming embedded GA heuristic to construct and improve inter and intra-cell layout. The effectiveness of the proposed graph-pair heuristic research method is very encouraging based on the results of the small and large-sized problems.

3. Problem description

This research attempts to develop a mathematical programming model to address the machine and cell layout problem simultaneously within the shop floor under a static environment.

The objective function aims at minimizing the intra and inter-cell material handling cost concerning the overlapping restriction of the machines in each cell as well as cells within the shop floor. The proposed model is constructed based on a rectangular facility layout approach, similar to Javadi et al. (2013), which is adopted to obtain the optimal location of machines in each cell as well as the arrangement of cells within the shop floor.

Generally, the following assumptions are made for the proposed model formulation:

The cell formation stage is performed in advance, and parts and machine groups have been allocated to cells;
The intra- and intercell material handling costs increase linearly based on the rectilinear distance between the centroid of each pair of machines;
The processing route of each part includes several operations with a specified operation sequence;
Machines have unequal-sized areas either square or rectangular;
The location of machines in each cell and cells within the shop floor is illustrated by their coordinates;
The dimensions of the shop floor on which cells are located are given; and
The adjacency factor between the machines of each cell depends on the distance between each pair of machines.

Mathematical model:

(1) $\begin{matrix} Minimize Z = \sum_{p = 1}^{P} \sum_{j = 1}^{O_{p} - 1} \sum_{m = 1}^{M} \sum_{\begin{array}{l} n = 1 \\ n \neq m \end{array}}^{M} \sum_{c = 1}^{C} \sum_{\begin{array}{l} k = 1 \\ k \neq c \end{array}}^{C} α_{j p m} β_{m c} α_{j + 1, p n} β_{n k} γ_{0} . d_{m n} ⌈ \frac{D_{p}}{B_{p}} ⌉ \\ + \sum_{p = 1}^{P} \sum_{j = 1}^{O_{p} - 1} \sum_{m = 1}^{M} \sum_{\begin{array}{l} n = 1 \\ n \neq m \end{array}}^{M} \sum_{c = 1}^{C} α_{j p m} β_{m c} α_{j + 1, p n} β_{n k} γ_{0} . d_{m n} ⌈ \frac{D_{p}}{B_{p}} ⌉ \end{matrix}$ (2) $d_{m n} = | x_{m} - x_{n} | + | y_{m} - y_{n} | \forall {m, n}$ (3) $x_{m} + \frac{L_{m}}{2} + H d_{m n} \leq x_{n} - \frac{L_{n}}{2} + L_{\max} (2 - a_{m n}^{x} - a_{m n}^{y}) \forall m \in {1, \dots, M - 1} \forall n \in {n \neq m}$ (4) $y_{m} + \frac{W_{m}}{2} + V d_{m n} \leq y_{n} - \frac{W_{n}}{2} + L_{\max} (1 - a_{m n}^{x} + a_{m n}^{y}) \forall m \in {1, \dots, M - 1} \forall n \in {n \neq m}$ (5) $a_{m n}^{x} + a_{n m}^{x} = 1 \forall m \in {1, \dots, M - 1} \forall n \in {n > m}$ (6) $a_{m n}^{y} + a_{n m}^{y} = 1 \forall m \in {1, \dots, M - 1} \forall n \in {n > m}$ (7) $x l c_{c} - L_{\max} (1 - β_{m c}) \leq x_{m} - \frac{L_{m}}{2} - D m \forall {m, c}$ (8) $x_{m} + \frac{L_{m}}{2} + D m \leq x u c_{c} + L_{\max} (1 - β_{m c}) \forall {m, c}$ (9) $y l c_{c} - W_{\max} (1 - β_{m c}) \leq y_{m} - \frac{W_{m}}{2} - D m \forall {m, c}$ (10) $y_{m} + \frac{W_{m}}{2} + D m \leq y u c_{c} + W_{\max} (1 - β_{m c}) \forall {m, c}$ (11) $x u c_{c} + H d_{c k} \leq x l c_{k} + L_{\max} (2 - b_{c k}^{x} - b_{c k}^{y}) \forall c \in {1, \dots, C - 1} \forall k \in {k \neq c}$ (12) $y u c_{c} + V d_{c k} \leq y l c_{k} + W_{\max} (1 - b_{c k}^{x} + b_{c k}^{y}) \forall c \in {1, \dots, C - 1} \forall k \in {k \neq c}$ (13) $b_{c k}^{x} + b_{k c}^{x} = 1 \forall c \in {1, \dots, C - 1} \forall k \in {k < c}$ (14) $b_{c k}^{y} + b_{k c}^{y} = 1 \forall c \in {1, \dots, C - 1} \forall k \in {k < c}$ (15) $x_{m}, y_{m}, x l c_{c}, y l c_{c}, x u c_{c}, y u c_{c}, d_{m n} \geq 0 \forall {m, n, c}$ (16) $a_{m n}^{x}, a_{m n}^{y}, b_{c k}^{x}, b_{c k}^{y} \in {0, 1} \forall {m, n, c, k, i}$

Model description

The objective function of the model presented in equation (1) minimizes the total material handling costs (i.e. intra and inter-cell material handling costs). Equation (2) calculates the rectilinear distance between machines. Equations (3)–(6) restrict the overlapping between any pair of machines by separating them at least in one of the x-coordinate or y-coordinate directions. Equations (7)–(10) determine the location of each cell according to the coordinates of the lower left-hand corner and upper right-hand corner. Equations (11)–(14) restrict the overlapping of each pair of cells at least in the horizontal or vertical direction. Finally, equations (15)–(16) represent the restrictions of decision variables. Figure 1 illustrates the relative locations of machines and cells within the layout obtained through the proposed model.

Linearization of the model

The presented model is a nonlinear MIP due to absolute terms of equation (2). To transform these non-linear terms into linear terms, positive variables are introduced and replaced with, respectively, the additional constraints given below: (17) $s_{m n} \geq x_{m} - x_{n} \forall {m, n} \in c; m < n$ (18) $s_{m n} \geq x_{n} - x_{m} \forall {m, n} \in c; m < n$ (19) $t_{m n} \geq y_{m} - y_{n} \forall {m, n} \in c; m < n$ (20) $t_{m n} \geq y_{n} - y_{m} \forall {m, n} \in c; m < n$

4. Graph pair representation

Graph pairs represent the RLs of facilities within the shop floor by eliminating the binary variables of the proposed MIP model. The values of all binary variables are set according to their corresponding graph, and the proposed MIP model is transformed into an LP model without NP-complexity, which is solvable for real-sized problems in reasonable computational time. In this regard, four binary variables namely, and $a_{n m}^{y}$ , as denoted in Section 3, are used to separate the machines of each cell. Similarly, variables are used to prevent the overlapping of cell boundaries.

The proposed representation is defined on two graphs, each of which determines the RLs of machines and cells either in “left-right direction”, (i.e. x-coordinate) or “below-up direction”, (i.e. y-coordinate). In a given cell c two graphs, say, $G_{_{L R}}^{M c} (M_{c}, A_{c}^{x})$ and $G_{B U}^{M c} (M_{c}, A_{c}^{y})$ , where is the vertex set representing the machines in the cell c and is the edge set which is equivalent to the binary variable. When taking value 1, it means that the machine m is located left/below of machine n. (i.e. $G_{_{L R}}^{M c}$ and $G_{_{B U}}^{M c}$ hold the RLs of machines in a cell c in “left-right direction” and “below-up direction,” respectively).

The same representation procedure is used to determine the RLs of cells within the shop floor. Two graphs, say, $G_{B U}^{C} (C, B^{y})$ are defined where the vertex set represents the number of cells and the edge set is equivalent to the binary variable $b_{c k}^{x} / b_{c k}^{y}$ . When takes value 1, it means that the cell c is left/below of cell k (i.e. $G_{L R}^{C}$ and hold the RLs of machines in a cell c in “left-right direction” and “below-up direction,” respectively). Figure 1 illustrates the proposed representation procedure for a given cellular manufacturing layout, as shown in Figure 1(a). The graph pair shown in Figure 2(a) corresponds to cell 2. Also, the graph pair of cells within the shop floor is depicted in Figure 2(b).

Graph pair construction

Given an empty graph pair for the machines set of the same cell, for n = 1,2,…, Mc such that m < n, one of graphs $G_{L R}^{M c}$ or $G_{B U}^{M c}$ is randomly selected with equal probability, and edge or (n, m) is added to the selected graph again with equal probability. The obtained graph pairs will contain one edge for each machine pair.

Suppose that the above-mentioned procedure is used to manipulate a graph pair related to the relative location of each machine set; then the solution might be infeasible if either graph includes any cycles. For example, if edge (n, l) are added to, say, a three-node cycle, it implies that m is located to the left of n, n is located to the left of l and l is located to the left of m, which is impossible.

To avoid any cycles, it is necessary to use Dijkstra’s algorithm (Bondy and Murty, 1976) to search for the shortest path from node n to node for the randomly selected edge setting all the edge weights equal to 1. If such a path is detected we simply add an edge instead of (m, n) to prevent cycle.

In addition to the above procedure, we also need to mention transitivity relationships (Meller et al., 1998), i.e. when the machine m is located to the left (below) of the machine n and the machine n is located to the left (below) of the machine l, then the machine must be essentially located to the left (below) of the machine l. The resultant edge is labeled as the transitivity edge (edge).

The same procedure suggested, to which the RLs of machine sets were specified, is reengaged to determine the RLs of cells within the shop floor on the graph pair $(G_{L R}^{C}, G_{B U}^{C})$ referred to the left-right and below-up directions of cells. To conserve space, we omit the remainder of the graph construction related to the RLs of cells, as already clarified thoroughly.

5. Linear programming embedded genetic algorithm heuristic

Biologically motivated approaches have gained increasing popularity for solving complex optimization problems in the last decades. GA, which was first introduced in the 1970s by Holland (1992),is one of the optimization approaches constructed based on evolutionary processes occurring in the natural systems. GA strives to synthesize the good features of different individuals within a population via operators such as crossover and mutation to create individuals who are better suited. For a given solution point in the proposed CMS layout problem, a GA procedure is embedded in the linear programming model resulting from the model presented in the previous section after the RLs of the machines and cells are determined and the values of binary variables are obtained by random graph construction. The omission of the binary variables and transition of the model from MIP to LP subsequently make it solvable efficiently on a real-sized scale. Then, the resulting LP subproblem is implemented in GAMS software using a CPLEX solver to compute the value of the objective function as well as continuous variables. The idea of using a meta-heuristic algorithm integrated with an LP model instead of a MIP model was adopted by Teghem et al. (1995). Besides the complexity reduction of the LP-embedded approach, this approach most likely performs more efficiently than the pure GA to obtain a near-optimal solution. This is obvious as the LP-embedded approach is a partially random procedure as the LP subproblem is solved based on an exact procedure after binary variables are obtained. On the contrary, pure GA is entirely based on a random search mechanism, which decreases its efficiency to reach optimal solution compared with the LP-embedded approach.

Chromosome representation

The chromosome representation or encoding of a solution is the first step whenever using a GA. In the proposed GA, the initial population is generated according to the procedure explained in graph pair construction. Each solution of the initial population is the RLs of a machine set in a cell manipulated by graph pair $(G_{L R}^{M c}, G_{U B}^{M c})$ , forming a matrix of size Mc ×. Likewise, a matrix of size contains the RLs of cells within the shop floor manipulated by the graph pair $(G_{L R}^{C}, G_{U B}^{C})$ .

Fitness function

The fitness function is calculated to evaluate the candidate solutions in the population for the objective function and constraints of the model. For a given solution of the proposed problem, the fitness value is the objective function obtained by solving the LP subproblem.

Genetic operators

Genetic operators are used to create better solutions and replace them with those that existed in the initial population to obtain near-optimum solutions. Generally, genetic operators are classified as selection, crossover and mutation. In the proposed GA, roulette wheel operator is used to probabilistically select the parents within the initial population to construct new children. The Roulette Wheel selection procedure is the selection strategy used in the proposed algorithm. This strategy aims at selecting the “fittest” individual more likely to reproduce children for the next generation.

The main operator of the GA is crossover, which reproduces individuals by combining the information of randomly selected parents such that created offspring share the characteristics of both parents. These offspring are compared in terms of fitness function and passed on to the next generation. The crossover operator used in the proposed GA is a uniform crossover. For binary variables represented by graph pairs, binary chromosomes, namely those with the same size as corresponding cells or machine sets, are generated. Offspring 1 adopts that gene of parent 1 whose corresponding genes take value 1 and adopts the rest of genes from parent 2. The reverse procedure is applied to create offspring 2. The procedure of uniform crossover for the machines of a given cell is shown in Figure 3. Also, the equations of uniform crossover are given as follows: (21) $o f f s p r i n g 1 = α \times P a r e n t 1 + (1 - α) \times P a r e n t 2$ (22) $o f f s p r i n g 2 = α \times P a r e n t 2 + (1 - α) \times P a r e n t 1$

The other genetic operator is mutation. This operator is mainly used to avoid local optimization by randomly changing individual genes and increasing the search space. In this study, binary operator is used for the mutation process. This operator is applied to the randomly selected individual as follows: Parameter µ is defined between [0,1], and the number of genes within the selected parent that should be replaced to create new offspring is obtained as follows:

Then, the binary mutation changes the number of randomly selected genes in the list of chromosomes from a 1 to a 0, and vice versa, to generate a new offspring. Figure 4 illustrates the binary mutation, given that two genes are to be changed according to the above equation: (23) $N u m b e r o f r e p l a c e d g e n e s = [μ \times N u m b e r o f g e n e s w i t h i n a c h r o m o s o m e] + 1$

Chromosome repairing

The RLs of the machines and cells directly obtained from the offspring generated by either crossover or mutation crossover might represent an infeasible solution. The infeasibility occurs due to both arcs (m, n) and (n, m) or (k, c) might have taken value 1 in their corresponding matrix simultaneously. The violation of transitivity relationships could be another reason demonstrating the viability of chromosome repairing in our proposed algorithm. Also, it is probable that neither of the graph pairs contains at least one arc between any two nodes, which incurs the violation of overlapping constraint between the corresponding machines or cells.

Chromosome decoding

Chromosome decoding of a solution is referred to the process of obtaining the variables of a model from the values of its chromosome gene, as the scale might be differently defined in the algorithm. In the proposed algorithm, however, the values of binary variables of the model specifying RLs of the machines and cells are directly read from the chromosome genes after the repairing process.

For each offspring, solution resulting from crossover or mutation operator, an LP subproblem is solved and evaluated based on their fitness value to constitute the next generation. The flowchart of the proposed LPEGA is given in Figure 5 using the notations given below.

= Index for individuals within the population of each generation;

= Index for generation, i.e. iterations of the algorithm;

= Crossover rate;

= Mutation rate;

= Population size of each generation;

MPS

= Merged population size of current crossover and mutation as well as previous population;

G_max

= Maximum number of generations;

Phase

= A binary variable taking value 0 for the initialization phase or 1 for the improvement phase;

= The number of successive generations counted in the algorithm without any improvement in terms of fitness function; and

S_max

= The maximum value of s at which the algorithm will be terminated.

Parameters setting

The efficiency and effectiveness of meta-heuristic algorithms highly depend on the appropriate adjustment of the parameters. In most research studies, parameters are set based on either reference values of the literature or trial and error. Since the optimal parameters of the algorithms vary from one problem to another, specific adjustment of each newly developed algorithm substantially increases the quality of the algorithm solutions. In this regard, experimental design approaches such as full factorial design, response surface methodology (RSM) and Taguchi method have been widely used to estimate the appropriate parameters of the algorithms. In this study, the parameter optimization of the proposed LPEGA is performed based on the Taguchi method. The Taguchi experimental design has been extensively used for optimization problems. This method studies a large number of decision variables with only a small number of well-defined experimental sets (Nourmohammadi and Zandieh, 2011). Taguchi's design is based on two major tools: orthogonal array (OA) and signal-to-noise (S/N) ratio. The OA is a matrix of numbers containing experimental schemes based on different levels of factors. The S/N ratio is the measure of variation and guarantees the robustness of this kind of experimental design. The term “signal” represents “mean response variable” as the desirable value, and “noise” represents “standard deviation” as the undesirable value (Mehdizadeh et al., 2015). Taguchi method attempts to minimize the impact of noise and find the best level of controllable parameters simultaneously on the robustness basis (Tsai et al., 2007; Naderi et al., 2009). In such conditions, it is necessary to replicate the experiments in different situations to decrease the detrimental effect of noise parameters. In this study, the proposed LPEGA is adjusted over various test problems designed and illustrated in Tables 5 and 6. To experiment, each test problem is run three times to yield more reliable information owing to the stochastic nature of GA. Then, the experiments are implemented by MATLAB software on a computer with Intel® Core 5 CPU, 2.67 GHz speed and 4 GB RAM.

Taguchi method aims to maximize the S/N ratio, which is calculated by equation (24) for minimization problems for each parameter i on its related level j: (24) ${(S / N ratio)}_{i j} = - 10 \log_{10} (\frac{\sum z_{i j}^{2}}{n}) \forall i, j$ where Z_ij is the objective function value using parameter i on the level j and n is the number of times the level j of the parameter i is repeated over the runs of all trials.

The first step of parameter setting is to determine the parameters as control factors and their levels to implement the adopted experimental design. Parameters of the proposed GA include several iterations (G_max) initial population size (PS), crossover population size (PS × Cr) and mutation population size (PS × Mr). It is set according to a stoppage criterion that terminates the search over the initial population after searching 10 iterations without improvement, which is obtained based on trial and error. LPEGA parameter setting is carried out on different levels PS, Mr as shown in Table 2.

From the standard table of orthogonal arrays, L₉ (3³) is chosen, as illustrated in Table 3. In this table, rows denote the level of parameters in each experimental scheme, and columns indicate a specific level of a parameter that is changeable in each scheme.

Results of the test problems for the LPEGA procedure are achieved after they are implemented in MATLAB software, and Taguchi designs of LPEGA parameters are implemented in Minitab14. Therefore, the optimal level of the proposed LPEGA parameters is shown in the last column of Table 3 as depicted in Figure 6.

6. Experimental results

In this section, several numerical examples are designed and tested to demonstrate the applicability of the proposed algorithm. The proposed LPEGA procedure was implemented by linking MATLAB and GAMS software on a computer with Intel® Core 5 CPU, 2.67 GHz speed and 4 GB RAM. Parameters of the model are either generated randomly or given by a user-specified value, as included in Table 4. The experiments were implemented in two categories: firstly, for small-sized instances, and secondly, for large-sized instances.

Small-sized problems

The first set of experiments is carried out on seven small-sized instances. Here, small-sized instances are referred to as problems that are solvable optimally in GAMS software using CPLEX solver in reasonable CPU time. The solutions obtained from the LPEGA, which is coded in MATLAB software, are compared with optimal solutions of these instances to verify the efficiency of the proposed algorithm. Table 5 represents the data for the test problems and a comparison between exact solutions obtained from the GAMS and those that resulted from the proposed LPEGA procedure in terms of objective function values. The reasonable gap between the optimal solution and LPEGA solution, with the average of 0.75% presented in Table 5, permits us to generalize the proposed algorithm for large-sized instances that are not solvable optimally by the CPLEX solver. Looking at the CPU run times of the proposed LPEGA shows the comparatively high run time of this algorithm. This originated from the linkage of two different software, as a large amount of time is devoted to the information transmission between the two software.

Large-sized problem

Another set of experiments is performed for large-sized instances since the authenticity of the proposed LPEGA procedure for small-sized problems was proven in the previous section. To establish the desired experiments, five large-sized instances, as presented in Table 6, are designed and implemented in MATLAB software. Results consisting of objective function values and CPU run time are presented in Table 6. Besides, column 4 of Table 6 represents the objective values of large-sized instances after running for an hour in the GAMS-CPLEX solver as a lower bound of LPEGA solutions. An average gap of −2.04 resulted from every pair of solutions reported in the last column of Table 6, proving the efficiency of the proposed LPEGA for large-sized instances.

Illustrative example

In this section, the small-sized example number 5 is illustrated in detail using both GAMS software and the proposed LPEGA to confirm the viability of the proposed approach. As shown in Table 3, this problem handles the layout of three cells, each of which includes three, four and three machines, respectively, which are supposed to produce 12 products. The machines’ dimensions are shown in Table 7. Also, the products’ route, demand and batch sizes are given in Table 8.

Implementing the above-mentioned problem in GAMS software brings about the optimal layout of cells and machines given in Table 9, as depicted in Figure 7. For the proposed LPEGA, however, the RLs of cells and machines are primarily specified, as depicted by the graph pairs in Figure 8, and launched to GAMS software. Then, an LP problem is solved, and the layout of LPEGA is acquired and given in Table 6, as shown in Figure 9.

7. Conclusion

In this paper, an LPEGA is proposed by which the RLs of the machines and cells and consequently the binary variables of the model are specified through a pair of graphs. Then, a GA is embedded in the resulting LP after graph-pair construction with a heuristic approach is implemented to determine the coordinates of machines and cells within the shop floor. After tuning the parameters of the GA part of the proposed LPEGA, seven small-sized numerical examples are implemented with a linkage between MATLAB and GAMS software to tackle the proposed procedure. Compared to the optimal solutions obtained from GAMS software CPLEX solver for small-sized problems, the efficiency of the LPEGA to obtain near-optimum solutions was proven owing to the average gap of 0.75%. Another set of experiments included five large-sized instances evaluating the quality of large-sized problems against their corresponding lower bound solution obtained after running an hour the GAMS software. The average gap of −2.04% for large-sized instances proves that the proposed LPEGA can tackle large-sized problems for the proposed model. The proposed algorithm's applicability in real-world scenarios, as demonstrated by its ability to handle small and large size instances efficiently, offers a valuable contribution to the practical application of the proposed optimization techniques in the field of cellular manufacturing layout and contributes to improving efficiency in industrial settings. In future study, the current research can be extended in real industrial case study.

The authors would like to express their appreciation to the University of Tehran for the financial support of this study. They are also grateful to the respected reviewers for their valuable comments in preparation of the revised manuscript.

Figure 1.

Sample cellular manufacturing layout

Figure 2.

Graph-pair representation of the sample floor is illustrated in Figure 1

Figure 3.

A sample uniform crossover procedure of a graph in one direction

Figure 4.

A sample binary mutation of a graph in one direction

Figure 5.

Flowchart of the proposed LPEGA

Figure 6.

S/N ratio diagrams for different parameters of LPEGA

Figure 7.

The layout of cells and machines obtained from GAMS for the illustrated example (problem number 5)

Figure 8.

The layout of cells and machines obtained from LPEGA for the illustrated example (problem number 5)

Figure 9.

RLs of cells and machines obtained from GA procedure for the illustrated example

Table 1.

Summary of research works on the inter and intra-cell layout problems in CMSs

Authors	Year	UFLP	CMS
			CF	Layout		Layout type
				Inter-cell	Intra-cell	Continuous	Discrete	Graph theory utilization	Solution method
Alfa et al.	1992		✓	✓	✓		✓		SA
Hertza et al.	1994		✓					✓	Maximum weighted stable set
Kim	1995	✓						✓	Heuristic
Kochhar et al.	1998	✓					✓		GA
Lee	1998			✓	✓	✓			Heuristic
Bazargan-lari et al.	2000		✓	✓	✓	✓			SA
Salum	2000				✓		✓		Heuristic
Chan et al.	2004				✓	✓			MAIN
Castillo et al.	2005	✓					✓		Branch and bound and Extended cutting plane
Tavakkoli-Moghaddam et al.	2007			✓	✓		✓		Stochastic programming
Wu et al.	2007		✓	✓	✓		✓		GA
Jolai et al.	2011	✓		✓	✓	✓			BPSO
Jolai et al.	2012	✓	✓	✓	✓	✓			MOPSO
Bozer and Wang	2012	✓				✓		✓	SA
Chang et al.	2013		✓	✓	✓		✓		TS
Kulkarni et al.	2013			✓			✓		GA
Kulturel-Konak and Konak	2013	✓					✓		Hybrid GA and LP
Javadi et al.	2014			✓	✓	✓			GA and EM-like algorithm
Li et al.	2015			✓		✓			SA
Rabbani et al.	2017			✓	✓				GA, TS
Hunagund et al.	2018	✓							SA
Forghani et al.	2020			✓	✓				SA, GA and MA
Al‐Zuheri et al.	2022		✓		✓		✓		GT&GA and Desirability function
Mansour et al.	2022	✓	✓		✓	✓			Heuristic
Wu et al.	2023		✓		✓		✓		GA
Motahari et al.	2023		✓	✓	✓		✓		NSGA-II
Current study		✓		✓	✓	✓		✓	LPEGA

Notes:Branch and bound (BB), extended cutting plane (ECP), maximum weighted stable set (MWSS), stochastic programming (SP), desirability function (DF)