A hybrid genetic and imperialist competitive algorithm approach to dynamic cellular manufacturing system

Abstract

Cellular manufacturing system is an important application of group technology, which deals with grouping the parts and machines into cells, based on their similarity in design or production process. Since a purpose of this article is designing the cells under indefinite demand values up to the end of previous period, a dynamic multi-objective mathematical model based on this condition is proposed, and a heuristic approach has been developed in order to solve the problem. During this procedure, since the proposed model is a nondeterministic polynomial-time-hard problem, a new hybrid meta-heuristic approach called genetic imperialist competitive algorithm is implemented to solve it. Also, an experimental design has been used for tuning essential parameters. The proposed model has been verified by some hypothetical numerical examples with different input parameters and also by a real-world case study taken from a glass mold company. The comparison of results of the proposed genetic imperialist competitive algorithm and the genetic algorithm verifies the efficiency of the proposed solution approach. Also, the results show that the accuracy of the proposed algorithm is comparable with the exact solution methods such as branch and bound algorithm in both solution quality and computational time aspects.

Keywords

Imperialist competitive algorithm genetic algorithm cellular manufacturing design of experiments

Introduction

In today’s competitive environment, it is necessary to reduce total production cost and enhance the total manufacturing system’s efficiency through implementing new developed techniques. Cellular manufacturing system (CMS) is an application of group technology (GT) aimed at increasing production efficiency and system flexibility concurrently. Also, dynamic cellular manufacturing system (DCMS) is a production system that deals with designing a CMS over a production horizon when we have some production periods with different parameters such as demand and processing time. Hence, a cell design that is optimal in a period may not be optimal in remaining periods.

In an ideal DCMS, it is preferable that each part be processed in only one cell without any trip between the cells. But in practice, there are many constraints such as machine availability and production physical space limitations that force practitioners to assign the machines into cells in such a way that a suitable and flexible production flow will be obtained. As it is pointed out by Dimopoulos and Zalzala,¹ a CMS design is recognized as a nondeterministic polynomial-time (NP)–hard problem, which means increasing the problem size will increase the computational time of exact solution methods with nonpolynomial function. Therefore, the heuristic and meta-heuristic solution approaches are proper alternatives to exact solution methods such as branch and bound (B&B) algorithm to solve the problem in a reasonable computational time. In this research, a new hybrid genetic imperialist competitive algorithm (GICA) is proposed, which provides the following options.

Solution clustering in search space affects the optimality of problem. In other words, in the proposed approach, colonies can move toward the best country that is nearest, irrespective of its capability to be an imperialist. This policy avoids the local optimum solutions.

The proposed approach can be implemented efficiently in problems with discrete search space as well in continuous space.

Search space can be explored more efficiently by applying crossover operators on different solution clusters (local search). Hence, the proposed GICA outperforms both original imperialist competitive algorithm (ICA) and genetic algorithm (GA).

In real industrial environment, the demand value for each part type is almost not deterministic. There are many articles in literature in which demands are considered as a probabilistic factor. However, the demand value determining through a certain statistic distribution or other methods such as scenario planning is not applicable in some cases. For example, suppose a condition in which there is no sufficient information from past planned horizons to determine the demands. Hence, in this article, a new heuristic approach has been used to solve the CMS problem where the demands of products for a period will be arrived at the end of previous production period. In majority of previous DCMS studies, a virtual cell for machine collection at the end of planning period is considered. In this article, the machines are transferred to other cells at the end of a period in order to start the next period without any interruption in the production system.

Literature review

Recently, many studies are conducted based on production philosophies such as Just In Time (JIT), Lean Manufacturing Theory and GT, which try to design an appropriate production environment. For example, De Coster and Bateman² have examined the opportunities for improving the environmental impact of products within the constraints of existing manufacturing infrastructure. Bhat³ has simulated the analysis of a multi-stage lean manufacturing cell. The analysis conducted in this research investigates how the ordering policies of manufactured parts affect the system efficiency under demand variability and imperfect supplier performance. Many studies have been conducted to design an efficient CMS. Ameli and Arkat⁴ have proposed a pure integer mathematical model to solve the cell formation (CF) problem considering machine reliability and alternative process routing. Their research shows that the reliability consideration has significant impacts on the overall system efficiency. Also, Onwubolu and Mutingi⁵ have formulated the CF problem by attention to minimization of the cell load variation. A comprehensive mathematical model considering many real production factors such as operation sequence, routing flexibility, machine duplication and tool requirements has been proposed by Fantahun and Mingyuan,⁶ which is solved by a GA. In fact, because of complexity of mathematical programming especially for large-size problems, many heuristic and meta-heuristics are developed to solve the CF problem efficiently. The main strategy of these methods is searching the solution space in such a way that an optimum or near to optimum solution be found in a reasonable computational time. Especially, they can be implemented in many large problems. The main algorithms used in this area are GA (Zhao and Wu,⁷ Krishnan et al.⁸), simulated annealing (SA) (Caux et al.⁹), tabu search (TS) (Onwubolu and Songore¹⁰) and the recently developed ICA. Tavakkoli-Moghaddam et al.¹¹ have developed a dynamic CF problem. Three basic meta-heuristics including GA, SA and TS are implemented to solve the model, and then, introduced approaches have been compared to each other. Recently, Wu et al.¹² have proposed a water flow–like algorithm to solve the CF problem. Their meta-heuristic solution approach has been verified in both solution effectiveness and efficiency aspects in comparison with other existing solution methods.

