Computers & Industrial Engineering 143 (2020) 106439

Contents lists available at ScienceDirect

Computers & Industrial Engineering

journal homepage: www.elsevier.com/locate/caie

A vibration damping optimization algorithm for the integrated problem of T

cell formation, cellular scheduling, and intercellular layout
Vahid Rahimi, Jamal Arkat , Hiwa Farughi
⁎

Department of Industrial Engineering, University of Kurdistan, Sanandaj, Iran

ARTICLE INFO ABSTRACT

Keywords: The three problems of cell formation (CF), cellular scheduling, and cellular layout are closely interrelated in the
Cell formation design of cellular manufacturing systems (CMSs) and should, therefore, be considered in an integrated structure.
Cellular scheduling This paper presents a mixed-integer programming (MIP) model to examine such concurrent design by con-
Cellular layout sidering many design attributes, such as the machine duplication, alternative processing routes, reentrant parts,
Vibration damping optimization algorithm
and variable cell size. In the presented model, decisions including machine grouping, processing route selection,
operation sequencing, and cell assignment into candidate locations are taken such that the total completion time
is minimized. Since the problem in hand belongs to the NP-hard class, a vibration damping optimization (VDO)
algorithm is proposed to solve large-sized problems. In order to verify the efficiency of the proposed algorithm
comparing to the CPLEX solver of the GAMS software and two other metaheuristic algorithms, namely a genetic
algorithm (GA) and an ant lion optimizer (ALO) algorithm, several sample problems with different sizes and
settings are implemented. The results demonstrate that the proposed algorithm can obtain better solutions in less
computational time.

1. Introduction arrangement of cells on the shop floor and arrangement of machines in

cells; (3) the cellular scheduling, which determines the processing se-
Due to the rapid changes in customer requirements in competitive quence of operations on machines, and is aimed at the minimization of
markets, manufacturing companies should be able to produce a wide the makespan or completion time; and (4) the resource assignment, in
range of products. In such an environment, companies need manu- which the required resources such as operators are assigned to the cells.
facturing systems that both have high flexibility for producing various The CF and the cellular layout problems are highly interdependent.
products, like job shops, and produce high volumes of products in a On the one hand, the way machines are categorized, and the number of
short time, like mass production systems. Group Technology (GT) is a machines in each cell are effective on the intercellular and intracellular
manufacturing philosophy that seeks to identify physical and produc- layout; on the other hand, a suitable cellular layout can significantly
tion similarities between parts and uses these similarities to group reduce distances of inter- and intracellular movements. There have
machines and parts for speeding up the design and production. As one been many studies in the field of the CMS design that are dedicated to
of the well-known applications of the GT, the cellular manufacturing the inter-cell and intra-cell layout problems. In most of these studies,
system seeks to form relatively independent manufacturing units in the the layout problem is considered after solving the CF problem, and in
form of machine cells to produce part families by considering the si- some research, these two decisions are addressed simultaneously. A
milar design and production features of different parts. The most im- comprehensive literature review of the layout problem in the CMS
portant benefits of using a CMS include the simplification and reduction design has been conducted by Kia et al. (2012). Some of the most im-
of material handling, reduction of work-in-process inventory, reduction portant studies that have addressed the integrated problem of the CF
of setup and production times and costs, increase in flexibility, and and cellular layout are presented below. Kia et al. (2012) used the si-
better production control. mulated annealing (SA) algorithm for solving the integrated problem of
Designing a CMS includes four main steps: (1) the cell formation, CF and inter- and intra-cell layout. Mahdavi, Teymourian, Baher, and
which groups parts and machines into part families and machine cells, Kayvanfar (2013) presented a new integrated model considering the CF
and is aimed at the minimization of objective functions like inter- and and the cellular layout decisions simultaneously. Machines are placed
intra-cell movements; (2) the cellular layout, which considers the in a linear arrangement within the cells, and cells are allocated to the

⁎
Corresponding author at: Department of Industrial Engineering, University of Kurdistan, Sanandaj, Iran.
E-mail addresses: [email protected] (V. Rahimi), [email protected] (J. Arkat), [email protected] (H. Farughi).

https://doi.org/10.1016/j.cie.2020.106439
Received 11 February 2019; Received in revised form 16 February 2020; Accepted 23 March 2020
Available online 30 March 2020
0360-8352/ © 2020 Elsevier Ltd. All rights reserved.
V. Rahimi, et al. Computers & Industrial Engineering 143 (2020) 106439

