1 Introduction

The group technology (GT) is one of the innovative methodologies which is defined as the manufacturing strategy, sorts out similar parts and group them together into families to take advantage of their similarities in design and manufacturing. The GT builds on the concept that single solution can be found to solve a set of problems sharing common principle and tasks, so that time and effort can be saved [1].

The cellular manufacturing (CM) is based upon the principles of group technology. It makes useful advantage of the similarity among parts, through standardization and common processing. The CM groups machines into machine cells and parts into part families [2]. The CM suppresses the demerits of job shops and flow lines by increasing the flexibility and variety in production. The major advantage in terms of material flow is significantly improved, which reduces inventory, distance travelled by the material, and cumulative lead times.

The principle of cellular manufacturing is to break up a complex manufacturing facility into several groups of machines (cells), each being dedicated to the processing of a part family. Each part type is ideally produced in a single cell. During any alteration, the changes at any section of process of the part type, only a particular cell would be affected, keeping rest of the manufacturing system intact. Thus, material flow is simplified and the scheduling task is made much easier [3].

The use of general-purpose machines and equipment in the cellular manufacturing allows machines to handle new product designs and product demand with little efforts in terms of cost and time. Hence, it brings flexibility to produce a variety of products while maintaining the higher production rate. The cellular manufacturing aims at minimizing the manufacturing cost which depends upon the cell configuration. The biggest challenge while implementing cellular manufacturing system in a company is division of the entire manufacturing system into cells.

Even though the entire production system becomes more accommodating, each individual cell is still optimized for a relatively narrow range of tasks in order to take advantage of the mass-production efficiencies of specialization and scale. To the extent that a large variety of products can be designed to be assembled from a small number of standardized parts, both high product variety and high productivity can be achieved.

The conventional cellular manufacturing systems (CMS) do not respond to the changes in part operation sequence while redesigning a part, the variation in product mix and the demand size over time span. In the conventional CMS the product mix and part demand is considered to be stable for the entire planning span. Thus, the designed CMS configuration in one period may not be efficient for the successive periods. In the dynamic production conditions, a planning horizon breaks into multiple periods with different product mix and part demand requirements [4]. Hence the manufacturing cells need to be reconfigured during successive periods to obtain optimal result. Reconfiguration involves machine relocation in the cells and modification in part process route in successive periods. The flexibility in the CMS is of paramount importance. The manufacturing industries have acknowledged the benefits of flexibility in part process routing [5, 6].

This paper suggests an integrated mathematical model for dynamic production in a cellular manufacturing environment. The dynamic part demand can be satisfied from internal production or through subcontracting part operation in successive period segments of the planning horizon. Multiple process plans for each part and alternatives process routes for each of them are considered. The proposed model for the design of CMS incorporates several production aspects simultaneously such as system reconfiguration, multiple part process route, production capacity, machine duplication, material handling, in-house production, and subcontracting part operation. A simulated annealing based genetic algorithm (SAGA) is applied to optimize the number of machines in different manufacturing cells in a manufacturing system producing multiple product mix. The main constraints are the production capacity and the maximum cell size.

2 Literature review

Over the last three decades, a large number of clustering methods have been developed for identifying potential manufacturing cells [1, 7, 8]. Kusiak and Cheng [9] have reviewed some applications of models and algorithms for cell formation problem (CFP). Majority of cell formation methods reported in the literature consider the machine requirements of parts. The problem is formulated using binary machine-part incidence matrix [10]. The binary representation assumes that each part is processed following a unique route with a certain set of machines. It is important to recognize that in an actual manufacturing environment, each part type may have more than one process plan, if one or more operations can be processed on alternative machine [11].

Arbib et al [12] suggested that an optimal machine work load balancing can be obtained by routing the parts to a limited number of distinct paths considering resource capacity. The best routing is obtained by minimizing the global part transfer among all the machines existing in different cells. However, this approach does not take into consideration the impact of various cell configurations on transportation cost.

Gupta and Seifoddini [13] presented a similarity coefficient based approach for solving the machine component grouping problem, considering production data such as production volume, alternative routes and operation time. Alternative solutions are identified based on exceptional parts, and the best solution is obtained by grouping solutions among alternatives generated by the algorithm. A software package has been developed to verify the implementation.

Nagi et al [14] proposed heuristics to iteratively solve two independent problems (a) route selection for parts and (b) decomposition of machines in manufacturing cells. They assumed that part operation can be performed on more than one machine. They decomposed manufacturing system in manufacturing cells so as to minimize the inter-cell part traffic, along with the part demand and the work center capacity constraints. The problem is formulated as a linear programming problem and further it is approached by an existing bottom-up aggregation procedure, known as inter-cell traffic minimization method.

Sankaran and Kasilingam [15] presented mathematical models to handle problems in cell formation and part routing. They developed 0–1 integer programming formulation for selection of part routings and cell formation based upon the total machine operating costs. The formulation is further modified for cell formation in order to maximize the routing flexibility of the system. The optimal solution to the part routing would yield the cell configuration and the maximum number of alternative feasible routing for the production of all parts.

Logendran et al [11] proposed the cell formation activity to be divided into two phases. The first phase is to determine the number of machines of each type, and a unique process plan for each part type. In the second phase, the assignment of part types and machine types to cells is determined. They assumed that a part can have more than one process plan and each operation can be performed by more than one machine. A mathematical model is developed with the objective to minimize the total annual cost evaluated as the sum of the amortized cost of machines and the operating cost of producing all the parts. A tabu search based meta-heuristic has been employed to solve the problem.

