1 Introduction

Setup time reduction, work-in-process inventory reduction, material handling cost reduction, machine utilization improvement, and quality improvement are some of the benefits which have been reported by implementation of cellular manufacturing (CM). The design steps of a cellular manufacturing system (CMS) consists of: (1) cell formation (CF) (i.e., grouping parts with similar processing requirements into part families and clustering machines into machine cells), (2) group layout (GL) (i.e., arranging machines within each cell, called intra-cell layout, and cells in connection with one another, called inter-cell layout), (3) group scheduling (GS) (i.e., scheduling part families and machine groups), and (4) resource allocation (i.e., assigning tools, human and material resources) [20].

This paper investigates the effects of lot splitting feature on the CM design under a dynamic environment, in which the product mix and part demands vary during a multi-period planning horizon and necessitate reconfigurations of cells to form cells efficiently for successive periods. This type of the model is introduced as the dynamic cellular manufacturing system (DCMS) by Rheault et al. [15]. Drolet et al. [6] developed a stochastic simulation model and indicated that DCMSs are generally more efficient than classical CMSs or job shop systems, especially with respect to performance measures (e.g., throughput time, work-in-process, tardiness and the total marginal cost for a given horizon).

Since a comprehensive literature review related to dynamic issues in designing a CMS has been carried out by Kia et al. [9, 12], the authors mention only studies which have been implemented in the area of the DCMS assessing the effects of a lot splitting feature on the CMS design. Furthermore, the readers interested in a comparative review on the DCMS literature are referred to Kia et al. [10] and Shirazi et al. [16] as they have carried out a comprehensive literature review related to DCMS by presenting a list of important features proposed for the CM design, counting different conflicting objectives for multi-objective modeling in CMSs and summarizing recent studies of DCMS issue.

Wagner and Ragatz [19] investigated the benefits of lot splitting and studied the impact of lot splitting that varies with the amount of setup times. In addition, they considered the effect of the transfer batch size on the lot splitting performance. Süer et al. [18] presented four mathematical modeling formulations to consider setup times and lot-splitting decisions for minimizing the number of tardy jobs in identical parallel machine scheduling. Süer and Bera [17] extended the previous work, in which a product could be assigned to only one of its feasible cells. The impact of lot-splitting was also discussed in terms of setup times. Mathematical models proposed in the previous work were modified to allow for lot-splitting and consider setup times. Lockwood et al. [14] examined CM scheduling in the presence of a lot splitting feature. In addition, they employed various scheduling policies to analyze the underlying principles of the synchronous manufacturing philosophy. They designed exhaustive and non-exhaustive scheduling heuristics simultaneously at bottleneck and non-bottleneck work centers. Their results indicated that, under certain conditions, performing additional set-ups before the bottleneck can improve the due date performance without an adverse effect on average flow time.

Defersha and Chen [2, 3] proposed comprehensive mathematical models incorporating alternative routings, lot splitting, sequence of operations, multiple units of identical machines, machine capacity, operation cost, setup cost, cell size limits, and machine adjacency and other constraints. Balakrishnan and Cheng [1] showed that the corresponding costs were incurred by reconfiguring cells, such as moving machines, installing or uninstalling machines, lost production time and relearning.

Huang [7] analyzed a job-shop scheduling problem with a lot splitting feature, which minimized the weighted total of stock, machine idleness and handling costs. Kensen et al. [8] considered the case, in which there were multiple jobs with different processing sequences in virtual manufacturing cells (VMCs). Multiple machine types were also considered with identical duplicates, which were distributed through the shop floor. Minimizing the makespan and total travelling distance were two scheduling objectives. Two mixed-integer linear programming (MILP) formulations were developed with and without batch splitting. Computational results illustrated that batch splitting leads to more desirable system performance while it increases the computational time.

The aims of this study are twofold. The first one is to formulate a new mathematical model with an extensive coverage of important manufacturing features including alternative process routings, operation sequence, production volume of parts, duplicate machines, machine capacity, batch size-based processing time, batch size-based production lost rate, part movements in batches, learning effect and machine relocation. The main purpose of the developed model is to assess the effects of lot splitting feature on the performance of a DCMS regarding to the burdened costs of processing part operations, idleness of cells and machines, inter-cell movements, splitting production lots, machine relocation, machine overhead, production lost, and dispersing machines among cells. The main constraints of the formulated model are part processing requirements, demand satisfaction, machine availability, maximal and minimal cell size, machine time-capacity, machine relocation, and order-based creation of production lots. Some linearization procedures are employed to transform the proposed MINLP into a linear counterpart. The second aim is to design an efficient SA algorithm with a matrix-based solution representation is designed, in which a heuristic procedure creates a good initial solution and mutation operators explore the solution space for solving the presented mathematical model because of its NP-hardness.

An illustrative numerical example is solved along with a sensitivity analysis by the GAMS software (CPLEX solver) as an optimization package to assess the effects of lot splitting feature in designing a DCMS and analyze the model sensitivity. Additionally, several numerical examples are solved using the extended SA to verify the efficiency of the developed algorithm. Furthermore, the efficiency of the SA algorithm is shown by comparing its results to those found in examples solved by GAMS. The results show the efficiency of SA in reaching good solutions in terms of the objective function value and computational time.

The remainder of this paper is organized as follows. In Sect. 2, a new mathematical model is presented to assess the effects of a lot splitting feature in designing a DCMS. The linearization procedures are also given in this section. The SA algorithm is developed in Sect. 3. Section 4 solves the test problems in order to investigate the features of the presented model, analyze the model sensitivity and show the performance of the developed SA algorithm. Finally, this paper ends with conclusions in Sect. 5.

2 Mathematical model and problem descriptions

2.1 Model assumptions