In recent years, many researchers have investigated the combination of ICA with other approaches to improve both solution quality and computational time aspects. Talatahari et al.¹³ have proposed a new improved ICA. Seven different chaotic maps to be used during the imperialists’ movements are introduced. However, their proposed approach can be used only in a continuous space. In order to adapt the angel of colonies movement toward the imperialists’ position, a new adaptive ICA is introduced by Abdechiri et al.¹⁴

Table 1 reports the comparison between recently developed ICAs for different optimization problems. From this table, it can be realized that proposing new heuristic and meta-heuristic approaches capable of increasing the solution’s optimality—especially for large-scale problems—is necessary. Moreover, ICA is a new solution approach, which has not been applied to solve a CMS problem. Also in this table, the symbol * shows whether the search space type is discrete or continuous.

Table 1.

Recent studies about combination of ICA with other algorithms.

Study	Year	Solution approach	Search space		Problem type	Solution approach novelty
			Discrete	Continuous
Talatahari et al.¹³	2012	Improved ICA		*	Global optimization	Seven different chaotic maps to be used during the imperialists’ movements are introduced
Abdechiri et al.¹⁴	2010	Adaptive ICA		*	Global optimization	The angel of colonies movement toward the imperialists’ position is adapted
Yousefikhoshbakht and Sedighpour¹⁵	2013	ICA	*		TSP	Comparing with other meta-heuristics
Karimi et al.¹⁶	2011	ICA + electromagnetic	*		Flow shop scheduling	Electromagnetic-like mechanism concepts are employed to influence of the imperialist on their colonies
Lian et al.¹⁷	2012	ICA	*		Process planning + scheduling	–
Jolai et al.¹⁸	2012	AICA + PBSA	*		Flexible flow shop scheduling	Population-based SA is applied to local search process
Mollayi-Berneti¹⁹	2012	Adaptive neuro-fuzzy inference system + ICA		*	Global optimization	The proposed model combines the global search ability of ICA with local search ability of gradient descent method
This article	2013	ICA + GA	*		Cellular manufacturing system (CMS)	Solution clustering during the inner competition avoids the local solutions

GA: genetic algorithm; GICA: genetic imperialist competitive algorithm; PBSA: population-based simulated annealing; AICA: adapted imperialist competitive algorithm; TSP: traveling salesman problem.

In this research, a multi-objective mathematical model is presented considering the operation sequence for different parts. The first objective is to minimize the cell load variation. The second objective is to minimize the inter- and intra-cell part trips, and the third one is to minimize the system reconfiguration cost during the different production periods.

This article is organized as follows: problem formulation, parameters, decision variables and objective function are presented in the next section. Then, the proposed GICA solution approach is described in section “Proposed heuristic procedure and GICA method.” The comparison of obtained results with other algorithms will be discussed in section “Numerical examples.” Finally, section “Conclusion” concludes this research.

Problem formulation

In this article, a multi-objective model is proposed based on the three main goals. The first objective is minimization of cell load variation in order to maximize the total efficiency of the system. This function is based on the model proposed by Onwubolu and Mutingi.⁵ But in this study, we improve it through considering the demand volume for each part type in a production period. The second objective function is minimization of the total inter- and intra-cell part trips. In the proposed model, it is assumed that the cost of a trip is independent of distances and only depends on trip type (inter- or intra-cell). This means that when a part moves between the cells, the cost of this movement is constant and greater than an inner movement cost. The third objective function emphasizes the dynamic nature of the model. In the presence of dynamic production circumstances, the best CF design for one period may not be an efficient design for other periods. By reconfiguring the manufacturing cells, the CF can continue operating efficiently as the product mix and demand change.²⁰ As shown in section “Numerical examples,” a CMS can be designed in manufacturing companies with small- and medium-sized machines such as drilling machines, computer numerical control (CNC) milling machines, conventional milling machines and electro-erosion machines, which are capable of moving. These kinds of machines can be relocated considering many real-world manufacturing costs. In other words, considering the part trip costs and cell load variation cost, it may be efficient to remove and install the machines from and in a cell, respectively, just between two production periods in order to decrease total cost. Basically, it is assumed that when a machine is relocated from one cell to another cell, it is removed from its current position and installed in another cell; the cost of this relocation is called machine relocation cost.^20,21 In this objective function, it is assumed that this kind of cost depends on the distances between the cells. Also, it is assumed that the demands for each part type are determined at the end of previous period.

