Integrated dynamic cell formation with operator assignment and inter-cell layout problems: A mathematical model

Abstract

Designing a cellular manufacturing system involves four major decisions: cell formation, cellular layout, operator assignment and cellular scheduling which should be considered, simultaneously. This article presents a new mathematical model to solve the cell formation, operator assignment and inter-cell layout problems, concurrently. The objectives of proposed model are minimization of inter–intra cell part movements, machine relocation cost and operator-related issues including hiring, firing, training and salary costs. Two numerical examples in both small and large sizes are optimally solved by the Lingo software to verify and validate the proposed mathematical model. Also, a sensitivity analysis is performed to analyze the behavior of operators in different production periods.

Introduction

Cellular manufacturing system (CMS) is an application of group technology in which parts and machines should be grouped into production cells with respect to their similarities in design, production process, shape and so on. Designing of a CMS includes four main steps, each of which can be treated as a sub problem. The first step corresponds to cell formation (CF) problem which copes with grouping parts and machines into cells for some objectives such as minimization of inter–intra cell part trips, resulting in total cost reduction, to be satisfied. The second step is related to the determination of machines and cells’ layout. In fact, optimal system efficiency depends on optimal layout of machines within cells and cells within shop floor, respectively. The third step is group scheduling. In most of the cases, the aim of this problem is minimization of total process completion time of parts. The last step which is recognized in recent years is operator assignment. Operator-related issues such as training, hiring, firing, salary and dynamic operator assignment are very essential to be discussed and this necessity is because of economical limitations in a factory. Also, dynamic cellular manufacturing system (DCMS) is a production system which deals with designing CMS over a production period with different production parameters such as demand and processing time in each period. Hence, a cell design which is optimal in a period may not be optimal in remaining periods. Four mentioned sub problems in a dynamic environment should be considered, concurrently to design a comprehensive practical CMS. In recent decade, many studies have been conducted to solve the CMS design problem which can be categorized with respect to the mentioned sub problems.

CF-related studies

Since the CF is a first step in designing CMS, many heuristic and meta-heuristics have been proposed to solve this problem, efficiently. Bagheri and Bashiri ¹ have proposed a new hybrid genetic and imperialist competitive algorithm to solve a traditional CF problem, optimally. In their mathematical model, the cell load variation has been considered. Schaller ² has proposed a mathematical model for CF problem in the presence of stochastic demands. In his research, the composition of a cell can be changed from one period to another. Five heuristic methods have been employed to solve the problem. Ameli and Arkat ³ have proposed a pure integer mathematical model to solve the CF problem considering machine reliability and alternative process routings of parts. Their research shows that the reliability consideration has significant impacts on the overall system efficiency. The integration of CF problem with production planning and system reconfiguration, considering many other production factors such as alternative process routings, operation sequence, duplicate machines, machine capacity and lot splitting, has been investigated by Kioon et al. ⁴ Also, Wu et al. ⁵ have proposed a water flow–like algorithm to solve the CF problem. Their meta-heuristic solution approach has been verified in both solution effectiveness and efficiency aspects in comparison with other solution methods, proposed in the literature. Paydar and Saidi-Mehrabad ⁶ have proposed a new bi-objective possibilistic optimization mathematical model to integrate the procurement, production and distribution planning and also they have considered various conflicting objectives simultaneously as well as the imprecise nature of some critical parameters such as customer demands and machine capacities.

In the last decade, many researchers have shown interest in integrating the CF problem with three other sub problems of CMS design.

Group layout–related studies

There have been many researches devoted to inter–intra cell layout problems. Most of these researches have considered the layout problem as a sequel to the CF problem because of the complexity of the model. Tavakkoli-Moghaddam et al. ⁷ have developed a new mathematical model to solve the inter–intra cell layout problem in the presence of stochastic demands. In their research, it is assumed that CF is first completed and known as a prior. The total cost of inter–intra cell trips has been minimized through solving the proposed model. Also, a multi-objective mathematical model to generate the layout designs for machines and cells in a CM environment has been proposed by Bazargan-Lari ⁸ and the application of the proposed model to a food manufacturing and packaging company has been demonstrated. Krishnan et al. ⁹ have investigated the inter–intra cell layout problem in a CM environment. Their research includes three basic steps: at first, a mathematical model has been proposed for grouping the machines into cells in order to minimize the total inter-cell part trips. The second step addresses two heuristic procedures to grouping the parts into cells based on machine grouping solution. Finally, a genetic algorithm has been implemented to determine the best inter–intra cell layout. Zheng et al. ¹⁰ have proposed a multi-objective-integrated optimization model that minimizes the total material handling distance and the area of the cellular layout.

CF and group layout–related studies

Some researchers have studied the CF and inter–intra cell layout determination problems, concurrently. Kia et al. ¹¹ have proposed a mathematical model to solve the joint problem of CF and inter–intra cell layout. Due to the complexity of the given problem, a simulated annealing approach has been implemented to solve the proposed model. Also, Jolai et al. ¹² have integrated the CF problem with layout problems. An electromagnetism-like meta-heuristic has been implemented to solve the problem. Wu et al. ¹³ have proposed a mathematical model which considers the CF, inter–intra cell layout and group scheduling problems, simultaneously. Since the proposed mathematical model is a completely non-deterministic polynomial-time hard (NP-hard), a genetic algorithm with two heuristic operators has been introduced. Arkat et al. ¹⁴ have proposed two mathematical models to design a CMS. The first model has been proposed based on integration of CF problem with group layout (GL) and the second model has been developed by integrating the first model with group scheduling problem. The experimental results show that the second model increases the total system efficiency. Kia et al. ¹⁵ have presented a new mixed-integer non-linear programming model for designing the GL of unequal-area facilities in a CMS in the presence of a dynamic environment.

Operator-related studies