In this section, the integrated problem is formulated as an MINLP model to minimize the total costs of idleness of cells and machines, parts inter-cell movements, machine operations, machine relocation, machine overhead, production lost, splitting production lots and dispersing machines among cells under the following assumptions:

  1. 1.

    Each part type has a number of operations that are processed based on its operation sequence.

  2. 2.

    The demand for each part type in each period is known.

  3. 3.

    Inter-cell movements impose different costs for different parts in each period.

  4. 4.

    The limited capacity of each machine type expressed in hours during each time period is constant over the planning horizon.

  5. 5.

    The overhead cost of each machine type involving maintenance and other constant costs such as energy cost and general service is known. This cost is required for each machine in each period only if that machine is utilized on the cells to process part-operations.

  6. 6.

    The maximum number of available machines to be utilized in each period is known.

  7. 7.

    The variable cost which is burdened by production of parts for each machine type is depended on the number of parts allotted to that machine.

  8. 8.

    The number of cells is specified in advance. Also, the maximum and minimum of the cell size is known.

  9. 9.

    Cell reconfiguration involves transferring machines between cells because of changing capacity requirements in successive periods. The reconfiguration cost of cells is calculated in terms of the number of machines relocated between cells.

  10. 10.

    All machine types are assumed to be multi-purposed ones, which are capable of processing one or more operations. Each operation of a part can be processed on different machine types with different processing times and costs.

  11. 11.

    As the lot splitting is allowed, a part operation can be distributed among several machines which are capable to process that operation within the same cell or even in different cells.

  12. 12.

    The dispersing cost is considered for assigning duplicates of a machine type to different cells.

  13. 13.

    The learning effect feature associates the processing time with the amount of the assigned parts.

  14. 14.

    To reduce the underutilization, idleness costs of machines and cells are included.

  15. 15.

    Lost costs due to splitting the production lots of a part among machines are calculated based on the number of defined lots for that part.

  16. 16.

    To regard supervision costs enforced by tracking production lots, splitting costs for each part type are incorporated.

  17. 17.

    In order to analyze the influence of specialization degree of parts on production lost rate, the parts are divided into two general groups: (1) the specialized parts whose production times and the relevant costs unit are higher, the operators need higher skills and experience, the processing demands high specialization and sensitivity, as a result, the production lost cost is very high, and (2) the conventional parts whose production lots have more normal range in terms of production time. Also, the type of the production is in an average specialization degree and consequently, the workers will acquire sufficient skills faster and the wastes will be declined. In addition, in the case of production lost as a result of splitting the production lots, low costs will be incurred regarding their low production cost.

  18. 18.

    A parameter is considered for a batch size of each part type, in which average processing time and losses mean are defined.

Sets

\(p=\{ 1,2,...,P\}\) :

Index set of part types

\(j=\{ 1,2,...,OP\}\) :

Index set of operations

\(m=\{ 1,2,...,M\}\) :

Index set of machine types

\(c=\{ 1,2,...,C\}\) :

Index set of cell types

\(h=\{ 1,2,...,H\}\) :

Index set of time periods

\(i=\{ 1,2,...,{I_p}\}\) :

Index number of split batch

Model parameters

\({\alpha _{mh}}\) :

Overhead cost of machine type m in period h

\({\lambda _{ph}}\) :

Inter-cell material handling cost for part type p in period h

\({\delta _{mh}}\) :

Relocation cost of machine type m in period h

\({\beta _{mh}}\) :

Processing cost of machine type m per unit time in period h

\({\sigma _{mh}}\) :

Idleness cost of machine type m per unit time in period h

\({\eta _h}\) :

Idleness cost of a cell per unit time in period h

\({v_{jph}}\) :

Lost cost of operation j of part type p in period h

\({T_m}\) :

Capacity of one duplicate of machine type m in terms of hour

M :

An arbitrary big positive number

D ph :

Demand for part type p in period h

UM :

Upper cell size limit for each cell

LM :

lower cell size limit for each cell

\({t_{jpm}}\) :

Processing time of operation j of part type p on machine type m

r jpm :

1 if operation j of part p can be processed on machine type m; 0 otherwise

\(A{v_{mh}}\) :

Available number of machine type m in period h

\({\varphi _{ijp}}\) :

Losses percentage of production lot number i of operation j of part type p

\({n_p}\) :

Batch size of part type p in which average processing time and losses mean is defined

\({O_p}\) :

Maximum number of operations of part type p

\({\varepsilon _{ip}}\) :

Learning effect factor based on the i-th split batch decreasing processing time of part type p

\({\gamma _{ph}}\) :

Split cost for part type p in period h

\({\mu _m}\) :

Dispersing cost for machine type m

Decision variables

Z jpmch :

Number of operation j of part type p that is processed on machine type m in cell c in period h

X jpmch :

1 if operation j of part p is processed on machine m in period h; 0 otherwise

\({N_{mch}}\) :

Number of machine type m assigned to cell c in period h

\(K_{{mch}}^{+}\) :

Number of machine type m added to cell c in period h

\(K_{{mch}}^{ - }\) :

Number of machine type m removed from cell c in period h