Notation

Indices and their relative upper bounds

P number of parts

C number of cells

m number of machines

np number of production periods

Input parameters

$θ_{1}, θ_{2}, θ_{3} and θ_{4}$ are the coefficients representing the importance of each objective term. These coefficients can also be implemented as the cost functions. (For instance, $θ_{2}$ as an inter-cell movement cost and $θ_{3}$ as an intra-cell movement cost). Dimopoulos²² suggests $θ_{2} = 0.7$ and $θ_{3} = 0.3$ as weights attributed to the inter- and intra-cell trips, respectively. However, possibility of selecting the values of these coefficients depends on the decision maker opinion and makes the model more flexible.

${[R]}_{np \times p}$ is a np×p, period–part matrix, where r_ji is the demand for part j in time period i; ${[W]}_{m \times p}^{np}$ is a m×p, machine–part matrix, where w_kj is the operation time of part j on machine k in period i; ${[u]}_{M \times p}^{np}$ is a m×p, machine–part matrix, where $u_{kj}^{i}$ is the total workload operation time of part j on machine k in period i. By considering the demand for each part in that period, it can be formulated as equation (1)

u_{kj}^{i} = w_{kj}^{i} \times r_{ji}

(1)

The table ${[os]}_{p \times m}$ is a p×m, part–machine table, where each row represents the operation sequence of the part related to this row. Also, “om_j” is the number of machines implemented to produce part j.

Variables

$x_{kl}^{i}$ is 1 if machine k is assigned to cellule l in period i, otherwise 0. ${[m]}_{c \times p}^{np}$ is a c×p, cell–part incidence matrix, where $m_{lj}^{i}$ is the average load for cellule l and part j in period i. $m_{lj}^{i}$ can be formulated as equation (2)

m_{lj}^{i} = \frac{\sum_{k = 1}^{m} x_{kl}^{i} \times u_{kj}^{i}}{\sum_{k = 1}^{m} x_{kl}^{i}}

(2)

The mathematical model

f_{1} = \sum_{k = 1}^{m} \sum_{l = 1}^{c} \sum_{j = 1}^{p} θ_{1} {(u_{kj}^{i} - m_{lj}^{i})}^{2}

(3)

f_{2} = \sum_{j = 1}^{p} \sum_{l = 1}^{c} \sum_{k = 1}^{o m_{l} - 1} θ_{2} | x_{(o s (j, k)) l}^{i} - x_{(o s (j, k + 1)) l}^{i} | \times R (j, i) + \sum_{j = 1}^{p} \sum_{l = 1}^{c} \sum_{k = 1}^{o m_{l} - 1} θ_{3} \times \max (x_{(o s (j, k)) l}^{i} + x_{(o s (j, k + 1)) l}^{i} - 1, 0) \times R (j, i) \forall i = 1, \dots, n p

(4)

\begin{matrix} f_{3} & = \sum_{l = 1}^{c} \sum_{n = 1}^{c} θ_{4} \times D_{\ln} \sum_{k = 1}^{m} max (x_{kl}^{i} + x_{kn}^{i - 1} - 1, 0) \\ \forall i & = 2, \dots, np \end{matrix}

(5)

Subjected to

\begin{matrix} \sum_{l = 1}^{c} x_{kl}^{i} = 1 & k = 1, \dots, m & \forall i = 1, \dots, np \end{matrix}

(6)

\begin{matrix} \sum_{k = 1}^{m} x_{kl}^{i} \geq lc & l = 1, \dots, c & \forall i = 1, \dots, np \end{matrix}

(7)

\begin{matrix} \sum_{k = 1}^{m} x_{kl}^{i} \leq uc & l = 1, \dots, c & \forall i = 1, \dots, np \end{matrix}

(8)

The first term in the objective function minimizes the total cell load variation. This term gives the extent of variation of the load on machine k in cell l (induced by all parts) from the mean load of cell l.⁵ The second and third terms minimize the total inter- and intra-cell part trips, respectively, which are independent of distances. The last term minimizes the total machine relocation cost. Machine relocations are based on distances between the cells.