Some researchers have also studied the operator assignment problem in a CM environment. Satoglu and Suresh ¹⁶ have proposed a goal programming technique to solve a hybrid CMS. The proposed article includes three main steps. At first, the parts with erratic demands should be selected, as special parts, to be processed in a functional layout of the shop floor. In the second step, a mathematical model has been proposed to solve the CF problem and finally, operator assignment problem has been solved using a goal programming technique. Mahdavi et al. ¹⁷ have solved the integration of CF problem with production planning and operator assignment in a dynamic environment. Also, minimization of holding and backorder, inter-cell material handling, machine and reconfiguration, hiring, firing and salary costs have been considered in their proposed mathematical model. Furthermore, Aryanezhad et al. ¹⁸ have developed a new mathematical model which deals with concurrent solving of CF and operator assignment problems. Part routing flexibility, machine flexibility and also promotion of workers from one skill level to another have been considered. Azadeh et al. ¹⁹ have considered the decision-making styles of operators and then they have proposed a new mathematical programming model for clustering parts, machines and workers, concurrently. Actually, their model includes two objectives: minimization of intracellular movements and cell establishment costs and minimization of decision-making style inconsistency among operators in each cell.

It is clear from the literature that most of the previous studies have attempted to solve only one of the four mentioned sub problems and some investigations have been conducted to solve two or three mentioned sub problems. However, as pointed by Wu et al., ¹³ Bagheri and Bashiri ²⁰ and also Logendran, ²¹ these sub problems are interrelated and the interactions between them should be regarded an optimal solution for obtaining overall CMS.

Table 1 summarizes recent researches that have dealt with two or three sub problems in CMS and their approach. It can be realized from this table that no research has been attempted to solve the CF, GL and operator assignment sub problems, concurrently. This article tries to fill the gap by proposing a mathematical model approach to these problems. The aim of the presented model is to minimize the total costs of inter–intra cell part trips, machine relocation, hiring, firing and salary of operators in a dynamic environment.

Table 1.

The summary of literature review.

Study	Types of problem				Approaches
	Cell formation	Group layout	Group scheduling	Operator assignment	Concurrent	Sequential
Tavakkoli-Moghaddam et al. 7	*	*				*
Krishnan et al. 9	*	*				*
Kia et al. 11	*	*			*
Jolai et al. 12	*	*			*
Wu et al. 13	*	*	*		*
Arkat et al. 14	*	*	*		*
Satoglu and Suresh 16	*			*		*
Mahdavi et al. 17	*			*	*
Aryanezhad et al. 18	*			*	*
Azadeh et al. 19	*			*	*
Kia et al. 15	*	*	*
Zheng et al. 10	*	*				*
Presented article	*	*		*	*

The mathematical model

Problem description and crucial assumptions

In this article, a non-linear mathematical model based on three main problems including CF, operator assignment and inter-cell layout is proposed. Hence, considering these problems, simultaneously, can increase the complexity of model, only the basic objectives of CMS including inter–intra cell part trips, hiring, firing, salary and machine relocation costs are considered. The major assumptions of the proposed model can be categorized into three groups with respect to three mentioned problems.

• CF-related assumptions.

• 1.  Each part type has a number of operations that must be processed as numbered, respectively.

• 2.  The processing times for all operations of a part type are known and deterministic.

• 3.  The relocation cost of each machine type from one cell to another between periods is constant and known. This cost is the sum of uninstalling, shifting and installing costs.

• 4.  The time required for relocation is assumed to be 0.

• 5.  The cost of inter- and intra-cell part trips, demand value and machine capacity of different cells are known.

• 6.  Equal-sized machines or cells are considered.

• 7.  Parts are moved in a batch between and within cells.

• 8.  The unit cost of an inter-cell part trip depends on the distance between each pair of cells.

• 9.  The unit cost of an intra-cell part trip is constant regardless of the distance traveled.

• 10.  Each machine can perform only one operation at a time.

• 11.  The process sequence of each part type is constant in each production period. Routing flexibility is not considered. However, the operation sequence of each part type can be different from one period to another.

• Operator assignment–related assumptions.

• 12.  An operator can be assigned to only one cell. The operator transmission between cells is not allowed.

• 13.  An operator can be assigned to more than one machine based on his or her ability (operator assignment flexibility).

• 14.  An operator can be trained to perform with specific machine in a production period. Training cost is different for each operator based on his or her learning coefficient and is known. Training is based on the production costs. For example, it is possible to train an operator to work with a machine even if there is an operator which can work with the same machine without any extra learning cost, because the salary of the second operator is higher than the first one. The training is performed between two production periods and its time effect is not considered.

• 15.  Learning effect is considered. This means that if an operator is trained to perform with a machine, he or she can be assigned to this machine in next production periods without any extra learning cost.

• 16.  An operator can be employed or fired in each period independent of other periods. This can occur in many seasonal companies especially in automobile industries. For example, in Iran, there is an automobile manufacturing company named SAIPA. This company produces specific tools and machines in each season which requires different skills. So, it requires to hire/fire operators based on its requirements in each production period.

• 17.  The training is performed between two periods and it takes zero time.

• 18.  Learning curve is not regarded explicitly in the model formulation.

• 19.  Inter-cell layout–related assumptions.

• 20.  The number of candidate locations to be a cell is determined and constant over production horizon.

• 21.  Constructing a cell in a location has no cost and it takes zero time.

• 22.  The optimal cell layout in a period may not be optimal in next periods and depends on production elements such as process sequence and demand value.

Notation

Indices and their relative upper bounds

• I number of machines

• J number of parts

• C number of machine cells

• G number of candidate locations to be a cell ( $G⩾C$ )

• T number of production periods

• ${\mathrm{OP}}_j^t$  number of operations required by part j in period t

• K number of available operators

• i, $i\prime$  index for machines ( $i=1,\dots ,I$ )

• j index for parts ( $j=1,\dots ,J$ )

• c, $c\prime$  index for machine cells ( $c=1,\dots ,C$ )