Adil et al [16] developed a nonlinear integer programming model and efficient solution procedure for grouping of machine-part matrix considering alternative routings to improve the cell formation such as (i) simultaneous grouping of parts and machines; (ii) consideration of alternative process plans; (iii) consideration of additional machines as available; and (iv) minimization of a weighted sum of the voids and the exceptional parts. The large cells make production planning and scheduling control more difficult. Also smaller size cells may lead to increase in inter-cell movement of parts. The non-linear integer programming model was attempted using HYPERLINDO on PC 486/33 Hz by converting it into a linear integer programming model for small sized problems. The large sized problems were attempted using simulated annealing to obtain the solution in short duration. The approach has been to obtain the best sequence of operation and simultaneous grouping of parts and machines.

Gupta et al [17] proposed a genetic algorithm based solution approach to the machine cell-part grouping problem. The objective has been to (i) minimize the cell load variation, (ii) minimize inter-cell movement of parts and (iii) minimization of both the objectives simultaneously. The part movement is determined as the weighted sum of both inter-cell and intra-cell moves. The cell load variation is computed as the difference between the workload on the machine and the average load on the cell. The cell load variation is minimized to aid the smooth flow of materials inside each cell.

Lee et al [18] proposed method for cell formation to minimize the total manufacturing cost considering key parameters such as production volume, process sequence, and alternative routing. They developed a machine chain similarity coefficient to recognize best alternative routes for part operation in terms of cell formation before attempting to cluster the machines and parts. They further attempted the problem so as to yield the highest number of independent machine cell, minimize the inter-cell movements of parts, thereby maximizing the machine chain similarity coefficient using genetic algorithm.

Askin et al [19] considered different flexibility criteria – process flexibility (alternate routing), part volume flexibility (change in production volume) and part mix flexibility (ability of cell to handle different product mixes). They considered that an operation can be processed on more than one machine type. The cell formation method consists of following four phases—

Phase I:

Assignment of parts to machines based on factors—capacity, capability and machine cost

Phase II:

Assignment of individual part-operations to individual machines for minimum material handling cost in the final system design

Phase III:

Assignment of individual machines to cells

Phase IV:

Evaluation and improvement of the cell configuration considering routing flexibility and volume flexibility. An improvement in routing flexibility is obtained by reassignment of parts to individual machines, whereas improvement in volume flexibility is obtained by identifying the inter-cell move of the parts and re-arranging load in the same cell or by rerouting to another cell.

Sofianopoulou [20] proposed a comprehensive model for the design of medium-sized CMS with duplicate machines and/or alternative process plans for some or all of the parts to be produced. He assumed that an operation on a part can be performed on more than one machine. The objective is to assign machines and parts to cells as well as to determine part routings (process plans for parts) in order to minimize inter-cell traffic. First, a mathematical model for allocating machines to cells as well as selecting the most advantageous process plan to each part is developed. Given a machine-to-cell assignment, a mathematical model to assign parts to cells and to form part families is developed. A heuristic based on simulated annealing algorithm is employed to solve the above model.

Mungwattana [21] addressed the dynamic and stochastic production requirements with routing flexibility. The problem covers multi-period planning with system reconfiguration. Alternative part process routings exist for each part type since each machine type has multiple operational capabilities and multiple copies. The model considers various cost factors such as machine allocation cost, machine operating and machine amortized cost together with machine having multifunctional capabilities. However the model ignores the intracellular material handling cost and the outsourcing. A simulated annealing based solution procedure is developed to solve the problem.

Zhao and Wu [22] presented the cell formation problem considering multiple process routes and multiple objectives—minimizing part tradeoff in different cell, minimizing exceptional element, and workload balancing. They presented a genetic algorithm based solution for cell formation.

Chan et al [23] developed a heuristic procedure for machine assignment in the single period cellular layout problems by considering practical constraints, such as the part handling factor and the number of parts per transportation. An objective function is formulated to determine the total travelling score taking into account the travelling distance.

Chen and Cao [24] proposed the regulation of production planning in cellular manufacturing systems. They presented the production planning problem over a certain planning span in the cellular manufacturing system with fixed cost. The objective is to minimize the total cost including intercellular material handling cost, fixed cell set-up cost, production set-up cost and product inventory cost in the system. Assumptions include single process plan, limited machine capacities and multiple machines of the same type. The model considers general CMS features such as inter-cell material handling and manufacturing cell formation. The mathematical model is transformed to equivalent simpler models and is attempted using Tabu search based algorithm.

Tavakkoli-Moghaddam et al [25] presented solution of a dynamic cell formation problem with multiple routing considering multiple cost objectives (machine cost, operating cost, inter-cell material handling cost and machine relocation cost) by using meta heuristic techniques such as genetic algorithm, simulated annealing and tabu search. The simulated annealing algorithm seems to have reported better and near optimal solutions in short average computational time than the other two.

Tavakkoli-Moghaddam et al [26] proposed a new multi-objective cell formation model for dynamic production, alternative process plan, machine duplication, operation sequence and machine relocation. The model is designed with the objective to determine the optimal number of cells while minimizing inter-cell cost and machine relocation cost in each period. A memetic algorithm (MA) with a simulated annealing based local search engine is proposed to solve the model. The model is solved optimally by Lingo software then the optimal solution is compared with MA implementation.

Tavakkoli-Moghaddam et al [27] present a new mathematical model to solve a facility layout problem with stochastic demands. The objective is to minimize the total cost of inter and intra cell movements in both machine and cell layout problems simultaneously. A non-linear mathematical formulation for the facility layout problem with stochastic demand is presented. For the optimal solution of the problem in a reasonable time, an approximate approach is used to linearize the nonlinear model, which is solved for different confidence level using the Lingo software.

Nsakanda et al [28] considered single and multi-period planning for part demands, machine capacity limits, multiple process plans, alternative routings for each part type, the processing sequence of parts, the tradeoff between intercellular and intracellular costs and the option of outsourcing. The availability of multiple machines of the same type and production planning are important aspects of the model. The proposed solution methodology is based on a combination of a genetic algorithm and large-scale optimization techniques.

