# An Integrated Model for Production Planning and Cell Formation in Cellular  Manufacturing Systems

Authors: Reza Raminfar; Norzima Zulkifli; Mohammadreza Vasili; Tang Sai Hong
Journal: Journal of Applied Mathematics
 (2013)

---

## Abstract

Cellular manufacturing (CM) is a production approach directed towards reducing costs, as well as increasing system's flexibility in today's small-to-medium lot production environment. Many structural and operational issues should be considered for a successful CM design and implementation such as cell formation (CF), production planning, and facility layout. Most researchers have addressed these issues sequentially or independently, instead of jointly optimizing a combination of these issues. In order to attain better results to ensure that the system will be capable of remaining efficient in unknown future situations, these issues should be addressed simultaneously. In this paper, a mathematical model is developed using an integrated approach for production planning and cell formation problems in a CM. A set of numerical examples are provided from existing the literature in order to test and illustrate the proposed model. In order to evaluate and verify the performance of the proposed model, it is compared with a well-known cell formation methods (rank order clustering and direct clustering analysis), using group capability index (GCI) measure. The results and comparisons indicate that the proposed model has a significantly higher and satisfactory performance and it is reliable for the design and the analysis of CM systems.


---

## Body

## 1. Introduction

Cellular manufacturing (CM) is a production system that involves processing a collection of similar parts (part families) on dedicated cluster of machines or manufacturing processes (cells) [1]. CM is an application of group technology (GT) which offers the advantages of both job shops (flexibility in producing a wide variety of products) and flow lines (efficient flow and high production rate) [2]. The advantages of CM include simplified material flows and reduced material handling cost, reduced production time, reduction  in setup time,  reduced production cost, reduction in inventory and work-in-process (WIP) inventories, reduction in scrap and waste, decentralization of responsibilities, and saving manufacturing space [3–6]. The design and implementation of an effective CM system involves many issues such as machine-part cell formation (CF), production planning, layout design, and scheduling.In the design of a CM system, similar parts are grouped into families and associated machines into groups so that one or more part families can be processed within a single machine group [7]. The process of determining part families and machine groups in order to form the manufacturing cells is referred to as the CF problem. This problem may be solved by using different methods and considering different manufacturing features. The CF problems can be classified into binary and comprehensive problems depending on whether or not processing times and the machine capacities are considered.The binary problem arises if the part demands are unknown when the CM system is being developed [8–10]. If the part demand can be accurately predicted, processing time and machine capacities have to be included in the analysis. This gives rise to comprehensive problems [11]. In addition, the comprehensive models can be classified considering the production requirements. They are static versus dynamic production requirements and deterministic versus stochastic production requirements [12]. A static production requirement implies a single period when designing a CM system. It assumes that product mix and part demand are constant for the entire planning horizon. The product mix refers to a set of part-types to be produced at each period, and the part demand is the quantity of each part-type to be produced [13]. Product mix and demand in such cases can be deterministic or stochastic. For static and deterministic production requirements, there is only one possible set of product mix and demand which are known [14, 15]. In contrast, static and stochastic production requirements have a set of possible product mixes and demands to occur; each has its probability of occurrence [16]. However, dynamic production requirements imply multiple periods when designing a CM system. In the dynamic environment, the entire planning horizon is divided into multiple smaller periods, and each period has different product mix and part demand. Meanwhile, as mentioned earlier, production requirements can be deterministic or stochastic in each period. For dynamic and deterministic production requirements, product mix and demand in each period are known [17, 18]. For dynamic and stochastic production requirements, the possible product mixes and demands in each period are known with certain probabilities [19, 20].In today’s world of rapidly changing product demand, small internet orders, tight delivery schedules, high competition, and high service level requirements, it will be increasingly difficult to maintain good operational performance over the time. In such a case, managing the production resources and balancing them between successive time periods with the aim of minimizing the production costs is known as “production planning” [21]. Based on the literature, numerous mathematical models and solution methods have been developed to solve the existing problems in general manufacturing or service industries [22, 23]. However, in the recent researches, critical manufacturing features such as production flexibility and manufacturing cell formations have received considerable attention in developing production planning models. Furthermore, in order to achieve more practical results, the production planning features such as machine capacity, machine cost, operations sequence, inventories holding, backorders, and subcontracting can be considered in order to form the manufacturing cells. In this regard, integrated approaches should be pursued in manufacturing system analysis, since different aspects of the system are interrelated in many ways [24]. Integrated system approaches can minimize the possibility of certain important aspects of the system being neglected, while other issues are being studied [25]. In general, integrating the concepts of the CM system design and production planning is a fundamental requirement for modeling and simulating of the real manufacturing systems. This integrated concept has been discussed, for example, in Chen [25], Safaei and Tavakkoli-Moghaddam [21], Ah kioon et al. [26], and Mahdavi et al. [27].Although each of these researches has covered some of the features problem, or utilize special method to solve problems and their efficiencies are different too. For instance, Chen [25] solved problems with a decomposition-based heuristic algorithm or he considered unit cost to move for every part-type in batches between cells; however, it seems not practical enough. Other example is a Safaei and Tavakkoli-Moghaddam [21], although this is a very comprehensive dynamic integrated model and utilizes mathematical linear programming to solve problems, but for material handling cost feature, this research does not take into account different travel distance between cells. Ah kioon et al., [26] research is also a very well-integrated model too, but it does not take into consideration some issues that are addressed within this research paper such as machine set-up cost (with respect to the machine set-up cost for each operation) or they consider intercell material handling cost feature, but they do not take into account different travel distance between cells too. Mahdavi et al., [27]  or other called researches proposed their integrated model and solved numerical examples by their models, but they do not try to evaluate and verify performance of their models, although we try to evaluate and verify the CF section performance of the proposed model within this research.This study aims at introducing a comprehensive dynamic deterministic integrated model to offer an optimal solution for grouping the part families and machine cells, as well as an optimal production plan for minimizing inventory and machine set-up costs. The aim of proposed model is to minimize machine operating cost, intercell material handling cost (with respect to the different travel distances between cells), machine operating cost, finished-goods inventory cost, and machine set-up cost (with respect to the machine set up cost for each operation). Our model considers cell size limitation, machine duplication in one period time, and operation sequence features too.The rest of this paper is organized as follows. Detailed description of the problem and the proposed model are presented in Section2. Some numerical examples are presented in Section 3, in order to illustrate the proposed model. Discussions to verify the model are presented in Section 4. Summary and conclusions of the research are discussed in Section 5.