predetermined candidate locations. They also consider backtracking In the research conducted in the field of the CMS design, some pa-
and forward movements. Kia, Shirazi, Javadian, and Tavakkoli- pers consider more than two sub-problems as integrated or sequential.
Moghaddam (2013) presented a multi-objective mixed-integer pro- Wu et al. (2007) proposed a model that considers the CF, inter- and
gramming (MIP) model for designing group layout of a CMS with the intra-cell layout, and group scheduling problems simultaneously. Arkat,
variable number of cells in a dynamic environment. Chang, Wu, and Wu Farahani, and Hosseini (2012) proposed two mathematical models for
(2013) presented a two-stage model to integrate the CF, cell layout, and designing the CMS. The first model involves the integration of the CF
intracellular machine sequencing by considering alternative processing and group layout problems. The second model integrates the first model
routes, and production volumes. Moreover, due to the NP-hardness of with group scheduling in order to improve system efficiency. They
the problem, they proposed a Tabu search (TS) algorithm based on the developed a GA for solving large-sized problems. Fahmy (2015) con-
generalized similarity coefficient. Kia, Khaksar-Haghani, Javadian, and sidered the CF, scheduling, and layout problems, and developed a MILP
Tavakkoli-Moghaddam (2014) presented a MIP model for designing a model. He considered inter- and intra-cell transportation times and
multi-floor layout in a dynamic CMS. Mohammadi and Forghani (2016) sequence-dependent setup times, and also examined the model con-
presented an integrated bi-objective CF and layout problem considering sidering two objectives of minimizing the makespan and minimizing
a new framework based on the S-shaped layout. The objectives of their the mean flow time. Mehdizadeh and Rahimi (2016) considered a dy-
model are to minimize the total inter- and intra-cell material handling namic CMS in order to solve the CF, inter- and intra-cell layout, and
costs and maximize the total similarity between machines. Due to the operator assignment simultaneously. They presented a three-objective
NP-hardness of the problem, they developed an efficient solution model including the minimization of the inter- and intra-cell move-
method combining the SA algorithm and dynamic programming. ments, machine relocation costs, and operator-related costs and the
Houshyar et al. (2016) presented a linear programming (LP) model for maximization of the consecutive forward flow ratio. Ebrahimi, Kia, and
configuring cells and designing layouts of facilities with unequal areas Komijan (2016) presented an integrated model for designing a CMS,
in a dynamic CMS. Defersha and Hodiya (2017) developed a model for considering the three problems of CF, layout, and scheduling, si-
the integration of the CF and the distributed layout design in order to multaneously. Their model considers several design attributes such as
minimize the weighted sum of material handling and intercellular the due dates, material handling times, operation sequences, processing
movement costs. They also addressed the operation sequence, alter- times and intercellular layouts of facilities with unequal areas, and part
native routes, and intra-cell workload balance in their model. Feng, Xi, schedules. The objective of their model is to minimize the makespan,
Xia, and Pan (2018) presented a mixed-integer linear programming tardiness penalties, and material handling costs. They investigated the
(MILP) model which considers various design elements like unequal concurrent and sequential approaches and demonstrated that the con-
machine dimensions, machine duplication, alternative processing current approach obtains better results than the sequential approach.
routes, lot splitting, and production planning. Moreover, they presented Some recent papers available on the design of CMSs that integrate
two hybrid approaches, one of them combining the genetic algorithm the three problems above in the CMS design, along with the design
(GA) and linear programming and the other one combining the SA al- attributes of their models are summarized in Table 1.
gorithm and linear programming for solving large-sized problems. Because of the dependency between CF, cellular layout, and sche-
Wu, Chu, Wang, and Yue (2007) demonstrated that the results of the duling decisions, these decisions should be considered simultaneously
CF affect cellular scheduling, and it is, therefore, better to consider for better design of the CMS. Given the little attention paid to this in-
these decisions simultaneously. A few papers have considered the CF tegrated problem, a more comprehensive, realistic model is demanded
and scheduling problems as an integrated problem. In this regard, a in the presence of alternative processing routes and machine duplica-
literature review has been presented by Feng, Xia, Da, Xi, and Pan tions. An integrated mathematical model is presented in this paper in
(2019). They presented an integrated CF – cellular scheduling model which decisions including allocation of machines into manufacturing
which considers machine duplication, alternative processing routes, cells, selection of processing routes for parts, specification of operation
reentrant parts, and variable cell sizes. Elmi, Solimanpur, Topaloglu, sequences on machines, and allocation of cells into candidate locations
and Elmi (2011) considered the job-shop cell scheduling problem given are made so that the completion time is minimized. For considering a
the exceptional parts and reentrant parts. They presented an integer more realistic application, the intercellular transportation time is con-
linear programming model to minimize the makespan. Moreover, be- sidered as a function of the distances between cells.
cause of the complexity of the problem, they proposed a SA algorithm Considering the intercellular layout provides a more precise esti-
to solve it. Liu, Wang, Leung, and Li (2016) addressed the CF and mation of the distances and times of the intercellular movements, and
scheduling problems considering resource constraints on machines and causes the scheduling sub-problem to be modeled and solved with more
operators. In their model, multi-functional machines and multi-skilled precise inputs. The design attributes that are considered include the
operators are assumed. The objective of their model is to minimize operation sequences, variable number of cells, reentrant parts, proces-
variable costs of the intercellular movements and operations and fixed sing times, and distance-related intercellular transportation times.
costs of the machines and workers. Due to the NP-hardness of the Given that there is no guarantee of obtaining the global solution, even
problem, a discrete bacteria foraging algorithm was developed by Liu for problems of small sizes, because of the nonlinearity of the model,
and colleagues. Considering multi-functional resources and multi-skill several linearization techniques are proposed to convert the model into
workers, Liu and Wang (2016) modeled the CF and scheduling pro- a MILP model.
blems as a nonlinear integer programming (NLIP) model. They pre- Considering various design features and realistic assumptions, get
sented a hybrid SA algorithm and a heuristic algorithm of priority rules. the problem under study closer to the real-world situation. If it is
Iqbal, Aziz, Jahanzaib, Ahmad, and Hussain (2017) presented a two- possible to solve the model optimally, therefore, it can be assured that
phase approach in order to solve the CF and scheduling problems to the optimal solution for the model does not make much difference with
minimize the makespan and the total energy consumption. Feng, Li, and that for the real-world application. However, a large number of design
Sethi (2018) investigated the scheduling problem in a dynamic CMS, features increases the complexity of the model, and hence decreases the
considering flexible routes and machine sharing. They presented a bi- chances of obtaining the optimal solution. To tackle this difficulty, a
objective MIP model in order to minimize the makespan and the total metaheuristic algorithm, namely the Vibration Damping Optimization
workload. Lin and Ying (2019) considered the no-wait cell scheduling (VDO) algorithm, is used to solve large-sized problem instances.
problem with the sequence-dependent family setup times to minimize
the makespan.

2
V. Rahimi, et al. Computers & Industrial Engineering 143 (2020) 106439

2. Problem description and mathematical model

g

*
*

*
*
*
*

*
*
In this section, we present an integrated mathematical model in
F

*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
order to make the CF, scheduling, and layout decisions in a CMS si-
E

*
*
*
*
*
*
*
*

*
multaneously. For this purpose, a CMS is considered with several ma-
chines for processing several parts. The parts are considered such that it
D

*
*
*

*
*

*
is feasible to process disjunctive operations on the same machine, re-
C

Designing attributes: a operation sequence; b variable cell number; c reentrant parts; d duplicate machines; e alternative process routings; f processing time; g intercellular transportation time.
ferred to as reentrant parts (Arkat, Farahani, & Ahmadizar, 2012), and
to process some part operations on several alternative machines
b

*
(Ebrahimi et al. (2016)). There are several candidate cell locations to
A

*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
which cells are allocated (Bagheri and Bashiri (2014)), and the number
of cells that should be formed is considered as a decision variable (Feng
Operator assignment

et al. (2019)). In the presented model, tasks including the allocation of

machines into manufacturing cells, selection of processing routes for
parts, specification of operation sequences on machines, and allocation
of cells into candidate locations are performed so that the completion
time is minimized as an objective function. The following assumptions
*

are made for the presented model.

scheduling

– For each machine type, there are one or more identical duplications
(Feng, Xi et al. (2018)).
*
*

*
*

*
*
*
*

*
*

– Machines required on processing routes for each part are predefined

(Kia et al. (2012), Defersha and Hodiya (2017)).
*unequal area

– Setup times for operations are included in processing times (Feng, Li

*distributed

et al. (2018)).
Layout

– The intercellular transportation time is considered as a function of

*

*
*

*
*
*

the distance between cells (Feng, Li et al. (2018), Ebrahimi et al.

(2016)).
*machine sharing
Types of problem

– The number of candidate locations of cells and the distances be-

tween them are predefined (Bagheri and Bashiri (2014) and
Mehdizadeh and Rahimi (2016)).
– All parts are assumed to be available for processing from the be-
CF

*
*
*
*
*
*
*
*
*
*
*
*
*
*

ginning (Iqbal et al. (2017)).

– There is no possibility of stopping an operation after it starts on a
Inter–Intra-cell part trips, machine relocation cost, and operator related costs

machine (Iqbal et al. (2017), Liu and Wang (2016)).

– The maximum and minimum numbers of machines in each cell are
Sum of material handling, machine operating and subcontracting costs
Weighted sum of material handling and inter-cellular movement costs

predefined (Kia et al. (2012), Ebrahimi et al. (2016)).

– The maximum and minimum numbers of cells that should be formed
are predefined (Feng et al. (2019)).
Makespan, tardiness penalties, and material handling costs

In the following, the notations applied in the model are introduced.

Indices, sets, and their relative upper bounds

M Number of machines
The design attributes in research on integrated CMS design problems.

P Number of parts
MSm Number of duplicate machines of type m
Makespan-Energy Consumption

Kp Number of operations of part p

G Number of candidate locations of a cell
Makespan-Total workload

M = {1, 2, , M } Set of machine types

Tardiness penalty cost

Tardiness penalty cost

P = {1, 2, , P } Set of parts

Objective function

MSm = {1, 2, , MSm} Set of duplications of machine type m

Mean flow time
Multi-objective

C = {1, 2, , Cmax } Set of cells

Operation sequence of part p
Total costs

Kp = {1, 2, , Kp}
Flow time

Makespan
Flowtime

Flowtime

Flowtime

Mkp Set of alterative machine types for the k th operation of

part p
G = {1, 2, , G} Set of candidate locations
m Index for machine types (m M )
Tang, Yan, Wang, and Zeng (2014)

p , p' Indices for parts ( p, p' P )

Mehdizadeh and Rahimi (2016)

Indices for duplications of machine type m

Wang, Tang, and Yung (2010)

'
Halat and Bashirzadeh (2015)

j, j
Defersha and Hodiya (2017)

Bagheri and Bashiri (2014)

