To cite this article:
Ignacio Eguia, Jose Carlos Molina, Sebastian Lozano & Jesus Racero (2017), Cell
design and multi‐period machine loading in cellular reconfigurable manufacturing
systems with alternative routing, International Journal of Production Research,
55:10, 2775‐2790
DOI: 10.1080/00207543.2016.1193673
Cell design and multi-period machine loading in cellular
reconfigurable manufacturing systems with alternative routing
Ignacio Eguia, Jose Carlos Molina, Sebastian Lozano & Jesus Racero
Department of Industrial Management, University of Seville, Spain
Abstract
This paper deals with the design and loading of Cellular Reconfigurable
Manufacturing Systems in the presence of alternative routing and multiple time
periods. These systems consist of multiple reconfigurable machining cells, each
of which has Reconfigurable Machine Tools and Computer Numerical Control
machines. Each reconfigurable machine has a library of feasible auxiliary
machine modules for achieving particular operational capabilities, while each
CNC machine has an automatic tool changer and a tool magazine of a limited
capacity. The proposed approach consists of two phases: the machine cell design
phase that involves the grouping of machines into machine cells, and the cell
loading phase that determines the routing mix and the tool and module allocation.
In this paper, the cell design problem is modeled as an Integer Linear
Programming formulation considering the multiple process plans of each part
type as if they were separate part types. Once the manufacturing cells are formed,
a Mixed Integer Linear Programming model is developed for the cell loading
problem considering multi-period demands for the part types and minimizing
transportation and holding costs while keeping the machine and cell utilizations
in each period and the system utilization across periods approximately balanced.
An illustrative problem and experimental results are presented.
Keywords: Cellular manufacture; Reconfigurable manufacturing systems; Mixed
Integer Linear Programming; Cell formation; Machine loading
1. Introduction
Given the current turbulent and uncertain manufacturing environment, some critical
requirements for a manufacturing system are essential to survive. Short lead times, more
variants, low and fluctuating volumes and low prices are some of these general features
of next generation manufacturing systems (Molina et al., 2005). Strategies designed to
meet these requirements lead to different types of manufacturing systems such as
Dedicated Manufacturing Systems (DMS), Cellular Manufacturing Systems (CMS) or
Flexible Manufacturing Systems (FMS). DMS provide profitable and cost-effective
production in a stable market, but these systems are unable to operate effectively in the
present dynamic market scenario. CMS aim at achieving production efficiency when
there are a variety of part types that can be grouped in part families. FMS use expensive
Computer Numerical Control (CNC) machines with fixed hardware and software to
produce a variety of parts, but the implementation of these systems has not been very
successful with abrupt market fluctuations because of the lower throughput, high cost or
complex design. An emerging paradigm in manufacturing environment defines the
Reconfigurable Manufacturing System (RMS) concept and the Reconfigurable Machine
Tools (RMT) technology.
In contrast to conventional CNCs, that are general-purpose machines, RMTs are
designed for a specific, customized range of operation requirements and may be costeffectively converted when the requirements change (Landers et al., 2001). An RMT is
designed with an adjustable and modular structure that enables either machine
scalability or machine convertibility, using some basic and auxiliary machine modules
(Koren, 2010, pp. 211-218). When the auxiliary modules are changed, different
operations can be performed on the new machine configuration. In response to the
market changes, new Modular Reconfigurable Machine tools (MRM) have been
developed (Padayachee and Bright, 2012). In an MRM the modularity and flexibility of
the machines is achieved by adding and removing the modules, selected from
precompiled modules and concatenated by means of a series of standardized mechanical
interfaces, thus permitting a variety of combinations in which modules could be joined
(Majija et al., 2013). RMTs and MRMs are generally used as part of an RMS.
An RMS is “a manufacturing system designed at the outset for rapid changes in
structure as well as in hardware and software components in order to quickly adjust
production capacity and functionality within a part family in response to sudden
changes in market or in regulatory requirements” (Koren et al., 1999). These
manufacturing systems are configured to produce a family of different part types that
share some similarities (Xiaobo et al., 2000). Time reduction for introducing new
products to the market, together with high quality and low cost, is key for enterprise
survival in the current environment. The manufacturing system must be able to yield
different batch sizes from different product types, using the exact capacity and
functionality required in each case.
A CMS is based on the group technology principle of grouping similar parts into
part families. In this type of manufacturing systems, machines are grouped into cells,
where each cell is dedicated to process one or more part-families. There are numerous
papers in the literature dealing with CMS, specially studying methods for cell formation
based on graph theory (e.g. Askin and Chiu, 1990), clustering (e.g. Chandrasekharan
and Rajagopalan, 1987), mathematical programming (e.g. Defersha and Chen, 2006),
metaheuristics (e.g. Ying et al., 2011; Farahani and Hosseini, 2011), neural networks
(e.g. Ateme-Nguema and Dao, 2009; Sengupta et al., 2011), etc. There are also some
review papers on this topic (e.g. Selim, 1998; Ghosh et al., 2014).
A CMS helps in reducing work-in-process, set-up time, manufacturing lead-time
and material handling, and improve productivity (Wemmerlöv and Johnson, 1997).
However, a CMS lacks flexibility and, thus, cannot respond to some requirements such
as dynamic part mix and demand variation. Integration of modular machines within a
CMS can help to reduce the level of performance deterioration, including some degree
of adaptability.
This paper is related to the cell design and loading problem in the presence of
alternative routing and multiple time periods within a cellular manufacturing system
containing RMT and CNC machines. Alternative routing arises when there are multiple
process plans for each part type, giving rise to the generalized group technology (GGT)
concept (Kusiak, 1987). An Integer Linear Programming (ILP) model for cell design
and a new Mixed-Integer Linear Programming (MILP) model for multi-period cell
loading have been developed in that framework, including as basic objectives the
minimization of total intercellular transportation and holding costs and workload
imbalances, and considering production limitations on tools and modules.
Several methods have been proposed for cell design and loading with alternative
routing as part of the GGT literature. Many authors have developed methods for
grouping parts into families or machines into cells but considering only one of the
alternative process plans (Logendran et al. 1994; Sofianopoulou, 1999). This approach
makes only partial use of the flexibility provided by the multiplicity of process plans.
Some studies have imposed machine capacity constraints (Choobineh, 1998; Kang and
Wemmerlöv, 1993), without considering the workload distribution. Some researchers
(Kumar and Shanker, 2000; Swarnkar and Tiwari, 2004) have addressed the loading
problem using a bi-criteria approach (minimizing system unbalance and maximizing the
throughput), but not taking into account alternative routing.
Methods in the literature specifically aimed at cell formation using
reconfigurable machines can be found in Pattanaik et al. (2007) and Pattanaik and
Kumar (2010). In these works a methodology is presented to design machine cells with
modular machines using characteristics of reconfigurable manufacturing. The
methodology is based on the clustering approaches used in group technology, grouping
machines into cells but without dealing with the loading problem.
Xing et al. (2009) developed an artificial neural network to solve the cell
formation problem in a Cellular Reconfigurable Manufacturing Systems (CRMS),
which are defined as a set of reconfigurable manufacturing cells (RMC) with the
following advantages compared with traditional manufacturing cells: machines are
logically, instead of physically, organized in a RMC, the RMC is changeable during a
production plan horizon, and machines can be shared by different RMC. This paper is
focused on the cell formation problem.
Eguia et al. (2013) also centred their studies in CRMS but considering a new
approach to simultaneously solve the cell formation and the scheduling of part families
for an effective working of a CRMS. The approach consists of a MILP model to
represent both problems at the same time with the objective of minimizing production
costs and the development of a tabu search algorithm for solving large instances.
To the best of our knowledge, only one research (Yu et al. 2012) regards to part
grouping and loading in CRMS. These authors considered multiple cells, each of which
has CNC machines with tool limitations, and presented a MILP model to solve both
problems at the same time with the objective of minimizing the maximum workload
assigned to machines. The methodology to be presented in this paper extends the
formulation of Yu et al. (2012) considering: multiple process plans for each part type,
RMT with a library of auxiliary modules, multi-period demands for the part types,
transportation and holding costs as main objective function and balancing workloads as
secondary objective.
This paper is organized as follows. In the next section, the cell design problem
for CRMS with alternative process plans for each part type is described in detail
together with its mathematical formulation and methods from the literature that can be
used to solve the problem. In Section 3, the multiple-period loading problem for CRMS
is presented and formulated. In Section 4, numerical results from a case study are
reported. The last section summarizes and concludes.
2. Reconfigurable manufacturing cells design
A CRMS consists of multiple reconfigurable manufacturing cells (RMC), each of which
has RMT and/or CNC machines, a setup station, and an automatic material handling and
storage system. Each CNC machine within an RMC has an automatic tool changer and a
tool magazine with limited capacity. The automatic tool changer gives flexibility to the
CNC machine so that it can perform various types of operations without requiring a
great effort in switching from one operation to another. Each RMT within an RMC has
a library of basic and auxiliary modules. The basic modules are structural in nature
(such as base, columns, slideways and tables) and auxiliary modules are kinematical or
motion-giving (such as spindles, tool changers, etc). A particular combination of
different basic and auxiliary modules provides a particular set of operational capabilities
to the RMT. Figure 1 shows a schematic description of a CRMS with two different
RMC.
============================= Figure 1 ==========================
The RMC design problem involves the grouping of machines (RMT and CNC
machines) into machine cells using the information on the sequence of operations for
the different process plans of each part type. For conventional manufacturing cell design
problems, two alternatives are considered in the literature: either the alternative process
plans are treated as if they were separate part types; or aggregate part types are built
from the alternative process plans of each part type.
In the first case, the problem transforms itself into a conventional (i.e. without
alternative routing) cell formation problem, except that instead of grouping machines
and part types, what must be grouped are machines and process plans. The objective is
to find clusters of machines and process plans so that the maximum number of
operations of each process plan family can be performed within the cell. Most cell
formation methods from the literature use as input data the information on the sequence
of operations for each process plan, and then generate a binary machine/process plan
incidence matrix. Some of these methods assume that the number of cells to form is
given. Also, some methods have the possibility of imposing a limit on the number of
machines per cell. Most of these methods assume that there is only one machine of each
type.
Alternatively, when a binary machine/process plan incidence matrix is given, the
multiple process plans of each part type can be aggregated in order to form virtual part
types. One way is to form a non-binary machine/virtual part type incidence matrix with
the average use of each machine per each unit part type and then apply a fuzzy
clustering technique.
Different mathematical formulations for the cell formation problem have been
proposed in the literature to solve the problem optimally. Some of these formulations
consider indirect measures such as similarity, bond energy, ranking etc., to obtain a
block diagonal form from the part-machine incidence matrix using a sequential
approach (Kusiak, 1987; Srinivasan et al., 1990). In such approaches, the machine
groups and part families formed are such that the number of exceptional elements and
voids is minimized. But in a manufacturing situation, the costs of voids and exceptional
elements may vary, indicating that the importance of voids and exceptional elements
might be considered explicitly.
In this paper, an ILP model for the simultaneous grouping of machines and
alternative process plans is developed using the alternative process plans as if they were
separate part types. The problem is transforms itself into a standard cell formation
problem (i.e. without alternative routing), except that it is machines and process plans
that must be grouped instead of machines and part types. This formulation is based on
the nonlinear mathematical model proposed by Adil et al. (1993) and the ILP model
proposed by Boctor (1991).
The notation used in the ILP model to solve the simultaneous cell formation
problem with alternative routing is the following:
Indexes and input data:
•
Part types: i=1,…,N
•
Process plans of each part type: r=1,…, PPi (PPi is the number of process plans
of part type i)
•
CNC machines (set NM) and RMT (set RM): k=1,…,M
•
Cells: c=1,…,C (C is the maximum number of cells to be formed)
•
akir: machine/process plan binary incidence matrix (=1 if machine type k is
required for any operation of the r-th process plan of part type i, and 0
otherwise)
•
q: weighting parameter that measures the importance of voids versus exceptional
elements ( 0 ≤ q ≤ 1 )
Decision variables of cell formation:
•
Xkc=1 if machine type k is assigned to cell c
•
Yirc=1 if r-th process plan of part type i is assigned to cell c
•
Ekirc=1 (exceptional element) if r-th process plan of part type i requires a
machine type k outside of the cell c to which that process plan is assigned
•
Hkirc=1 (void) if r-th process plan of part type i does not require a machine type
k inside of the cell c to which that process plan is assigned
The cell formation problem that identify machine groups and process plan
families simultaneously can be formulated as the following ILP model.
[ P1 ]
q⋅∑∑
M inimize
c
r = PPi
∑ ∑
r =1
k
H kirc + ( 1 − q ) ⋅ ∑ ∑
i
c
PPi
∑ ∑ E kirc
k r =1 i
(1)
subject to
∑ Yirc
= 1 ∀ i ,∀ r
(2)
= 1 ∀k
(3)
c
∑ X kc
c
∑ PPi ⋅ X kc −
r = PPi
i
∑
r =1
∑ akir Yirc +
i
r = PPi
∑ ∑ a kir E kirc
r =1
r = PPi
≥0
∀ k ,∀ c
i
r = PPi
∑ PPi ⋅ ( 1 − X kc ) − ∑ ∑ ( 1 − akir )Yirc + ∑ ∑ ( 1 − akir )H kirc ≥ 0
r =1
i
∑ PPi ⋅ ∑ X kc
i
M ⋅
k
≥
r = PPi
∑ ∑ Yirc
r =1
r = PPi
i
k
∀c
∀k ,∀c (5)
i
(6)
i
∑ ∑ Yirc ≥ ∑ X kc
r =1
r =1
i
(4)
∀c
(7)
X kc ,Yirc , Ekirc ,H kirc ∈ {0,1} ∀k = 1,...,M ; ∀i = 1,...,N ; ∀r = 1,...,PPi ; ∀c = 1,...,C
(8)
The objective function (1) minimizes the weighted sum of intracellular voids
and intercellular movements. Constraints (2) ensure that each machine is allocated to a
cell. Similarly, constraints (3) guarantee that each process plan is assigned to a cell.
Constraints (4) indicate that if a machine type k is not assigned to cell c ( X kc = 0 ), the
number of times that machine type k is required to complete parts in the process plans
assigned to cell c, that is, the corresponding number of exceptional elements (
r = PPi
∑ ∑ akir Ekirc ), must be greater than or equal to the number of operations requiring
r =1
i
r = PPi
that machine in all the process plans assigned to cell c (
∑ ∑ akir Yirc ). Similarly,
r =1
i
constraints (5) imply that if a machine type k is assigned to cell c ( X kc = 1 ), the number
of times that machine type k is not required in any of the process plans assigned to cell
r = PPi
c, that is, the corresponding number of voids (
∑ ∑ ( 1 − akir )H kirc ), must be greater
r =1
i
than or equal to the number of process plans assigned to the cell c that do not use that
r = PPi
machine type (
∑ ∑ ( 1 − akir )Yirc ).
r =1
Finally, constraints (6) and (7) are added to
i
guarantee that if any machine type is assigned to a cell c then at least one process plan
must be assigned to this cell, and vice versa. Binary restrictions on the variables are
imposed by constraints (8). The value of C is an upper bound on the number of cells to
be formed.
If the machine/process plan binary incidence matrix is small, the above model
can be optimally solved using appropriate optimization software. But for the efficient
solution of larger problems, heuristics approaches are needed. There are a number of
heuristic techniques to solve the standard cell formation problem efficiently. Some of
the solution methods try to rearrange the binary machine/part incidence matrix (akir) in
order to bring the non-zero elements around the diagonal. There are also clustering
techniques that identify clusters of either parts or machines. A third group of methods
use graph decomposition techniques to find the manufacturing cells. Also, several
multi-step or iterative ad-hoc heuristics have been proposed in the literature. Finally,
other methods to efficiently solve the manufacturing cell formation problem include
metaheuristics: Tabu Search, Simulated Annealing or Genetic Algorithms.
In this paper, in addition to solving the model optimally, and for the sake of
comparison, some existing cell formation heuristics and metaheuristics from the
literature have also been applied, namely ZODIAC (Chandrasekharan and Rajagopalan,
1987), GRAFICS (Srinivasan and Narendran, 1991), MST (Srinivasan, 1994),
Simulated Annealing (Boctor, 1991; Chen et al., 1995), Tabu Search (Sun et al. 1995)
and Self-Organizing Neural Network - SONN (Lozano et al., 1998). MST is a greedy
heuristic which can handle cell size constraints while the other two heuristics (ZODIAC
and GRAFICS) are two commonly used, non-hierarchical clustering approaches for
manufacturing cell formation. In these heuristics the information about the binary
machine/process plan incidence matrix (akir) is used for grouping machines into cells
maximizing the sum of similarity coefficients between every two machines in a cell
(with similarity measured according to the number of process plans which use both
machines). Process plans are then assigned to the cell in which the majority of its
operations are performed. Simulated Annealing and Tabu Search are two well-known
metaheuristics applied to solve a large number of combinatorial problems, and, in
particular, they have been used to solve the cell formation problem. Both methods start
with an initial feasible solution and repeatedly generate neighboring solutions. Both
methods differ in the mechanism to generate the neighborhood and to select the new
solution. Finally, in SONN a fuzzy aggregate part-machine incidence matrix is
computed using equation (9). The assignment of process plans to machine cells is
performed using the same criterion as in the previous heuristics.
a% ki =
∑ a kir
r
PPi
(9)
3. Multi-period cell loading problem
Once the cell design problem has been solved, the resulting cells can be physically
implemented and the cell loading planned. The cell loading consists in determining the
routing mix and the tool and module allocation, i.e., which quantity of each part type to
be assigned to each alternative route in each time period and how many auxiliary
modules and tools of each available type to be assigned to each RMT and CNC machine
in each period. To do this a MILP model, formulated below, is proposed. The basic
objectives of this phase are to minimize total intercellular transportation and holding
costs of parts as well as to balance machine and cell utilizations.
Let us introduce additional notation to be used in the cell loading problem.
Indexes and basic input data:
•
Time periods: t=1,…,T (T is the planning horizon)
•
Dit: demand for part type i in period t
•
Tool types (set TT) and auxiliary module types (set AM): z=1,…,Z
•
szk: number of tool slots required by tool type z in CNC machine k
•
TMCk: tool magazine capacity of CNC machine k (k ∈ NM)
•
MNAk: maximum number of auxiliary modules for RMT k (k ∈ RM)
•
TCzt: number of available units of tool type z (z ∈ TT) in period t
•
TAzt: number of available units of auxiliary module type z (z ∈ AM) in period t
•
TLz: tool life of tool type z (z ∈ TT)
•
ALz: average life of auxiliary module type z (z ∈ AM)
•
dijrz=1 if j-th operation of r-th process plan of part type i requires tool type z, and
0 otherwise
•
pijrk: processing time of j-th operation of r-th process plan of part type i at
machine k
•
Hkt: maximum workload available for machine k in period t
•
α: maximum inter-cell utilization imbalance
•
β: maximum intra-cell utilization imbalance
•
γ: maximum inter-period utilization imbalance
•
CM: unit intercellular transportation cost
•
CHt: unit holding cost in period t
Additional input data from cell design
•
nir: number of inter-cell movements along route r of part type i (obtained from
phase 1 Xkc and airk)
•
bkc=1 if machine type k belongs to cell c (obtained from phase 1 Xkc)
•
qc: number of machines in cell c (obtained from phase 1 Xkc)
Decision variables of cell loading
•
xirt: quantity of part type i to be assigned to route r in period t
•
Iit: inventory of part type i at the end of period t
εzkt: number of tools of type z (z ∈ TT) assigned to CNC machine k (k ∈ NM) in
•
period t and number of auxiliary modules of type z (z ∈ AM) assigned to RMT k
(k ∈ RM) in period t
•
ukt: workload of machine k in period t
•
wct: total workload of machines in cell c in period t
The cell loading problem can be formulated as the following MILP model.
[ P2 ]
Minimize
CM ∑ ∑ ∑ nir xirt + ∑ ∑ CH t I it
t i r
t i
(10)
subject to
t' = t
t' = t
t' =1 r
t' =1
I it = ∑ ∑ xirt' − ∑ Dit'
I iT = 0
(12)
z∈TT
t
∑ ε zk ≤ MNAk
z∈ AM
t
t
∑ ε zk ≤ TC z
k ∈M
k ∈ RM
t
zk
(11)
∀i
t
∑ s zk ε zk ≤ TMC k
∑ε
∀ i ,∀ t
≤ TA zt
∀ k ∈ NM ,∀ t
∀ k ∈ RM ,∀ t
(13)
(14)
∀ z ∈ TT ,∀ t
(15)
∀ z ∈ AM , ∀ t
(16)
t
t
∑ ∑ ∑ d ijrz pijrk xir ≤ TL z ε zk
∀ z ∈ TT ,∀ k ∈ NM ,∀ t
(17)
t
t
∑ ∑ ∑ d ijrz pijrk xir ≤ AL z ε zk
∀ z ∈ AM ,∀ k ∈ RM ,∀ t
(18)
i
i
j r
j r
t
t
∑ ∑ ∑ ∑ d ijrz pijrk xir = u k
i
∀k , ∀ t
(19)
j r z
wct = ∑ bkc u kt
∀ c ,∀ t
(20)
k
u kt ≤ H kt
∀ k ,∀ t
(21)
t
(1 − α )
∑ wc
c
C
t
≤ wct ≤ ( 1 + α )
∑ wc
∀ c ,∀ t
c
C
wct
wct
t
( 1 − β )∑
bkc ≤ u k ≤ ( 1 + β )∑
bkc
c qc
c qc
t
(1 − γ )
∑ ∑ wc
t c
T ⋅C
t
≤
∑ wc
c
C
∀ k ,∀ t
(22)
(23)
t
≤ (1 + γ )
t
xir
, I it ,u kt ,wct ≥ 0 , ε tzk ∈ Z +
∑ ∑ wc
t c
T ⋅C
∀ i ,r ,t ,k ,c , z
∀t
(24)
(25)
The objective function (10) minimizes total costs, including both intercellular
transportation costs and inventory holding costs. Constraints (11) compute inventories
at the end of each period and impose that the part demand of each period must be
satisfied. Constraints (12) impose a zero inventory at end of the planning horizon for all
part types. The limitations on the tool magazine capacity of each CNC machine and the
physical limitations on the number of auxiliary modules that can be attached to each
RMT are represented by constraints (13) and (14), respectively. Constraints (15) and
(16) impose the limitations on the number of available tools and auxiliary modules.
Constraints (17) and (18) imply that for each tool type (respectively, auxiliary module
type) the total life corresponding to the number of tools (respectively, auxiliary
modules) assigned to each machine should be larger than or equal to the corresponding
workloads for that tool type (respectively, auxiliary module type) on that machine.
Constraints (19) compute the workload of each machine in each period while
constraints (20) compute the workload of each cell in each period as the sum of the
workloads of machines assigned to the cell. Constraints (21) correspond to the
maximum workload allowed for each machine. Workload balancing in each period is
considered through constraints (22), (23) and (24), which bound for each period, the
deviation of each cell workload, of each machine workload and of the system workload
with respect to their average values. Constraints (25) declare that all variables are
continuous except for the integer variables εzkt.
The above model is different from other approaches in that not only it considers
the total costs as main objective function but also balancing the workload as secondary
objective function. The latter objective seeks that all machines in the same cell be
approximately equally loaded, that the average utilization of the machines in each cell
be approximately the same for all the cells in each period, and that the average system
utilization for each period be similar. This objective helps prevent bottlenecks and thus
increases throughput. Also this model includes RMT and auxiliary modules as part of
the CRMS, considering limitations on the number of modules per machine and on the
total number of module copies of each auxiliary module type.
A MILP formulation is a natural approach for this problem. The number of
integer variables depends on the degree of tool and module commonality between
operations and in any case cannot exceed the number of machine types times the
number of tool types. Constraints (13)-(16) are multiknapsack, which implies that the
problem may not be easily solved in the worst case. Although in the illustration
presented in the next section, given its moderate size, the model has been solved
optimally, more efficient solution strategies (e.g. metaheuristic approaches) may have to
be developed for larger sized problems.
4. Illustration
This section considers a manufacturing system involving 14 machines (of which 11
CNC machines, numbered 1-11, and 3 RMT, numbered 12-14), and 10 part types. Table
1 shows the sequence of operations of the alternative process plans of each part type.
Note that there are a total of 23 alternative routes (ranging from 1 to 6 operations per
route) and using 6 tool types (numbered 1-6) and 3 auxiliary module types (numbered
7-9).
============================== Table 1 ==========================
From the Table 1, the machine/process plan incidence matrix is generated using
only the first attribute (i.e. machine type) of each operation. Table 2 shows the
corresponding binary machine/process plan incidence matrix (akir).
============================== Table 2 ==========================
The cell design model [P1] has been solved optimally using the linear
programming software LINGO® v.9 on a 3.3 GHz Intel® Core(TM) i5-2400 CPU.
Table 3 shows the machine cells and associated process plan families obtained by the
optimization software for different values of the weighting parameter q from 0 to 1 (in
steps of 0.1) and a maximum number of 6 cells (C). According to these results, the
minimum number of intracellular voids obtained is 6 and occurs when q=1 and the 14
machines are grouped into the maximum number of 6 cells while the minimum number
of exceptional elements is 0 corresponding to q=0 and 3 cells formed. For intermediate
values of the weighting parameter q, the number of cells, voids and exceptional
elements vary between the above limits. In this illustration, choosing a value for the
relative weight of voids and exceptional elements q=0.1 is reasonable due to the
resulting cell sizes (between 3 and 4 machines per cell) and the number of formed cells
(4 cells).
============================== Table 3 ==========================
As mentioned in section 2, three ad-hoc heuristics (MST, ZODIAC and
GRAFICS), three metaheuristics (SA-Boctor, SA-Chen and TS-Sun) and a fuzzy neural
network (SONN) have also been applied to solve this cell design problem. In order to be
able to compare these methods with the optimal ILP model results, a cell size limit has
not been considered and the same objective function has been used. The comparison has
been carried out for a value of q=0.1. The three ad-hoc heuristics do not need the
number of cells to be fixed a priori and process plans are assigned to the cell in which
the impact on the objective function is lowest. For the other four methods, a maximum
number of C=4 cells has been established. The cell design results for these seven
heuristic methods are shown in table 4. Note that six of the methods have also obtained
the optimal solution, while ZODIAC has grouped the 14 machines into 6 cells. Note
that, in the optimal four cell configuration, many part types (e.g. 1, 3, 4, 7, 8, 9 and 10)
have process plans that are assigned to different cells, thus increasing the flexibility for
the cell loading phase. Let us assume that the four-cell solution that appears in both
Tables 3 and 4 is selected. This CRMS configuration is shown in Figure 2.
============================== Table 4 ==========================
============================= Figure 2 ==========================
The cell loading model [P2] has been solved for the optimal four cell solution.
In order to analyse the performance of the proposed approach in a dynamic environment
four time periods have been considered, with production requirements shown in Tables
5 and 6.
============================== Table 5 ==========================
============================== Table 6 =========================
MILP model [P2] has been solved using the linear programming software
LINGO® v.9 with on a 3.3 GHz Intel® Core(TM) i5-2400 CPU, taking 7 seconds.
Tables 7-10 show the optimal solution computed, which has an objective function value
of 17.53 (representing total intercellular transportation and inventory holding costs).
Solving the problem imposing additional integrality constraints on the xirt variables took
longer than 8 min and gave an optimal objective function value of 20.71, i.e. a 18.1%
gap. Note that the rounding errors for not imposing integrality constraints on the xirt
variables are less important the higher the values of the demands.
============================== Table 7 ==========================
============================== Table 8 ==========================
============================== Table 9 ==========================
============================= Table 10 ==========================
Note that although part types 2, 3, 4 and 5 have similar production requirements
in periods 1 and 2, their corresponding production plan varies completely for each
period. Thus, although the proposed CRMS uses the same cell configuration for the
whole planning horizon, the flexibility provided by the possibility of selecting different
process plans allows meeting dynamic production requirements with high system
performance.
The problem has also been solved assuming that for each part type only one of
the alternative routes can be used along the whole planning horizon. That approach is
quite common in the literature. The criterion that has been used for selecting the route is
the minimization of total intercellular transportation and inventory holding costs in the
loading phase. That means adding to model [P2] some binary variables δir (=1 if route r
of part type i is selected, 0 otherwise) and the following constraints, which may also use
upper bounds of the total quantity of each part type to be produced:
∑ δ ir ≤ 1 ∀ i
(26)
r
t
t
∑ xir ≤ δ ir ⋅ ∑ Di
t
∀ i,∀ r
(27)
t
For this single-route variant, the optimal objective function value that results is
103.68 (104.31 if the values of the variables xirt are forced to be integer). Note how
allowing more than one route per part type, using the same resources (CNC and RMT,
tools and auxiliary modules) and balancing the workloads, costs have been greatly
reduced due to flexibility. Actually, most of the potential flexibility associated to the
existence of alternative routing is lost if, as many approaches do, only one of the
alternative routes of each part type is selected in the cell design phase.
Finally, the problem has also been solved using all routes but forcing the
selection of just one route per part type in each period, that is, all alternative routes are
available for the cell loading phase, but in each time period only one route per part type
can be selected. In this case, not all the flexibility is lost. This variant involves adding to
model [P2] some binary variables δirt (=1 if route r of part type i is selected in period t,
0 otherwise) and constraints similar to (26)-(27) for each period. The optimal objective
function value obtained is 100.64 (100.91 if the values of the variables xirt are forced to
be integer). Table 11 summarizes these results.
============================= Table 11 ==========================
5. Conclusions
This study has considered the cell design and multi-period loading problem for CRMS
with CNC machines and RMT, taking into account the presence of alternative process
plans for each part type. Alternative routing is recognized as an effective means of
coping with the loss of flexibility inherent to dedicated machines in CMS. The
methodology proposed in this paper has handled both problems sequentially; first
solving the cell design once and for all, and then carrying out cell loading for each
planning horizon using the solution from the cell design step.
For cell design, an ILP model has been presented that minimizes a weighted
linear combination of intercellular movements and intracellular voids. This model has
been solved optimally and with some heuristic methods from the group
technology/cellular manufacturing literature on an illustrative example. In some of the
heuristic methods, process plans are treated as if they were separate part types, and
families of process plans and associated machine cells are formed. In one of these
methods (namely, SONN), however, the different process plans of each part type are
used to form aggregate part types and to group machines using these aggregate part
types.
For multi-period cell loading, a MILP model for assigning parts to the
alternative routes is proposed, minimizing total intercellular transportation and
inventory holding costs while keeping intra-cellular, inter-cellular and inter-period
utilization approximately balanced. Constraints on tool magazine capacity, number of
auxiliary modules per RMT, number of tool and auxiliary modules available, tool and
module life restrictions, and finite machine capacity are imposed.
The proposed approach has been applied to a small example for the purpose of
illustration and has been confirmed that cell design and cell loading for CRMS,
considering specific production features of CNC machines and RMT, can be handled as
sequential problems, which can therefore be solved separately. As for the cell design
phase, apart from solving the proposed model optimally, some existing cell formation
methods have been applied, provided that they do not exclude the subsequent use of any
route. As for the cell loading phase, it has been modelled as a MILP aiming at two
objectives (i.e. inter-cell flow and workload balancing), allowing in each period the
selection of more than one route for each part type in order to take maximum advantage
of the existing flexibility.
The machine loading solution obtained using the proposed approach could be
validated through simulation, which represents a topic for further research. Thus,
simulating the system configuration, part routing and workloads computed, the system
performance for the multiple-period production plan may be assessed. Moreover,
considering random machine failures and disturbances would allow studying also the
robustness of the proposed solution.
Finally, in this paper the solution approach is based on exact methods. However,
computing an optimal solution for this type of MILP may become impractical for large
size problems due to the excessive computation time required. This means that for
larger problems a metaheuristic solution algorithm would have to be developed. Such
approximate solution approach can be validated comparing the known optimal solutions
for the smaller-sized problems. This is also a topic for further research.
Acknowledgements
This research was carried out with the financial support of the Andalusia Government [grant
number P10-TEP-6332], the Spanish Ministry of Science [grant number DPI2013-41469-P] and
the European Regional Development Fund (ERDF).
References
Adil, G.K., Rajamani, D. and Strong, D. (1993). AAA-an assignment allocation
algorithm for cell formation. Univ. Manitoba, Canada. Working paper.
Askin, R. G. and Chiu, K. S. (1990). A graph partitioning procedure for machine
assignment and cell formation in Group Technology. International Journal of
Production Research, 28, 1555-1572.
Ateme-Nguema, B. and Dao, T.M. (2009). Quantized Hopfield networks and tabu
search for manufacturing cell formation problems. International Journal of
Production Economics, 121(1), 88-98
Boctor, F.F. (1991). A linear formulation of the machine-part cell formation problem.
International Journal of Production Research, 29, 343-356.
Chandrasekharan,M.P. and Rajagopalan,R. (1987). ZODIAC - an algorithm for
concurrent formation of part-families and machine cells. International Journal
of Production Research, 25, 835-850.
Chen, C.L., Cotruvo, N.A. and Baek,W. (1995). A simulated annealing solution to the
cell formation problem. International Journal of Production Research, 33,
2601-2614.
Choobineh, F. (1988). A framework for the design of cellular manufacturing systems.
International Journal of Production Research, 26, 1161-1172.
Defersha, F.M. and Chen, M. (2006). A comprehensive mathematical model for the
design of cellular manufacturing systems. International Journal of Production
Economics, 103 (2), 767-783.
Eguia, I., Racero, J., Guerrero, F. and Lozano, S. (2013). Cell formation and scheduling
of part families for reconfigurable cellular manufacturing systems using Tabu
search. SIMULATION. Transactions of The Society for Modeling and Simulation
International, 89(9), 1056-1072.
Farahani, M.H. and Hosseini, L. (2011). An ant colony optimization approach for the
machine-part cell formation problem. International Journal of Computational
Intelligence Systems, 4 (4), 486-496.
Ghosh, T., Sengupta, S., Doloi, B, Dan, P.K. (2014). AI-based techniques in cellular
manufacturing systems: A chronological survey and analysis. International
Journal of Industrial and Systems Engineering, 17 (4), 449-476.
Kang, S. L and Wemmerlöv, U. (1993). A work load-oriented heuristic methodology for
manufacturing cell formation allowing reallocation of operations. European
Journal of Operational Research, 69, 292-311.
Koren, Y., Heisel, U., Jovane, F., Moriwaki, T., Pritschow, G., Ulsoy, G., and Van
Brussel, H. (1999). Reconfigurable Manufacturing Systems. Annals of the CIRP,
48, 1-14.
Koren, Y. (2010). The Global Manufacturing Revolution. John Wiley & Sons.
Kumar, N and Shanker, K. (2000). A Genetic Algorithm for FMS Part Type Selection
and Machine Loading. International Journal of Production Research, 38 (16),
3861-3887.
Kusiak, A. (1987). The generalized group technology concept. International Journal of
Production Research, 25, 561-569.
Landers, R.G., Min, B.K., and Koren, Y. (2001). Reconfigurable machine tools. CIRP
Annals-Manufacturing Technology, 50 (1), 269-274.
Logendran, R., Ramakrishna, P., and Sriskandarajah, C. (1994). Tabu search-based
heuristics for cellular manufacturing systems in the presence of alternative
process plans. International Journal of Production Research, 32, 273-297.
Lozano, S., Guerrero, F., Eguia, I., Canca, D., and Smith, K. (1998). Cell Formation
Using Two Neural Networks in Series. In Intelligent Engineering Systems
Through Artificial Neural Networks. Volume (8). Nueva York, EE.UU. ASME
Press. 341-346
Majija, N., Mpofu, K. and Modungwa, D. (2013). Conceptual Development of Modular
Machine Tools for Reconfigurable Manufacturing Systems. In Advances in
Sustainable and Competitive Manufacturing Systems, Lecture Notes in
Mechanical Engineering. Springer International Publishing Switzerland. 467477.
Molina, A., Rodríguez, C.A., Ahuett, H., Cortés, J.A., Ramírez, M., Jiménez, G., and
Martínez, S. (2005). Next-generation manufacturing systems: key research
issues in developing and integrating reconfigurable and intelligent machines.
International Journal of Computer Integrated Manufacturing, 18, 225-236.
Padayachee, J. and Bright, G. (2012). Modular machine tools: design and barriers to
industrial implementation. Journal of Manufacturing Systems, 31(2), 92-102.
Pattanaik, L.N., Jain, P.K., and Mehta, N.K. (2007). Cell formation in the presence of
reconfigurable machines. International Journal of Advanced Manufacturing
Technology, 34, 335-345.
Pattanaik, L.N. and Kumar, V. (2010). Multiple levels of reconfiguration for robust
cells formed using modular machines. International Journal of Industrial and
Systems Engineering, 8 (4), 424-441.
Selim, H.M., Askin, R.G. and Vakharia, A.J. (1998). Cell formation in group
technology: Review, evaluation and directions for future research. Computers &
Industrial Engineering, 34(1), 3-20.
Sengupta, S., Ghosh, T. and Dan, P.K. (2011). A hybrid neural network approach to cell
formation in cellular manufacturing. International Journal of Intelligent Systems
Technologies and Applications, 10(4), 360–376.
Sofianopoulou, S. (1999). Manufacturing cells design with alternative process plans
and/or replicate machines. International Journal of Production Research, 37,
707-720.
Srinivasan, G., Narendran, T.T. and Mahadevan, B. (1990). An assignment model for
the part-families problem in group technology. International Journal of
Production Research, 28, 145-152.
Srinivasan, G. and Narendran, T. T. (1991) GRAFICS-a nonhierarchical clustering
algorithm for group technology. International Journal of Production Research,
29, 463-478.
Srinivasan, G. (1994). A clustering algorithm for machine cell formation in group
technology using minimum spanning trees. International Journal of Production
Research, 32, 2149-2158.
Sun, D., Kim, L. and Batta, R. (1995). Cell formation using tabu search. Computers and
Industrial Engineering, 28, 485-494.
Swarnkar, R. and Tiwari, M.K. (2004). Modeling Machine Loading Problem of FMSs
and its Solution Methodology is using a Hybrid Tabu Search and Simulated
Annealing-Based Heuristic Approach. Robotics and Computer Integrated
Manufacturing, 20, 199–209.
Wemmerlöv, U. and Johnson, D.J. (1997). Cellular manufacturing at 46 user plants:
implementation experiences and performance improvements. International
Journal of Production Research, 35 (1), 29-49.
Xiaobo, Z., Jiancai, W., and Zhenbi, L. (2000). A Stochastic Model of a Reconfigurable
Manufacturing System, Part 1: A Framework. International Journal of
Production Research, 38 (10), 2273-2285.
Xing, B., Nelwamondo, F.V., Battle K, Gao, W. and Marwala, T. (2009). Application of
artificial intelligence (AI) methods for designing and analysis of reconfigurable
cellular manufacturing system (RCMS). In: Proceedings of the 2nd
International Conference on Adaptive Science & Technology, 1, 402–409.
Ying, K.C., Lin, S.W. and Lu, C.C. (2011). Cell formation using a simulated annealing
algorithm with variable neighbourhood. European Journal of Industrial
Engineering, 5 (1), 22–42.
Yu, J.M., Doh, H.H., Kim, H.W., Kim, J.S., Lee, D.H., and Nam, S.H. (2012). Iterative
algorithms for part grouping and loading in cellular reconfigurable
manufacturing systems, Journal of the Operational Research Society, 63, 16351644.
List of Tables
Table 1. Routing data
Table 2. Machine/process plan incidence matrix
Table 3. Optimal cell design solutions (machine groups and process plan families)
Table 4. Cell design solutions from heuristic methods (machine groups and process plan
families)
Table 5. Demand scenario for cell loading
Table 6. Additional data
Table 7. Optimal cell loading solution: production plan (xirt)
Table 8. Optimal cell loading solution: inventories (Iit)
Table 9. Optimal cell loading solution: workloads (ukt; wct)
Table 10. Optimal cell loading solution: number of tools, modules and tool magazine
slots used
Table 11. Optimal cell loading solution: comparison with other approaches
List of Figures
Figure 1. RMC and CRMS: schematic description
Figure 2. Visual representation of the cell design solution
Figure 1. RMC and CRMS: schematic description
CRMS
CNC 30
pallet10
RMT 20
CNC 10
pallet3
pallet2
pallet4
L/U
Robot
RMT 10
buffer 2
buffer 10
pallet1
buffer 1
pallet11
pallet12
L/U
Robot
CNC 20
RMT 30
buffer 11
RMC #1
RMC #2
CNC 40
Figure 2. Visual representation of the cell design solution
CRMS (Cell design solution)
CNC 5
CNC 6
CNC 7
CNC 11
CNC 1
CNC 2
CNC 8
RMT 14
CNC 3
CNC 4
RMT 13
CNC 9
CNC 10
RMT 12
RMC #1
RMC #2
CNC 1 – CNC 11
Cell design
RMC #3
RMT 12 – RMT 14
RMC #4
Table 1. Routing data
Part ty
pe
Route
i
r
1
1-1
1-2
1-3
2
2-1
2-2
3
3-1
3-2
3-3
4
4-1
4-2
5
5-1
5-2
6
6-1
6-2
7
7-1
7-2
7-3
8
8-1
8-2
9
9-1
9-2
10
10-1
10-2
Operation sequence (machine, processing time, tool/module)
j=1
(6,5,2)
(4,8,1)
(3,10,6)
(14,6,8)
(8,3,1)
(6,2,3)
(10,9,1)
(9,8,2)
(10,7,6)
(7,7,1)
(11,4,4)
(6,4,2)
(11,3,4)
(5,8,6)
(6,4,2)
(6,5,5)
(4,7,4)
(10,7,3)
(3,6,3)
(4,6,2)
(2,4,1)
(4,5,4)
(14,10,7)
j=2
(5,12,3)
(13,6,9)
(13,5,8)
(1,5,3)
(2,9,4)
(7,8,5)
(12,7,9)
(12,4,9)
(9,10,6)
(6,4,2)
(5,6,6)
(5,4,5)
(7,6,4)
(6,7,3)
(7,3,4)
(5,4,5)
(3,8,2)
j=3
(6,7,5)
(3,5,6)
(3,10,2)
(8,4,5)
(8,5,6)
(6,3,5)
(10,9,3)
(9,6,6)
(10,6,1)
(11,12,4)
(11,4,6)
(7,4,1)
j=4
j=5
j=6
(4,5,1)
(13,8,9)
(14,5,7)
(1,10,3)
(13,6,9)
(4,4,2)
(8,5,5)
(1,5,1)
(13,4,8)
(10,4,6)
(12,5,7)
(7,9,4)
(6,5,3)
(5,8,5)
(6,4,5)
(7,5,5)
(5,5,6)
(6,6,3)
(7,3,5)
(13,5,8)
(4,6,1)
(3,6,6)
(8,3,6)
(3,5,6)
(13,5,9)
(2,6,5)
(10,5,1)
(4,7,2)
(3,5,3)
(11,5,4)
Table 2. Machine/process plan incidence matrix
Machin
e type
(k)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
1
1
0
0
0
0
1
1
0
0
0
0
0
0
0
0
1
2
0
0
1
1
0
0
0
0
0
0
0
0
1
0
1
3
0
0
1
1
0
0
0
0
0
0
0
0
1
0
2
1
1
0
0
0
0
0
0
1
0
0
0
0
0
1
2
2
1
1
0
0
0
0
0
1
0
0
0
0
0
0
3
1
0
0
0
0
0
1
1
0
0
0
0
0
0
0
3
2
0
0
0
0
0
0
0
0
0
1
0
1
0
0
3
3
0
0
0
0
0
0
0
0
1
1
0
1
1
0
Part-Process Plan (i-r)
4 4 5 5 6 6 7 7
- - - - - - - 1 2 1 2 1 2 1 2
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 1 1 1 0 1 1 1
0 1 0 1 0 1 1 1
0 1 0 1 1 0 1 0
0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0
0 1 1 0 1 0 1 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
7
3
0
0
1
1
0
0
0
0
0
0
0
0
1
0
8
1
0
0
0
0
0
0
0
0
0
1
0
0
0
0
8
2
0
0
1
0
0
0
0
0
0
0
0
0
0
0
9
1
0
0
1
1
0
0
0
0
0
0
0
0
1
0
9
- 10 10
2 -1 -2
0 0 0
1 0 0
0 1 0
0 1 0
0 0 0
0 0 0
0 0 0
1 0 0
0 0 0
0 1 0
0 0 0
0 0 0
0 0 0
0 0 1
Table 5. Demand scenario for cell loading
Part type
1
2
3
4
5
6
7
8
9
10
Demand for period 1
-
18
15
8
9
-
16
12
18
-
Demand for period 2
10
18
18
8
10
8
-
-
-
12
Demand for period 3
12
18
-
-
-
12
18
8
15
14
Demand for period 4
-
10
16
12
8
-
-
15
12
10
Table 6. Additional data
Tool slots per tool type (∀z ∈ TT, ∀k ∈ NM))
szk
1
Tool magazine capacity (∀k ∈ NM)
TMCk
3
Number of auxiliary modules (∀k ∈ RM)
MNAk
2
Number of available tool copies (∀z ∈ TT)
TCzt
6
Number of available module copies (∀z ∈ AM)
TAzt
2
Tool life (∀z ∈ TT)
TLz
120
Auxiliary module life (∀z ∈ AM)
ALz
120
Maximum workload for machine (∀k ∈ NM, ∀t)
Hkt
240
Maximum inter-cell imbalance
α
0.30
Maximum intra-cell imbalance
β
0.60
Maximum inter-period system utilization imbalance
γ
0.30
Unit intercellular transportation cost
CM
1
Unit holding cost ∀t
CHt
0.1
Table 7. Optimal cell loading solution: production plan (xirt)
Part-Process Plan
(i-r)
xir1
Production plan
xir2
xir3
1-1
0.646
4.865
1-2
1.478
3.750
1-3
11.261
0.000
xir4
2-1
3.486
0.000
0.000
0.000
2-2
16.997
18.126
15.494
9.897
3-1
9.599
12.360
7.065
3-2
3.358
3.506
2.525
3-3
2.043
2.134
1.427
4-1
7.613
7.950
4.177
4-2
0.387
0.050
0.800
5-1
9.000
5.775
3.707
5-2
0.000
4.225
4.293
6-1
0.000
12.000
6-2
8.000
0.000
7-1
5.841
0.811
7-2
10.159
17.189
7-3
0.000
0.000
8-1
0.000
0.000
0.000
8-2
12.000
8.770
14.230
9-1
18.000
15.000
12.000
9-2
0.000
0.000
0.000
10-1
0.000
0.000
0.000
10-2
12.000
12.000
10.000
Table 8. Optimal cell loading solution: inventories (Iit)
Part type (i)
Ii1
1
I i2
I i3
3.385
0
0.103
I i4
2
2.483
2.609
3
0
0
0
4
0
0
0
5
0
0
0
0
6
0
0
7
0
0
8
0
0.770
0
9
0
0
0
0
0
10
2.000
Table 9. Optimal cell loading solution: workloads (ukt; wct)
uk1
uk2
uk3
uk4
3
180
232.61
161.367
157.383
4
108
64.259
138.75
72
13
98.173
172.665
127.541
65.71
Total (wct)
386.173
469.534
427.658
295.093
9
104.732
109.378
96.623
61.758
10
167.571
175.005
154.597
105.461
12
41.893
43.751
38.649
30.521
Total (wct)
314.196
328.135
289.869
197.739
5
126.941
123.702
131.189
45.81
6
160.69
159.797
152.432
76.866
7
118.041
137.696
76.865
107.951
11
105.857
46.799
40.054
39.25
Total (wct)
511.53
467.994
400.541
269.877
1
204.832
181.257
154.937
98.974
2
152.971
163.131
139.443
89.077
8
167.352
145.005
123.949
79.179
14
58.351
120
120
100
Total (wct)
583.507
609.393
538.329
367.23
403.55
448.851
468.764
414.099
282.485
Cell (c) Machine (k)
I
II
III
IV
Average
Table 10. Optimal cell loading solution: number of tools, modules and tool magazine slots
used
Tool type (z∈TT)
∑k εzk1
∑k εzk2
∑k εzk3
∑k εzk4
1
4
4
3
3
2
3
4
3
3
3
5
5
6
4
4
4
4
4
3
5
4
3
3
3
6
6
6
5
6
Module type (z∈AM)
∑k εzk1
∑k εzk2
∑k εzk3
∑k εzk4
7
2
2
2
2
8
2
1
1
1
9
2
2
2
2
CNC Machine (k∈NM)
∑z szkεzk1
∑z szkεzk2
∑z szkεzk3
∑z szkεzk4
1
3
2
2
1
2
2
2
2
1
3
2
2
2
2
4
1
2
2
1
5
2
3
3
2
6
3
3
3
3
7
3
3
2
3
8
3
2
2
2
9
2
2
2
2
10
3
3
3
3
11
2
2
1
2
Reconf. Mach. Tool
(k∈RM)
∑z szkεzk1
∑z szkεzk2
∑z szkεzk3
∑z szkεzk4
12
2
2
2
2
13
2
2
2
2
14
2
1
1
1
Table 11. Optimal cell loading solution: comparison with other approaches
Without integrality
constraints on xirt
With integrality
constraints on xirt
Objective
function
CPU time
(hh:mm:ss)
Objective
function
CPU time
(hh:mm:ss)
Proposed approach
17.527
0:00:07
20.712
0:08:47
Single-route selection
103.677
0:00:03
104.310
0:00:10
Multiple-route, single
assignment per period
100.643
0:00:38
100.911
5:36:51