Defersha and Chen [29] described the structural and operational issues of cellular manufacturing. They presented a mathematical model for dynamic cellular manufacturing system incorporating dynamic cell reconfiguration, alternative routing, lot splitting, sequence of operations, machine duplication, production capacity, workload balancing among cells, operation cost, and outsourcing cost. They demonstrated the importance of several design issue in an integrated manner. Commercially available optimization software is used to solve the problems.

Ahkioon et al [30] developed a CM model that integrates several manufacturing attributes such as multi-period production planning, dynamic system reconfiguration, flexible part routing, production planning: internal manufacturing, outsourcing, and inventory held from period to period. The model is solved by comprehensive mixed integer programming formulation using CPLEX 10.

Defersha and Chen [31] suggested mathematical model for multiple period problems is more complex than their single period counterparts due to combinatorial nature of integer programming. They developed six parallel genetic algorithms (PGA) for solving dynamic cell formation problem addressed in their previous work [32]. They evaluated the performance of PGA against a sequential GA and found substantial reduction in computing time and improve search performance.

Safaei et al [33] developed a mixed integer programming model to design the cellular manufacturing system under dynamic environment. The proposed model reflects several manufacturing aspects: operation sequence, alternative part process plans, inter/intra cell material handling and machine relocation in different planning segments. The objective is to minimize the total cost [machine procurement cost, variable cost (machine running cost), material handling cost and machine relocation cost]. A hybrid meta-heuristic based on mean field annealing (MFA) and simulated annealing (SA) so-called MFA-SA is used to solve the proposed model.

Ahkioon et al [34] introduced part routing flexibility in the machine cell formation system in dynamic conditions. They suggested that multiple routings are possible for each part type because of availability of multi-functional machines and multiple copies of each machine type. They created alternate contingency part process route in addition to the alternate main part process route for all part types. The design implies that the part processing can be addressed to contingency route during the failure of main part process route. The obtained results verify the insignificant additional cost by implementing the additional contingency part process route. The problem solved through a comprehensive mixed integer programming formulation.

Kioon et al [35] proposed an integrated approach to CMS design where part production and system reconfiguration decision are incorporated in presence alternate process routing, operation sequence, multiple machine of same type, machine capacity and lot splitting, etc. They formulated the problem as mixed integer non-linear program and verified the model using some random small/medium-scale problems.

Safaei and Tavakkoli-Moghaddam [36] presented an integrated mathematical model of multi-period cell formation and production planning in dynamic cellular manufacturing system. The aim is to minimize the inter- and intra-cell material handling cost, machine relocation costs, part production cost including inventory, backorder and partial subcontracting costs. The major constraints are cell size and machine time capacity. The performance shows that part subcontracting significantly affects the cell configuration in convulsive manner as a large portion of the total demand is satisfied in few periods and no production is required in other periods. The performance of the proposed model is verified by branch and bound method under the Lingo 8.0 software.

Tunnukij and Hicks [37] attempted optimization of the cell formation problem (CFP). The CFP has been shown to be a nondeterministic polynomial (NP) hence the amount of computation time increases exponentially with problem size. They presented the enhanced grouping genetic algorithm (EnGGA) to solve the CFP without predetermining the number of manufacturing cells or the number of machines and parts within each cell. The EnGGA employs a rank-based roulette–elitist strategy, for creating successive generations. The EnGGA is effective and outperforms all the other methods considered such as bond energy algorithm, direct clustering algorithm, rank order clustering and graph theoretical approach. The program required less than 1 min computational time in all situations, even with the large population size.

Ozcelik and Sarac [38] proposed hybrid genetic algorithm to solve the cell formation problem considering alternative part route. They considered some of the natural constraints encountered in real life production systems, such as cell size, co-location (grouping certain machines in the same cell for technical reasons) and separation (prevent placing certain machines in close vicinity) constraints. Their objective is to minimize the weighted sum of the voids and the exceptional elements. The results show that the hybrid genetic algorithm generates feasible solutions for all of the test problems.

Solimanpur and Foroughi [39] developed a new approach to cell formation problem (CFP) including factors such as alternative part process routes, operation sequence, part process time, budget, production volume and machines cost. Two linear mathematical programming models are proposed to solve the CFP. The first stage determines the part route to be selected for each part and forms the part families simultaneously. The objective function of this model is to minimize the total dissimilarity between the processing routes of parts located in the same cell. The second stage determines the machines to be allocated to each cell considering processing time, production volume, budget and cost of machines. The result obtained by genetic algorithm provides very promising results in terms of the quality and computation time as compared to Branch & Bound method implemented in Lingo Software.

Saidi-Mehrabad et al [40] presented a new mathematical model for production planning based on dynamic cellular manufacturing system considering worker assignment. The model is proposed with an extensive coverage of important manufacturing features considering multi-period production planning, sequence of operations, system reconfiguration, duplicate machines, machine capacity and training of workers. The model formulation is based on three principles: (1) production planning, (2) worker assignment and worker training, and (3) machine reconfiguration. The objective is to minimize the sum of penalty cost in terms of inventory holding and back orders cost, training and salary costs of workers, maintenance and overhead cost and reconfiguration cost. The main constraints are demand satisfaction, machine availability, machine time-capacity, available time of worker and training. The performance and applicability of the proposed model is verified by solving a comprehensive example with randomly generated data using a branch-and-bound (B&B) method by Lingo 9.0 software.

The review of the research literature cited above reveals various techniques proposed for the design of CMS under dynamic conditions. These methods generally assume that the production size is equal to demand requirements in each period segment of planning horizon. In reality, however, the production size may not be equal to the demand requirements due to production capacity shortage and/or sudden machine breakdown. Thus demand requirements in each period segment of planning horizon can be satisfied by in-house production and/or subcontracting.