( j , j' MSm )
'
c, c Indices for cells (c, c ' C)
Ebrahimi et al. (2016)
Feng, Xi et al. (2018)
Feng, Li et al. (2018)

k, k ' Indices for operations of part p (k, k ' Kp )

Arkat et al. (2012)
Iqbal et al. (2017)

Feng et al. (2019)

Wu et al. (2007)
Kia et al. (2012)

g, g ' Indices for cell locations g, g ' G)

Fahmy (2015)
This study
Research
Table 1

3
V. Rahimi, et al. Computers & Industrial Engineering 143 (2020) 106439

Parameters Zkpk'p' mj + Z k'p' kpmj

= (Xkpmjc · X k'p' mjc ) p , p' , k , k ', j, c, m (Mkp M k'p'),
Cmin Minimum number of cells that should be formed c C
Cmax Maximum number of cells that should be formed p p' , k k' (13)
BL Minimum number of machines in each cell
BU Maximum number of machines in each cell
L A large positive number
Fkp F k'p' + L . (1 Z k'p' kpmj ) Tkpm p, p' , k, k ', j, c
Tkpm Processing time of operation k of part p on machine typem
,m (Mkp M k'p'), p p' , k k'
TEp Intercellular transportation time for part p per unit of distance
Dgg' Distance between candidate locations g and g ' (14)
Ymjc , Xkpmjc , Zkpk'p' mj, Wcg , YYc {0, 1} (15)
Decision variables
The objective function (1) minimizes the total completion time of
parts. Constraint (2) shows that each machine should be assigned
Fkp Completion time of the k th operation of part p maximally into one cell. Constraint (3) ensures that each operation of a
Xkpmjc A binary variable that takes value 1 if the k th operation of part p is part is processed on one machine in a specific cell. Constraint (4)
processed on the j th duplication of machine type m in cell c , and takes guarantees that operations assigned to a specific cell are processed on
value 0 otherwise machines assigned to that cell. The number of machines in each cell is
A binary variable that takes value 1 if the j th duplication of machine type
Ymjc
set by Constraint (5). Constraint (6) shows that cells are formed re-
m is allocated into cell c , and takes value 0 otherwise
YYc A binary variable that takes value 1 if cell c is formed, and takes value 0
spectively according to the numbers; i.e., first cell 1 is formed, cell 2 is
otherwise formed next, and the following cells are formed respectively if needed.
Wcg A binary variable that takes value 1 if candidate location g is assigned to This constraint has also been created in order to prevent the generation
cell c , and takes value 0 otherwise of multiple identical solutions. The lower bound of the number of
Zkpk'p' mj A binary variable that takes value 1 if the k th operation of part p is
formed cells is applied by Constraint (7). Constraint (8) shows that each
processed before the k ' th operation of part p' on the j th duplication of formed cell should be assigned to one candidate location. Constraint (9)
machine type m , and takes value 0 otherwise
states that each candidate location can be considered only for one cell.
Eq. (10) calculates the transportation time between the k th and
Objective function and constraints (k + 1) th operations of part p . In this relation, the summation operator
after TEp calculates the intercellular distance between the machines
min FKp, p that perform operations k and (k + 1) on part p . If these two machines
(1)
are in the same cell, the max operator will return the value of zero for
p P

s.t. the intercellular distance. Through the multiplication of this quantity

by TEp , the total intercellular transportation time for part p is achieved.
Ymjc 1 m, j Constraint (11) guarantees that the completion time of the first op-
c C (2)
eration of part p is as large as its processing time. Constraint (12) shows
Xkpmjc = 1 p, k the precedence relationships among the operations of each part. Con-
c C m Mkp j MSm (3) straint (13) determines the precedence relation between the operations
of two different parts or two different operations of the same part on a
Xkpmjc Ymjc m, c, p, k , j (4) machine. This means that if both the k th operation of part p and the k ' th
operation of part p' are processed on the j th duplication of machine
BL . YYc Ymjc BU . YYc c
type m , one and only one of the variables Zkpk'p' mj and Z k'p' kpmj should be
m M j MSm (5)
one. Alternatively, if at least one of the two operations is not performed
YYc YYc + 1 c, c Cmax (6) on this machine, both variables Zkpk'p' mj and Z k'p' kpmj will be zero. Con-
straint (14) guarantees that at most one part is processed on each ma-
YYc Cmin chine at a time. Constraint (15) shows the range of the decision vari-
(7)
c C
ables.
Wcg = YYc c
g G (8) 2.1. Linearization

Wcg 1 g The presented mathematical model is not linear; the nonlinearity of

(9)
c C
the model is due to Constraints (10) and (13). To linearize these rela-
tp, k, k + 1 tions, the following techniques are used:
The nonlinear term max(.,0) in Constraint (10) can be substituted
with a new positive variable Ekpcgc'g ' . The following three constraints
= TEp Dg, g 'max X(k + 1) pmjc
c C c' C g G g ' G m Mk + 1, p j MSm
should be added to the model to apply this substitution:

Ekpcgc'g' Wcg Xk + 1, pmjc + W c 'g ' Xkpmjc ' 1

Wcg + Xkpmjc' W c'g ' 1, 0 p, k, k Kp m Mk + 1, p j MSm m Mk, p j MSm
m Mk , p j MSm (10) p, k, c, c ', g , g ' , k k' (16)
F1p T1pm. X1pmjc p Ekpcgc'g' Xk + 1, pmjc · Wcg p , k , c , c ', g , g ' , k k'
c C m M1p j MSm (11) m Mk + 1, p j MSm (17)
Fk + 1, p Fkp + (Tk + 1, pm·Xk + 1, pmjc ) + tp, k, k + 1
c C m Mk + 1, p j MSm
Ekpcgc'g' Xkpmjc' ·W c 'g ' p , k, c, c ', g , g ', k k'
m Mk, p j MSm (18)
p, k , k Kp (12)
With a simple analysis, it can be seen that the max term in

4
V. Rahimi, et al. Computers & Industrial Engineering 143 (2020) 106439