The first constraint is to ensure that each machine is assigned to only one cell in each period. Lower and upper bounds on the sizes of a cell are constrained according to the statements 5 and 6, respectively.

Proposed heuristic procedure and GICA method

In many recent studies, it is assumed that the demand values are deterministic. However, in DCMS, demands are considered as probabilistic factors and should be determined by scenario planning or other determining methods. In the DCMS proposed here, we consider a condition in which the demands for a production period will be determined at the end of previous period, and demands are not definite at the first of production horizon. So, a heuristic procedure is developed to solve the problem with considering mentioned situation. In the proposed heuristic, the optimal CF solution should be found only for the first period. Then, cellular design for other periods will be planned sequentially using previous period’s solution.

As it was mentioned previously, the proposed model is known as NP-hard problem.¹ In recent years, many studies have been conducted to solve this type of problems. These studies include the heuristic and meta-heuristic methods.^23–25

In this article, a new meta-heuristic hybrid GICA has been implemented to solve the problem mentioned. ICA is a new meta-heuristic evolutionary algorithm that starts with a population of solutions, any of them called a country. These countries are divided into two basic groups. The best solutions or the powerful countries become the imperialists and the rest of the solutions become the colonies.

Inner competition

In each empire, it is preferable that the colonies move toward an imperialist, and these movements make the algorithm neighborhoods, so we can explore the solution space by this strategy.

Outer competition

The basic competition during this algorithm is between the empires where each imperialist wants to take possession of other colonies. After some iterations, the weak imperialists will collapse, and at the end of the algorithm, only the powerful empire will be remained, and the remaining imperialist is the optimal or at least close to optimal solution. In each of the iterations, the weakest empire is selected, and its weakest country is assigned to other empires.

ICA parameters

Each country is evaluated by a fitness function. Nevertheless, this function should be normalized in order to choose the powerful and weak empires in the solution space. The normalized power of a country is calculated by equation (9)

p_{i} = | \frac{C_{i}}{\sum_{i = 1}^{n_imp} C_{i}} |

(9)

where C_i is the power of the country i evaluated by the objective function and n_imp is the initial number of the imperialists in the world or in the solution space.

To start the outer competition, the total power of an empire should be determined first using equation (10)

\begin{matrix} Total_\cos t_{i} = \cos t (imp) \\ + ε \times mean (\cos t (colonies of that imp)) \end{matrix}

(10)

where “ε” is a coefficient that indicates the colonies’ participation proportion in the empire power determination. The normalized total power of an empire is determined by equation (11)

normal_Total_\cos t_{i} = Total_\cos t_{i} - max (Total_\cos t)

(11)

The second step is determining the possession probability of each empire according to equation (12)

p_tota l_{i} = | \frac{normal_Total_\cos t_{i}}{\sum_{i = 1}^{n_imp} normal_Total_\cos t_{i}} |

(12)

One of the main contribution of this article is to permit the colonies to only move toward the nearest dominant string in the inner competition. Furthermore, the GA operations are applied to explore the solution space efficiently. Here, each four strings are considered as a group (batch). In each group, the meritorious string is selected, and the crossover operators are applied on three other members of group, thereby having an essential advantage. In fact, this method avoids the local optimal solution. Three methods have been used to apply the solution making operators: reversing the best string (Figure 1), two-point crossover (Figure 2) and selection and replacement (Figure 3).

Figure 1.

Reverse the string.

Figure 2.

Two-point crossover.

Figure 3.

Select and replacement.

The crossover operation may create the infeasible solutions. For example, in Figure 2, we can see that none of the machines is assigned to cells 2 and 3 in child 1. So, a penalty is assumed to be added to the fitness function for infeasible solutions.

Solution representation and pseudocode

Choosing a suitable representation of a solution is very essential in meta-heuristic algorithms. In this article, a solution is represented by a string as a country. For example, let consider a string as follows:

This string represents that machines 1, 5 and 7 are assigned to cell 2, machines 2 and 3 to cell 3 and machines 4 and 6 to cell 1.

Considering these descriptions, the pseudocode of proposed GICA meta-heuristic can be written as follows:

1- Start

2- Create the initial population randomly.

3- Select the “n_imp” best strings as the imperialists and construct the empires.

4- Divide the rest of strings (countries) between the empires based on their normalized power.

5- If only one empire remains, go to step 8.

6- Start the inner competition:

-Divide the each empire to groups with four countries.

-Apply the crossover operator to each group.

7- Start the outer competition:

-Find the weakest empire based on the total normalized power of the empires.