A few authors [28, 29, 32, 34] addressed subcontracting/outsourcing as a subset of the part demand size. Hence a complete part processing (sequence of operations) is accommodated by subcontractor which is unrealistic and gives an impractical manufacturing view. It may lead to a vacillation or convulsive behavior in the cells reconfiguration by increasing work load unbalancing, machine duplication, and reduction in the effectiveness of manufacturing system.

This paper presents an integrated mathematical model for DCMS design retorts dynamic and deterministic production requirement. The model formulation is based on the realistic industrial manufacturing vision considering multiple part process routes for each part type since each machine type with multiple copies has multiple operational capabilities. In the proposed model, a part operation processing can be tradeoff between different production modes (in-house production and subcontracting) based on the production capacity of manufacturing cells. An optimization method for such problems usually requires substantial amount of time and memory space, therefore a simulated annealing based genetic algorithm has been developed to cope with the complexity of a problem and to expedite the solution search space.

The next section presents mathematical formulation of the CMS design problem. The proposed algorithm is presented in section 4. A case study for demonstration of the proposed approach has been presented in section 5. Conclusion of the research and future scope has been presented in the last section.

3 Problem formulation

The proposed integrated CMS model comprises traditional cell formation problem linked to multi-period production planning and system reconfiguration. The system reconfiguration involves machines relocation in cells or it may also involve change in part process route from period to period. The traditional cell formation problem follows formation of part families, machines grouping in the form of cells and assignment of part families to cells. In multi-period production planning variation in product mix and the part demand size are met through internal production, or subcontracting.

There are different machine types in the cells with multiple operational capabilities and limited capacity to process part families. Also, there are different part types with specific operations requirement and processing time. The proposed model assumes that a candidate part operation is processed internally considering production capacity or through subcontracting to satisfy the part demand. In the past a few authors [28, 29, 32, 34] addressed subcontracting/outsourcing, but only as a subset of the part demand size.

The proposed approach emphasizes on the flexibility in part operation processing by permitting it to be switched to different production modes (in-house production or subcontracting) considering production capacity shortage and/or sudden machine breakdown.

The overall objective of the model is to minimize the machine constant cost, the machine operating cost, the system reconfiguration cost, the production cost, the subcontracting part operation cost, and the inter and intra-cellular material handling cost. A mixed-integer mathematical formulation for the CMS design is presented below.