$$L{N_{mch}}=\left\{ {\begin{array}{*{20}{l}} 1&{{If\,machine}\,m{\,is\,utilized\,in\,cell}\,c{\,in\,period}\,h{;}} \\ 0&{{0\,otherwise}} \end{array}} \right.$$
$$L{N'_{mh}}=\left\{ {\begin{array}{*{20}{l}} 1&{{If\,machine}\,m{\,is\,utilized\,in\,period}\,h{;}} \\ 0&{{0\,otherwise}} \end{array}} \right.$$
$${l_{ijpmch}}=\left\{ {\begin{array}{*{20}{l}} 1&\begin{gathered} {If\,the}\,i{th\,batch\,is\,created\,for\,processing\,operation}\,j{\,of\,part}\,p{\,on\,machine\,m} \hfill \\ {\,assigned\,to\,cell}\,c{\,in\,period\,}h \hfill \\ \end{gathered} \\ 0&{{Otherwise}} \end{array}} \right.$$
\({s_{ijpmch}}\) :

Auxiliary variable

\({L_{jpmch}}\) :

Auxiliary variable

2.2 Mathematical model

The mathematical model is now formulated as an MINLP one:

$$\min \;Z={Z_1}+{Z_2}+{Z_3}+{Z_4}+{Z_5}+{Z_6}+{Z_7}+{Z_8}+{Z_9}$$

s.t.

$${Z_1}=\sum\limits_{h=1}^H {\sum\limits_{c=1}^C {\sum\limits_{m=1}^M {{N_{mch}}{\alpha _{mh}}} } }$$
(1)
$${Z_2} \geqslant \sum\limits_{m=1}^M {({T_m}{N_{mch}} - \sum\limits_{p=1}^P {\sum\limits_{j=1}^{OP} {\sum\limits_{i=1}^I {({n_p}{l_{ijpmch}}} +}\, } } ({Z_{jpmch}} - {n_p}{L_{jpmch}}){s_{ijpmch}}){\varepsilon _{ip}}{t_{jpm}}){\eta _h}\quad \forall h,c$$
(2)
$${Z_3} \geqslant \sum\limits_{c=1}^C {({T_m}{N_{mch}} - \sum\limits_{p=1}^P {\sum\limits_{j=1}^{OP} {\sum\limits_{i=1}^I {({n_p}{l_{ijpmch}}} +}\, } } ({Z_{jpmch}} - {n_p}{L_{jpmch}}){s_{ijpmch}}){\varepsilon _{ip}}{t_{jpm}}){\sigma _{mh}}\quad \forall h,m$$
(3)
$${Z_4}=\sum\limits_{h=1}^H {\sum\limits_{c=1}^C {\sum\limits_{m=1}^M {(K_{{mch}}^{+}+K_{{mch}}^{ - })} } } {\delta _{mh}}$$
(4)
$${Z_5}=\sum\limits_{h=1}^H {\sum\limits_{m=1}^M {(\sum\limits_{c=1}^C {L{N_{mch}} - L{{N'}_{mh}}){\mu _m}} } }$$
(5)
$${Z_6}=\sum\limits_{h=1}^H {\sum\limits_{c=1}^C {\sum\limits_{m=1}^M {\sum\limits_{p=1}^P {\sum\limits_{j=1}^{OP} {\sum\limits_{i=1}^{{I_p}} {({n_p}{l_{ijpmch}}} +} } } } } ({Z_{jpmch}} - {n_p}{L_{jpmch}}){s_{ijpmch}}){\varepsilon _{ip}}{t_{jpm}}{\beta _{mh}}$$
(6)
$$Z_{7} = \left( {\frac{1}{2}} \right)\sum\limits_{{h = 1}}^{H} {\sum\limits_{{c = 1}}^{C} {\sum\limits_{{p = 1}}^{P} {\sum\limits_{\begin{subarray}{l} \;\,j = 1 \\ j < OP \end{subarray} }^{{OP}} {\left| {\sum\limits_{{m = 1}}^{M} {Z_{{(j + 1)pmch}} - } Z_{{jpmch}} } \right|} } } } \lambda _{{ph}}$$
(7)
$${Z_8}=\sum\limits_{h=1}^H {\sum\limits_{c=1}^C {\sum\limits_{m=1}^M {\sum\limits_{p=1}^P {\sum\limits_{j=1}^{OP} {\sum\limits_{i=1}^{{I_p}} {({n_p}{l_{ijpmch}}} +} } } } } ({Z_{jpmch}} - {n_p}{L_{jpmch}}){s_{ijpmch}}){\varphi _{ijp}}{v_{jph}}$$
(8)
$${Z_9}=\sum\limits_{h=1}^H {(\sum\limits_{p=1}^P {(\sum\limits_{m=1}^M {\sum\limits_{c=1}^C {\sum\limits_{j=1}^{OP} {{X_{jpmch}}) - {O_p}){\gamma _{ph}}} } } } }$$
(9)

s.t.

$$\sum\limits_{p=1}^P {\sum\limits_{j=1}^{OP} {\sum\limits_{i=1}^{{I_p}} {({n_p}{l_{ijpmch}}} } } +({Z_{jpmch}} - {n_p}{L_{jpmch}}){s_{ijpmch}})\,{\varepsilon _{ip}}{t_{jpm}} \leqslant {T_m}{N_{mch}}\quad \forall m,c,h$$
(10)
$$\sum\limits_{c=1}^C {{N_{mch}}} \leqslant A{v_{mh}}\quad \forall m,h$$
(11)
$$\sum\limits_{m=1}^M {{N_{mch}}} \leqslant UM\quad \forall c,h$$
(12)
$$\sum\limits_{m=1}^M {{N_{mch}}} \geqslant LM\quad \forall c,h$$
(13)
$$\sum\limits_{c=1}^C {{X_{jpmch}}} \leqslant {r_{jpm}}\quad \forall j,p,m,h$$
(14)
$${Z_{jpmch}} \leqslant \;M.{X_{jpmch}}\quad \forall j,p,m,c,h$$
(15)
$$\sum\limits_{c=1}^C {\sum\limits_{m=1}^M {{Z_{jpmch}}} } ={D_{ph}}\quad \forall \,j,p,h$$
(16)
$${N_{mc(h - 1)}}+K_{{mch}}^{+} - K_{{mch}}^{ - }={N_{mch}}\quad \forall \;m,c,h>1$$
(17)
$$K_{{mc1}}^{+}={N_{mc1}}\quad \forall m,c$$
(18)
$${Z_{jpmch}} - {n_p}{L_{jpmch}} \geqslant 0\quad \forall j,p,m,c,h$$
(19)
$$\frac{{{Z_{jpmch}}}}{{{n_p}}} - 0.9999 \leqslant {L_{jpmch}}\quad \forall j,p,m,c,h$$
(20)
$${l_{ijpmch}} \geqslant {l_{(i+1)jpmch}}\quad \forall j,p,m,c,h,i<{I_p}$$
(21)
$${s_{ijpmch}}={l_{(i - 1)jpmch}} - {l_{ijpmch}}\quad \forall j,p,m,c,h,i>1$$
(22)
$${s_{1jpmch}}={X_{jpmch}} - {l_{1jpmch}}\quad \forall j,p,m,c,h$$
(23)
$${N_{mch}} \leqslant M \cdot L{N_{mch}}\quad \forall m,c,h$$
(24)
$$\sum\limits_{c=1}^C {L{N_{mch}}} \leqslant M \cdot L{N'_{mh}}\quad \forall m,h$$
(25)
$$L{N'_{mh}} \leqslant \sum\limits_{c=1}^C {L{N_{mch}}} \quad \forall m,h$$
(26)
$${L_{jpmch}}=\sum\limits_{i=1}^{{I_p}} {{l_{ijpmch}}} \quad \forall j,p,m,c,h$$
(27)
$${X_{jpmch}},{l_{ijpmch}},{s_{ijpmch}},L{N_{mch}},L{N'_{mh}} \geqslant 0\quad \& \;\;Binary\quad \forall i,j,p,m,c,h$$
(28)
$${N_{mch}},\;K_{{mch}}^{+},\;K_{{mch}}^{ - },\;{Z_{kpmch}} \geqslant 0\quad \& \;\;Integer\quad \forall j,p,m,c,h.$$
(29)

The objective function consists of nine cost components. Term (1) calculates the overhead cost for all machine types that are utilized during all periods. Inequality (2) computes the maximum idleness cost of all cells. The right side of this inequality denotes to cell idleness costs in each period. For calculating this part, total production time in a cell is subtracted from time capacity of all machines assigned to that cell and then is multiplied by cell idleness cost per unit time. It is worth mentioning that the effect of learning factor on decreasing processing times based on the number of created production batches is considered in Inequality (2).

As term \(\sum\nolimits_{p=1}^P {\sum\nolimits_{j=1}^{OP} {\sum\nolimits_{i=1}^I {({n_p}{l_{ijpmch}}+({Z_{jpmch}} - {n_p}{L_{jpmch}}){s_{ijpmch}})} } }\) is used in several other parts in the model to incorporate the learning effect on processing time, it is explained more as follows. As the splitting production lot is allowed, each production lot of a part can be split into different batches to be processed by different machines. In this model, it is assumed that there would be a related cost and processing time for each batch. For example, consider that 34 units of a part should be processed and defined batch size is 10. Therefore, there will be four processing batches for that part and, due to the learning effect; each of them has a different processing time and cost in a decreasing order based on the number of each batch.

Term (3) presents idleness cost of machines in each period. This term is calculated similar to the pervious term excepting that it is calculated for the maximum value of the idleness cost of all machines and then placed in the objective function to reduce machines underutilization. Splitting production lots increases the capability of the model in reducing the underutilization level of machines and cells. Term (4) represents the relocation cost of machines during successive periods. Term (5) shows dispersing cost of same duplicates of a machine among the cells. There are some expected advantages of having all duplicates of a machine type in one cell such as reduction in set up times and costs for the same machine duplicates installed in a same cell, decrease in learning costs for operators working with the same machine duplicates, and bringing more flexibility by switching the process of a part operation from a machine duplicate to another one in the case of machine breakdown. To calculate this term, the sum of the m-type machines utilized in various cells is subtracted from the m-type machines number available in period h and considering machines dispersing cost for all various machines within the whole periods, this term is obtained.

Term (6) takes into account the operating cost of all machine type. To calculate this term, the processing cost of each machine type per unit time is multiplied by the workload assigned to machines by considering the learning effect associated with the processing time to the amount of parts assigned to that machine. Term (7) is the inter-cell material handling cost incurred whenever consecutive operations of the same part type are transferred between different cells. Term (8) calculates the lost cost of production lots for each part by considering the losses percentage, lost cost and the number of batch sizes created for that part. Term (9) is splitting cost for all parts during all periods. It is calculated by multiplying the number of splits for each part by the related split cost to incorporate supervision costs resulted from tracking parts in a CMS with more congested paths for split lots.

Inequality (10) is a machine time capacity constraint and guarantees that the total production time on a machine should not exceed the available time capacity regarding that the processing time for each part operation decreases due to the learning effect. Inequality (11) ensures that a number of machine type m utilized in different cells do not exceed from the maximum number of machine type m available to be utilized in each period. The cell size limits in terms of the number of assigned machines is specified with the system designer and defined through constraints (12) and (13).

Inequality (14) enforces that each operation of a part is performed by the machine that is capable of processing that operation. Inequality (15) connects the values of decision variables X jpmch and Z jpmch to each other. If decision variable Z jpmch representing the number of operation j of part type p that is processed on machine type m takes a positive value, then decision variable X jpmch is 1; otherwise is 0. Equality (16) considers the demand satisfaction obligation and enforces that the number of operations of each part type processed by different machines should be equal to its demand volume.

Equality (17) implies that the number of machine type m located in cell c at the current period, h, is equal to the number of machine of the same type located in that cell at the previous period, h-1, plus the number of machine type m installed in cell c or minus the number of machine type m uninstalled from cell c at the beginning of the period h. Constraint (18) counts the number of machines of each type installed in a cell in the first period.

Constraints (19) and (20) associate the value of decision variable L jpmch with that of Z jpmch . Dividing the amount of operation j of part type p that is processed on machine type m in cell c by related batch size n p returns the number of created batches. Creating the lot i+1 for operation j of part p on machine m depends on the creation of the preceding lot, i, for that part. In fact, Constraint (21) is to guarantee that the production lots made for each part type are numbered in order.

Constraints (22) and (23) illustrate the way to calculate the auxiliary variable s ijpmch . Constraint (24) describes if one or more duplicates of machine type m are assigned to cell c in period h, the decision variable LN mch is 1; otherwise is 0. Constraints (25) and (26) enforce the decision variable LN’ mh to hold value 1 if at least one duplicate of machine type m is assigned to one of cells; otherwise, it holds value 0. The value for decision variable L jpmch is obtained through Constraint (27). Constraints (28) and (29) are the logical binary and non-negativity integer necessities on the decision variables.

2.3 Linearization of the proposed model

The proposed model is nonlinear because of the product of decision variables in term \(({Z_{jpmch}} - {n_p}{L_{jpmch}}){s_{ijpmch}}\) in Eqs. (2), (3), (6), (8) and Constraint (10) as well as an absolute term in Eq. (7). To linearize Eqs. (2), (3), (6), (8), and Constraint (10), the product term \(({Z_{jpmch}} - {n_p}{L_{jpmch}}){s_{ijpmch}}\) is substituted for the auxiliary variable Y′ jpmch with the following equation:

$${Y'_{ijpmch}}=({Z_{jpmch}} - {n_p}{L_{jpmch}}){s_{ijpmch}}\quad \forall i,j,p,m,c,h,$$
(30)

where the following constraints should be added to the main model:

$${Z_{jpmch}} - {n_p}{L_{jpmch}} - (1 - {s_{ijpmch}}).M \leqslant {Y'_{ijpmch}}\quad \forall i,j,p,m,c,h$$
(31)
$${s_{ijpmch}}.M \geqslant {Y'_{ijpmch}}\quad \forall i,j,p,m,c,h$$
(32)
$${Z_{jpmch}} - {n_p}{L_{jpmch}} \geqslant {Y'_{ijpmch}}\quad \forall i,j,p,m,c,h.$$
(33)

To linearize the Eq. (7), the absolute term \(\left| {\sum\nolimits_{m=1}^M {{Z_{(j+1)pmch}} - } {Z_{jpmch}}} \right|\) is substituted for auxiliary variable Y jpch with the following equation:

$${Y_{jpch}}=\left| {\sum\limits_{m=1}^M {{Z_{(j+1)pmch}} - } {Z_{jpmch}}} \right|\quad \forall j,p,c,h,$$
(34)

where the following constraints must be added to the main model:

$${Y_{jpch}} \geqslant \sum\limits_{m=1}^M {{Z_{(j+1)pmch}} - } \sum\limits_{m=1}^M {{Z_{jpmch}}} \quad \forall j,p,c,h$$
(35)
$${Y_{jpch}} \geqslant \sum\limits_{m=1}^M {{Z_{jpmch}} - } \sum\limits_{m=1}^M {{Z_{(j+1)pmch}}} \quad \forall j,p,c,h.$$
(36)

2.4 Problem description and the possible effects of the lot splitting feature

Recently, Kia et al. [9] provided a mixed-integer nonlinear programming (MINLP) model for designing the GL of a DCMS. A novel aspect of their model was the utilization of a multi-row layout to configure cells with flexible shapes. The model incorporated several design features, such as alternate process routings, operation sequence, processing time, production volume of parts, purchasing machine, duplicate machines, machine capacity, lot splitting, group layout, multi-rows layout of equal area facilities, and flexible reconfiguration. In a similar study, Kia et al. [11] presented a novel MINLP model based on the previous model for designing a GL of a DCMS and considering the production planning (PP) decisions. The other advantages of the extended model were as follows: (1) considering the variable number of cells, (2) defining a machine depot keeping idle machines, and (3) integrating CF, GL and PP decisions in a dynamic environment. To evaluate the effect of a lot splitting feature on the objective function value, they eliminated it from the basic model in solving a numerical example. It was shown that the cost saving is significant for that example problem if lot splitting is allowed. The reason for that result in the case of eliminating lot splitting feature was explained as follows. When the splitting of the production lot is not allowed, workload which can be assigned to the machines is reduced and as a result more machines should be purchased and added to the system. Consequently, purchasing and maintaining more machines with underutilization needs forming additional cells and increases cost components related to purchasing machine, machine overhead and forming cell. Also, moving parts among more machines means more intra-cell and inter-cell movements and imposes more material handling costs.

Generally, the presented study incorporates some other important aspects of the lot splitting feature into the design of a DCMS in comparison with the previous studies [9, 11] and models available in the literature. It also analyzes the cost effects of lot splitting in the objective function by introducing novel cost components. In the first aspect, idleness costs of machines and cells are calculated to reduce the underutilization that may be enforced by the case where splitting of a production lot is not implemented. In the second aspect, lost cost resulted from splitting the production lots of a part among machines is calculated based on the number of defined lots for that part. This aspect seeks to regard the parts that might be lost where the disorder in a system is serious because of splitting parts among machines. In the third aspect, learning effect is regarded to make a connection between processing time of a part operation on a machine and the amount of parts assigned to that machine. Due to this effect, processing more units of a part operation by a machine develops more skills for an operator to reduce the processing time. This aspect is against the lot splitting that might not allow an operator to process the whole demand of a part in one production lot by a machine. In the fourth aspect, splitting costs of production lots are incorporated to regard supervision costs resulted from tracking parts in a CMS with more congested paths for split lots. In the fifth aspect, the cost of dispersing duplicates of a machine among different cells are formulated to regard expected advantages of having all duplicates of a machine type in one cell including reduced setup times and costs for the same machine duplicates controlled in a same cell, decreased learning costs for operators working with the same machine duplicates, and obtaining more flexibility by switching the process of a part operation from a machine duplicate to another one in the case of machine breakdown. In the sixth aspect, two general groups of parts are defined as follows: (1) the conventional parts with a normal range in terms of production times and costs, and lost costs, and (2) the specialized parts with higher levels of production times and costs, and lost cost.

It is understood that the adverse and limiting effects of lot splitting are intensified as the production level rises. As the parts movements increase, the probability of the parts getting defective in transportation increases. Also, it is better to make the movements in such a manner that along with the minimization of costs, the production flexibility is maintained and production process is not interrupted. In large manufacturing systems, due to a longer distance between the cells and the warehouse, production time is more, compared with that in small systems. As the splitting parts increases, fewer number of the parts can be made within a pre-determined time since the movement and traffic resulted in the aisles consume more time. The more variety, volume and specialization of the parts production, the longer the machines setup time and parts flow time will be.

The production time is considered dependent on some factors including (1) parts variety, (2) the specialization level of the operation, (3) cell number, (4) machine number and (5) worker’s skill level. When the production conditions change, the mentioned factors results in different production times in the presence of the lot splitting feature.

Some advantages and disadvantages of a lot splitting feature are described below.

Reduction of the machine maintenance and purchase cost The machine maintenance cost in the state of lot splitting incline to be lower than the splitting-free state. Given Fig. 1, suppose that a part requiring 90% of machine capacity is assigned to a cell and the remaining capacity of the two available machines together can fulfill this need. However, in the splitting-free state, it is needed to use a new machine, as a result the machine maintenance cost increases. In the case of splitting permission, the production lots are split on two or even more machines available in the cells and there is no need to use a new machine. Consequently, the machines maintenance cost will be less than or equal to that of split-free state. It is vivid that by considering the purchase cost in the objective function, this cost will increase as well.

Fig. 1
figure 1

Effect of lot splitting in the case of producing a new part

Full size image

Reduction of cell and machine idleness cost Split results in lowering idleness costs of cells and machines. In the above-mentioned example, in the case of splitting permission, the remained capacity of machines is utilized and by this way, the machine and cell idleness has decreased. However, in split-free state, not only the remained capacity of the current machines available in the cells is not used completely, but also a new machine has been added that again its full capacity is not utilized. Consequently, a split-free state raises the idleness costs of machines and cells significantly. As depicted in Fig. 1, in the state that there is no lot split, employing a new machine leads to high percentage of machine underutilization. As a result, there is 50% underutilization for the cell. In the case of splitting permission, the lots are split on two machines available in the cell and due to this action, the cell idleness will drop by 25% and as a result, the less cost will be followed.

Increase in the operation cost One of the adverse and important effects of lot splitting is on the operation cost occurring as it follows. In performing the specialized operations where the worker’s skill plays a significant role, especially the operations demanding high setup time, as the number of the times the worker performs that operation or as the worker’s skill increases, the time of processing that operation will decrease. Consequently, if the production lots are split, it results in increasing setup times. Also, performing the part operations newly assigned to workers will increase the processing time of those operations.

Increase in the lost cost Under the conditions that a large number of parts are produced, the part operations become more specialized. Although in the initial parts production, the workers may not have the necessary skill, they become more skilled gradually by producing more. This enhances the action speed and accuracy. As a result, the failure rate and losses percentage drop gradually. Due to an increase in parts variety and specialization, the production process becomes more complicated. As a result, splitting production lots among the cells reduces processing speed and accuracy level and increases losses percentage.

Increase in the lot splitting cost Splitting production lots results in the operation process slows down, some parts may be lost, and the production system becomes more disordered. Even in some cases, we have to hire more supervisors to control and track the parts routings. Hence, the more splitting the production lots, the higher related costs are incurred. It is obvious that lot splitting cost resulted from the supervision of part routings is much higher in comparison with a split-free state Some advantages and disadvantages of a lot splitting feature are described below and summarized in Table 1.

Table 1 The effects of lot splitting feature
Full size table

3 Simulated annealing algorithm

The simulated annealing (SA) algorithm was introduced by Kirkpatrick et al. [13] as a stochastic neighborhood search technique for solving hard combinatorial optimization problems. SA imitates the annealing process attempting to enforce a system to its lowest energy level through a controlled cooling scheme. Generally, the annealing process happens as follows: (1) the temperature is increased to a sufficient level, (2) the temperature is kept in each level for an adequate time, and (3) the temperature is decreased under the controlled conditions until reaching the desired energy level. SA has been employed in many optimization problems in a wide variety of areas, including dynamic cellular manufacturing systems [4, 5, 9, 11, 12; Tavakkoli-Moghaddam et al. 2008, 4, 5]. In this section, the elements of the extended SA are described as follows:

3.1 Solution structure representation

The solution structure as shown in Fig. 2 indicates one point in the feasible solution space, whose representation in each meta-heuristic approach is effective at the algorithm performance. In this representation, m stands for the machine index, c for the cell index, p for the part index and k for the index of part operations. The solution structure represented in the proposed algorithm consists of two components as explained below:

Fig. 2
figure 2

Solution structure representation

Full size image

The first part as shown in Fig. 3 represents the number of machines utilized of each type in each cell expressed as a 2-D matrix m × c to depict decision variable N mch . The number of machines selected to be utilized in each cell should be limited to the upper and lower bounds of each cell. Also, the number of utilized duplicates of each machine type should not exceed the available number.

Fig. 3
figure 3

Utilized duplicates of machines

Full size image

Since there is a limitation size for each cell in terms of assigned machines number, the total number of machines assigned to all cells should be placed in an acceptable range obtained by the sum of the upper and lower limits of all cells. For example, if there are two cells with upper cell size limit equal to 4, the maximum number of machines which could be assigned to cells is 8.

An example is given in Fig. 4. One duplicated machine type 1 is assigned to cell 1 and two duplicates are assigned to cell 3. Besides, no duplicate of machine type 2 is assigned to any cells. All three duplicates of machine type 3 are assigned to cell 2.

Fig. 4
figure 4

An example for matrix Ma_Ce

Full size image

The values of decision variables K + mch and K − mch are obtained by Constraints (18) and (19). Then, the values of decision variables LN mch and LN ’ mh are found by Constraints (25) to (27).

The second part as shown in Fig. 5 defines a 3-D matrix m × c × k for each part type p and implies the number of the processed parts of type p by operation k on machine m in cell c to depict the value of decision variable Z jpmch . In fulfilling this matrix, Constraint (10) (i.e., machine time capacity), Constraint (14) (i.e., machine capability) and Constraint (17) (i.e., demand satisfaction) should be regarded.

Fig. 5
figure 5

Assignment of part operations to machine duplicates in cells

Full size image

Consider the example given in Fig. 6 for part type 2. It shows that 100 units of operation 1 of part 2 are processed on machine 1 in cell 1 and 50 units on machine 1 in cell 3. Also, 50 units of operation 2 of part 2 are done on machine 1 in cell 3 and 100 units on machine 3 in cell 2.

Fig. 6
figure 6

An example for matrix Ma_Ce_Oper_Pa

Full size image

Then, the value of decision variable X jpmch is obtained by Constraints (15) and (16). Also, the values of decision variables L jpmch and l jpmch is obtained by Constraints (20) to (22) and (28). The values obtained for decision variable l jpmch is used to return the value of auxiliary decision variable s jpmch in Constraints (23) and (24).

3.2 Initial solution generation

An initial solution as a starting point employed in the search process is generated according to a hierarchical approach in two steps, in which matrices [Ma_Ce] and [Ma_Ce_Op_Pa] are constructed in each period by random numbers limited in the determined interval provided that those matrices satisfy corresponding constraints as follows:

In the first stage, matrix [Ma_Ce] determining how many duplicates of each machine type are chosen to be utilized in cells is constructed. While completing this matrix, satisfying Constraints (11)–(13), (18), (19) and (25) to (28) are considered.

In the second stage, matrix [Ma_Ce_Op_Pa] is constructed by considering the machine capacity, machine capability and demand satisfaction. In fact, with respect to the number and type of the machines selected, efforts are made to assign the parts to the cells. The values for decision variables X jpmch and l ijpmch are derived from Constraints (15), (16) and (20)–(22). After generating a solution for the first period, theses stages are repeated for the successive periods to construct a complete solution structure. If after a certain number of iterations, no feasible solution is obtained, the first stage is reproduced and the process is repeated until a feasible solution is obtained.

3.3 Mechanism for creating a neighboring solution

To explore the feasible solution space, it is necessary to produce another feasible solution referred to the neighboring solution by changing the current one. Then, the feasibility of the solution should be examined. The procedure for producing a new feasible solution using the current one is described as follows.

First, one of the periods is chosen to implement the creating neighboring mechanism. For a selected solution, three kinds of solution mutation operators can be done as follows:

  1. 1.

    Machine-inter-cell mutation operator (MO1) This mutation can influence on the matrix [Ma_Ce] of a solution structure in two forms:

    1. a.

      Transferring one machine from one cell to another cell: this change is done only if the number of machines in origin cell is more than the lower cell limit and the number of machines in the destination cell is less than the upper cell limit.

    2. b.

      Simultaneously substituting two different machines between two cells: this change can be done in all cells without changing the number of machines in each cell. Implementing this operator needs updating matrix [Ma_Ce_Op_Pa] and can influence on Terms (2)–(9) of objective function. An example for implementing mutation (MO1) in two forms is shown in Fig. 7a, b.

    1. 2.

      Part-operations assignment operator (MO2) This mutation changes a part operation assignment by selecting one part operation randomly and then assign it to other machines by redistributing the amount of the part operation processed by different machines without changing the number of utilized machines or replacing them. Implementing this operator can influence on Terms (2), (3) and (6) to (9) of the objective function. If the generated solution by MO1 or MO2 is infeasible, it will be repaired to be a feasible one.

    2. 3.

      Machine number mutation operator (MO3) This operator can be done in two forms:

      1. a.

        Removing one machine from a cell

      2. b.

        Removing one machine and adding another machine in the same cell or in a different one simultaneously. Implementing this operator needs updating matrix [Ma_Ce_Op_Pa] and can influence on all Terms (1)–(9) of the objective function. If the generated solution by MO3 is infeasible, it will be omitted and another solution is generated to obtain a feasible one.

Fig. 7
figure 7

a An example for transferring one machine. b An example for simultaneous substitution of two different machines

Full size image

The pseudo code of the developed SA for the proposed mode, termination condition, acceptance/rejection mechanism of a neighborhood solution and cooling schedule including initial temperature, Markov chain length (MCL), and cooling rate is defined as same as those defined by Kia et al. [9].

4 Computational results

4.1 Illustrative numerical example

In order to verify the proposed model mathematically and illustrate the effects of incorporated features on its performance, a numerical example is solved by GAMS software (CPLEX solver) executed on an Intel® CoreTM i7-240M 2.3 GHz with 16 GB RAM. The example is solved in a computational time equal to 0:39′:18″. In this example, two periods, six parts, three operations per part, six machines and the maximum five splits per part are taken into account. The inter-cell movement costs in periods 1 and 2 are 40 and 60, respectively. The cell lower and upper limits are 2 and 7 for each cell, respectively. The cell idleness cost in the periods 1 and 2 are 30 and 35, respectively.

The input data for this example has been given in Tables 2, 3, 4 and 5. Table 2 represents the parameters including machine maintenance cost, machine operation cost, machine relocation cost, available machines number, machines idleness cost, time capacity and dispersing machines cost.

Table 2 Machine information
Full size table
Table 3 Parts information
Full size table
Table 4 Information related to learning effect factor (\({\varepsilon _{ip}}\))
Full size table
Table 5 Information related to losses percentage (\({\varphi _{ijp}}\))
Full size table

Table 3 presents the information related to the processing time for each part operation by different machines. Each part operation can be performed with a certain time by two different machine types. This makes it possible to split the production lots for each operation of a part between two different machine types. Also, the demand for each part in each period is given. Besides, the information related to the production lost cost, lot splitting cost for each part and the batch size for each part creating different mean processing time in each lot is given in Table 3. The production lost cost for a part is expressed regarding its importance, value and the specialization level of its operations. For instance, because of the production process being more specialized for part 4 and makes it more valuable, the related production lost cost is higher than that of the other parts. Finally, the batch size for each part is defined in order to simplify the computations and standardize processing time reduction during planning horizon; that means the parts are divide into the lots to reduce the mean processing time gradually for the successive lots made for each part type.

Tables 4 and 5 show important parameters including the learning effect factor i for decreasing the processing time of part type p (\({\varepsilon _{ip}}\)) and losses percentage of lot number i of operation j of part type p (\({\varphi _{ijp}}\)), respectively.

Reconfiguration is implemented at the beginning of the second period to handle the changing parts demand volume with fewer costs. The solution obtained from the presented model on the given example is detailed out in the rest of this section.

Table 6 represents the number of the part operations assigned to the machines located in different cells and also the number of machines installed in each cell. This table shows some of the characteristics and advantages of the presented model. For instance, in the first period, one duplicate of machine types 1 and 2 and two duplicates of machine type 3 are installed in cell (1) In addition, one duplicate of machines 5 and 6 are installed in cell (2) In the second period, it is required to add a duplicate of machine 4 to cell 2 to increase the available machine capacity.

Table 6 Machine assignments to cells and part operations assignment to machines
Full size table

In the configuration shown in Table 6, parts can be produced on the different machines assigned to multiple cells (i.e., lot splitting). This is also shown in Table 7 representing the selected routings for all part types in two periods. The routing for a part is defined in terms of both the sequence of operations required and the machines assigned to process operations, sequentially. For example, in the second period, part P1 should go through three operations in order to complete its production as quantity as 50 units equal to the demand volume of part P1 in period 2. A portion of the operations processes 32 parts on machines M1 in cell C1 and another portion processes 18 parts on machines M2 in cell C1. Then a form of lot splitting is done by dividing the production batch between two machines 1 and 2 in cell 1.

Table 7 Part routings for the first example
Full size table

Let us give an example of inter-cell movement. Consider the second operation of part P6 in the first period as 20 units are processed on machine M6, in C2, and then for the third operation, these 20 units are transferred to machine M1, located in C1, to complete production. This is an example for inter-cell movement. As can be seen, the production lot of part type 4 as a specialized one with high processing time and splitting cost is not split in any of the operations and periods. This clearly displays an advantage of the presented model.

The objective function values obtained represented in Table 8 cannot be compared to the previous studies because of the different cost components in the objective function and different issues, such as learning effect, batch size-based processing time and lost cost involved. This table shows the total objective function value (OFV) and its cost components including costs of machine overhead, machine operation, inter-cell movement, machine relocation, cell idleness, machines idleness, production lost, splitting production lots and dispersing machines. It is worth mentioning that no machine of a same type is installed simultaneously in two cells; thus there is no cost for dispersing machines among different cells.

Table 8 Objective function value and cost components
Full size table

4.2 Sensitivity analysis

In order to demonstrate the lot splitting effect on the model performance and different cost components of the objective function, the main example is solved in two cases: (1) with doubled split cost for each part, and (2) splitting-free state. As can be seen in Table 9, while the lot splitting costs double, only one production lot for operation 1 of part P5 in the second period is split into two batches with quantities of 27 and 45.

Table 9 Part routings for the first example with doubled lot splitting cost
Full size table

A comparison between the obtained OFV for the first example with the base lot splitting cost, with the doubled lot splitting cost and splitting-free state is illustrated in Table 10.

Table 10 Comparison between the OFV for the first example with base lot splitting cost, with doubled lot splitting cost and splitting-free state (i.e., infinite lot splitting cost)
Full size table

Since in three cases, the number and type of the utilized machines are not changed, the machines overhead cost is not changed. As mentioned before, as the lot splitting cost increases the splits number decreases. This results in the underutilization of machines and cells and increase in the cells and machines idleness. Because of the equality of the machines number and their assignments to cells in the solutions obtained for three cases, the cost of the machines relocation and machines dispersing are not changed.

As the lot splitting cost increases and splits number decreases, the workers skill in doing the operations gets promoted and consequently, the operation time for workers decline. As a result, in the second case, less operation cost is incurred. As expected, while the splits number gets down, due to the workers’ accuracy and skill getting boosted, the production time and cost decrease. Also, the production lost cost reduces due to easier and better tracking of fewer production lots. In the first case, four production lots are split. As expected, by an increase in the lot splitting cost, this number has decreased and in the second case, only one production is split; consequently, lot splitting cost decreases.

By observing the results, it is understood that the specialized parts are not split due to the high cost of lost and the corresponding cost is reduced by decreasing the splits numbers. In addition, the model tries to keep the utilized machines number at the least possible level satisfying the demand appropriately. As a result, the system does not run into the additional costs of maintenance, relocation, machines idleness and dispersing machines.

4.3 Analysis of computational efficiency

In this section, 15 example problems are solved using the developed SA to evaluate its computational efficiency in terms of the objective function value and computation time. The solutions obtained by SA are compared with those obtained by GAMS software and shown in Table 11. As it has been reported in the literature, an effective cooling schedule is essential for reducing the amount of time effort required by the algorithm to find an optimal solution. However, cooling schedules should be defined almost always in a heuristic way and it is needed to balance moderately the computational time with the simulated annealing dependence on problem size.

Table 11 Comparison of SA and GAMS solutions
Full size table

By carrying out several experiments on small numerical samples 1–4 to gain insights into some assumptions and intuition behind cooling schedules, a theoretical framework for parameter setting of the simulated annealing algorithm is presented based on the model size. The simulated annealing schedule is defined by initial temperatures in points (80,000, 100,000, 150,000, 170,000, 200,000), an MCL in points (30, 50, 60, 80, 100, 120), final temperature of 100 and cooling rate of 0.985. Because of exponential reduction of error probability, several short-term runs of SA results better than a long-term one [4]. Hence, each run is repeated five times to solve each example and the best obtained solution among them is reported.

Since there are numerous decision variables and constraints in the proposed model, some of the numerical examples cannot be solved in a reasonable time by GAMS. Therefore, the solving process will be continued until the GAMS software encounters a time limit defined as 10 h. At this point, the best obtained objective function value is reported as GAMSbest to be compared with SA. GAMS can only reach optimal solutions for examples 1–4, reported as GAMSopt. For the examples 5–15, GAMS is interrupted at a pre-determined time (i.e., 10 h) because of out of memory predicament. As a result, the best obtained solutions for those examples are not optimal. Generating numerical examples is stopped at example 15, as solution space is enlarged so much that GAMS even cannot generate a feasible solution before encountering out of memory message. As it can be seen, the obtained solutions by SA are better than those obtained by GAMS for examples 6, 8, and 12–14. This can be regarded as a remarkable achievement for a meta-heuristic algorithm, especially in solving large-scale problems, which cannot be solved optimally by any optimization package (e.g., GAMS).

In general, the following results can be concluded:

  • The SA algorithm finds the optimal solutions, in nearly as the same computational times as GAMS for example problems 1 and 2. In addition, for examples 3–5, 7 and 9–11, the near-optimal solutions are obtained by SA in a relative gap less than 5% compared to those obtained by GAMS and in less computational times.

  • The SA algorithm finds better near-optimal solutions than GAMS in less computational times for example problems 6, 8, and 12–14.

These promising results are obtained by the developed SA algorithm because of the elaborately-designed solution representation schema, hierarchical procedure to generate an initial solution and explorative solution mutation operators embedded in the algorithm.

5 Conclusion

In this paper, a mixed-integer nonlinear mathematical model has been presented to study the effect of lot splitting feature on a dynamic cellular production system (DCMS). Some new cost components, which had not been incorporated in the previous studies, were defined including idleness of cells and machines, production lost, splitting production lots and dispersing machines among cells. These cost components have incorporated the effects of lot splitting feature. To the best of our knowledge, it has been the first time that cost components have stemmed from tracking split batches, production lost and learning effect. Also, machine dispersing cost has been regarded to better control cells and take some advantages of having same duplicates of a machine type in a cell.

It can be generally stated that the lot splitting leads to decrease the costs of machine overhead, the cell and machine idleness, and increasing the cost of operation, production lost and supervising. In addition, in the case of specialized parts requiring worker’s high skill and high setup time, splitting of part production lot has no economic benefit. The presented model has no limitation to the splitting number of production lots. In fact, it makes optimal decision about the production lots and their amounts in order to reduce the resulted costs. In order to investigate the performance of the presented model, an illustrative numerical example was solved after using some linearization techniques to convert it into a linearized counterpart. Furthermore, the effect of change in the lot splitting cost was shown as a sensitive analysis. Then, the changes in different cost components of the objective function as a result of doubling and making infinite splitting cost were analyzed. Since solving the model using exact methods is only practical for small-sized problems, thus in order to solve the model for large-sized ones, an efficient simulated annealing algorithm was proposed. The efficiency of the designed SA has been shown by solving some numerical examples and comparing with the solutions obtained by GAMS software (CPLEX solver).

Besides, for future studies, we can point out the following cases: employing the other meta-heuristic methods for solving the proposed model and comparing the solutions, considering the backorder or inventory holding, taking into account the layout of machines and cells, designing multi-objective models for modeling the problem, incorporating other features, such as considering uncertainty for part demands, machine time capacity and cost coefficients, and integrating with machine reliability and workers issues.