-Find the worst country in selected empire and release it from that country.

-Form the vector “P” consists of the possession probability of each empire

-Form the vector “E” with the same size of “P” vector and create the elements of “E” between zero and one randomly.

-Form the vector R as R=P-E. Find the maximum element of R and save its index.

-Select the empire of recognized index.

-Assign the released country to this empire.

-Go to step 5.

8- End;

The flowchart of the proposed procedure is illustrated as Figure 4.

Figure 4.

The flowchart of proposed algorithm for the DCMS problem.

Numerical examples

A test problem

The performance of proposed GICA is verified not only in the CMS design problem. In fact, the power of a new algorithm should be tested for other types of problems also to visualize its complete power and weaknesses. Hence, a test problem proposed by Haupt and Haupt²⁶ is taken to be solved. In order to evaluate the performance of proposed method, it should be compared with other meta-heuristics such as GA and original ICA. Table 2 reports the results. It is clear that the proposed GICA outperforms the original ICA, and it is also comparable with the GA. However, it will be shown that the performance of proposed GICA is much better than GA, especially in large-scale CF problems. Figures 5 and 6 demonstrate the convergence processing in iterations 5 and 24, respectively.

Table 2.

Comparison of proposed GICA with GA and original ICA.

Objective function	The optimal solution	Total iteration number			Computational time (s)
		Original ICA	GA	GICA	Original ICA	GA	GICA
$min f (x, y) = y \sin (4 x) + 1.1 x \sin (2 \times y), 0 \leq x, y \leq 10$	−18.56	34	20	7	1.62	0.1	0.46

GA: genetic algorithm; GICA: genetic imperialist competitive algorithm.

Figure 5.

Locations of the countries in solution space (iteration 5).

Figure 6.

Locations of the countries in solution space (iteration 24).

CF problem

The essential parameters of the proposed GICA are ε, population size and number of imperialists. The accuracy and computational time of the algorithm depend on these factors strictly. So, in order to design a robust and suitable algorithm, the proper levels of the mentioned factors should be selected. In this article, the response surface methodology (RSM) has been implemented to adjust the model parameters. After determination of factor levels, the second step is running the experiments for each treatment. In this example, the RSM method has been designed using Minitab software with two replicates. Table 3 illustrates the minimum and maximum levels of factors, and Table 4 reports some of experimental results. After analyzing the RSM, two regression equations are obtained, and by optimizing them, the optimal levels for each factor are determined. In this case, the optimum levels of population size, ε and n_imp are 100, 0.9 and 20, respectively.

Table 3.

Different levels for three essential parameters.

Levels	−1.68	−1	0	1	1.68
Population size	100	150	200	250	300
ε	0.1	0.3	0.5	0.8	0.9
Number of imperialists	5	10	15	20	25

Table 4.

Response surface design for parameter tuning.

ε	Initial population size	Number of imperialists	Objective function value	Computational time
1.68179	0	0	17,467	3.82
−1	1	1	17,595	11.739
1	1	−1	17,467	57.229
−1	−1	1	17,207	4.833
0	0	0	17207	34.92
…	…	…	…	…
0	1.68179	0	17,467	19.249
1	1	1	17,207	7.663
0	0	0	17,207	43.347
−1	1	−1	17,207	9.127
−1	−1	1	17,467	13.591
0	0	0	17,207	15.162
1	−1	1	17,681	7.699

Randomly generated examples

In this section, several test problems are presented based on GICA. Examples 1–4 are generated randomly by uniform distribution in hypothetical limits. In these examples, it has been assumed that the production planning horizon consists of two production periods.

A real case study

The last example is taken form a real industrial case proposed by Satoglu and Suresh.²⁷ In order to verify our proposed methodology, we apply it on a glass mold manufacturing company. This company manufactures 35 various parts by means of eight types of machines, including CNC lathe (M1), conventional lathes (two types: M2 and M3), drilling machine (M4), CNC milling machine (M5), conventional milling machine (M6) and electro-erosion machine (two types: M7 and M8). However, some of these parts have erratic demands, which decrease the system robustness. In other words, some of these parts should be manufactured in functional layout of company and not in cells. In order to simplify the computational effort of the model, special parts (parts 18–35) having low or erratic demands are not considered in this article. Table 5 reports the monthly demand of parts and also the process sequence for each part type. Moreover, workload of each part on each machine (matrix U ) is reported in Table 6. Other information of this company, including number of cells and also maximum and minimum number of machines required by each cell, is stated in Table 7. However, since this case is considered only for one production period, we modify it through considering a two-period production horizon.

Table 5.

Monthly demand of each part type (industrial case).

	Monthly demand period 1	Monthly demand period 2	Process sequence