3.1 Notations

  1. (a)

    Index sets

    P :

    {p = 1, 2, 3,…, P.} Part types

    Op :

    {k = 1, 2, 3,…, Op.} Operation k of part type p

    M :

    {m = 1, 2, 3,…, M.} Machine types

    C :

    {c = 1, 2, 3,…, C.} Manufacturing cells

    T :

    {t = 1, 2, 3,…, T.} Time periods

  2. (b)

    Model parameters

    A mc (t):

    Number of machine type m available in cell c at time period t

    B U :

    Upper cell size limit

    B L :

    Lower cell size limit

    D p (t):

    Demand for part type p at time period t

    IE p :

    Intercellular material handling cost per part type p

    IA p :

    Intracellular material handling cost per part type p

    t kpm :

    Time required to perform operation k(k = 1,…,Op) of part type p (p = 1,…,P) on machine type m (m = 1,…,M)

    α m :

    Amortized cost of machine type m per period

    β m :

    Operating cost per hour of machine type m

    δ m :

    Relocation cost of machine type m including installing, shifting, and uninstalling

    T m :

    Capacity of each machine type m in hours

    o kp :

    Subcontracting cost of operations k of part type p

    μ kp :

    Internal manufacturing cost of operation k of part type p

  3. (c)

    Decision variables

    N + mc (t):

    Number of machines of type m added in cell c in period t

    N − mc (t):

    Number of machines of type m removed from cell c in period t

    OP kp (t):

    Number of parts of type p processed for operation k through subcontracting in period t

    XP kpmc (t):

    Number of parts of type p processed for operation k on machine type m in cell c in period t

    a kpm :

    \( \left\{ \begin{array}{ll} 1&\quad{\text{if operation }}k{\text{ of part type }}p{\text{ carried out on machine type }}m .\\ 0&\quad {\text{otherwise}} . \\ \end{array} \right. \)

    X kpmc (t):

    \(\left\{ \begin{array}{ll} 1&\quad{\text{if operation }}k{\text{ of part type }}p{\text{ carried out on machine }}m{\text{ in cell }}c{\text{ in period }}t . \\ 0&\quad {\text{otherwise}} . \\ \end{array} \right. \)

3.2 Mathematical model

$$ MinimizingZ = C_{1} + C_{2} + C_{3} + C_{4} + C_{5} + C_{6} + C_{7} $$
(1)
$$ C_{1} = \sum\limits_{t = 1}^{T} {\sum\limits_{m = 1}^{M} {\sum\limits_{c = 1}^{C} {A_{mc} (t)\alpha_{m} } } } $$
$$ C_{2} = \sum\limits_{t = 1}^{T} {\sum\limits_{p = 1}^{P} {\sum\limits_{k = 1}^{op} {\sum\limits_{m = 1}^{M} {\sum\limits_{c = 1}^{C} {XP_{kpmc} (t)t_{kpm\,} \beta_{m} } } } } } $$
$$ C_{3} = \sum\limits_{t = 1}^{T} {\sum\limits_{p = 1}^{P} {\sum\limits_{k = 1}^{op} {\sum\limits_{m = 1}^{M} {\sum\limits_{c = 1}^{C} {XP_{kpmc} (t).\mu_{kp} } } } } } $$
$$ C_{4} = \sum\limits_{t = 1}^{T} {\sum\limits_{p = 1}^{P} {\sum\limits_{k = 1}^{op} {Op_{kp} (t)o_{kp} } } } $$
$$ C_{5} = \sum\limits_{t = 1}^{T} {\sum\limits_{p = 1}^{P} {\sum\limits_{m = 1}^{M} {\sum\limits_{c = 1}^{C} {IE_{p} .XP_{kpmc} (t)\sum\limits_{{{\text{k}} = 1}}^{{o_{p} - 1}} {\left( {1 - X_{k + 1,pmc} (t).X_{kpmc} (t)} \right)} } } } } $$
$$ C_{6} = \sum\limits_{t = 1}^{T} {\sum\limits_{p = 1}^{P} {\sum\limits_{m = 1}^{M} {\sum\limits_{c = 1}^{C} {IA_{p} .XP_{kpmc} (t).\sum\limits_{k = 1}^{{o_{p} - 1}} {X_{k + 1,pmc} (t).X_{kpmc} } (t)} } } } $$
$$ C_{7} = \frac{1}{2}\sum\limits_{t = 1}^{T} {\sum\limits_{m = 1}^{M} {\sum\limits_{c = 1}^{C} {(N^{ + }_{mc} (t) + N_{mc}^{ - } (t))\delta_{m} } } } $$

Subjected to

$$ \sum\limits_{t = 1}^{T} {\sum\limits_{p = 1}^{P} {\sum\limits_{k = 1}^{op} {\sum\limits_{m = 1}^{M} {\sum\limits_{c = 1}^{C} {a_{kpm} X_{kpmc} } (t) = 1} } } } $$
(2)
$$ \sum\limits_{t = 1}^{T} {\sum\limits_{p = 1}^{P} {\sum\limits_{k = 1}^{op} {\sum\limits_{m = 1}^{M} {\sum\limits_{c = 1}^{C} {XP_{kpmc\,} (t) + OP_{kp} (t) \le D_{p} (t)} } } } } $$
(3)
$$ \sum\limits_{t = 1}^{T} {\sum\limits_{p = 1}^{P} {\sum\limits_{k = 1}^{op} {\sum\limits_{m = 1}^{M} {\sum\limits_{c = 1}^{C} {t_{kpm} } } .XP_{kpmc} (t) \le T_{m} A_{mc} (t)} } } $$
(4)
$$ \sum\limits_{t = 1}^{T} {\sum\limits_{p = 1}^{P} {\sum\limits_{k = 1}^{op} {\sum\limits_{m = 1}^{M} {\sum\limits_{c = 1}^{C} {(XP_{k + 1,pmc} (t) + OP_{k + 1p} (t) = XP_{kpmc} (t)} } } } + OP_{kp} (t))} $$
(5)
$$ \sum\limits_{t = 1}^{T} {\sum\limits_{m = 1}^{M} {\sum\limits_{c = 1}^{C} {A_{mc} (t) \le B_{u} } } } $$
(6)
$$ \sum\limits_{t = 1}^{T} {\sum\limits_{m = 1}^{M} {\sum\limits_{c = 1}^{C} {A_{mc} (t) \ge B_{L} } } } $$
(7)
$$ a_{kpm} \in \{ 0,1\} $$
(8)
$$ X_{kpmc} (t) \in \{ 0,1\} $$
(9)
$$ XP_{kpmc} (t) \ge 0\,{\text{and}}\;{\text{integer}} $$
(10)
$$ OP_{kp} (t) \ge 0\;{\text{and}}\;{\text{integer}} $$
(11)
$$ N_{mc}^{ + } (t) \ge 0,N_{mc}^{ - } (t) \ge 0\;{\text{and}}\;{\text{integer}} $$
(12)
Objective function. :

The model objective function consists of seven cost components, explained below

C1::

The constant cost of all machines required in manufacturing cells over the planning horizon. This cost is obtained by the product of the number of machine type m allocated to cell c in period t and their associated costs

C2::

The operating cost of all machines required in manufacturing cells over the planning horizon. It is the sum of the product of the time-workload (i.e., number of hours) allocated to each machine type in each cell and their associated operating costs

C3::

Production cost for part operation

C4::

Subcontracting cost for part operation; The cost is incurred whenever part operation is subcontracted due to production capacity shortage or sudden machine breakdown. The model considers unit subcontracting cost for part type being handled

C5::

Intercellular material handling cost; The cost is sustained whenever the successive operations of the same part type are carried out in different cell. The cost is directly proportional to number of parts moved between two cells. In this model unit intercellular movement is expressed only as a function of part type being handled

C6::

Intracellular material handling cost; The cost upholds the consecutive operations of candidate part processing on different machines in the same cell. It is assumed that unit intracellular cost depends upon the type of part being handled

C7::

Manufacturing cells reconfiguration cost; The cost upholds the number of machine type relocated/added and/or removed in successive period segments of planning horizon

Constraints. :

The constraints of the problem are shown in equation set (2–11) as discussed below

Equation (2)::

Each part operation is assigned to one machine, and one cell in period t

Equation (3)::

Each part demand can be satisfied in time period t objectively through internal production or subcontracting part operation. More specifically the term “XP kpmc ” represents internal processing of part operations, based a sub-set of operation sequence of part type p are assigned to machines in the cells. Since limiting machine capacity or sudden machine break down results subcontracting of part operation

Equation (4)::

Internal part operation processing to be limited to available machine capacity

Equation (5)::

The material flow conservation—all the consecutive operations of part type consist of equal production quantities, thus a part operation can be internally processed or subcontracted to satisfy the part demand

Equations (6 and 7)::

The cell size lies within the upper and lower limits.

In addition to these constraints, restrictions represented by Eqs. (8–12) denote the logical binary and non-negative integer requirement on decision variables.

3.3 Distinguishing properties of the proposed CMS model

3.3a Production flexibility: The model is designed such that it can be set to different levels of manufacturing mode (internal production or subcontracting part operation) considering internal production capacity to satisfy demand requirements in the dynamic condition. The proposed model offers more flexibility in production planning that can be achieved by producing parts within the machine capacity limit of the manufacturing system. It is seldom noticed, the internal resource does not satisfy the part demand within the available machine capacity limits; however if it happens so/or during machine breakdown, parts operation can be subcontracted to satisfy the demand requirements.

3.3b Dynamic system reconfiguration and machine procurement: The CMS model might not be optimal for dynamic deterministic demand in terms of overall cost for future planning, therefore system needs to be reconfigured in each period owing to variation in part type and their lot size. The Proposed model allows the formation of the best configuration within each planning period in terms of the type and number of machines assigned to cells and part routings. The system eliminates procurement of extra machines when inter-cell move cost is less than machine procurement cost. This is achieved when machines are relocated and new process routings are chosen based on tradeoff in cells and minimum machine operating time. The strength of this CMS model to deal with variation in part mix demand is improved by the fact that new machine can be brought in through machine procurement to increase the internal production capacity.

3.3c Cell formation with flexible resource routing: Multiple part routings are an important characteristic of the model. The part routing is a set of possible machines that can be used to perform the required operation on a part. With multifunctional machines and multiple copies of each machine type allowed in the system, the presence of multiple routing is important since this gives more flexibility in deciding upon the CMS configurations. In this research, the model permits the system to select the best route instead of the user specifying predetermined routes. The model permits all the possible routes to coexist; and more than one route can be chosen to make a part considering resources availability (internal and subcontracting part operation process).

4 The simulated annealing based genetic algorithm

The traditional genetic algorithm suffers from premature convergence and affects the quality of solution. The traditional mechanism of genetic algorithm set off the pattern of effective solutions higher than the average in next generation. It strict the hunting zone and rapidly converge the population, does not necessarily achieve global optimum solution. In order to explore the solution region efficiently and to expedite the solution search space, the simulated annealing strategy is combined in the genetic algorithm.

The simulated annealing based genetic algorithm (SAGA) incorporates the best features of genetic algorithm (searching larger regions of solution spaces) and simulated annealing (refining exhaustive solution of local region). The basic idea is to use the genetic operators of genetic algorithm to quickly converge the search to near-global minima/maxima, which will further be refined to a near-optimum solution by using simulated annealing process. Recent work on genetic algorithm-oriented hybrids is the simulated annealing genetic algorithm (SAGA) proposed by Brown et al [41].

The proposed algorithm imparts synergy effect between the SA and GA by presenting a hybrid algorithm employing the SA. In this algorithm, the initial solution of SA comes from the evolution of GA. The solution obtained by sampling of SA serves as the initial individual of GA so that a hybrid search is made possible. The proposed hybrid SAGA algorithm is applied for the considered DCMS problem with a matrix schema and the novel operators are presented in following sections.

4.1 Solution representation schema

In the solution representation schema, two matrices [PMpk] and [PCpk] are employed in each period segment of the planning horizon. The matrix [PMpk] denotes the allocation of part-operation to machine and the matrix [PCpk] denotes the allocation of part-operation to cell. PM pk is the machine performs operation k of part type p, where PM pk ∊ \( \phi_{kp} {\text{and }}\phi_{kp} = \left\{ {{\text{m}}\left| {a_{kpm} = 1} \right.} \right\} \). Also, PCpk is the cell allocated with operation k of part type p, where 1 ≤ PCpk ≤ C. By combining the two matrices described above, the solution representation schema is shown in figure 1.

Figure 1
figure 1

Solution representation schema.

Full size image

4.2 Initial solution generation

The initial solution of preferred volume is generated randomly in steps. In first step, the matrices [PMpk] of the solution schema are generated randomly considering feasibility of performing part operation on machines. In second step, the segment [PCpk] is filled randomly.

A strategy is applied with objective to minimize the number of inter-cell move of parts. The part operations associated with each part type are assigned to machines existing in the cells. This process is repeated until all the parts are assigned to machines. Given a candidate part-machine assignment solution, the heuristic computes the number of inter-cell part transfer that would result minimum number of inter-cell transfer (if a part operation is assigned to cell C1, each operation of part is assigned to cell C1).

Occasionally cells may not have minimum and maximum number of specified parts that contravene lower or upper limit condition as per Eqs. (6) and (7). To ensure the cell size within the specified lower and upper limits, parts family is to be adjusted by moving parts from cell having maximum number of parts to cell having less than minimum number of parts specified.

4.3 Fitness assessment

The fitness value is a decisive factor to measure the quality of a candidate solution with reference to the designed objective function (equation set 1) subjected to constraints (equation set 2–7) and restrictions (8–12). The fitness values are used to select the parent solutions to obtain the next generation of solutions. The descendants or new solutions are selected with higher fitness value obtained by playing binary tournament between parent solutions.

4.4 Genetic operators

4.4a Parent selection: After evaluating the fitness value of the parent solutions in the population, better performing solutions are selected to produce the descendants. Parent solutions with higher fitness value have a higher chance of being selected more often, which is achieved by playing binary tournament between solution sets according to their fitness value. Different selection schemes have been presented by Goldberg [42].

4.4b Crossover or recombination: Crossover is performed between two selected parent solutions which create two new descendant solutions by exchanging segments of the parent solutions, thus descendant solutions retain partial properties of the parent solutions. Figure 2 depicts the solution sets of parent 1 and parent 2 selected for crossover. There are two segments in the parent solution one each for machine and cell. For crossover, the selection of segments can be row-wise or column-wise following the matrix limits and the crossover probabilities.

Figure 2
figure 2

Crossover or recombination (a) Row wise crossover and (b) Column wise crossover.

Full size image

4.4c Mutation: The mutation is performed to maintain the diversity in the solutions to explore new solution space. The mutation operator is carried out on parent solutions with a low probability of occurrence. The operator can be implemented by inverting the segment of a solution schema and place the mutated content in the reverse order, as shown in figure 3.

Figure 3
figure 3

Mutation.

Full size image

4.5 Emendation operation

The crossover and mutation operation may distort solution set by violating the cell size constraint, i.e. every cell may not have minimum number of machine type. The emendation operation is performed on the distorted solution schema to preserve the cell size as per Eqs. (6) and (7).

4.6 Heuristic to eliminate the duplicate machine

The obtained solution in terms of part family and machine cell is based upon the perception that no inter-cell move is allowed. In other words independent cells are created. It leads to machine duplication in cells which has to be minimized to drive down the investment. Whereas, the reduction in machine duplication results increase in inter-cell material handling cost. However in certain circumstances, it is more economical to have inter-cell moves instead of having extra machines [43]. In this segment, tradeoff of having duplicate machines versus having inter-cell move is considered. If eliminating duplicate machines in lieu of inter-cell movement results in reduction of total cost, the machine will be eliminated. In order to eliminate the extra machine from a cell the following algorithm is used.

  1. 1.

    Select a machine type to be considered. Calculate the total number of machines allocated in different cells to meet the production requirements.

  2. 2.

    To eliminate duplicate machines of the machine type selected, calculate the work load which the machine type performs in each cell. The work load is defined as the amount of the part type to be produced. If the cost of saving in eliminating a unit of the machine type is greater than the inter-cell material handling cost, eliminate the unit of machine in the cell which has the minimum work load.

  3. 3.

    If all the machine types have been considered, terminate. Otherwise go to step 1.

4.7 Simulated annealing based search

In simulated annealing phase, the algorithm effectively regulates the search direction by avoiding solution being trapped in local optima during the evolutionary process. It attempts to perform a Metropolis random walk that samples the objective function from close solutions in current population.

The search starts with an objective function value at a feasible solution f(z) and moves from solutions to neighboring solution to improve the objective function value. If the objective function value of the neighbor solution f(n) is less than the current feasible solution f(z), it is accepted as a current solution. Otherwise to escape from local optima the Metropolis algorithm accepts the move with a probability, exp \( \left( {\tfrac{ - (f(n) - f(z)}{t}} \right) \). The pseudo code for the SA based search is shown in figure 4.

Figure 4
figure 4

Pseudo code for the SA based search.

Full size image

4.8 Termination of algorithm

The algorithm continues to generate the solution sets of descendants until a criterion for termination is met. A single criterion or a set of criteria for termination can be adopted. In this case the termination criterion is the maximum number of iteration, i.e. the algorithm stops functioning when a specified number of iteration is reached (figure 5).

Figure 5
figure 5

The flow chart of SAGA.

Full size image

5 Computational results

To evaluate the computational performance of the proposed algorithm for the design of CMS, data sets of different bench mark problem have been taken from the research literature reported by Wicks [44], Wicks and Reasor [45], Mungwattana [21], and Jayakumar and Raju [46]. Since the proposed mathematical model developed in this study is different from those reported in the research literature (additional features include internal and subcontracting part operation manufacturing cost etc.), the unknown cost parameters were extracted by cross referencing between the data sets containing them. Therefore all of the data sets used in each numerical example contain value within the same range in terms of unit costs. Emphasis was put on number of parts types, machine type, operations and number of cells. Each one of the numerical examples used is solved as an integrated model. The meta-heuristic algorithms were developed using MATLAB-2009 and run on a PC Pentium IV, 1.86 GHz speed with 1 GB of RAM.

A set of seven numerical problems have been attempted to demonstrate the proposed approach. It is evident that the required computational time increases with the problem size in terms of number of variables, constraints and periods as shown in table 1.

Table 1 Result comparisons of meta heuristics.
Full size table

To evaluate the computational performance of the proposed algorithm (SAGA), results obtained for all the benchmark problems using GA, SA and SAGA heuristics are compared as shown in table 2. The percentage improvement value is used to compare the results of three algorithms. The percentage improvement in the obtained best solutions is computed using equation, % improvement = ((Z BestA  − Z BestB )/Z BestA ) × 100. The obtained results illustrate that percentage improvement in the best objective function value of SAGA is slightly more than of SA and GA. The computational time of SAGA is more than GA and SA for all the test problems.

Table 2 Comparison of computational results of all the test problems.
Full size table

5.1 Result and discussion

Jayakumar and Raju [46] used extended lingo [47] to solve the problem. This illustrates various features of the solution for the proposed CMS model. Using this problem instance, an optimal solution has been obtained with making use of the evolutionary process of the proposed simulated annealing based genetic algorithm (SAGA). The population size is set to 100, the probability of crossover is 75% and the probability of mutation is 0.025%. In the SA search process of SAGA algorithm, the initial temperature \( (t_{\hbox{max} } = {{ - \left| {Z_{1} (PM1PC1) - Z_{2} (PM2PC2)} \right|} \mathord{\left/ {\vphantom {{ - \left| {Z_{1} (PM1PC1) - Z_{2} (PM2PC2)} \right|} {{\text{ln(0}} . 9 5 )}}} \right. \kern-0pt} {{\text{ln(0}} . 9 5 )}}) \) is set in such a way that non-improver solution are accepted with the probability value of 95% in the primary iterations with temperature decrement by 5%.

The objective function value obtained in the proposed work cannot be compared meaningfully because of inherent difference in the objective cost value as obtained by Jayakumar and Raju [46]. The proposed approach is comparably more general for taking up (i) the internal part operation manufacturing cost considering production capacity and (ii) the subcontracting part operation cost. These data sets are superimposed on the original data shown in table 3.

Table 3 Data set for example 6.
Full size table

Despite a few differences in the mathematical model, a meaningful comparison can be made in terms of the decision aspects of the CMS design resulting from two different solutions. The solution obtained with the proposed model on Problem 6 (table 3) is detailed out in the rest of this section and simultaneously compared with that obtained in the model from Jayakumar and Raju [46].

The cell configuration for three periods corresponding to the optimal solution of the proposed DCMS model is shown in table 4, in which three cells are formed for each period. Part families, machine groups, part-operation allocation, and machine replication are also depicted in the cell configuration presented in table 5. For instance one unit each of machine type 3, 5 and 6 is assigned to cell 2 in period 3. The part operations assignment within the cell is represented by incidence matrix in rectangular shape. For instance operation 1 of part 2 in period 1 must be done by machine 2 in cell 2, operation 2 by machine 2 in cell 2 and operation 3 by machine 4 in cell 2. Thus, the processing of part 2 in period 1 requires two inter-cell movements. One unit of machine type 3 is added to cell 1 and one unit of machine type 7 is removed from cell 1 at the beginning of period 2.

Table 4 Optimal cell configuration obtained by the proposed DCMS model: (a) Period 1, (b) Period 2, and (c) Period 3.
Full size table
Table 5 Optimal alternative process route for each part type in each period.
Full size table

The solution obtained in terms of optimal part operation process route and part operation tradeoff in different production modes considering production capacity shortage for each part operation in each period are depicted in table 5. For instance, the operation 1 of part 5 in period 3 is assigned to machine 6 in cell 2, operation 2 is assigned to machine 7 in cell 3, whereas operation 3 on machine 6 in cell 2 cannot be assigned as machine capacity is over limit. Hence operation 3 of part 5 is subcontracted from cell 2 (figure 6).

Figure 6
figure 6

Progress of algorithm for search of optimal solution corresponding to the objective function value (OFV): (a) Period 1, (b) Period 2, and (c) Period 3.

Full size image

Table 6 demonstrates the selected routings for part 6 (machine and cell) in period 2. It undergoes three different operations in cell 2 to complete the production process. The first operation is performed on machines 3 and second on machine 5 whereas the third operation cannot be performed due to limited production capacity of 600 h of machine type 4. Since part type 6 and 12 are assigned on machine type 4 in cell 2 (see table 3b). The part type 12 with demand size of 600 units and process time of 0.59 h per unit exploits 354 h of machine type 4. Hence third operation of part 6 cannot be processed on machine 4 in cell 2 as it requires 315 h to satisfy demand size of 500 units with processing time of 0.63 h per unit. Hence part 6 is subcontracted for operation 3 from cell 2. The solution obtained from Jayakumar and Raju [46] does not involve flexibility in production for each part operation.

Table 6 Comparison routing for part type P6 in period 2.
Full size table

In this paper, the possible routing for the part p is defined in terms of internal production and subcontracting part operation. Thus, the co-existence of multiple possible resource routing (in-house production and subcontracting) for all the part types are allowed and it is a tangible advantage during unexpected machine breakdown and production capacity shortage occurring in real world.

Table 7 illustrates that the parts demand are met for part type P7 and P10 in period 1, part type P4 and P6 in period 2 and part type P10 and P11 in period 3 through internal production considering internal production capacity and subcontracting part operations during three period segment of planning horizon. The option for subcontracting part operation is not present in the model proposed by Jayakumar and Raju [46]. Hence no comparison can be made in terms of different resource routings. By simultaneously considering the internal production and subcontracted part operation which relies on reality shows production flexibility of the proposed model in meeting product demand requirement economically.

Table 7 Comparison of production plan for parts P7 and P10 for (t = 1), P4 and P6 for (t = 2), P10 and P11 for (t = 3).
Full size table

In this study the tradeoff is made between intracellular, intercellular part movement and machine duplication by simultaneously minimizing all the three costs within the objective function. This is essential since, high intracellular movement cost for successive part operations implies large cell size, reducing the effectiveness of manufacturing system. On the other side, minimum inter-cell movements lead to increase in number of duplicate machines in the cells and adversely affect the benefits of CMS by inappropriate workload distribution among cells.

6 Conclusion and future research direction

This paper presents a novel integrated mathematical model for design of cellular manufacturing system considering dynamic production and multi-period production planning. The integrated model in this research incorporates the traditional cell formation problem bridged with the machine allocation problem, multiple part process routing problem and system reconfiguration problem. The proposed model offers flexibility in production planning (production/subcontracting) that can be achieved by producing product mixes at each period of planning horizon considering production capacity shortage.

The algorithm aggregates resources into different manufacturing cells based on selected optimal process route from user specifying multiple routes. The results obtained show that the co-existence of multiple possible resource routings (in-house production/subcontracting) builds up flexibility in production and it is a tangible advantage during unexpected machine breakdown and production capacity shortage occurring in real world.

The model is computable with single part routing as well as multiple part routings. The proposed approach can also be readily used where limits are imposed on the cell sizes and/or number of cells. The proposed CMS model has been attempted using a simulated annealing based genetic algorithm. The algorithm uses simulated annealing strategy and genetic operators to avoid premature convergence. The algorithm improves intensification, diversification and increases possibility of achieving near-optimum solutions.

The research reported in this paper is a part of the major research project on robust design of CMS. The authors are working to further improve the mathematical model for design of CMS incorporating more real world aspects of the manufacturing system, such as lot splitting and machine adjacency requirements to widen its area and make the study more useful.