## 2. Mathematical Model Development

### 2.1. Problem Description

In this section, a mixed integer nonlinear programming model is developed to simultaneously solve the cell formation and production planning problems in CM systems. The objective function of this model is to minimize intercell material handling cost, machine operating cost, production set-up cost for every operation in every part, and part inventory cost. A manufacturing system which includes a number of machines to process different part-types is considered. Each part-type has a number of operations, and that must be processed as numbered respectively, in order to take the sequence of operations into account. The manufacturing system is considered in a number of time periodst, where t=1,2,…,T, with T>1. One time period could be a day, a week, or a month. Demands for different part-types are assumed to be known and deterministic. Demands may be satisfied from production in the same time period or from inventory. Back orders and shortage cost are not considered in this study. This model assumes that there is a single process plan for each part-type. Since both the quantity of different part-types to be processed by the machines and the formation of the machine cells are decision variables, nonlinear terms are presented in the objective function of the mixed integer programming model.


### 2.2. Notations

Indices:
t: time period index: t=1,…,T.
i: part-type index:  i=1,…,I(t).
j: index of operations of part-type  i:j=1,…,Ji.
l: cell index:  l=1,…,L.
k: machine index: k=1,…,K.Coefficients and Parameters:
H
i
(
t
): unit inventory holding cost of part-type i for time period t.
D
i
(
t
): known demand of part-type i for time period t.
M
k
(
t
): unit machine operating cost for machine-type k in time period t.
S
i
[
j
k
]: set-up cost to performing operation j on machine k from part-type i.
R
l
l
′: cost of moving a unit of part-type from cell l to cell l′.
L
B
l: minimum number of machines in cell l.
U
B
l: maximum number of machines in cell l.Binary Decision Variables:
(1)
β
i
(
t
)
=
{
1
,
if
part
type
i
is
processed
in
period
t
,
0
,
otherwise
,
n
k
l
(
t
)
=
{
1
,
if
one
unit
of
type
k
machine
is
placed
in
cell
l
at
time
t
,
0
,
otherwise
,
δ
i
[
j
k
]
l
(
t
)
=
{
1
,
if
operation
j
of
part-type
i
to
be
processed
by
machine
type
k
,
is
done
in
cell
l
during
time
t
,
0
,
otherwise
.
Subscripts i[jk] of variable δi[jk]l(t) indicates that machine k is required to process operation j of part-type i. This information is known from the given part process plan.Continuous Decision Variables:
X
i
(
t
): amount of part-type i to be processed in time period t,
V
i
(
t
): amount of part-type i in inventory at the end of time period t.


### 2.3. Mathematical Models Development

With the given notations, the proposed model is formulated as follows:(2)MinimizeZ=∑t=1T∑k=1KMk(t)·∑l=1Lnkl(t)+∑t=1T∑i=1I(t)Xi(t)·∑j=1ji-1∑k=1Kji∑k′=1K∑l=1L∑l′=1LRll′δi[jk]l(t)δi[(j+1)k′]l′(t)+∑t=1T-1∑i=1I(t)Hi(t)Vi(t)+∑t=1T∑l=1L∑i=1I(t)∑j=1Ji∑k=1KSi[jk]δi[jk]l(t).
Subject to:
(3)∑l=1Lδi[jk]l(t)=βi(t),i=1,…,I,j=1,…,Ji,k=1,…,Kji∀(t),(4)∑i=1I∑j=1Jiδi[jk]l(t)≥nkl(t),i=1,…,I,j=1,…Ji,k=1,…,K,l=1,…,L∀(t),(5)δi[jk]l(t)≤nkl(t),k=1,…,K,l=1,…,L∀(t),(6)LBl≤∑k=1Knkl(t)≤UBl,k=1,…,K∀(t),(7)vi(t+1)=vi(t)+Xi(t)-Di(t),i=1,…,I,t=1,…,T-1,(8)∑t=1TXi(t)=∑t=1TDi(t),i=1,2,…,I,(9)βi(t)={1,ifXi(t)>00,ifXi(t)=0,i=1,2,…,I,∀(t),(10)Xi(t)≥0,vi(t)≥0,δi[jk]l(t),βi(t),nkl(t)=0,1,∀i,j,l,l′,k,k′,t.
The objective function of the proposed model has been shown in (2), and it consists of four terms. The first term of the objective function is the machine operating cost. It is assumed that the machines can be included when they are needed and can be removed from the system when they are not required. The second term of the objective function is the intercell material handling cost. This cost function is similar to those in Atmani et al. [28] and Chen [25]. In a typical cell formation problem, the number of part-type i to be produced in time t, Xi(t), is usually considered constant. In that case, the material handling cost function will be linear. However, in this model, the term of the material handling cost is non-linear, because it has been assumed that the distances between each pair of cells are different (part-type i after completion of its operation j by machine k in cell l moves to machine k′ for its next operation, j+1, in cell l′). It is further assumed that the specifications of different part-types (e.g., size or volume of different part-types) do not influence the material handling cost. The third term is the finished goods inventory cost, and the last term of the objective function is the system set-up cost with consideration of set-up cost for each operation in each part-type. The first two cost items in the objective function are related to forming manufacturing cells, while the latter two cost items are related to production and inventory control.Constraints of the model consist of equations and inequalities (3) to (10). Equation (3) is to ensure that if operation j of part-type i will be processed by machine k in one of the cells in time period t, then the corresponding binary variable for system set-up must be 1. Inequality (4) ensures that once machine k is assigned to cell  l  in time period t, then the operations of part-types may be assigned to that machine. Inequality (5) ensures that sufficient machine capacity is assigned to each cell in time period t. Inequality (6) consists of two constraints for the upper and lower limits to the number of machines in each cell. The upper limit for the number of machines is due to the limitations of the physical space. Furthermore, there should be at least one machine in each cell, otherwise the cell will disappear. Equation (7) provides the relationship of storage levels at different time periods. In fact, in planning the production, demand of part-type i at time t should be deducted from the finished parts in storage at time t. Equation (8) implicates that the production in the entire planning horizon definitely meets the total demand. Equation (9) shows the relationship between the set-up variable βi(t) and the part processing quantity Xi(t). Equation  (10) imposes nonnegativity and integrality, respectively.


### 2.4. Model Linearization

The proposed model is a nonlinear mixed-integer programming model because of the existing two nonlinear parts including the second term of objective function (see (2)) and the seventh constraint (see (9)). In order to find a global solution, the nonlinear model should be transformed into the linear form. Hence, the linearization phase is implemented for these two parts. Consider the second term of the objective function:
(11)∑t=1T∑i=1I(t)Xi(t)·∑j=1ji-1∑k=1Kji∑k′=1Kji∑l=1L∑l′=LLRll′δi[jk]l(t)δi[(j+1)k′]l′(t).
It can be modified as follows:
(12)∑t=1T∑i=1I(t)∑j=1Ji∑k=1K∑k′=1K∑l=1L∑L′=1LRll′Xi(t)δi[jk]l(t)δi[(j+1)k′]l′(t),∑t=1T∑i=1I(t)∑j=1ji-1∑k=1K∑k′=1K∑l=1L∑L′=1LRll′[Xi(t)(δi[jk]l(t)δi[(j+1)k′]l′(t))].
In order to linearize the previous expression, let us assume that
(13)Yi[jk]lk′l′(t)=δi[jk]l(t)δi[(j+1)k′]l′(t),(14)Wi[jk]lk′l′(t)=Xi(t)Yi[jk]lk′l′(t).
These variables imply that
(15)Yi[jk]lk′l′(t)={1,ifpart-typeimovestomachinek′incelll′toperformoperation(j+1)afterperformingoperationjonmachinekincelll,0,otherwise,Wi[jk]lk′l′(t)={Xi(t),ifYi[jk]lk′l′(t)=1,0,ifYi[jk]lk′l′(t)=0.
Finally, the second term of objective function can be replaced by the following linear expression:
(16)∑t=1T∑i=1I(t)∑j=1Ji-1∑k=1K∑k′=1K∑l=1L∑L′=1LRll′Wi[jk]lk′l′(t).
Furthermore, the following constraints should be added to this model:
(17)δi[jk]l(t)+δi[(j+1)k′]l′(t)-2Yi[jk]lk′l′(t)≥0,(18)δi[jk]l(t)+δi[(j+1)k′]l′(t)-Yi[jk]lk′l′(t)≤1,(19)Wi[jk]lk′l′(t)≥Xi(t)+MYi[jk]lk′l′(t)-M,(20)Wi[jk]lk′l′(t)≤Xi(t),(21)Wi[jk]lk′l′(t)≤MYi[jk]lk′l′(t).
Inequalities (17) and (18) imply that  Yi[jk]lk′l′(t) is equal to 1, if one unit of part-type i is moved to machine k′ in cell l′ for operation (j+1) after performing operation j on machine k in cell l. Inequalities (19) and (20) enforce Wi[jk]lk′l′(t) to be Xi(t) when Y[jk]lk′l′i(t) is equal to 1. The last constraint (21) enforces Wi[jk]lk′l′(t) to be 0, when Y[jk]lk′l′i(t) is equal to 0.For (9) which should be linearized, the conditional 0-1 requirement for variable βi(t) can be simply converted to the following set of constraints:
(22)βi(t)≤Xi(t),(23)Mβi(t)≥Xi(t),
where βi(t) are 0-1 variables and M is a large positive number. One can easily verify that (22) serve the same purpose as (9) in the model.


### 2.5. A Single Model for Cell Formation Problem

The proposed model (see (2) to (10)) can be simplified through some modifications in the formulation, in order to solve the cell formation problem, without considering the production planning issues. In this model, the variable Xi(t) is equal to Di(t). After linearization, the model can be expressed as follows:
(24)MinimizeZ=∑t=1T∑k=1KMk(t)·∑l=1Lnkl(t)+∑t=1T∑i=1I(t)Di(t)·∑j=1ji-1∑k=1K∑k′=1K∑l=1L∑l′=LLRll′·Yi[jk]lk′l′(t).
Subject to
(25)∑l=1Lδi[jk]l(t)=1,i=1,…,I,j=1,…,Ji,k=1,…,K,∀(t),(26)∑i=1I∑j=1Jiδi[jk]l(t)-nkl(t)≥0,i=1,…,I,j=1,…,Ji,k=1,…,K,l=1,…,L∀(t),(27)-δi[jk]l(t)+nkl(t)≥0,i=1,…,I,j=1,…Ji,k=1,…,K,l=1,…,L,∀(t),(28)∑k=1Knkl(t)≥LBl,k=1,…,K,∀(t),(29)∑k=1K-nkl(t)≥-UBl,k=1,…,K,∀(t),(30)δi[jk]l(t)+δi[(j+1)k′]l′(t)-2Yi[jk]lk′l′(t)≥0,i=1,…,I,j=1,…,ji-1,l,l′∈L,k,k′∈K,∀(t),(31)-δi[jk]l(t)-δi[(j+1)k′]l′(t)+Yi[jk]lk′l′(t)≥-1,i=1,…,I,j=1,…,ji-1,l,l′∈L,k,k′∈K,∀(t),(32)nkl(t)≥0,Wi[jk]lk′l′(t)≥0,Yi[jk]lk′l′(t),δi[jk]l(t),(33)nkl(t)=0,1∀i,j,l,l′,k,k′,t.


## 2.1. Problem Description

In this section, a mixed integer nonlinear programming model is developed to simultaneously solve the cell formation and production planning problems in CM systems. The objective function of this model is to minimize intercell material handling cost, machine operating cost, production set-up cost for every operation in every part, and part inventory cost. A manufacturing system which includes a number of machines to process different part-types is considered. Each part-type has a number of operations, and that must be processed as numbered respectively, in order to take the sequence of operations into account. The manufacturing system is considered in a number of time periodst, where t=1,2,…,T, with T>1. One time period could be a day, a week, or a month. Demands for different part-types are assumed to be known and deterministic. Demands may be satisfied from production in the same time period or from inventory. Back orders and shortage cost are not considered in this study. This model assumes that there is a single process plan for each part-type. Since both the quantity of different part-types to be processed by the machines and the formation of the machine cells are decision variables, nonlinear terms are presented in the objective function of the mixed integer programming model.


## 2.2. Notations

Indices:
t: time period index: t=1,…,T.
i: part-type index:  i=1,…,I(t).
j: index of operations of part-type  i:j=1,…,Ji.
l: cell index:  l=1,…,L.
k: machine index: k=1,…,K.Coefficients and Parameters:
H
i
(
t
): unit inventory holding cost of part-type i for time period t.
D
i
(
t
): known demand of part-type i for time period t.
M
k
(
t
): unit machine operating cost for machine-type k in time period t.
S
i
[
j
k
]: set-up cost to performing operation j on machine k from part-type i.
R
l
l
′: cost of moving a unit of part-type from cell l to cell l′.
L
B
l: minimum number of machines in cell l.
U
B
l: maximum number of machines in cell l.Binary Decision Variables:
(1)
β
i
(
t
)
=
{
1
,
if
part
type
i
is
processed
in
period
t
,
0
,
otherwise
,
n
k
l
(
t
)
=
{
1
,
if
one
unit
of
type
k
machine
is
placed
in
cell
l
at
time
t
,
0
,
otherwise
,
δ
i
[
j
k
]
l
(
t
)
=
{
1
,
if
operation
j
of
part-type
i
to
be
processed
by
machine
type
k
,
is
done
in
cell
l
during
time
t
,
0
,
otherwise
.
Subscripts i[jk] of variable δi[jk]l(t) indicates that machine k is required to process operation j of part-type i. This information is known from the given part process plan.Continuous Decision Variables:
X
i
(
t
): amount of part-type i to be processed in time period t,
V
i
(
t
): amount of part-type i in inventory at the end of time period t.


## 2.3. Mathematical Models Development

With the given notations, the proposed model is formulated as follows:(2)MinimizeZ=∑t=1T∑k=1KMk(t)·∑l=1Lnkl(t)+∑t=1T∑i=1I(t)Xi(t)·∑j=1ji-1∑k=1Kji∑k′=1K∑l=1L∑l′=1LRll′δi[jk]l(t)δi[(j+1)k′]l′(t)+∑t=1T-1∑i=1I(t)Hi(t)Vi(t)+∑t=1T∑l=1L∑i=1I(t)∑j=1Ji∑k=1KSi[jk]δi[jk]l(t).
Subject to:
(3)∑l=1Lδi[jk]l(t)=βi(t),i=1,…,I,j=1,…,Ji,k=1,…,Kji∀(t),(4)∑i=1I∑j=1Jiδi[jk]l(t)≥nkl(t),i=1,…,I,j=1,…Ji,k=1,…,K,l=1,…,L∀(t),(5)δi[jk]l(t)≤nkl(t),k=1,…,K,l=1,…,L∀(t),(6)LBl≤∑k=1Knkl(t)≤UBl,k=1,…,K∀(t),(7)vi(t+1)=vi(t)+Xi(t)-Di(t),i=1,…,I,t=1,…,T-1,(8)∑t=1TXi(t)=∑t=1TDi(t),i=1,2,…,I,(9)βi(t)={1,ifXi(t)>00,ifXi(t)=0,i=1,2,…,I,∀(t),(10)Xi(t)≥0,vi(t)≥0,δi[jk]l(t),βi(t),nkl(t)=0,1,∀i,j,l,l′,k,k′,t.
The objective function of the proposed model has been shown in (2), and it consists of four terms. The first term of the objective function is the machine operating cost. It is assumed that the machines can be included when they are needed and can be removed from the system when they are not required. The second term of the objective function is the intercell material handling cost. This cost function is similar to those in Atmani et al. [28] and Chen [25]. In a typical cell formation problem, the number of part-type i to be produced in time t, Xi(t), is usually considered constant. In that case, the material handling cost function will be linear. However, in this model, the term of the material handling cost is non-linear, because it has been assumed that the distances between each pair of cells are different (part-type i after completion of its operation j by machine k in cell l moves to machine k′ for its next operation, j+1, in cell l′). It is further assumed that the specifications of different part-types (e.g., size or volume of different part-types) do not influence the material handling cost. The third term is the finished goods inventory cost, and the last term of the objective function is the system set-up cost with consideration of set-up cost for each operation in each part-type. The first two cost items in the objective function are related to forming manufacturing cells, while the latter two cost items are related to production and inventory control.Constraints of the model consist of equations and inequalities (3) to (10). Equation (3) is to ensure that if operation j of part-type i will be processed by machine k in one of the cells in time period t, then the corresponding binary variable for system set-up must be 1. Inequality (4) ensures that once machine k is assigned to cell  l  in time period t, then the operations of part-types may be assigned to that machine. Inequality (5) ensures that sufficient machine capacity is assigned to each cell in time period t. Inequality (6) consists of two constraints for the upper and lower limits to the number of machines in each cell. The upper limit for the number of machines is due to the limitations of the physical space. Furthermore, there should be at least one machine in each cell, otherwise the cell will disappear. Equation (7) provides the relationship of storage levels at different time periods. In fact, in planning the production, demand of part-type i at time t should be deducted from the finished parts in storage at time t. Equation (8) implicates that the production in the entire planning horizon definitely meets the total demand. Equation (9) shows the relationship between the set-up variable βi(t) and the part processing quantity Xi(t). Equation  (10) imposes nonnegativity and integrality, respectively.


## 2.4. Model Linearization

The proposed model is a nonlinear mixed-integer programming model because of the existing two nonlinear parts including the second term of objective function (see (2)) and the seventh constraint (see (9)). In order to find a global solution, the nonlinear model should be transformed into the linear form. Hence, the linearization phase is implemented for these two parts. Consider the second term of the objective function:
(11)∑t=1T∑i=1I(t)Xi(t)·∑j=1ji-1∑k=1Kji∑k′=1Kji∑l=1L∑l′=LLRll′δi[jk]l(t)δi[(j+1)k′]l′(t).
It can be modified as follows:
(12)∑t=1T∑i=1I(t)∑j=1Ji∑k=1K∑k′=1K∑l=1L∑L′=1LRll′Xi(t)δi[jk]l(t)δi[(j+1)k′]l′(t),∑t=1T∑i=1I(t)∑j=1ji-1∑k=1K∑k′=1K∑l=1L∑L′=1LRll′[Xi(t)(δi[jk]l(t)δi[(j+1)k′]l′(t))].
In order to linearize the previous expression, let us assume that
(13)Yi[jk]lk′l′(t)=δi[jk]l(t)δi[(j+1)k′]l′(t),(14)Wi[jk]lk′l′(t)=Xi(t)Yi[jk]lk′l′(t).
These variables imply that
(15)Yi[jk]lk′l′(t)={1,ifpart-typeimovestomachinek′incelll′toperformoperation(j+1)afterperformingoperationjonmachinekincelll,0,otherwise,Wi[jk]lk′l′(t)={Xi(t),ifYi[jk]lk′l′(t)=1,0,ifYi[jk]lk′l′(t)=0.
Finally, the second term of objective function can be replaced by the following linear expression:
(16)∑t=1T∑i=1I(t)∑j=1Ji-1∑k=1K∑k′=1K∑l=1L∑L′=1LRll′Wi[jk]lk′l′(t).
Furthermore, the following constraints should be added to this model:
(17)δi[jk]l(t)+δi[(j+1)k′]l′(t)-2Yi[jk]lk′l′(t)≥0,(18)δi[jk]l(t)+δi[(j+1)k′]l′(t)-Yi[jk]lk′l′(t)≤1,(19)Wi[jk]lk′l′(t)≥Xi(t)+MYi[jk]lk′l′(t)-M,(20)Wi[jk]lk′l′(t)≤Xi(t),(21)Wi[jk]lk′l′(t)≤MYi[jk]lk′l′(t).
Inequalities (17) and (18) imply that  Yi[jk]lk′l′(t) is equal to 1, if one unit of part-type i is moved to machine k′ in cell l′ for operation (j+1) after performing operation j on machine k in cell l. Inequalities (19) and (20) enforce Wi[jk]lk′l′(t) to be Xi(t) when Y[jk]lk′l′i(t) is equal to 1. The last constraint (21) enforces Wi[jk]lk′l′(t) to be 0, when Y[jk]lk′l′i(t) is equal to 0.For (9) which should be linearized, the conditional 0-1 requirement for variable βi(t) can be simply converted to the following set of constraints:
(22)βi(t)≤Xi(t),(23)Mβi(t)≥Xi(t),
where βi(t) are 0-1 variables and M is a large positive number. One can easily verify that (22) serve the same purpose as (9) in the model.


## 2.5. A Single Model for Cell Formation Problem

The proposed model (see (2) to (10)) can be simplified through some modifications in the formulation, in order to solve the cell formation problem, without considering the production planning issues. In this model, the variable Xi(t) is equal to Di(t). After linearization, the model can be expressed as follows:
(24)MinimizeZ=∑t=1T∑k=1KMk(t)·∑l=1Lnkl(t)+∑t=1T∑i=1I(t)Di(t)·∑j=1ji-1∑k=1K∑k′=1K∑l=1L∑l′=LLRll′·Yi[jk]lk′l′(t).
Subject to
(25)∑l=1Lδi[jk]l(t)=1,i=1,…,I,j=1,…,Ji,k=1,…,K,∀(t),(26)∑i=1I∑j=1Jiδi[jk]l(t)-nkl(t)≥0,i=1,…,I,j=1,…,Ji,k=1,…,K,l=1,…,L∀(t),(27)-δi[jk]l(t)+nkl(t)≥0,i=1,…,I,j=1,…Ji,k=1,…,K,l=1,…,L,∀(t),(28)∑k=1Knkl(t)≥LBl,k=1,…,K,∀(t),(29)∑k=1K-nkl(t)≥-UBl,k=1,…,K,∀(t),(30)δi[jk]l(t)+δi[(j+1)k′]l′(t)-2Yi[jk]lk′l′(t)≥0,i=1,…,I,j=1,…,ji-1,l,l′∈L,k,k′∈K,∀(t),(31)-δi[jk]l(t)-δi[(j+1)k′]l′(t)+Yi[jk]lk′l′(t)≥-1,i=1,…,I,j=1,…,ji-1,l,l′∈L,k,k′∈K,∀(t),(32)nkl(t)≥0,Wi[jk]lk′l′(t)≥0,Yi[jk]lk′l′(t),δi[jk]l(t),(33)nkl(t)=0,1∀i,j,l,l′,k,k′,t.


## 3. Numerical Examples

Two numerical examples with different structures from the existing literature are presented in this section. The examples have been solved using LINGO 12.0, a commercially available optimization software, on a personal computer with Intel Core2 Duo T6400 @ 2.00 GHz processor and 4 GB RAM.


### 3.1. Example 1

The data used in this example has been adapted from Chen [25] with slight modifications. In this example, 3 cells, 3 time-periods, 10 part-types, and 7 machine-types are considered. The minimum and maximum numbers of machines in each cell are 1 and 5, respectively. Detailed production demand and unit inventory cost to hold each part-type are presented in Table 1. Table 2 shows machine operating costs, part-machine requirements, and refixturing costs. Machine operating costs are presented in the second column of this table. For example, it will cost 15 units to operate 1 unit of machine 1 in the system 10 units for machine 2, and so on. The 6th column of Table 2 shows that there are 2 operations for processing part 4. It also indicates that machine 4 and 7 are required to perform operations 2 and 1, respectively, for part 4. Meanwhile, intercell material handling costs are shown in Table 3.Table 1
Part processing demand and unit inventory cost for Example 1.
Part-type
1
2
3
4
5
6
7
8
9
10
Unit inventory cost
1.0
1.5
0.5
1.0
1.2
0.5
2.5
1.2
1.5
0.8
Time period,t
Part processing demand
1
22
20
18
12
23
24
22
30
19
25
2
28
16
20
24
30
22
18
28
18
14
3
36
22
30
39
32
26
16
26
33
22Table 2
Partial input data for Example 1.
Machine number
Machine cost
Part-type
1
2
3
4
5
6
7
8
9
10
Part operation requirement (upper number) and refixturing cost (lower number)
1
15
2
2
1
15
11
8
2
10
1
1
2
2
10
12
8
9
3
20
2
2
1
1
2
18
5
12
16
7
4
15
3
2
2
2
9
12
7
4
5
12
1
14
6
15
1
3
6
10
7
16
1
1
1
15
11
21Table 3
Intercell material handling cost for Example 1.
Cell number
1
2
3
1
0.0
1.0
1.4
2
1.0
0.0
1.2
3
1.4
1.2
0.0It is assumed that the specifications of time periods do not influence the production-related costs which were presented through Tables1 to 3 (e.g, there is no inflation). Considering the part-operation requirements in Table 2, in order to reduce the number of variables and constraints, the variables which can be fixed to zero were removed from the model using sparse set membership filtering technique of LINGO [29]. After fixing these variables, some constraints became redundant and were subsequently removed. LINGO solver defined the model of Example 1 as an integer linear problem (MILP) and used the branch and bound (B-and-B) method to solve it. The resulting formulation has a total of 1089 variables and 1526 constraints. The solution was achieved after 102 minutes of the solver running. The total cost of this problem (which appears as objective value in LINGO solution report) was 997.40 units. Table 4 shows the solution matrix for the cell formation problem (machines and part-types groups) in time-period 1. In addition, Table 5 presents machine cells for different time periods. The entries in this table are the machine numbers.Table 4
A solution matrix int=1 for Example 1.
Cell number
Machine number
Part-type
1
2
3
5
8
10
6
7
4
9
1
1
2
1
2
1
1
2
2
3
2
2
1
1
2
4
3
6
1
3
2
1
2
5
1
3
4
2
2
2
7
1
1
1Table 5
Cell formation of Example 1.
Time period,t
Cell 1
Cell 2
Cell 3
1
1, 2, 3, 4, 6
1, 5
4, 7
2
2, 3
7
4
3
1, 2
4, 7
2, 3From Tables4 and 5, it can be observed that multiple units of the same machine can be used in different cells. However, the usage of more than one unit of each machine-type in the same cell in neither necessary nor economical, since there is no machine capacity constraint in the model. For example, when  t=1, there are 2 units of machine-type 1 in cells 1 and 2, and 2 units of machine-type 4 in cells 1 and 3. Table 6 presents the solution of production planning problem. It shows the times and amounts of production to satisfy demands of all time periods. The sequence of parts in Table 6  the is same as that in the solution matrix for t=1 (Table 4). From Tables 2, 5 and 6, it can be observed that, for example, 22 units of part-type 7 processed in t=1 will flow from cell 3 to cell 1 to be processed by machines 7 and 4, respectively.Table 6
Part processing sequence and batch size in Example 1.
Time period,t
Part-type
1
2
3
5
8
10
6
7
4
1
50
36
68
23
30
61
72
22
36
37
2
0
0
0
30
28
0
0
18
0
0
3
36
22
0
32
26
0
0
16
39
33


### 3.2. Example 2

The data set of this example have been used from Mungwattana [12] with little modifications. In this example, 3 cells, 3 time periods, 19 part-types, and 12 machine-types are considered. The minimum and maximum numbers of machines in each cell are 3 and 9, respectively. Production demands for 19 part-types in 3 time-periods and unit inventory cost to hold each part-type are shown in Table 7. Table 8 shows machine operating costs, part-machine requirements, and refixturing costs. In addition, intercell material handling costs are presented in Table 9.Table 7
Part processing demand and unit inventory cost for Example 2.
Part-type
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
Unit inventory cost
70
140
120
135
190
56
40
104
145
80
85
90
150
60
45
67
130
65
95
t
Part processing demand
1
500
800
1000
600
600
900
700
700
400
700
400
800
1000
900
900
500
0
700
600
2
900
500
500
700
500
600
600
0
600
700
500
700
800
900
800
600
800
800
600
3
500
800
600
100
1000
700
500
600
700
0
500
1000
800
600
1000
800
700
1000
500Table 8
Partial input data for Example 2.
Machine number
Machine cost
Part-type
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
Part operation requirement (upper number) and refixturing cost (lower number)
1
1600
1
4
3
3
100
240
200
440
2
1300
1
3
1
2
200
150
250
160
3
1200
3
3
1
2
450
550
120
400
4
2000
1
2
2
2
200
200
310
200
5
1800
5
3
1
3
350
320
600
350
6
1600
3
3
3
2
1
200
430
500
270
280
7
1400
2
1
1
1
500
100
400
240
8
1100
2
1
2
3
3
1
1
200
330
300
100
340
150
150
9
2000
4
4
2
1
1
3
250
220
600
300
110
420
10
1800
2
1
2
2
1
150
400
200
320
260
11
1600
4
2
3
2
1
300
300
440
230
250
12
1400
2
2
1
2
2
300
700
100
230
420Table 9
Intercell material handling cost for Example 2.
Cell number
1
2
3
1
0
55
44
2
55
0
25
3
44
25
0The linear model of Example 2 consists of 3015 variables (including 849 integer variables) and 4421 constraints. The solver was interrupted by the authors, since it was unable to obtain the results after almost 70 hours of running. It is due to increasing the number of variables and constraints in comparison with Example 1.However, this example can be solved by the single cell formation model which was presented in Section2.5.  In this case, under the single model for the cell formation and with one time period, the model includes 663 variables and 727 constraints. The solver obtained the results after almost 6 minutes of running and objective function value was 19335. Table 10 shows the solution matrix of Example 2 (for one time period).Table 10
A solution matrix for Example 2.
Cell number
Machine number
Part-type
6
11
12
14
1
4
5
7
15
19
2
3
8
9
10
13
16
17
18
1
2
1
3
1
2
3
3
1
3
3
2
11
2
2
1
4
3
2
4
1
1
1
2
2
2
8
2
1
1
2
3
3
12
2
2
1
2
2
3
1
3
4
1
5
5
3
3
6
2
3
3
3
1
7
2
1
1
1
9
4
3
4
2
1
1
10
2
2
1
2
1


## 3.1. Example 1

The data used in this example has been adapted from Chen [25] with slight modifications. In this example, 3 cells, 3 time-periods, 10 part-types, and 7 machine-types are considered. The minimum and maximum numbers of machines in each cell are 1 and 5, respectively. Detailed production demand and unit inventory cost to hold each part-type are presented in Table 1. Table 2 shows machine operating costs, part-machine requirements, and refixturing costs. Machine operating costs are presented in the second column of this table. For example, it will cost 15 units to operate 1 unit of machine 1 in the system 10 units for machine 2, and so on. The 6th column of Table 2 shows that there are 2 operations for processing part 4. It also indicates that machine 4 and 7 are required to perform operations 2 and 1, respectively, for part 4. Meanwhile, intercell material handling costs are shown in Table 3.Table 1
Part processing demand and unit inventory cost for Example 1.
Part-type
1
2
3
4
5
6
7
8
9
10
Unit inventory cost
1.0
1.5
0.5
1.0
1.2
0.5
2.5
1.2
1.5
0.8
Time period,t
Part processing demand
1
22
20
18
12
23
24
22
30
19
25
2
28
16
20
24
30
22
18
28
18
14
3
36
22
30
39
32
26
16
26
33
22Table 2
Partial input data for Example 1.
Machine number
Machine cost
Part-type
1
2
3
4
5
6
7
8
9
10
Part operation requirement (upper number) and refixturing cost (lower number)
1
15
2
2
1
15
11
8
2
10
1
1
2
2
10
12
8
9
3
20
2
2
1
1
2
18
5
12
16
7
4
15
3
2
2
2
9
12
7
4
5
12
1
14
6
15
1
3
6
10
7
16
1
1
1
15
11
21Table 3
Intercell material handling cost for Example 1.
Cell number
1
2
3
1
0.0
1.0
1.4
2
1.0
0.0
1.2
3
1.4
1.2
0.0It is assumed that the specifications of time periods do not influence the production-related costs which were presented through Tables1 to 3 (e.g, there is no inflation). Considering the part-operation requirements in Table 2, in order to reduce the number of variables and constraints, the variables which can be fixed to zero were removed from the model using sparse set membership filtering technique of LINGO [29]. After fixing these variables, some constraints became redundant and were subsequently removed. LINGO solver defined the model of Example 1 as an integer linear problem (MILP) and used the branch and bound (B-and-B) method to solve it. The resulting formulation has a total of 1089 variables and 1526 constraints. The solution was achieved after 102 minutes of the solver running. The total cost of this problem (which appears as objective value in LINGO solution report) was 997.40 units. Table 4 shows the solution matrix for the cell formation problem (machines and part-types groups) in time-period 1. In addition, Table 5 presents machine cells for different time periods. The entries in this table are the machine numbers.Table 4
A solution matrix int=1 for Example 1.
Cell number
Machine number
Part-type
1
2
3
5
8
10
6
7
4
9
1
1
2
1
2
1
1
2
2
3
2
2
1
1
2
4
3
6
1
3
2
1
2
5
1
3
4
2
2
2
7
1
1
1Table 5
Cell formation of Example 1.
Time period,t
Cell 1
Cell 2
Cell 3
1
1, 2, 3, 4, 6
1, 5
4, 7
2
2, 3
7
4
3
1, 2
4, 7
2, 3From Tables4 and 5, it can be observed that multiple units of the same machine can be used in different cells. However, the usage of more than one unit of each machine-type in the same cell in neither necessary nor economical, since there is no machine capacity constraint in the model. For example, when  t=1, there are 2 units of machine-type 1 in cells 1 and 2, and 2 units of machine-type 4 in cells 1 and 3. Table 6 presents the solution of production planning problem. It shows the times and amounts of production to satisfy demands of all time periods. The sequence of parts in Table 6  the is same as that in the solution matrix for t=1 (Table 4). From Tables 2, 5 and 6, it can be observed that, for example, 22 units of part-type 7 processed in t=1 will flow from cell 3 to cell 1 to be processed by machines 7 and 4, respectively.Table 6
Part processing sequence and batch size in Example 1.
Time period,t
Part-type
1
2
3
5
8
10
6
7
4
1
50
36
68
23
30
61
72
22
36
37
2
0
0
0
30
28
0
0
18
0
0
3
36
22
0
32
26
0
0
16
39
33


## 3.2. Example 2

The data set of this example have been used from Mungwattana [12] with little modifications. In this example, 3 cells, 3 time periods, 19 part-types, and 12 machine-types are considered. The minimum and maximum numbers of machines in each cell are 3 and 9, respectively. Production demands for 19 part-types in 3 time-periods and unit inventory cost to hold each part-type are shown in Table 7. Table 8 shows machine operating costs, part-machine requirements, and refixturing costs. In addition, intercell material handling costs are presented in Table 9.Table 7
Part processing demand and unit inventory cost for Example 2.
Part-type
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
Unit inventory cost
70
140
120
135
190
56
40
104
145
80
85
90
150
60
45
67
130
65
95
t
Part processing demand
1
500
800
1000
600
600
900
700
700
400
700
400
800
1000
900
900
500
0
700
600
2
900
500
500
700
500
600
600
0
600
700
500
700
800
900
800
600
800
800
600
3
500
800
600
100
1000
700
500
600
700
0
500
1000
800
600
1000
800
700
1000
500Table 8
Partial input data for Example 2.
Machine number
Machine cost
Part-type
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
Part operation requirement (upper number) and refixturing cost (lower number)
1
1600
1
4
3
3
100
240
200
440
2
1300
1
3
1
2
200
150
250
160
3
1200
3
3
1
2
450
550
120
400
4
2000
1
2
2
2
200
200
310
200
5
1800
5
3
1
3
350
320
600
350
6
1600
3
3
3
2
1
200
430
500
270
280
7
1400
2
1
1
1
500
100
400
240
8
1100
2
1
2
3
3
1
1
200
330
300
100
340
150
150
9
2000
4
4
2
1
1
3
250
220
600
300
110
420
10
1800
2
1
2
2
1
150
400
200
320
260
11
1600
4
2
3
2
1
300
300
440
230
250
12
1400
2
2
1
2
2
300
700
100
230
420Table 9
Intercell material handling cost for Example 2.
Cell number
1
2
3
1
0
55
44
2
55
0
25
3
44
25
0The linear model of Example 2 consists of 3015 variables (including 849 integer variables) and 4421 constraints. The solver was interrupted by the authors, since it was unable to obtain the results after almost 70 hours of running. It is due to increasing the number of variables and constraints in comparison with Example 1.However, this example can be solved by the single cell formation model which was presented in Section2.5.  In this case, under the single model for the cell formation and with one time period, the model includes 663 variables and 727 constraints. The solver obtained the results after almost 6 minutes of running and objective function value was 19335. Table 10 shows the solution matrix of Example 2 (for one time period).Table 10
A solution matrix for Example 2.
Cell number
Machine number
Part-type
6
11
12
14
1
4
5
7
15
19
2
3
8
9
10
13
16
17
18
1
2
1
3
1
2
3
3
1
3
3
2
11
2
2
1
4
3
2
4
1
1
1
2
2
2
8
2
1
1
2
3
3
12
2
2
1
2
2
3
1
3
4
1
5
5
3
3
6
2
3
3
3
1
7
2
1
1
1
9
4
3
4
2
1
1
10
2
2
1
2
1


## 4. Performance Comparison

Several different CF problem-solving methodologies have been proposed in the literature. Likewise, various performance measures have been suggested in order to evaluate and compare the efficiency of these methodologies. Hsu [30] proposed the group capability index (GCI) as a measure of goodness and claimed that this measure maybe is more consistent in predicting the suitability of a manufacturing system for CM. GCI simultaneously considers production volume and processing time of operations factors and excludes voids (“zero” entries) from the calculation of goodness. GCI is defined by
(34)GCI=1-eοe,
where  eο is the number of exceptional elements in the machine-part matrix and e is the total number of  “one” entries in the machine-component matrix.Therefore, in this section, the CF results of the proposed model are compared with the results of rank order clustering (ROC) method [31] and direct clustering analysis (DCA) [32] methods, by means of GCI measure. Table 11 shows this comparison based on the results presented in Tables 4 and 10 and also the results of ROC and DCA methods. For the sake of concise presentation, those steps required to solve the examples with ROC and DCA methods are not described in this paper. From Table 11, it is observed that the proposed model represents significant improvements in GCI, in comparison with the ROC and DCA methods for Examples 1 and 2.Table 11
CF results of the proposed model versus the results of ROC method.
Example number
Method
e
0
e
GCI
1
ROC
6
22
72.72%
DCA
13
22
40.90%
Proposed model
0
22
100%
2
ROC
33
57
42.11%
DCA
33
57
42.11%
Proposed model
20
57
64.91%


## 5. Conclusions

In this paper, a comprehensive dynamic deterministic integrated mathematical model was developed to simultaneously solve the production planning and cell formation problems in CM systems. The overall objective function of the proposed model minimizes the intercell material handlings (with respect to the different travel distances between cells), machine operating cost finished goods inventory, and machine set-up costs (considering the machine set up cost for each operation) for CM systems. The constraints of proposed model define the relationships between variables, such as the relationship of storage levels at different time periods, and upper machine and minimum machine limits for each cell. Some numerical examples with different sizes from  the existing literature were considered to test and illustrate the proposed model.  The examples were solved by means of LINGO optimization software. In order to evaluate the performance of the proposed model, it was compared with the rank order clustering (ROC) method and direct clustering analysis (DCA) method, using group capability index (GCI) measure. It was shown that the proposed CF model has a higher and satisfactory performance.The proposed mathematical model offers the advantage of solving CF problem with high performance, while it simultaneously considers the production planning issues with sequence data. However, it can be observed that the proposed model is not suitable for solving the large scale problems. Hence, the use of heuristic methods to deal with such problems deserves further study.



---

*Source: 487694-2013-03-13.xml*