Part 1	195	180	1-3-2-7-4-8
Part 2	192	200	1-2
Part 3	207	140	3-1-2
Part 4	144	200	7-3-1-2
Part 5	127	20	6-2-1-4-7
Part 6	125	400	1-2-3-7-5
Part 7	120	20	2-1-4-5-7
Part 8	78	150	2-1
Part 9	67	90	7-4-5-2-1
Part 10	76	100	2-1
Part 11	68	90	4-1
Part 12	66	97	7-1
Part 13	65	35	2-1-5
Part 14	57	25	4-6-3-2-1
Part 15	60	78	6-3-1-8
Part 16	58	62	2-1
Part 17	51	26	6-2-1
Part 18	52	98	2-1

Table 6.

Workload of parts on each machine type.

	M1	M2	M3	M4	M5	M6	M7	M8
Part 1	147,361	61,934	42,713	42,713	0	0	10,678	32,035
Part 2	26,165	8051	0	0	0	0	0	0
Part 3	93,217	198,333	35,700	0	0	0	0	0
Part 4	44,680	184,677	32,233	0	0	0	35,744	0
Part 5	23,640	34,147	0	6567	0	6567	7880	0
Part 6	102,440	258,727	31,520	0	19,700	0	45,967	0
Part 7	39,733	34,767	0	6208	7450	0	9933	0
Part 8	4033.33	6453.33	0	0	0	0	0	0
Part 9	39,733	34,767	0	6208	7450	0	9933	0
Part 10	37,335	3905	0	0	0	0	0	0
Part 11	8027	0	0	1745	0	0	0	0
Part 12	38,043	0	0	0	0	0	13,587	0
Part 13	16666.7	2000	0	0	400,000	0	0	0
Part 14	58,710	41,406	11,124	9270	0	6180	0	0
Part 15	11,893	0	4757	0	0	2973	0	5947
Part 16	7657	14,136	0	0	0	0	0	0
Part 17	14,831	13,771	0	0	0	2119	0	0
Part 18	58,710	41,406	0	0	0	0	0	0

Table 7 also demonstrates the objective function values for production planning horizon obtained by implementing the proposed procedure. To show the efficiency of the proposed algorithm, the DCMS problem has been solved by the GA as well, and the results have been reported in Table 7, and the comparison has been done by an efficiency index according to equation (13). The optimal solution has been obtained by an exact solution algorithm using LINGO software. However, according to Table 7, the B&B algorithm is unable to find the optimal solution after 2220 s. The schematic view of CF obtained by GICA algorithm is depicted in Figure 7. For better analysis of results in each period, the results of examples 1 and 2 have been reported and compared for each period separately in Tables 8 and 9, respectively

% Efficiency = (1 - \frac{O F_{GICA} - O F_{optimum}}{O F_{optimum}}) \times 100

(13)

Table 7.

The comparison of results of proposed GICA approach, GA and exact solution for simulated numerical examples.

Example number	Number of machines	Number of parts	Number of cells	Maximum cell size	Exact solution	Exact Solution time (s)	Objective function value (GA)	GA efficiency (%)	Solution time (s) (GA)	Objective function value (GICA)	GICA efficiency (%)	Solution time (s) (GICA)	Total iteration number (GA)	Total iteration number (GICA)
1	4	2	2	2	1206.2	0	1206.7	100	10	1206.2	100	5.95	800	796
2	8	9	3	3	10,980	40	11,035	99.5	17.54	10,980	100	6.73	1600	860
3	10	12	3	4	15,076	238	15,165	99.4	18.71	15,148	99.52	13.06	1600	860
4	11	12	4	3	33,554	494	35,081	95.64	24.1	34,903	96.13	18.9	1600	924
Case study	8	18	3	3	–	2220	2,788,500	–	135.83	2,783,500	–	93.24	1600	958

GA: genetic algorithm; GICA: genetic imperialist competitive algorithm.

Figure 7.

Schematic view of obtained solution.

Table 8.

The comparison of results of proposed GICA approach, GA and exact solution for the first production period for the first and second examples.

Example number	Number of machines	Number of parts	Number of cells	Maximum cell size	Optimum solution	Solution time (min) (LINGO)	Objective function value (GA)	Efficiency (%)	Solution time (s) (GA)	Objective function value (GICA)	Efficiency (%)	Solution time (s) (GICA)
1	4	2	2	2	854.83	0	854.83	100	6	854.83	100	5.4
2	8	9	3	3	5446.25	21	5447.1	99.98	8.74	5446.2	100	3.64

GA: genetic algorithm; GICA: genetic imperialist competitive algorithm.