Constraint (10) only accepts binary values. According to Constraints (3) relationship with G (the number of candidate locations) and Kp (the
and (4), the values of the terms m Mk + 1, p
X
j MSm k + 1, pmjc
and number of operations of part p ). Also, the number of constraints has a
X ' are binary, and the products of these terms quadratic relationship with G and Cmax (the maximum number of cells).
m Mk, p j MSm kpmjc
multiplied by the binary variables Wcg and W c 'g ' are, therefore, also These two tables illustrate the rapid increase in the number of decision
binary variables. As a result, the term inside the max operator takes one variables and constraints with increasing parameter values.
of the values −1, 0, and +1, which means that the output value of the For validation of the presented model, a numerical example is
max term makes up a binary value. Constraint (16) ensures that if the presented. The example has been solved using the GAMS software on a
two summation terms (i.e. X · Wcg and PC with an Intel Core i5, 1.6 GHz processor and 6 GB of RAM. The
m Mk + 1, p j MSm k + 1, pmjc
example includes seven parts and six machine types, and the lower and
' · W ' ' ) take value 1, the new variable (E
m Mk, p
X
j MSm kpmjc cg kpcgc'g ' ) upper bounds for the number of cells are 2 and 3, respectively (i.e.,
also takes value 1. Constraints (17) and (18) guarantee that if at least P = 7, M = 6, Cmin = 2 and Cmax = 3). Machine type 5 has two
one of the summation terms takes value 0, the value of the new variable
duplications (i.e. MS5 = 2 ), and the other machine types have only one
is also zero.
duplication. It has also been assumed that there are three candidate
Moreover, in order to linearize the product of the two binary vari-
locations for cells. Information on this example is shown in Tables 4 and
ables in the max term, we introduce the following new variable:
5. Also, BL = 2, BU = 5.
XWkpmjcg = Xkpmjc · Wcg p, k, m, j, c, g (19) Table 4 shows information concerning the operation sequences of
parts, processing times on alternative machines, and intercellular
By replacing the above equation, we add the following auxiliary transportation times of parts per unit of distance. For example, part 1
constraints to the model: requires five operations. The first, second, and third operations are
2XWkpmjcg Xkpmjc + Wcg p , k, m, j, c, g (20) processed on machines 1, 4, and 5 in processing times of 8, 12, and 3,
respectively. The fourth and fifth operations have alternative machines
XWkpmjcg Xkpmjc + Wcg 1 p, k, m, j, c, g (21) for processing. The fourth operation can be processed on machine 3 or 5
Constraint (13) is substituted with the following constraints: in a processing time of 7 or 14. The distances between the candidate
locations for cells are shown in Table 5.
Zkpk'p' mj + Z k'p' kpmj (Xkpmjc + X k'p' mjc ) 1 p , p' , k , k ', j , c The results concerning the optimal solution of the sample problem
c C using the GAMS software are presented in Tables 6 and 7.
,m (Mkp M k'p'), p p' , k k' (22) The information in Table 6 shows that two cells have been formed,
and cells 1 and 2 are allocated to candidate locations 2 and 1, respec-
Zkpk'p' mj + Z k'p' kpmj Xkpmjc p, p' , k, k ', j, c, m (Mkp M k'p'), p tively. Machines 2, 3, 5, and 6 are assigned into cell 1, and machines 1
c C and 4 and the second duplication of machine 5 are assigned into cell 2.
p' , k k' (23) Many parts are processed in only one cell without intercellular move-
ments, while some other parts are processed in two cells, in which case
Zkpk'p' mj + Z k'p' kpmj X k'p' mjc p , p ' , k , k ', j , c the intercellular transportation times are obtained according to the
c C locations of cells. For example, the second operation of part 1 is pro-
,m (Mkp M k'p'), p p' , k k' (24) cessed in cell 2 on machine 4, while the third operation is processed in
cell 1 on machine 5. In this case, intercellular transportation of part 1
Finally, the linearized model can be presented as follows: between cells 1 and 2 is needed. The information in Table 7 specifies
the starting and completion times of the parts operations. For example,
min FKp, p
p P
the first operation of part 2 is started on machine 5 in cell 1 at time 0
and is completed at time 4, according to the time required for proces-
subject to: sing the operation.
The sets of constraints (2)–(9), (11)–(12) and (14) and the sets of In the following, we perform a sensitivity analysis on MSm , i.e., the
auxiliary constraints (16)–(24). number of duplicate machines of type m . It has been assumed that
Constraint (10) is replaced by: machine type 5 has two duplications (i.e. MS5 = 2 ), and the other
tp, k, k + 1 = TEp· Dgg ' · Ekpcgc 'g ' p, k , k Kp machine types have only one duplication. If one intends to add a copy
c C c' C g G g' G (25) to one of the machine types, optimal values of the objective function
can be obtained for different scenarios. By adding a new copy to ma-
Constraint (13) is replaced by Constraints (22)–(24), and Constraint chine types 1 to 6, the optimal values of the objective function will be
(15) is replaced by: 165, 166, 168, 164, 172, and 158, respectively. Given these optimal
Ymjc , Xkpmjc , Zkpk'p' mj, Wcg , YYc , Ekpcgc'g', XWkpmjcg {0, 1} values, the best decision to make is to buy a new copy for machine type
(26)
6.
In order to determine the complexity of the proposed MILP, Tables 2 On the other hand, if there is only one copy for each machine type
and 3 reports the number of variables and constraints, respectively. As (that is, the extra copy of machine 5 is omitted), then the objective
can be seen, the number of decision variables has a quadratic function value will be 175, which is worse than the current optimal

Table 2
The number of decision variables in the linear model.
Variable Count Variable Count

Fkp p P Kp Wcg Cmax · G

Xkpmjc p P K p· m M MSm· Cmax Zkpk'p' mj K p 2· MSm
p P m M
Ymjc m M MSm·Cmax Ekpcgc'g ' Kp·Cmax 2 · G 2
p P
YYc Cmax XWkpmjcg p P K p· m M MSm· Cmax ·G
Sum = p P Kp + p P K p 2· m M MSm + Cmax ·(1 + m M MSm + G ) + p P Kp·Cmax · ( m M MSm + m M MSm·G + Cmax ·G 2)

5
V. Rahimi, et al. Computers & Industrial Engineering 143 (2020) 106439

Table 3
The number of constraints in the linear model.
Constraint Count Constraint Count

(2) m M MSm (16) (Kp 1)·Cmax 2 ·G 2

p P
(3) p P Kp (17) (Kp 1)·Cmax 2 ·G 2
p P
(4) p P K p· m M MSm· Cmax (18) (Kp 1)·Cmax 2 ·G 2
p P
(5) Cmax (19) p P K p· m M MSm· Cmax ·G
(6) Cmax 1 (20) p P K p· m M MSm· Cmax ·G
(7) 1 (21) p P K p· m M MSm· Cmax ·G
(8) Cmax (22) p P p' P k Kp k' Kp m Mkp M ' ' MSm·Cmax
kp
p p' k k'
(9) G (23) p P p' P k Kp k' Kp m Mkp M ' ' MSm·Cmax
kp
p p' k k'
(11) P (24) p P p' P k Kp k' Kp m Mkp M ' ' MSm·Cmax
kp
p p' k k'
(12) p P (Kp 1) (25) p P (Kp 1)
(14) p P p' P k Kp k' Kp m Mkp M ' ' MSm·Cmax
kp
p p' k k'

Sum = m M MSm + p P Kp + p P K p· m M MSm·Cmax ·(1 + 3G ) + 3Cmax + G + P + 2 p P (Kp 1) + 4 p P

p P
k Kp
k Kp
m Mkp M k p MSm·Cmax
p p k k

+3 p P (Kp 1)· Cmax 2 ·G 2 + (Number of constraints in Costraintset (26))

Table 4 Table 7
Information for the first sample problem. Results concerning the operations start and finish times.
Part No. Machine type m (Tkpm ) TEp Part No. Starting time and Completion time of part operations Fkp

k=1 k=2 k=3 k=4 k=5 k=1 k=2 k=3 k=4 k=5

1 1(8) 4(12) 5(3) 3(7), 5(14) 2(5), 4(15) 6 1 5,13 13,25 31,34 34,41 41,46
2 3(6), 5(4) 4(12), 6(10) 5(5) 9 2 0,4 4,14 14,19
3 3(8) 2(4) 6(7) 3(5) 12 3 0,8 8,12 14,21 21,26
4 2(2) 3(4) 6(14) 5 4 0,2 8,12 21,35
5 1(2), 2(3) 4(5), 6(6) 11 5 3,5 5,10
6 1(3) 3(5), 5(3) 8 6 0,3 3,6
7 4(3) 5(5) 1(7) 5(6) 4(4), 6(7) 10 7 0,3 6,11 13,20 20,26 26,30

solution value (172). In this case, again, assuming that only a new copy
Table 5 (of one of the machine types) can be purchased, it is possible to cal-
Distances between the candidate locations for cells. culate the optimal objective function values for different scenarios to
From To
determine the best type of machine to be duplicated. By adding another
copy to each of the machine types 1–6, the optimal values of the target
1 2 3 function will be 173, 175, 175, 167, 172 and 158, respectively.
Therefore, if only one machine were to be added to the set, it would be
1 0 1 1.5
2 1 0 2.5
better to have a new machine of type 6.
3 1.5 2.5 0

3. The VDO algorithm