• t index for production periods ( $t=1,\dots ,T$ )

• g, $g\prime$  index for candidate locations ( $g=1,\dots ,G$ )

• d index for operations required by part j in period t ( $d=1,\dots ,{\mathrm{OP}}_j^t$ )

• k index for operators ( $k=1,\dots ,K$ )

Input parameters

• $a_{\mathrm{ki}}$  training cost for operator k to perform with machine i

$$Z_{ki}^t=\{\begin{array}{cc}1;& \mathrm{If\; worker}k\mathrm{is\; unable\; to\; perform\; with\; machine}i\mathrm{in\; first\; period}(t=1)\\ 0;& \mathrm{Otherwise}\end{array}$$

• $D_j^t$  demand value of part j in period t

• $B_j^t$  handling batch size for part j in period t

• $\mathrm{di}{s}_{\mathrm{gg}\prime }$  distances between two candidate locations $g$ and $g\prime$

$$P_{jdi}^t=\{\begin{array}{cc}1;& \mathrm{If\; operation}d\mathrm{of\; part}j\mathrm{is\; processed\; by\; machine}i\mathrm{in\; time\; period}t\\ 0;& \mathrm{Otherwise}\end{array}$$

• $W_{\mathrm{jd}}^t$  processing time of operation d of part j

• $S{a}_{\mathrm{ki}}$  salary for operator k to perform with machine i (per hour)

• $H_k$  hiring cost of operator k

• $F_k$  firing cost of operator k

• $minh$  minimum number of operators hired in each production period

• $A_1$  unit cost of inter-cell part trips

• $A_2$  unit cost of intra-cell part trips

• $A_3$  unit cost of machine relocation

• $u_c,l_c$  upper and lower machine capacities of cell c

• $u_i,l_i$  maximum and minimum number of operators required by machine i

• $u_k,l_k$  maximum and minimum number of machines which can be assigned to operator k

Decision variables

$$X_{\mathrm{ic}}^t=\{\begin{array}{cc}1;\hfill & \mathrm{If\; machine}i\mathrm{is\; assigned\; to\; cell}c\mathrm{in\; period}t\\ \multicolumn{1}{c}{0;}& \mathrm{Otherwise}\end{array}$$

$$Y_{\mathrm{cg}}^t=\{\begin{array}{cc}1;\hfill & \mathrm{If\; cell}c\mathrm{is\; constructed\; in\; location}g\mathrm{in\; period}t\\ \multicolumn{1}{c}{0;}& \mathrm{Otherwise}\end{array}$$

$$h_k^t=\{\begin{array}{cc}1;\hfill & \mathrm{If\; operator}k\mathrm{is\; hired\; in\; period}t\\ \multicolumn{1}{c}{0;}& \mathrm{Otherwise}\end{array}$$

$$r_{\mathrm{ki}}^t=\{\begin{array}{cc}1;\hfill & \mathrm{If\; operator}k\mathrm{is\; assigned\; to\; machine}i\mathrm{in\; period}t\\ \multicolumn{1}{c}{0;}& \mathrm{Otherwise}\end{array}$$

$$S_{\mathrm{kc}}^t=\{\begin{array}{cc}1;\hfill & \mathrm{If\; operator}k\mathrm{is\; assigned\; to\; cell}c\mathrm{in\; period}t\\ \multicolumn{1}{c}{0;}& \mathrm{Otherwise}\end{array}$$

$$\begin{array}{c}{Z}_{\mathrm{ki}}^t=\hfill \\ \{\begin{array}{cc}1;\hfill & \mathrm{If\; operator}k\mathrm{is\; unable\; to\; operate\; with\; machine}i\mathrm{in\; period}t\\ \multicolumn{1}{c}{0;}& \mathrm{Otherwise}\end{array}\hfill \end{array}$$

Objective function and constraints

The 0-1 mixed-integer polynomial programming model for the CMS design is presented as follows

$$\min OB=A_1{\displaystyle \sum _{t=1}^T{\displaystyle \sum _{j=1}^J{\displaystyle \sum _{d=1}^{O{P}_j^t-1}{\displaystyle \sum _{i=1}^I{\displaystyle \sum _{i^{\prime }=1}^I{\displaystyle \sum _{c=1}^C{\displaystyle \sum _{c^{\prime }=1}^C{\displaystyle \sum _{g=1}^G{\displaystyle \sum _{g^{\prime }=1}^G\left[\frac{D_j^t}{B_j}\right]di{s}_{g{g}^{\prime }}{P}_{jdi}^t{P}_{j(d+1)i^{\prime }}^t\max (X_{ic}^t{Y}_{cg}^t+X_{i^{\prime }{c}^{\prime }}^t{Y}_{c^{\prime }{g}^{\prime }}^t-1,0)}}}}}}}}}$$

(1-1)

$$\begin{array}{c}+A_2\sum _{j=1}^J\sum _{t=1}^T\sum _{d=1}^{{\mathrm{OP}}_j^t-1}\sum _{c=1}^C\left[\frac{D_j^t}{B_j}\right]\hfill \\ max(\sum _{i=1}^I{P}_{\mathrm{jdi}}^t{X}_{\mathrm{ic}}^t+\sum _{i=1}^I{P}_{j(d+1)i}^t{X}_{\mathrm{ic}}^t-1,0)\hfill \end{array}$$

(1-2)

$$+A_3{\displaystyle \sum _{t=1}^{T-1}{\displaystyle \sum _{i=1}^I{\displaystyle \sum _{c=1}^C{\displaystyle \sum _{c^{\prime }=1}^I{\displaystyle \sum _{g=1}^G{\displaystyle \sum _{g^{\prime }=1}^G\max (X_{ic}^t{Y}_{cg}^t+X_{i{c}^{\prime }}^{t+1}{Y}_{c^{\prime }{g}^{\prime }}^{t+1}-1,0)di{s}_{g{g}^{\prime }}}}}}}}$$

(1-3)

$$+\sum _{t=1}^T\sum _{c=1}^C\sum _{i=1}^I\sum _{k=1}^K{h}_k^t{r}_{\mathrm{ki}}^t{X}_{\mathrm{ic}}^t{S}_{\mathrm{kc}}^t{Z}_{\mathrm{ki}}^t{a}_{\mathrm{ki}}$$

(1-4)

$$+\sum _{t=1}^T\sum _{k=1}^K{h}_k^t{H}_k+(1-h_k^t)F_k$$

(1-5)

$$+\sum _{t=1}^T\sum _{j=1}^J\sum _{d=1}^{{\mathrm{OP}}_j^t}\sum _{i=1}^I\sum _{k=1}^K{P}_{\mathrm{jdi}}^t{D}_j^t{W}_{\mathrm{jd}}^t{r}_{\mathrm{ki}}^{t}S{a}_{\mathrm{ki}}$$

(1-6)

Subjected to

$$\sum _{c=1}^C{X}_{\mathrm{ic}}^t=1\forall i,t$$

(2)

$$\sum _{i=1}^I{X}_{\mathrm{ic}}^t⩽u_c\forall c,t$$

(3)

$$\sum _{i=1}^I{X}_{\mathrm{ic}}^t⩾L_c\forall c,t$$

(4)

$$\sum _{k=1}^K{h}_k^t⩾minh\forall t$$

(5)

$$r_{\mathrm{ki}}^t⩽h_k^t\forall k,i,t$$

(6)

$$S_{\mathrm{kc}}^t⩽h_k^t\forall k,c,t$$

(7)

$$\sum _{k=1}^K{r}_{\mathrm{ki}}^t⩽u_i\forall i,t$$

(8)

$$\sum _{k=1}^K{r}_{\mathrm{ki}}^t⩾l_i\forall i,t$$

(9)

$$\sum _{i=1}^I{r}_{\mathrm{ki}}^t⩽h_k^t{u}_k\forall k,t$$

(10)

$$\sum _{i=1}^I{r}_{\mathrm{ki}}^t⩾h_k^t{l}_k\forall k,t$$

(11)

$$r_{\mathrm{ki}}^t⩽\sum _{c=1}^C{X}_{\mathrm{ic}}^t{S}_{\mathrm{kc}}^t\forall k,i,t$$

(12)

$$\sum _{c=1}^C{S}_{\mathrm{kc}}^t=h_k^t\forall k,t$$

(13)

$$Z_{\mathrm{ki}}^{t+1}=(1-r_{\mathrm{ki}}^t)\times Z_{\mathrm{ki}}^t\forall t=1,\dots ,T-1,\forall k,i$$

(14)

$$\sum _{g=1}^G{Y}_{\mathrm{cg}}^t=1\forall t,c$$

(15)

$$\sum _{c=1}^C{Y}_{\mathrm{cg}}^t⩽1\forall t,g$$

(16)

$$r,S,h,Z,X,Y\in \{0,1\}$$

(17)

The objective function consists of two main cost statements. The first is related to parts and machine trips and the second is about the operator-related issues. The first term of objective function (1-1) minimizes the total inter-cell part trips’ cost. These trips depend on the distance between each pair of cells. So, an optimal layout of cells within shop floor results in minimum value of total inter-cell trips cost.

Term (1-2) minimizes the total intra-cell part trips cost. It is assumed that an intra-cell part trip is independent of the distances between machines.

Term (1-3) minimizes the total system reconfiguration cost. Actually, the optimal design in a production period may not be optimal in the next periods. Hence, machines can be transferred between cells, which are in different locations, in order to obtain optimal design.

Term (1-4) minimizes operators’ training costs. Term (1-5) is related to hiring and firing costs and operator’s salary is minimized using term (1-6). This cost is based on the working time of each operator.

Equation (2) is to ensure that each machine is assigned to only one cell. Machine capacities of cells are constrained by equations (3) and (4). Equation (5) determines the minimum number of operators to be employed in a period. Equations (6) and (7) state that only the employed operator can be assigned to a machine and a cell, respectively. The minimum and maximum number of operators required by each machine is constrained by equations (8) and (9), respectively. Also, the maximum and minimum number of machines assigned to an operator are restricted by equations (10) and (11), respectively. Equation (12) is to ensure that an operator can be dedicated to a machine when both are in the same cell. In other words, this constraint prohibits the operator transmission between cells. Equation (13) guarantees that an employed operator must be assigned to only one cell. Training effect is taken into account by equation (14). Equations (15) and (16) state that a cell must be constructed in only one location. Also, equation (17) states that all variables are binary.

Linearization

The mathematical model proposed in this article is a non-linear model because of terms (1-1), (1-2), (1-3), (1-4) and constraints (12) and (14). As non-linear models are much more complicate to solve and need special solvers to find an optimal solution in a reasonable computational time, the proposed model is reformulated as a pure 0-1 linear programming model by introducing some new variables with auxiliary constraints. Two general techniques are implemented, sequentially as follows:

Step 1

Consider the pure quadratic 0-1 term $Z=X_1\times X_2\times \cdots \times X_n$ where $X_i(i=1,\dots ,n)$ is a binary variable. It is obvious that Z takes value of 1 if and only if all the variables are 1 and otherwise it must be 0. Considering this mathematical point, the following method can be applied by introducing some new auxiliary constraints

$$\begin{array}{c}Z⩽X_i\forall i=1,\dots ,n\hfill \\ Z⩾\sum _{i=1}^n{X}_i-(n-1)\hfill \end{array}$$

This type of nonlinearity came into view in terms (1-1), (1-3), (1-4) and set constraints (12) and (14). So, define new binary variables ${\mathrm{XY}}_{\mathrm{icg}}^t$ , ${\mathrm{RZ}}_{\mathrm{ki}}^t$ , ${\mathrm{XS}}_{\mathrm{ikc}}^t$ and $Q_{\mathrm{ikc}}^t$ which are computed by the following equations

$$\begin{array}{c}\multicolumn{1}{c}{{\mathrm{XY}}_{\mathrm{icg}}^t=X_{\mathrm{ic}}^t{Y}_{\mathrm{cg}}^t\forall i,c,g,t}\\ \multicolumn{1}{c}{{\mathrm{RZ}}_{\mathrm{ki}}^t=r_{\mathrm{ki}}^t{Z}_{\mathrm{ki}}^t\forall i,k,t}\\ \multicolumn{1}{c}{{\mathrm{XS}}_{\mathrm{ikc}}^t=X_{\mathrm{ic}}^t{S}_{\mathrm{kc}}^t\forall i,k,c,t}\\ \multicolumn{1}{c}{Q_{\mathrm{ikc}}^t=h_k^t{\mathrm{XS}}_{\mathrm{ikc}}^t{\mathrm{RZ}}_{\mathrm{ki}}^t\forall i,k,c,t}\end{array}$$

By considering these equations, the following auxiliary constraints should also be added to the proposed model

$$2{\mathrm{XY}}_{\mathrm{icg}}^t⩽X_{\mathrm{ic}}^t+Y_{\mathrm{cg}}^t\forall i,c,g,t$$

(18)

$${\mathrm{XY}}_{\mathrm{icg}}^t⩾X_{\mathrm{ic}}^t+Y_{\mathrm{cg}}^t-1\forall i,c,g,t$$

(19)

$$2{\mathrm{RZ}}_{\mathrm{ki}}^t⩽r_{\mathrm{ki}}^t+Z_{\mathrm{ki}}^t\forall i,k,t$$

(20)

$${\mathrm{RZ}}_{\mathrm{ki}}^t⩾r_{\mathrm{ki}}^t+Z_{\mathrm{ki}}^t-1\forall i,k,t$$

(21)

$$2{\mathrm{XS}}_{\mathrm{ikc}}^t⩽X_{\mathrm{ic}}^t+S_{\mathrm{kc}}^t\forall i,k,c,t$$

(22)

$${\mathrm{XS}}_{\mathrm{ikc}}^t⩾X_{\mathrm{ic}}^t+S_{\mathrm{kc}}^t-1\forall i,k,c,t$$

(23)

$$3Q_{\mathrm{ikc}}^t⩽h_k^t+{\mathrm{XS}}_{\mathrm{ikc}}^t+{\mathrm{RZ}}_{\mathrm{ki}}^t\forall i,k,c,t$$

(24)

$$Q_{\mathrm{ikc}}^t⩾h_k^t+{\mathrm{XS}}_{\mathrm{ikc}}^t+{\mathrm{RZ}}_{\mathrm{ki}}^t-2\forall i,k,c,t$$

(25)

Step 2

The maximum function in terms (1-1), (1-2) and (1-3) can be linearized by replacing an additional variable and two auxiliary constraints as follows

$$\begin{array}{cc}minT\hfill & minZ\hfill \\ \multicolumn{1}{c}{\mathrm{St}:}& \mathrm{St}:\hfill \\ \multicolumn{1}{c}{T=max(X,0)}& \begin{array}{c}Z⩾X\hfill \\ \multicolumn{1}{c}{Z⩾0}\end{array}\hfill \end{array}$$

So, let define new binary variables $M_{\mathrm{icgi}\prime c\prime g\prime }^t$ , $N_{\mathrm{jdc}}^t$ and $E_{\mathrm{icc}\prime \mathrm{gg}\prime }^t$ which are replaced by the following equations

$$\begin{array}{c}{M}_{\mathrm{icgi}\prime c\prime g\prime }^t=max({\mathrm{XY}}_{\mathrm{icg}}^t+{\mathrm{XY}}_{i\prime c\prime g\prime }^t-1,0)\forall i,i\prime ,c,c\prime ,g,g\prime ,t\hfill \\ N_{\mathrm{jdc}}^t=max(\sum _{i=1}^I{P}_{\mathrm{jdi}}^t{X}_{\mathrm{ic}}^t+\sum _{i=1}^I{P}_{j(d+1)i}^t{X}_{\mathrm{ic}}^t-1,0)\forall j,d,c,t\hfill \\ E_{\mathrm{icc}\prime \mathrm{gg}\prime }^t=max({\mathrm{XY}}_{\mathrm{icg}}^t+{\mathrm{XY}}_{\mathrm{ic}\prime g\prime }^{t+1}-1,0)\forall i,c,c\prime ,g,g\prime ,t\hfill \end{array}$$

By these considerations, six auxiliary constraints should also be added to the proposed model as follows

$$M_{\mathrm{icgi}\prime c\prime g\prime }^t⩾{\mathrm{XY}}_{\mathrm{icg}}^t+{\mathrm{XY}}_{i\prime c\prime g\prime }^t-1\forall i,i\prime ,c,c\prime ,g,g\prime ,t$$

(26)

$$M_{\mathrm{icgi}\prime c\prime g\prime }^t⩾0\forall i,i\prime ,c,c\prime ,g,g\prime ,t$$

(27)

$$N_{\mathrm{jdc}}^t⩾\sum _{i=1}^I{P}_{\mathrm{jdi}}^t{X}_{\mathrm{ic}}^t+\sum _{i=1}^I{P}_{j(d+1)i}^t{X}_{\mathrm{ic}}^t-1\forall j,d,c,t$$

(28)

$$N_{\mathrm{jdc}}^t⩾0\forall j,d,c,t$$

(29)

$$E_{\mathrm{icc}\prime \mathrm{gg}\prime }^t⩾{\mathrm{XY}}_{\mathrm{icg}}^t+{\mathrm{XY}}_{\mathrm{ic}\prime g\prime }^{t+1}-1\forall i,c,c\prime ,g,g\prime ,t$$

(30)

$$E_{\mathrm{icc}\prime \mathrm{gg}\prime }^t⩾0\forall i,c,c\prime ,g,g\prime ,t$$

(31)

Thus, the final version of the linear 0-1 programming model can be presented as follows

$$\min OB=A_1{\displaystyle \sum _{t=1}^T{\displaystyle \sum _{j=1}^J{\displaystyle \sum _{d=1}^{O{P}_j^t-1}{\displaystyle \sum _{i=1}^I{\displaystyle \sum _{i^{\prime }=1}^I{\displaystyle \sum _{c=1}^C{\displaystyle \sum _{c^{\prime }=1}^C{\displaystyle \sum _{g=1}^G{\displaystyle \sum _{g^{\prime }=1}^G\left[\frac{D_j^t}{B_j}\right]di{s}_{g{g}^{\prime }}{P}_{jdi}^t{P}_{j(d+1)i^{\prime }}^t{M}_{icg{i}^{\prime }{c}^{\prime }{g}^{\prime }}^t}}}}}}}}}$$

(1-7)

$$+A_2\sum _{j=1}^J\sum _{t=1}^T\sum _{d=1}^{{\mathrm{OP}}_j^t-1}\sum _{c=1}^C\left[\frac{D_j^t}{B_j}\right]N_{\mathrm{jdc}}^t$$

(1-8)

$$+A_3\sum _{t=1}^{T-1}\sum _{i=1}^I\sum _{c=1}^C\sum _{c\prime =1}^I\sum _{g=1}^G\sum _{g\prime =1}^G{E}_{\mathrm{icc}\prime \mathrm{gg}\prime }^t\mathrm{di}{s}_{\mathrm{gg}\prime }$$

(1-9)

$$+\sum _{t=1}^T\sum _{c=1}^C\sum _{i=1}^I\sum _{k=1}^K{Q}_{\mathrm{ikc}}^t{a}_{\mathrm{ki}}$$

(1-10)

$$+\sum _{t=1}^T\sum _{k=1}^K{h}_k^t{H}_k+(1-h_k^t)F_k+$$

(1-5)

$$+\sum _{t=1}^T\sum _{j=1}^J\sum _{d=1}^{{\mathrm{OP}}_j^t}\sum _{i=1}^I\sum _{k=1}^K{P}_{\mathrm{jdi}}^t{D}_j^t{W}_{\mathrm{jd}}^t{r}_{\mathrm{ki}}^{t}S{a}_{\mathrm{ki}}$$

(1-6)

Subjected to:

Unaltered set constraints (2)–(11), (13), (15) and (16); new auxiliary constraints (18)–(31) and also:

Set constraint (12) is replaced by

$$r_{\mathrm{ki}}^t⩽\sum _{c=1}^C{\mathrm{XS}}_{\mathrm{ikc}}^t\forall k,i,t$$

(32)

Set constraint (14) is replaced by

$$Z_{\mathrm{ki}}^{t+1}=Z_{\mathrm{ki}}^t-{\mathrm{RZ}}_{\mathrm{ki}}^t\forall t=1,\dots ,T-1,\forall k,i$$

(33)

Set constraint (17) is replaced by

$$r,X,S,h,Y,Z,\mathrm{XY},\mathrm{XS},\mathrm{RZ},Q,M,N,E\in \{0,1\}$$

(34)

The total number of variables and constraints in the proposed linear 0-1 programming model are reported in Tables 2 and 3, respectively. In Table 3, the constraints related to equation (34) are not counted.

Table 2.

The number of binary variables in the linearized model.

Variable	Count	Variable	Count	Variable	Cont
$r_{\mathrm{ki}}^t$	$K\times I\times T$	$Y_{\mathrm{cg}}^t$	$C\times G\times T$	$M_{\mathrm{icgi}\prime }^t$	$I^2\times C^2\times G^2\times T$
$S_{\mathrm{kc}}^t$	$K\times C\times T$	${\mathrm{XY}}_{\mathrm{icg}}^t$	$I\times C\times G\times T$	$N_{\mathrm{jdc}}^t$	$J\times {\mathrm{OP}}_j^t\times C\times T$
$h_k^t$	$K\times T$	${\mathrm{RZ}}_{\mathrm{ki}}^t$	$K\times I\times T$	$E_{\mathrm{icc}\prime }^t$	$I\times C^2\times G^2\times T$
$Z_{\mathrm{ki}}^t$	$K\times I\times T$	${\mathrm{XS}}_{\mathrm{ikc}}^t$	$I\times K\times C\times T$
$X_{\mathrm{ic}}^t$	$I\times C\times T$	$Q_{\mathrm{ikc}}^t$	$I\times K\times C\times T$
$\begin{array}{c}\multicolumn{1}{c}{\mathrm{SUM}=3(K\times I\times T)+(K\times C\times T)+(K\times T)+(I\times C\times T)+(C\times G\times T)+(I\times C\times G\times T)}\\ +2(I\times K\times C\times T)+(I^2\times C^2\times G^2\times T)+(J\times {\mathrm{OP}}_j^t\times C\times T)+(I\times C^2\times G^2\times T)\hfill \end{array}$

Table 3.

The number of constraints in the linearized model.

Equation	Count	Equation	Count	Equation	Count
(2)	$I\times T$	(16)	$G\times T$	(29)	$J\times {\mathrm{OP}}_j^t\times C\times T$
(3)	$C\times T$	(18)	$I\times C\times G\times T$	(30)	$I\times C^2\times G^2\times T$
(4)	$C\times T$	(19)	$I\times C\times G\times T$	(31)	$I\times C^2\times G^2\times T$
(5)	$T$	(20)	$I\times K\times T$	(32)	$K\times I\times T$
(6)	$K\times I\times T$	(21)	$I\times K\times T$	(33)	$K\times I\times (T-1)$
(7)	$K\times C\times T$	(22)	$I\times C\times K\times T$
(8)	$I\times T$	(23)	$I\times C\times K\times T$
(9)	$I\times T$	(24)	$I\times C\times K\times T$
(10)	$K\times T$	(25)	$I\times C\times K\times T$
(11)	$K\times T$	(26)	$I^2\times C^2\times G^2\times T$
(13)	$K\times T$	(27)	$I^2\times C^2\times G^2\times T$
(15)	$C\times T$	(28)	$J\times {\mathrm{OP}}_j^t\times C\times T$
$\begin{array}{c}\multicolumn{1}{c}{\mathrm{SUM}=3(I\times T)+3(C\times T)+T+5(K\times I\times T)+(K\times C\times T)+3(K\times T)+(G\times T)}\\ +3(I\times C\times G\times T)+7(I\times C\times K\times T)+2(I^2\times C^2\times G^2\times T)+2(J\times {\mathrm{OP}}_j^t\times C\times T)\hfill \\ +2(I\times C^2\times G^2\times T)+(K\times I\times (T-1))+\mathrm{number\; of\; constraints\; related\; to\; equation}(34)\hfill \end{array}$

Numerical illustration

In order to verify and validate the proposed model, two examples in small and large sizes are solved by branch-and-bound (B&B) approach using Lingo 8.0 software which have run on a PC including Core i5 and 1 GB RAM.

Example 1. The first example is a small-sized problem including two cells, four machines, five available operators, two production periods and four parts. Table 4 illustrates the part machine–related information. In this table, the demand value of each part, batch size of transmission and also processing time of each operation of parts are reported. The operator machine–related information including capabilities of operators in working with different machines, training cost, salary, hiring and firing costs are shown in Tables 5–8. For example, as shown in Table 5, operator 5 is able to perform with machines 1 and 3. Also, the number of operators required by each machine is $2(L_i=2,U_i=2)$ . Table 9 shows the distance between candidate cell locations. Moreover, the minimum and maximum machine capacities of cells are 1 and 2, respectively ( $L_c=1,U_c=2$ ).

Table 4.

The input information of part-machine matrix of instance 1.

Parts	Period 1				Period 2
	Process sequence	Processing time of each operation (W)	Demand ( $D_j^1$ )	Batch size	Process sequence	Processing time of each operation (W)	Demand ( $D_j^2$ )	Batch size
1	1-4-3	0.2, 0.1, 0.05	100	10	4-2	0.2, 0.07	200	10
2	1-3	0.2, 0.05	60	10	4-2-3-1	0.2, 0.1, 0.08, 0.05	160	10
3	4-2-1	0.15, 0.1, 0.05	80	10	4-2-3	0.15, 0.1, 0.05	180	10
4	2-1-3	0.1, 0.08, 0.05	90	10	3-1-2-4	0.15, 0.1, 0.08, 0.05	20	10

Table 5.

Capabilities of operators working with different machines (1 − Z)—instance 1.

Operators	Machine
	1	2	3	4
1	0	0	1	1
2	0	1	0	0
3	0	0	1	0
4	0	1	0	0
5	1	0	1	0

Table 6.

Training cost of operators to learn working with different machines (a)—instance 1.

Operators	Machine
	1	2	3	4
1	7	6	0	0
2	5	0	4	6
3	3	3	0	5
4	5	0	3	4
5	0	5	0	5

Table 7.

Salary of operators working with different machines (Sa)—instance 1.

Operators	Machine
	1	2	3	4
1	12	11	9	10
2	9	12	10	11
3	10	9	13	14
4	11	16	9	12
5	12	11	11	11

Table 8.

Hiring (H) and firing (F) costs, maximum and minimum number of machines to be assigned for each operator—instance 1.

Operators	Hiring cost	Firing cost	Uk	Lk
1	20	15	2	1
2	17	15	2	1
3	20	10	2	1
4	18	15	2	1
5	15	12	2	1

Table 9.

Distance between cell locations (Dis)—instance 1.

From	To
	1	2	3
1	0	5	7
2	5	0	2
3	7	2	0

The results are described in Tables 10 and 11, respectively.

Table 10.

Inter-cell layout and machine grouping instance 1.

Cells	Period 1		Period 2
	Cell location	Machines	Cell location	Machines
1	3	1, 2	2	2, 4
2	2	4, 3	3	1, 3

Table 11.

Operator assignment based on cell formation solution for instance 1.

Operators	Machines (Period 1)				Machines (Period 2)
	1	2	3	4	1	2	3	4
1			*	*				*
2	*	*			*		*
3	*	*				*
4					*		*
5			*	*		*		*

Hence, the objective function and also problem assumptions are different from existing articles; the objective value cannot be compared with previous studies. However, the value of 879.6 is obtained for this example. As shown in Table 11, operator 3 is assigned to machine 2 by training cost value of 3. It is realized from Table 10 that operator 4 can be assigned to this machine without any training cost. But for training operator 3 to perform with this machine, the salary value decreases 8 units per hour (Table 7). So, operator 4 is not employed in the second period.

Figure 1 illustrates the schematic view of optimal production plan obtained for this example.

Figure 1.

The schematic view of example 1.

Example 2. This example includes 7 machines, 3 cells, 8 parts, 10 available operators and 2 production periods. The input-related information is given in Tables 12–18. Moreover, the minimum and maximum operators required by each machine are $2(L_i=2,U_i=2)$ , and also the minimum and maximum machine capacities of each cell are 1 and 3, respectively ( $L_c=1,U_c=3$ ).

Table 12.

The input information of part-machine matrix of Example 2 (Period 1).

Parts	Process sequence	Processing time of each operation (W)	Demand ( $D_j^1$ )	Batch size
1	1-3-4-2-7-6	0.6, 0.3, 0.5, 0.7, 0.5, 0.4	90	10
2	5-6	0.1, 0.3	100	10
3	6-5-2-7-4-3	0.6, 0.1, 0.2, 0.2, 0.6, 0.6	20	10
4	2-4-5	0.7, 0.3, 0.6	100	10
5	1-2-7-5-3	0.5, 0.7, 0.5, 0.5, 0.5	70	10
6	1-2-5	0.1, 0.4, 0.3	10	10
7	7-6-1-4-7-5-3-2	0.1, 0.4, 0.2, 0.5, 0.1 0.7, 0.6, 0.6	30	10
8	5-2-7-6-4-3-7	0.1, 0.1, 0.4, 0.5, 0.1, 0.7, 0.4	60	10

Table 13.

The input information of part-machine matrix of Example 2 (Period 2).

Parts	Process sequence	Processing time of each operation (W)	Demand ( $D_j^1$ )	Batch size
1	2-5	0.7, 0.3	20	10
2	7-6	0.5, 0.4	50	10
3	6-7	0.1, 0.2	100	10
4	5-7-3-7	0.1, 0.5, 0.3, 0.5	80	10
5	6-1-7	0.2, 0.6, 0.5	100	10
6	5-3-7-1	0.6, 0.2, 0.6, 0.2	70	10
7	6-3-5-2-7-1	0.3, 0.6, 0.7, 0.6, 0.4, 0.4	10	10
8	5-1-2-7-3-7	0.1, 0.5, 0.2, 0.1, 0.4, 0.1	90	10

Table 14.

Capabilities of operators working with different machines for Example 2 (1 − Z).

Operators	Machine
	1	2	3	4	5	6	7
1	1	0	0	0	0	1	0
2	0	1	0	1	1	0	0
3	1	1	0	0	0	0	0
4	0	0	0	0	0	0	0
5	1	0	0	0	0	0	0
6	0	1	0	0	0	0	1
7	1	1	0	0	0	0	0
8	0	0	0	0	0	1	0
9	1	1	0	0	0	0	0
10	0	1	0	0	0	0	0

Table 15.

Training cost of operators to learn working with different machines for Example 2 (a).

Operators	Machine
	1	2	3	4	5	6	7
1	0	7	9	5	6	0	6
2	8	0	9	0	0	4	5
3	0	0	9	4	6	4	6
4	7	6	8	3	6	3	4
5	0	7	8	5	6	4	6
6	6	0	9	4	6	3	0
7	0	0	7	5	6	4	5
8	6	5	9	5	6	0	4
9	0	0	9	4	6	4	6
10	6	0	7	3	6	3	4

Table 16.

Salary of operators working with different machines for Example 2 (Sa).

Operators	Machine
	1	2	3	4	5	6	7
1	9	5	8	1	7	10	7
2	10	9	4	5	2	6	5
3	2	2	7	4	2	2	4
4	10	5	2	8	5	2	9
5	7	10	8	8	10	3	6
6	1	8	1	2	4	9	6
7	3	10	3	5	6	3	10
8	6	7	1	5	3	9	3
9	10	1	1	7	8	3	8
10	10	9	9	8	3	10	8

Table 17.

Hiring (H) and firing (F) costs, maximum and minimum number of machines to be assigned for each operator for Example 2.

Operators	Hiring cost	Firing cost	Uk	Lk
1	100	80	3	1
2	100	80	3	1
3	80	60	3	1
4	40	20	3	1
5	30	10	3	1
6	40	20	3	1
7	50	20	3	1
8	50	20	3	1
9	50	20	3	1
10	50	25	3	1

Table 18.

Distance between cell locations (Dis) for Example 2.

From	To
	1	2	3
1	0	5	7
2	5	0	2
3	7	2	0

Table 19 illustrates the optimal layout of cells in periods 1 and 2 and also machine grouping solution. Since a large value of machine relocation cost has been considered, it is predictable that machines are not moved between cells.

Table 19.

Inter-cell layout and machine grouping obtained for Example 2.

Cells	Period 1		Period 2
	Cell location	Machines	Cell location	Machines
1	3	1, 2, 4	1	6
2	2	3, 5, 7	3	1, 2, 4
3	1	6	2	3, 5, 7

Tables 20 and 21 show the optimal assignment of operators to machines in both periods 1 and 2, respectively. In order to obtain an optimal solution, operators 1, 2, 4, 5, 6 and 8 are trained to work with machines 4, (3, 7), 6, 6, (1, 4) and (3, 7), respectively. Also from Tables 20 and 21, it can be realized that operators 7 and 10 in Period 1 and operators 1, 7 and 10 in Period 2 are not employed. The objective value obtained for this example is 2311.

Table 20.

Operator assignment in Period 1 based on cell formation solution obtained for Example 2.

Operators	Machines
	1	2	3	4	5	6	7
1				*
2			*		*		*
3	*	*
4						*
5						*
6	*			*
7
8			*		*		*
9		*
10

Table 21.

Operator assignment in Period 2 based on cell formation solution obtained for Example 2.

Operators	Machines
	1	2	3	4	5	6	7
1
2			*		*		*
3	*	*		*
4						*
5						*
6	*			*
7
8			*		*		*
9		*
10

Since this example is a large-sized problem, the optimal solution is obtained after 1416 min. However, the computational time of the first example is 1 min. As pointed by Dimopoulos and Zalzala, ²² the CF problem is NP-hard. This article investigates the integrating CF problem with operator assignment and inter-cell layout problems. So because of the complexity of the given model, solving the model in a reasonable computational time is almost intractable.

Conclusion

In this article, integration of CF problem with inter-cell layout and operator assignment problems in a dynamic CM environment is investigated. A new mathematical model is proposed based on consideration of these three sub problems of CMS design, concurrently. To validate and verify the proposed mathematical model, two small- and large-sized numerical examples are generated randomly and have been solved using Lingo 8 software. However, since the proposed model is an NP-hard model such that solving a large-sized problem in a reasonable computational time is intractable, a meta-heuristic algorithm can be beneficial in improving time requirements. Also according to the provided framework, considering many other production concepts such as machine reliability, machine duplication and also intra-cell layout can be interesting fields for future research.