Table 9.

The comparison of results of proposed GICA approach, GA and exact solution of the second production period for the first and second examples.

Example number	Number of machines	Number of parts	Number of cells	Maximum cell size	Optimum solution	Solution time (min) (LINGO)	Objective function value (GA)	Efficiency (%)	Solution time (s) (GA)	Objective function value (GICA)	Efficiency (%)	Solution time (s) (GICA)
1	4	2	2	2	351.38	0	351.83	100	4	351.38	100	4.2
2	8	9	3	3	5533.66	19	5587.7	99.03	8.8	5533.7	100	3.84

GA: genetic algorithm; GICA: genetic imperialist competitive algorithm.

Figure 8 illustrates the comparisons between GICA and GA for Examples 1–4. It is clear that the proposed method is more efficient in both objective function value and the computational time aspects. According to this figure, it can be realized that the computational time for second example is less than that for example 1. It is because of difference in population size of these examples. The population sizes for examples 1 and 2 are 300 and 100, respectively.

Figure 8.

Comparison between the proposed GICA and GA.

Table 10 illustrates the best solution for every stage obtained by GICA. For instance, in an optimal sequence, the cell 1 contains machines 2 and 4, and machines 1 and 3 should be assigned to cell 2 considering example 1.

Table 10.

Best solutions for every example obtained by GICA.

Example 1	2	1	2	1
Example 2	1	1	3	3	2	3	2	2
Example 3	3	3	1	2	3	1	2	1	2	2
Example 4	3	4	4	4	3	1	1	2	2	3	1

Data analysis and managerial insights

As stated before, every mathematical model has some essential parameters, which should be analyzed more precisely. In this model, the cost indicators including $θ_{1}, θ_{2}, θ_{3} and θ_{4}$ are parameters that can affect the machine assignment solution and system efficiency. Introduced factors are the weights of model objectives and can be defined by the decision maker. $θ_{1}$ is the weight factor for cell load variation. $θ_{2} and θ_{3}$ are weights of cost functions related to inter- and intra-cell part trips, respectively. Figure 9 demonstrates the objective value of example 2 for various values of $θ_{1}, θ_{2} and θ_{3}$ . Here, we assume that $θ_{1} + θ_{2} + θ_{3} = 1$ . It is clear that $θ_{1}$ is more sensitive than other two parameters. However, the effect of inter-cell trip cost is high, and assigning the parts to a cell is preferable. The flexibility of model let the practitioner to select the suitable weights based on desired strategy.

Figure 9.

Sensitivity analysis of objective weights in DCMS problem.

However, there is another objective weight named $θ_{4}$ . It is clear that if inter-cell machine relocation cost is high, it is preferable that a machine stays in its current position. This matter has been illustrated in Table 11 considering the fourth objective weights as $θ_{4} = 300$ and $θ_{4} = 10$ .

Table 11.

The sensitivity analysis of the last objective weight considering the machine assignments.

$θ_{4} = 300$	Dominant imperialist in period 1	2	2	1	3	2	1	3	1	3	3	Imperialist power:	7418.8
	Dominant imperialist in period 2	2	2	1	3	2	1	3	1	3	3	Imperialist power:	7725.2
$θ_{4} = 10$	Dominant imperialist in period 1	1	1	3	2	1	3	2	3	2	2	Imperialist power:	7418.8
	Dominant imperialist in period 2	1	1	3	2	2	3	2	3	2	1	Imperialist power:	8004.8

Conclusion

In this article, a hybrid of GA and ICA called GICA was introduced to solve the multi-objective DCMS problem. The objectives of the proposed model were minimization of total cell load variation, minimization of inter- and intra-cell part trips and minimization of machine relocation cost. Also, response surface method was implemented for tuning essential parameters of the proposed algorithm. A real case study and also some simulated numerical examples were used to show the efficiency of the proposed approach, and the results confirm that the proposed GICA outperforms the GA for DCMS problem. For the future study, a clustering algorithm in grouping stage of the GICA is suggested. Also, selection operator can be added to GICA in each group for solving the DCMS problem more efficiently.

Footnotes

Declaration of conflicting interests

The authors declare that there is no conflict of interest.

Funding

This research received no specific grant from any funding agency in the public, commercial or not-for-profit sectors.

References

Dimopoulos

Zalzala

AMS

. Recent developments in evolutionary computations for manufacturing optimization: problems, solutions, and comparisons. IEEE T Evolut Comput 2000; 4: 93–113.

De Coster

Bateman

. Sustainable product development strategies: business planning and performance implications. Proc IMechE, Part B: J Engineering Manufacture 2012; 228(10): 1665–1674.