Table 6 Given that the proposed problem is in the NP-hard class in terms of
Results concerning the CF and the selection of alternative machines for the the computational complexity (Feng et al. (2019), a VDO algorithm is
sample problem. presented for solving the problem. The concept of VDO algorithms was
Cell No. (Candidate Location) Machine Type No. Part No. first introduced by Mehdizadeh and Tavakkoli-Moghaddam (2008),
resulting from the process of mechanical vibration damping. This al-
2 3 4 1 5 6 7 gorithm has been used in different problems such as the location-allo-
cation (Mehdizadeh, Tavarroth, & Hajipour, 2011, Mousavi, Niaki,
1(2) 2 2 1 5
3 1,4 2 4 Mehdizadeh, & Tavarroth, 2013, and Hajipour, Fattahi, Tavana, & Di
5 1,3 3 Caprio, 2016), production planning (Aliabadi, Jolai, Mehdizadeh, &
6 2 3 3 Jenabi, 2011), inventory control (Fattahi, Hajipour, & Nobari, 2015),
2(1) 1 1 1 1 3 job shop scheduling problem (Yazdani, Zandieh, Tavakkoli-
4 2 2 1,5 Moghaddam, & Jolai, 2015), lot-sizing problem (Hajipour, Kheirkhah,
5* 2 2,4 Tavana, & Absi, 2015), and CMS design (Mehdizadeh & Rahimi, 2016;
Mehdizadeh, Niaki, & Rahimi, 2016). There is a suitable, beneficial
* Represents the second copy of machine type.
relationship between the behavior of an oscillator system in the
damping state and optimization (finding the minimum value of a given

6
V. Rahimi, et al. Computers & Industrial Engineering 143 (2020) 106439

function with many parameters). When the power source of the oscil-
lator is disconnected, the vibration amplitude is gradually decreased,
and it is finally stopped from vibration. The VDO algorithm, inspired by
the nature of objects with elasticity, generates a solution in each
iteration and uses probability rules in the neighborhood searches. In
summary, four main steps should be taken: the problem coding, the Fig. 2. Representation of matrix Ma-Ce.
definition of the fitness function, the definition of the neighborhood
generation mechanism, and the definition of a plan for vibration
damping. The vibration amplitude in the damping plan should be re-
duced so that it is a descending function by time. It is initially possible Fig. 3. Representation of matrix Pa-Seq.
to generate more solutions in high vibration amplitude, but the prob-
ability of generating solutions is reduced as vibration amplitude de-
words, A2i specifies the type of machine numbered in the first row and
creases. According to the displacement relation in the vibration theory,
column i . For this purpose, in the second row, we first assign numbers
one of the damping plans can be A = A0 e . t /2 , where A is the vibration
from 1 to M ; then, for each machine type, we repeat the index of the
damping, A0 is the initial vibration damping, is the damping coeffi-
machine (m ) up to the number of duplications of that machine
cient, t is the iteration number of the damping loop, and is a para-
(MSm 1). The third row specifies the cell assigned to each machine.
meter concerning the reduction rate of the vibration amplitude. The
Correspondingly to this new numbering for machines, the set of alter-
smaller the value considered for , the higher the reduction rate of
native machines for the processing operations of parts needs to be
amplitude. Therefore, the highest accuracy should be considered in the
corrected. For example, suppose that the second operation of part 3 has
selection of the value of for the achievement of the desired quality in
two alternative machines for processing, and set M23 = {2, 3} contains
solving the problem as well as an appropriate execution time for the
the alternative machines for processing the second operation of part 3.
algorithm.
Assume that machine type 2 has two duplications, and the duplications
Repetition of the inner loop follows from the forced vibration. A
of machine 2 are specified with numbers 2 and 5 in the hypothetical
large number of inner loop repetitions make it possible to do a large
numbering, and those of machine type 3 are specified with numbers 3,
number of searches in a specific amplitude. The number of inner loop
6, and 7. According to the hypothetical numbers, the set of alternative
iterations is directly related to the execution time of the algorithm. The
machines for processing the second operation of part 3 is corrected as
stopping criterion is an essential issue in the VDO algorithm. The
M23 = {2, 3, 5, 6, 7} .
amount of vibration amplitude is one of the stopping criteria, and other
The second ingredient of the representation concerns the processing
potential criteria include reaching a specific number of damping loop
sequence of parts and is referred to as Pa-Seq. The numbers of rows and
iterations or a difference in objective function values in two successive
columns in this matrix are one and the total number of part operations
repetitions of the outer loop less than a prespecified threshold. Every
(O ), respectively. Fig. 3 represents matrix Pa-Seq. Si is interpreted ac-
metaheuristic algorithm needs a move, which means the way it can go
cording to its position in the matrix. For this purpose, all the operations
from one solution to a neighborhood. For an explanation of the pro-
of each part are named with the same symbol, i.e., the part number, and
posed algorithm for solving the proposed model, its implementation
interpreted according to its position in the sequence. For example,
steps are discussed in more detail below.
suppose that there are three parts, and the numbers of their operations
are 2, 3, and 2, respectively. Assume that Pa-Seq = [1 2 2 1 2 3 3]. In
3.1. Solution representation this matrix, 2 represents operations 1, 2, and 3 for part 2 in positions 2,
3, and 5, respectively.
One of the essential steps in the application and implementation of The third ingredient concerns the selection of machines for pro-
metaheuristic algorithms is the design of the solution representation, cessing the operations of parts and is referred to as Ma-Pa. The numbers
which should contain the values related to the decision variables. of rows and columns are one and the number of parts (P ), respectively,
According to the problem under review, a feasible solution should and any element of the matrix is, in turn, a matrix with one row and
guarantee the following conditions: 1. Machines should be assigned to columns as many as the number of operations of parts corresponding to
cells so that the constraints concerning the cell capacity and the number that element. Each element of this sub-matrix specifies the machine that
of cells are met. 2. Operations should be assigned to machines so that processes the operation corresponding to that element (machines are
the constraints concerning the assignment of operations to machines selected from among alternative machines from the corrected set Mkp ).
are met (The assigned machine should be capable of processing the Fig. 4 shows the representation of matrix Ma-Pa. For example, X1k1 re-
operation). 3. Operations should be processed on machines in a se- presents the k1th operation of part 1.
quence so that the constraints concerning the scheduling of parts are The fourth ingredient concerns the assignment of cells into candi-
met. 4. Cells should be allocated to candidate locations so that the date locations and is referred to as Ce-Lo. The number of rows is one,
constraints concerning the allocation of cells into candidate locations and the number of columns is G (the number of candidate locations).
are met. Fig. 5 shows the representation of matrix Ce-Lo. The allocation of cells
Solution representation is so that each solution consists of four in- into locations is such that each element specifies the location of the cell
gredients. Fig. 1 shows the solution representation. corresponding to that element. For example, suppose that Ce-Lo = [3 2
The first ingredient concerns the cells assigned to machines and is 1 4 5]. The number 3 at the first position indicates the assignment of
referred to as Ma-Ce. The numbers of rows and columns in matrix Ma- cell 1 to candidate location 3, and the number 2 at position 2 indicates
Ce are three and the total number of machines (N ), respectively. Fig. 2 the assignment of cell 2 into candidate location 2.
shows matrix Ma-Ce. The first row of the matrix is numbered from one
to the number of machines, which presents a new hypothetical num- 3.2. Generation of the initial solution
bering for machines and their duplications. The second row specifies
the type of machine numbered in the first row of the matrix; in other The VDO algorithm generates a solution in each iteration based on
its previous solution. Therefore, there needs to be an initial solution. In
order to generate an initial solution, we present a hierarchical approach
that completes constructive matrices. We describe this in more detail
Fig. 1. Solution representation. below.

7
V. Rahimi, et al. Computers & Industrial Engineering 143 (2020) 106439

Fig. 4. Representation of matrix Ma-Pa.

insertion, and revision operators is randomly applied. For the third

ingredient, one of the operations having alternative machines is ran-
Fig. 5. Representation of matrix Ce-Lo. domly selected, and the current machine is replaced by one of its al-
ternatives.
In the first stage, matrix Ma-Ce is completed concerning the corre-
sponding constraints on cell size and cell capacity. For this purpose, a 3.5. Fitness function
random integer (C ) is selected for the specification of the number of
cells from the interval [Cmin Cmax ]. Once the number of cells C is speci- A fitness function measures the quality of each generated solution.
fied, each machine is assigned to one of the cells 1 to C randomly. Given The fitness function is the same as the objective function in its pure
that the machines are randomly assigned into cells, the cell capacity form, but it is noteworthy that the generated solution may not be fea-
may not be met. For this reason, a heuristic is used to correct infeasible sible, in which case appropriate strategies should be applied. In the
solutions. We describe this in more detail below. problem under review, if a solution is infeasible, it will be repaired
In the second stage, matrix Pa-Seq is completed. For this purpose, using the repair strategy. Therefore, we assume that the fitness function
we copy the number corresponding to each part to the number of part is the same as the objective function, i.e., the total completion time of
operations for that part and put the numbers together in a matrix. Then, parts.
we sort the matrix with a random permutation.
In the third stage, matrix Ma-Pa is completed. This matrix con- 3.6. Reduction mechanism of the vibration amplitude
stitutes sub-matrices. Each sub-matrix corresponds to one part, in which
one of the alternative machines is randomly selected for each operation. The reduction mechanism of the amplitude is so that after each
To this aim, for each sub-matrix p and its k th element, we randomly iteration of the main loop, the vibration amplitude is reduced using
select a number from the modified set Mkp , and insert it in the corre-
( ). In this relation, the acceptance probability of a
t
Equation A = A0 e 2
sponding element. In the fourth stage, matrix Ce-Lo is completed. For neighbor solution decreases by increasing the number of iterations.
this purpose, we generate a random permutation of numbers 1 to G . The
allocation of cells into candidate locations is so that each element 3.7. Mechanism of accepting new solutions
specifies the location of the cell corresponding to that element.
When a solution is compared with its neighbor solution, if the new
3.3. Heuristic solution repair solution is better than the current solution, the former will replace the
latter; otherwise, the probability of accepting the neighbor solution is
As mentioned in the previous section, infeasible solutions may be 2
p = 1 e A /2 .
2

generated because of the infeasibility of the first ingredient of the so- Fig. 6 shows the pseudo-code of the VDO algorithm.
lution. That may also occur as neighborhoods are being generated. For
this reason, the structure of a heuristic method is described below for 4. Computational results
the correction of infeasible solutions (C is the largest number in the
third row of matrix Ma-Ce, which represents the number of cells). In this section, for demonstration of the efficiency of the presented
In the first stage, as long as any machine has not been assigned to solution method, 20 sample problems of different sizes are initially
cell C , set C = C 1. generated, and the computational results obtained with the proposed
In the second stage, if there is no machine allocated to cell c , replace VDO algorithm are compared with the GA, Ant Lion Optimizer (ALO)
all machines in cell C with those in cell c , set C = C 1, and proceed as algorithm (Mirjalili, 2015) and GAMS software. The proposed algo-
in the first stage. rithms have been coded in MATLAB programming environment. Since
In the third stage, if the number of cells C is smaller than Cmin , select the output of a metaheuristic algorithm is strongly dependent on its
one machine randomly, and assign it to a new cell (C = C + 1) until the input values, we determine the appropriate values of the input para-
number of cells reaches Cmin . meters of the proposed algorithms using the Taguchi method. This
In the fourth stage, if cell c has more than BU machines, assign one method, which is a well-known method for parameter tuning of meta-
machine in cell c to another cell randomly (a cell with fewer than BU heuristic algorithms, proposes the appropriate value for each parameter
machines) until the number of machines in cell c reaches BU . by performing several specific experiments instead of verifying all
In the fifth stage, if cell c has fewer than BL machines, until the feasible experiments. A Taguchi design uses orthogonal arrays, which
number of machines in cell c reaches BL , select one machine in another estimate the effects of factors on the response mean and variation. An
cell (a cell with more than BL machines), and assign it to cell c . orthogonal array means that the design is balanced, so that factor levels
are weighted equally. For this reason, each factor can be assessed in-
3.4. Neighborhood generation strategies dependently of all the others, so one factor does not affect the estima-
tion of another. This can reduce the time and cost associated with the
In order to move in the solution space and extract and explore better experiment when fractionated designs are used. In a Taguchi design, a
solutions, we need to design suitable strategies. By making small measure of robustness is used for the identification of control factors
changes in the current solution, we can achieve neighbor solutions. The that reduce variability in a product or process by minimizing the effects
performance of the strategy and its flexibility degree depend on the of uncontrollable factors (noise factors). The signal-to-noise (SN) ratio
solution structure. The matrix structure facilitates the implementation measures how the response varies concerning the nominal or target
and provides high flexibility in designing various strategies. The pro- value under different noise conditions. This method can choose from
posed strategy is randomly applied to one of the four ingredients of the among different SN ratios, depending on the purpose of the experiment.
solution. For the first ingredient, the operator is applied through the The Minitab software offers four SN ratios: (1) smaller is better, (2 and
replacement of two random machines belonging to different cells or 3) nominal is best (in two types), and (4) larger is better. Since the
change of the number of cells to a random number in an acceptable objective of the problem involves minimization, we use smaller is
range. For the second and the fourth ingredient, one of the swap, better. The SN ratio is calculated for each factor level combination. The

8
V. Rahimi, et al. Computers & Industrial Engineering 143 (2020) 106439

Fig. 6. The pseudo-code of the VDO algorithm.

values of the response variables are given by a comparison of the values rate, 0.3 for mutation rate, and 250 for the maximum number of
of the criterion obtained from the combination of the objective function iterations of the algorithm.
and computational time. In this research, 20 sample problems of different sizes are generated
In order to specify one of the three levels of each input parameter in for solving the proposed problem. The size of each problem depends on
the proposed algorithms, Taguchi analysis is performed in the Minitab the following factors:
software, and comparison is made based on two criteria, namely SN
ratio and mean. The graphs concerning the parameters of the VDO al- o number of machines (M )
gorithm based on the SN ratio relative to mean are shown in Figs. 7 and o number of machine duplications (NM )
8. Given that higher values of SN ratio are desired, the results obtained o number of parts (P )
for tuning the parameters of the VDO algorithm include initial vibration o total number of operations of parts (NOP )
amplitude: 10, number of forced loop iterations as the counter of o maximum number of cells (Cmax )
maximum number of neighborhood searches: 5, standard deviation as o minimum number of cells (Cmin )
the Rayleigh distribution parameter: 2, damping coefficient: 0.1, and o maximum number of machines in each cell (BU )
amplitude reduction counter as the maximum number of iterations of o minimum number of machines in each cell (BL )
the algorithm: 250. The results obtained for the tuning of the ALO al- o number of candidate locations (G ).
gorithm parameters include 20 for population size, 0.7 for crossover

Fig. 7. Comparison of the levels of the VDO algorithm based on SN ratio.

9
V. Rahimi, et al. Computers & Industrial Engineering 143 (2020) 106439

Fig. 8. Comparison of the levels of the VDO algorithm based on mean.

Table 8 not been able to find any feasible solution even in 20 h. Also, other
Specifications of the sample problems. parameters such as processing times and intercellular transport times
Problem No. M NM P NOP Cmin Cmax BL BU G
per distance unit specified in Table 9 are generated as uniform random
integers. Also, to determine the distance between candidate positions,
1 4 4 4 10 2 2 2 2 2 one-row and two-row random layouts have been generated, and based
2 4 5 5 12 2 2 2 3 3 on them, the values of these parameters have been determined.
3 5 5 6 17 2 2 2 3 3
4 5 6 6 18 2 3 2 4 3
Table 10 shows the solutions and computational times obtained
5 6 7 7 24 2 3 2 5 4 with the CPLEX solver of the GAMS software, VDO algorithm, ALO
6 8 8 8 29 2 4 2 4 4 algorithm, and a GA with a simple structure. In this table, the best value
7 8 10 10 36 3 4 2 5 4 obtained for each problem is shown in bold font. The point to be noted
8 10 13 12 52 3 4 2 5 5
is that as problem size is increased, the time index gradually increases.
9 15 18 15 70 3 5 2 6 6
10 18 20 20 82 4 7 3 6 8 The maximum run time of GAMS has been considered as 72,000 s. The
11 22 29 25 129 4 8 3 6 9 GAMS software presents optimal solutions to problems 1–7, in such a
12 22 29 30 167 4 8 3 6 9 way that the run times for problems 6 and 7 have risen dramatically.
13 24 31 35 197 4 8 3 6 10 Furthermore, problems 8–13 have failed to obtain optimal solutions
14 26 33 40 228 4 9 3 7 10
15 27 34 45 257 4 9 3 7 11
within 72,000 s, which illustrates the accuracy of the use of meta-
16 27 36 50 289 5 9 4 7 11 heuristic algorithms for solving large-sized problems. Also, problems
17 29 39 55 323 5 9 4 8 11 14–20 have failed to find a feasible solution within 72,000 s. As can be
18 29 41 60 357 5 10 4 8 12 seen from Table 10, the metaheuristic algorithm is capable of obtaining
19 30 42 65 392 5 10 5 9 12
optimal solutions for smaller-sized problems. Moreover, as problem size
20 30 44 70 423 6 11 5 9 12
increases, the metaheuristic algorithms are capable of presenting better
solutions in a shorter time than in GAMS. Besides, these results de-
Table 9 monstrate that the proposed VDO algorithm could find better solutions
Probability distributions of the required information. in shorter run times when compared to the two other metaheuristic
algorithms.
Parameter Value Parameter Value

Tkpm U(2,15) Dgg' U(0.5,2.5)

5. Conclusions and suggestions for future research
TEp U(5,15)

Due to the importance and interdependence of the CF, scheduling,

and layout problems in a CMS, an integrated MIP model was presented
The specifications of the 20 sample problems developed in this re-
in this paper for designing CF, cellular scheduling, and cellular layout
search are shown in Table 8.
simultaneously. The proposed model considers many design attributes,
The values of the parameters needed to generate sample problems
such as machine duplication, alternative machines, processing routes,
are adjusted by drawing on the literature in the field. These problems
reentrant parts, and variable cell size. The presented model has the
are designed to solve a wide range of instances, from small to large. The
capability of assigning machines into cells, selecting processing routes
size of these problems has been determined so that the GAMS software
for parts, determining the sequence of operations for processing on
has been able to obtain the optimal global solution for some of them
machines, and allocating cells into candidate locations, so that total
(small size problems) in a limited time. For another set of problems
completion time of parts, as the objective function, is minimized. Many
(medium size), the software has not been able to achieve the global
studies have sought to model and solve the cellular scheduling problem
optima within 20 h, and hence, the best (non-optimal) solution is re-
assuming that the cell configuration has been designed from the be-
ported. Finally, for the last set of problems (large size), the software has
ginning or, on the other hand, that the intercellular transportation

10
V. Rahimi, et al. Computers & Industrial Engineering 143 (2020) 106439

Table 10
Results and computational times for the sample problems.
Problem No. GAMS VDO ALO GA

Time Objective Function Time Objective Function Time Objective Function Time Objective Function

1 0.589 161 2.053 161 4.539 161 3.52 161

2 1.667 129 2.302 129 5.091 129 4.07 129
3 4.268 178 2.877 178 6.906 178 5.34 178
4 5.228 177 3.128 177 7.571 177 8.34 177
5 14.782 172 6.018 172 10.13 172 11.2 174
6 1017 368 14.38 368 25.59 373 28.5 372
7 6365 283 60.55 292 122.1 293 112 298
8 72,000 619 283.5 570 416.8 587 403 593
9 72,000 983 646.4 935 1209 945 1184 951
10 72,000 1304 1124.2 1152 2316 1193 2287 1190
11 72,000 2668 1691.3 1873 3241 1928 3194 1983
12 72,000 3530 1929.3 2570 3545 2718 3631 2752
13 72,000 3973 2083.8 3324 3913 3521 3856 3489
14 72,000 – 2254.6 3927 4536 4138 4457 4196
15 72,000 – 2545.4 4754 5042 4931 4982 4963
16 72,000 – 2792.3 5728 5474 6057 5424 6078
17 72,000 – 3125.5 6455 6124 6633 6085 6604
18 72,000 – 3405.4 7324 6513 7573 6476 7648
19 72,000 – 3732.2 8084 7241 8480 7164 8388
20 72,000 – 4067.7 9240 7655 9477 7618 9523

times have been considered without regard to the positions of the cells. Validation, Writing - original draft. Jamal Arkat: Supervision,
The positions of the cells on the shop floor affect the distances (and, Conceptualization, Methodology, Writing - review & editing. Hiwa
hence, the travel times of parts) between cells. Therefore, assignment of Farughi: Conceptualization, Writing - review & editing.
a fixed distance or travel time to all intercellular movements leads to an
inaccurate assessment of the objective function, which can, in turn, lead References
to a non-optimal final solution.
Given that there is no guarantee of obtaining a global solution, even Aliabadi, M., Jolai, F., Mehdizadeh, E., & Jenabi, M. (2011). A flow shop production
for problems of small sizes, because of the nonlinearity of the model, planning problem with basic period policy and sequence dependent set up times.
Journal of Industrial and Systems Engineering, 5(1), 1–19.
several linearization techniques have been proposed to convert the Arkat, J., Farahani, M. H., & Hosseini, L. (2012a). Integrating cell formation with cellular
model into a MILP model. Since the problem under review belongs to layout and operations scheduling. The International Journal of Advanced Manufacturing
the NP-hard class, the VDO algorithm was proposed to find near-op- Technology, 61(5–8), 637–647.
Arkat, J., Farahani, M. H., & Ahmadizar, F. (2012b). Multi-objective genetic algorithm for
timal solutions. As the output of a metaheuristic algorithm is strongly cell formation problem considering cellular layout and operations scheduling.
dependent on its input values, we determined the appropriate values of International Journal of Computer Integrated Manufacturing, 25(7), 625–635.
the input parameters of the VDO algorithm using the Taguchi method. Bagheri, M., & Bashiri, M. (2014). A new mathematical model towards the integration of
cell formation with operator assignment and inter-cell layout problems in a dynamic
For validation of the model and measurement of the performance of the
environment. Applied Mathematical Modelling, 38(4), 1237–1254.
presented metaheuristic algorithm, a numerical example was presented. Chang, C. C., Wu, T. H., & Wu, C. W. (2013). An efficient approach to determine cell
In order to verify the computational efficiency of the proposed algo- formation, cell layout and intracellular machine sequence in cellular manufacturing
systems. Computers & Industrial Engineering, 66(2), 438–450.
rithm as compared to GAMS, several sample problems with different
Defersha, F. M., & Hodiya, A. (2017). A mathematical model and a parallel multiple
sizes and settings were implemented. The results proved the efficiency search path simulated annealing for an integrated distributed layout design and
of the proposed VDO algorithm and the ALO algorithm in terms of the machine cell formation. Journal of Manufacturing Systems, 43, 195–212.
values of the objective function and computational time. Ebrahimi, A., Kia, R., & Komijan, A. R. (2016). Solving a mathematical model integrating
unequal-area facilities layout and part scheduling in a cellular manufacturing system
Due to the possibility of machine failure and machine in- by a genetic algorithm. SpringerPlus, 5(1), 1254.
accessibility, an important policy that raises the efficiency of the Elmi, A., Solimanpur, M., Topaloglu, S., & Elmi, A. (2011). A simulated annealing algo-
manufacturing system is to consider reliability issues. Therefore, con- rithm for the job shop cell scheduling problem with intercellular moves and reentrant
parts. Computers & Industrial Engineering, 61(1), 171–178.
sideration of reliability issues in a CMS can provide a functional area of Fahmy, S. A. (2015, March). Mixed integer linear programming model for integrating cell
research. Given the importance of operator assignment in CMSs and its formation, group layout and group scheduling. In 2015 IEEE International
relationship with the CF problem, investigation of a new model con- Conference on Industrial Technology (ICIT) (pp. 2403–2408). IEEE.
Fattahi, P., Hajipour, V., & Nobari, A. (2015). A bi-objective continuous review inventory
sidering the operator assignment problem can be a good topic for control model: Pareto-based meta-heuristic algorithms. Applied Soft Computing, 32,
continuing the present study. Given the importance of production 211–223.
planning in manufacturing systems and its dependence on the CF pro- Feng, H., Xia, T., Da, W., Xi, L., & Pan, E. (2019). Concurrent design of cell formation and
scheduling with consideration of duplicate machines and alternative process rout-
blem, its investigation, along with the problem under review in this
ings. Journal of Intelligent Manufacturing, 30(1), 275–289.
paper, can provide an appropriate research area. Feng, H., Xi, L., Xia, T., & Pan, E. (2018a). Concurrent cell formation and layout design
The sensitivity analysis on the number of identical copies of each based on hybrid approaches. Applied Soft Computing, 66, 346–359.
Feng, Y., Li, G., & Sethi, S. P. (2018b). A three-layer chromosome genetic algorithm for
machine type has shown that by adding identical copies to the set of
multi-cell scheduling with flexible routes and machine sharing. International Journal
machines, the optimal value of the objective function will change. of Production Economics, 196, 269–283.
However, the number of available copies of each machine could be Hajipour, V., Fattahi, P., Tavana, M., & Di Caprio, D. (2016). Multi-objective multi-layer
considered a decision variable and allowed the model to obtain the congested facility location-allocation problem optimization with Pareto-based meta-
heuristics. Applied Mathematical Modelling, 40(7–8), 4948–4969.
optimal number of unique versions for each machine type. Hajipour, V., Kheirkhah, A., Tavana, M., & Absi, N. (2015). Novel Pareto-based meta-
heuristics for solving multi-objective multi-item capacitated lot-sizing problems. The
International Journal of Advanced Manufacturing Technology, 80(1–4), 31–45.
CRediT authorship contribution statement Halat, K., & Bashirzadeh, R. (2015). Concurrent scheduling of manufacturing cells con-
sidering sequence-dependent family setup times and intercellular transportation
Vahid Rahimi: Conceptualization, Methodology, Software, times. The International Journal of Advanced Manufacturing Technology, 77(9–12),

11
V. Rahimi, et al. Computers & Industrial Engineering 143 (2020) 106439

1907–1915. algorithm for solving a new multi-objective dynamic cell formation problem with
Houshyar, A. N., Leman, Z. B., Ariffin, M. K. A. M., Ismail, N., Moghadam, H. P., & workers training. Computers & Industrial Engineering, 101, 35–52.
Iranmanesh, H. (2016). Proposed linear-mathematical model for configuring cell and Mehdizadeh, E., & Rahimi, V. (2016). An integrated mathematical model for solving
designing unequal-area facility layout in dynamic cellular manufacturing system. dynamic cell formation problem considering operator assignment and inter/intra cell
International Journal of Industrial and Systems Engineering, 22(3), 332–357. layouts. Applied Soft Computing, 42, 325–341.
Iqbal, N., Aziz, M. H., Jahanzaib, M., Ahmad, W., & Hussain, S. (2017). Integration of cell Mehdizadeh, E., & Tavakkoli-Moghaddam, R. (2008, September). Vibration damping
formation and job sequencing to minimize energy consumption with minimum make- optimization. In Proceedings of the International Conference of Operations Research
span. Proceedings of the Institution of Mechanical Engineers, Part B: Journal of and Global Business, Germany (pp. 3–5).
Engineering Manufacture, 231(14), 2636–2651. Mehdizadeh, E., Tavarroth, M. R., & Hajipour, V. (2011). A new hybrid algorithm to
Kia, R., Baboli, A., Javadian, N., Tavakkoli-Moghaddam, R., Kazemi, M., & Khorrami, J. optimize stochastic-fuzzy capacitated multi-facility location-allocation problem.
(2012). Solving a group layout design model of a dynamic cellular manufacturing Journal of Optimization in Industrial Engineering, 7, 71–80.
system with alternative process routings, lot splitting and flexible reconfiguration by Mirjalili, S. (2015). The ant lion optimizer. Advances in Engineering Software, 83, 80–98.
simulated annealing. Computers & Operations Research, 39(11), 2642–2658. Mohammadi, M., & Forghani, K. (2016). Designing cellular manufacturing systems con-
Kia, R., Khaksar-Haghani, F., Javadian, N., & Tavakkoli-Moghaddam, R. (2014). Solving a sidering S-shaped layout. Computers & Industrial Engineering, 98, 221–236.
multi-floor layout design model of a dynamic cellular manufacturing system by an Mousavi, S. M., Niaki, S. T. A., Mehdizadeh, E., & Tavarroth, M. R. (2013). The capaci-
efficient genetic algorithm. Journal of Manufacturing Systems, 33(1), 218–232. tated multi-facility location–allocation problem with probabilistic customer location
Kia, R., Shirazi, H., Javadian, N., & Tavakkoli-Moghaddam, R. (2013). A multi-objective and demand: Two hybrid meta-heuristic algorithms. International Journal of Systems
model for designing a group layout of a dynamic cellular manufacturing system. Science, 44(10), 1897–1912.
Journal of Industrial Engineering International, 9(1), 8. Tang, J., Yan, C., Wang, X., & Zeng, C. (2014). Using Lagrangian relaxation decomposi-
Lin, S. W., & Ying, K. C. (2019). Makespan optimization in a no-wait flowline manu- tion with heuristic to integrate the decisions of cell formation and parts scheduling
facturing cell with sequence-dependent family setup times. Computers & Industrial considering intercell moves. IEEE Transactions on Automation Science and Engineering,
Engineering, 128, 1–7. 11(4), 1110–1121.
Liu, C., & Wang, J. (2016). Cell formation and task scheduling considering multi-func- Wang, X., Tang, J., & Yung, K. L. (2010). A scatter search approach with dispatching rules
tional resource and part movement using hybrid simulated annealing. International for a joint decision of cell formation and parts scheduling in batches. International
Journal of Computational Intelligence Systems, 9(4), 765–777. Journal of Production Research, 48(12), 3513–3534.
Liu, C., Wang, J., Leung, J. Y. T., & Li, K. (2016). Solving cell formation and task sche- Wu, X., Chu, C. H., Wang, Y., & Yue, D. (2007). Genetic algorithms for integrating cell
duling in cellular manufacturing system by discrete bacteria foraging algorithm. formation with machine layout and scheduling. Computers & Industrial Engineering,
International Journal of Production Research, 54(3), 923–944. 53(2), 277–289.
Mahdavi, I., Teymourian, E., Baher, N. T., & Kayvanfar, V. (2013). An integrated model Yazdani, M., Zandieh, M., Tavakkoli-Moghaddam, R., & Jolai, F. (2015). Two meta-
for solving cell formation and cell layout problem simultaneously considering new heuristic algorithms for the dual-resource constrained flexible job-shop scheduling
situations. Journal of Manufacturing Systems, 32(4), 655–663. problem. Scientia Iranica. Transaction E Industrial Engineering, 22(3), 1242.
Mehdizadeh, E., Niaki, S. V. D., & Rahimi, V. (2016). A vibration damping optimization

12