Bhat

. The effect of ordering policies for a manufacturing cell changing to lean production. Proc IMechE, Part B: J Engineering Manufacture 2008; 222(11): 1551–1560.

Ameli

MSJ

Arkat

. Cell formation with alternative process routings and machine reliability consideration. Int J Adv Manuf Tech 2008; 35: 761–768.

Onwubolu

Mutingi

. A genetic algorithm approach to cellular manufacturing systems. Comput Ind Eng 2001; 39: 125–144.

Fantahun

Mingyuan

. A comprehensive mathematical model for the design of cellular manufacturing systems. Int J Prod Econ 2006; 103: 767–783.

Zhao

. A genetic algorithm for manufacturing cell formation with multiple routes and multiple objectives. Int J Prod Res 2000; 38(2): 385–395.

Krishnan

Mirzaei

Venkatasamy

. A comprehensive approach to facility layout design and cell formation. Int J Adv Manuf Tech 2011; 59: 737–753.

Caux

Bruniaux

Pierreval

. Cell formation with alternative process plans and machine capacity constraints: a new combined approach. Int J Prod Econ 2000; 64: 279–284.

10.

Onwubolu

Songore

. A tabu search-based approach to cellular manufacturing systems. Prod Plan Control 2000; 11(2): 152–164.

11.

Tavakkoli-Moghaddam

Aryanezhad

Safaei

. Solving a dynamic cell formation problem using meta-heuristics. Appl Math Comput 2005; 170: 761–780.

12.

Chung

S-H

Chang

C-C

. A water flow-like algorithm for manufacturing cell formation problems. Eur J Oper Res 2010; 205: 346–360.

13.

Talatahari

Farahmand

Sheikholeslami

. Imperialist competitive algorithm combined with chaos for global optimization. Commun Nonlinear Sci 2012; 17: 1312–1319.

14.

Abdechiri

Faez

Bahrami

. Adaptive imperialist competitive algorithm (AICA). In: 9th IEEE international conference on cognitive informatics, Beijing, China, 7–9 July 2010, pp.940–945. New York: IEEE.

15.

Yousefikhoshbakht

Sedighpour

. New imperialist competitive algorithm to solve the travelling salesman problem. Int J Comput Math 2013; 90: 1495–1505.

16.

Karimi

Zandieh

Najafi

. Group scheduling in flexible flow shops: a hybridised approach of imperialist competitive algorithm and electromagnetic-like mechanism. Int J Prod Res 2011; 49(19): 4965–4977.

17.

Lian

Zhang

Gao

. Integrated process planning and scheduling using an imperialist competitive algorithm. Int J Prod Res 2012; 50(15): 4326–4343.

18.

Jolai

Rabiee

Asefi

. A novel hybrid meta-heuristic algorithm for a no-wait flexible flow shop scheduling problem with sequence dependant set up times. Int J Prod Res 2012; 50(24): 7447–7466.

19.

Mollayi-Berneti

. A hybrid approach based on the combination of adaptive neuro-fuzzy inference system and imperialist competitive algorithm: oil flow rate of the wells prediction case study. Int J Comput Int Sys 2013; 6(2): 198–208.

20.

Mahdavi

Aalaei

Paydar

. Designing a mathematical model for dynamic cellular manufacturing systems considering production planning and worker assignment. Comput Math Appl 2010; 60: 1014–1025.

21.

Kia

Baboli

Javadian

. Solving a group layout design model of a dynamic cellular manufacturing system with alternative process routings, lot splitting and flexible reconfiguration by simulated annealing. Comput Oper Res 2012; 39: 2642–2658.

22.

Dimopoulos

. Multi-objective optimization of manufacturing cell design. Int J Prod Res 2006; 44(22): 4855–4875.

23.

Andres

Lozano

. A particle swarm optimization algorithm for part-machine grouping. Robot Cim: Int Manuf 2006; 22: 468–474.

24.

Defersha

Chen

. Machine cell formation using a mathematical model and a genetic algorithm based heuristic. Int J Prod Res 2006; 44(12): 2421–2444.

25.

Haleh

Iranmanesh

Kor

. A new hybrid evolutionary algorithm for solving multi objective cell formation problem. In: IEEE international conference on computers and industrial engineering, Troyes, France, 6–9 July 2009, pp.612–616. New York: IEEE.

26.

Haupt

. Practical genetic algorithm. Hoboken, NJ: John Wiley & Sons, 2004.

27.

Satoglu

Suresh

. A goal programming approach for design of hybrid cellular manufacturing system in dual resource constrained environments. Comput Ind Eng 2009; 56: 560–575.