An improved design for cellular manufacturing system associating scheduling decisions

Abstract

This paper presents a model for the design of Cellular Manufacturing System (CMS) to evolve simultaneously structural design decisions of Cell Formation (CF) and operational issue decisions of optimal schedule. This integrated decision approach is important for designing a better performing cell. The model allows machine duplication and incorporates cross-flow for scheduling flexibility. The cross-flow is the term introduced to mean the inter-cell movement of parts from parent cell to identical machines in other cells though machines are available in the parent cell. This cross-flow facilitates routing flexibility and paves way for reduced schedule length thereby optimizing resources leading to minimized operational cost. A non-linear integer mathematical programming model is formulated with the objective function of minimizing operating cost which is the sum of Machine Utility Cost (MUC) and inter-cell costs. The MUC is a new cost parameter based on machine utility and it integrates CF, scheduling, and machine duplication decisions. The proposed model belongs to the class of NP-hard problems. A hybrid heuristic (HH) that has “Simulated Annealing Algorithm (SAA) embedded with Genetic Algorithm (GA)” is proposed. A comparison with the mathematical solution reveals that the proposed HH is capable of providing solutions closer to optimal in a computationally efficient manner. The model is validated by studying the effect of integrated decisions, machine duplications, and association of scheduling and cross-flow. The model validation reveals that the proposed CMS model evolves CF, scheduling, and machine duplication decisions with minimum operating cost. Thus, it can be inferred that the proposed model gives optimal integrated decisions for designing an effectively and efficiently performing cells and thus evolves improved CMS design decisions.

1 Introduction

The Cellular Manufacturing System (CMS) finds application in discrete parts manufacturing industries like automobiles, furniture, machine tools, smartphones, and airplanes manufacturers [1] where the variety of end items and subassemblies for different models are produced. The CMS and its implementation bring forth significant advantages in the quest for faster, better, cheaper production and delivery of manufactured products [2]. The primary concern of CMS is cell formation (CF) problem that has to identify the groups of parts forming part families and set of machines for each part family forming the machine cells. The CF decisions are generally made by optimizing the objectives of minimizing inter-cell [3, 4] and intra-cell movements, minimize throughput time, minimize total operation cost [5], maximize machine utilization, minimize cell load unbalances, etc. The review paper of Papaioannou and Wilson [6] indicated that most authors of the CF problem have worked on the attainment of cell independence with the performance measure as minimizing inter-cell movements or material handling costs. The other main consideration is minimizing the sum of machine duplication and inter-cell move costs [7].

But there is a need for CF problem to consider operational issues and related costs in an integrated way to address the actual manufacturing system and its requirements. The advantages of CMS are effectively realized by the integration of design, and production planning and control with their objectives being shared through a suitable field [8]. The review by Chattopadhay et al [9] mentioned that the research objectives by researchers focus mostly on the design issues of CMS with the major focus on CF problem whereas the control issues are least bothered and a good design can be evolved with improved production performance by an integrated approach. Li et al [10] stated that the successful operation of CMS is influenced by both structural issues like cell formation (CF) and operational issues that deal with scheduling. Wemmerlov and Hyer [11] mentioned that even though the researchers widely focus on CF problem, the cell design would be incomplete if not related to the operational issues like scheduling of the system. Taking into account the above points, a few research works have included scheduling, however in different manner in the CF problems and are: Arkat et al [12] addressed the CF problem with the objectives of minimum transportation cost and minimum makespan; Mak et al [13] considered objectives of minimizing total material travel distance and minimizing the sum of tardiness of all the products in a virtual cellular manufacturing system; Kesen et al [14] proposed scheduling methodology and machine assignment with alternate machine routing for a virtual manufacturing environment with a temporary part grouping and considered a weight-based approach for the objectives of minimizing makespan and total travel distance; Jeon and Leep [15], Egilmez and Süer [16] discussed a two-phase procedure for part-family formation in phase I and scheduling aspects and machine cell formation in phase II. However, Arkat et al [12] and Mak et al [13] have not considered machine duplications, which, if included, can minimize inter-cell moves and minimize makespan under alternate machine routing flexibilities. The weight-based multi-objective approach of Kesen et al [14] is often related to the subjective preferences of the designer to the two criteria, makespan and inter-cell move. The two-phase procedure proposed by Jeon and Leep [15] and Egilmez and Süer [16] is a sequential approach and lacks a concurrent approach of CMS issues. This paper is an attempt to develop a model to consider scheduling and CF decisions concurrently to overwhelm the above issues.

Besides, it is accepted that alternate routings, if available for any operation, has the capability of increasing the utilization of production resources of machine, labor, and tool. If an operation has an option of selecting a machine from a set of different alternatives, and the operation time is a function of the machine selected, then it is a scheduling problem with alternate part routing/process plan. The alternate part routing/process plan enhances effective capacity usage by smoother part flow and better balancing of machine loads in a flexible manufacturing system [17]. Chung et al [18] considered different processing sequences for the same part type. Jeon et al [19], Caux et al [3] and Tavakkoli-Moghaddam et al [7] have included alternate process routing by considering different machine types to do the same operation of a part type. Solimanpur and Foroughi [20] have incorporated both alternate sequences in their alternate routings. However, all the alternate routing considerations ignore the concept of cross-flow operations under the decisions of duplicating machines in CMS problems. The cross-flow is the inter-cell movement of parts from parent cell to identical machines in another cell in spite of the availability of machines in the same cell. It is different from inter-cell exceptional element move where it is the movement of parts due to non-availability of machines in the parent cell. The admittance of the concept of cross-flow inter-cell move in the CF problems would lead to alternate machine routing and provides scheduling flexibility. Hence, the cross-flow concept paves way for cost minimization as a result of the possible reduction in schedule length and increase in machine utilization. Figure 1 illustrates the concept of cross-flow and exceptional element inter-cell moves. Consider a two cell CMS in which cell 1 has machines 1, 2, 3 and 5 and cell 2 has 2, 4, 5 and 6. Suppose that a part that belongs to cell 1 and its operations are to be carried out in the machines 1, 2, 3, 4 and 5, and in the sequence: 1-3-5-2-4, the operation on machine 4 can be done using the machine available in the cell 2 and the operation on machine 5 can be accomplished by using the machine 5 in cell 1 or cell 2. The part undergoes cross-flow inter-cell movement when it is assigned to machine 5 in cell 2 in spite of the availability of machine 5 in cell 1 and exceptional element inter-cell flow to machine 4 in cell 2 due to non-availability of that machine in cell 1.

Figure 1

Cross-flow and exceptional element inter-cell flow of parts in CMS.

The operational efficiency of a CF problem is generally influenced by the resource utilization and material flow of a CMS. Hence, the operational cost of CMS design is evaluated based on machine utility cost (MUC) and material handling cost (MHC). The MUC is based on cost per unit time of utilizing or hiring each machine-type and the time (i.e., makespan time) for which the system has to be utilized/hired for production of a certain demand. It is the machine-wise cost of using the system spread out equally over the expected life of the system. The MUC accounts machine, labor, power and overhead charges, and takes care of investment and labor cost of machines duplicated primarily to serve the purpose of minimizing inter-cell moves. In CMS models by [19, 21, 22], machine operating cost based on the processing time of parts is used as evaluation criteria. But MUC is different from machine operating cost in the way that MUC is based on schedule length and considers the time the parts are in the system. When there is a huge difference in the requirements and processing characteristics of the part-types, then makespan time varies considerably with different cell configurations. On these viewpoints that the inclusion of cross flow, scheduling and machine utility in CF decisions can pave way for the increase in the operational efficiency of CMS in addition to the other advantages of CMS. Taking these aspects into consideration, this paper presents a CF model integrated with scheduling and incorporates machine duplications with cross flow concept to facilitate the design of CMS including operational issues in addition to the design issues.

The proposed CMS model deals with concurrently CF and scheduling decisions. Both the categories are NP-hard and the computation time to find any reasonable solution increases particularly with the size of the problem as the search space increases exponentially [23,24,25]. The mathematical formulations for CMS design are hard to implement for large-sized combinatorial problems due to computational complexities caused by larger, complex and poorly understood search space inherent to large-sized CMS problems [7, 26,27,28]. These complexities lead to the search for alternate ways to solve the real industrial problems and lead to the development of many heuristic algorithm based solution to cell formation problem. Although heuristic approaches do not guarantee to provide optimal solutions, they are useful in producing an acceptable solution in a reasonable time [7]. The popular CF algorithms like rank order clustering [29], MODROC [30], ZODIAC [31], CASE [32], Accord [33], etc. are based on heuristic approaches. As a result of CF problems complexity and with the increase in computer processing speed, recent research papers mostly use meta-heuristic like simulated annealing algorithm (SAA) [34], tabu search [35], bacteria foraging algorithm [36], particle swarm optimization (PSO) [37], hybrid genetic ant lion optimization algorithm (HGALO) [38]. A comprehensive review of genetic algorithm (GA) and artificial neural network (ANN) approaches for CF is given by Chattopadhyay et al [9]. On this concern, to improve the solution within a reasonable computational time, so that there would be a better chance of implementation among practitioners, a hybrid heuristic (HH) that has “SAA embedded with GA” is developed to the CF integrated with scheduling decisions. The proposed heuristic solution methodology finds exceptional elements and thus identifies exceptional machines to be duplicated to reduce/avoid exceptional element inter-cell movement for a given CF solution and generates all CF configurations with or without exceptional machine duplications. Then the heuristic analyses each CF configuration using SAA for optimizing part operation assignment decisions considering cross-flow and GA for optimizing schedule decisions. The best configuration with the minimum cost of operation of all configurations is given as the optimal cell formation.

The rest of the paper is organized as follows. Section 2 describes the model with the environment, problem statement, objective function and mathematical formulation of the proposed CMS model. In section 3, proposed HH using SAA-GA solution methodology is elaborated with an illustrative example. Section 4 discusses the performance of the heuristic with computational experiences carried out on literature problems. Section 5 deals with conclusions and future research directions.

2 Problem description

The problem under study is a CMS design problem that includes cell formation and cell scheduling under cross-flow. This section describes the CMS problem addressing environment, objective criterion, problem statement and mathematical formulation.

2.1 Environment

There are m machine-types (indexed as j) in a cellular manufacturing system under considerations and are to be grouped in C number of cells (indexed as c). It needs to process n parts (indexed as i) with each part i has a specific processing sequence consisting of K_i number of operations (indexed as k) and demand d_i during the planning period. The machine required j_ik and the unit processing time t_ik for operation O_ik (k^th operation of part i) are given. All the parts are available at time zero and processing follows non-preemptive scheduling. The part subcontracting is not considered. The production scenario under consideration is a discrete part manufacturing that has to feed assembly and the production of items can be carried out as a single lot or more number of lots. Single lot production leads to more inventory. On the other hand, the set-up time cost increases linearly with lot sizes. Besides, synchronization of production with assembly is more complicated in the case of more number of lot sizes. Hence production centers that feed assembly operate as a single lot with buffers feeding assembly continuously. It is also to be noted that articles [10, 28, 39] which have considered scheduling aspects of CMS have used the single lot. On these considerations, this paper considers a single lot. In CMS, there are usually 4-8 machines in a cell arranged in U-loop and thus intra-cell move time is less compared to inter-cell moves [10]. Most of the job shop scheduling problems include handling time in their processing times. On this background, this paper considers intra-cell movement time as small and included in the processing time. The model environment permits both inter-cell movements both of exceptional element and cross-flow types. The machine duplications in other cells have a cost advantage of reducing or eliminating exceptional element inter-cell moves and also, under cross-flow considerations, reduce schedule length by using the surplus capacity of the duplicated machines. On the other hand, the machine duplication when done in the same cell, though reduce makespan, it adds an additional machine cost and results only in marginal cost advantage. Thus, duplication in other cells is comparatively more advantageous as it reduces the cost of exceptional element inter-cell moves and schedule length simultaneously. Hence, this paper allows machine duplications within the system and not within each cell (i.e., a cell c can have only one machine of machine-type j).

2.2 Problem statement

The problem is to determine the optimal CF and the schedule for minimum total cost of operation of CMS, which comprises of machine utility cost (i.e., cost based on makespan), and inter-cell movement cost (i.e., includes both cross-flow inter-cell moves and exceptional element inter-cell moves) given the following data:

• Number of parts n, number of machine-types m, number of cells C,

• Parts related data: part processing characteristics for K_i number of operations, machines required j_ik, unit processing time t_ik for operation O_ik and demand d_i,

• Cost related data: machine utility rate of machine-type j (MU_j) per unit time, inter-cell movement cost $IC_{{c^{\prime}c}}$

2.3 Objective criterion

The objective of the model is to minimize the total cost of operation (TC) which is the sum of machine utility and inter-cell costs.

The machine utility cost (MUC) is evaluated by optimal makespan (C_max) which is the maximum completion time $C_{{iK_{i} }}$ of last operation (i.e., K_i) of part i considering all the n parts and the total machine utility rate. The machine utility rate of machine j is fixed as MU_j irrespective of the state whether the machine is working or idle. But, MU_j differs with the machine running state and machine idle state. However, in the practical situation, machine and labor hiring charges should be considered for the entire period and only power consumption cost can be saved in the machine idle time. Hence, this work considers the same machine utility rate for machine working and idle states, as the savings on power consumption is usually comparatively lesser than other costs. The optimal schedule is determined considering the following job shop scheduling constraints like starting time S_ik of operation O_ik is always positive (i.e., $\ge 0)$, the jobs are non-preemptive and part operations follow precedence relationship. It is assumed that the machine utility rate of each machine j per unit time (MU_j) is known. Equation (1) gives the MUC for a planning period.

$$ {\text{MUC}} = \left( {\mathop \sum \limits_{c = 1}^{C} \mathop \sum \limits_{j = 1}^{m} C_{max} \times X_{j.c} \times MU_{j} } \right) $$

(1)

Where,

• $X_{j.c}$ Binary integer variable that indicates the assignment of machine j to cell c

• $$ X_{j.c} = \left\{ {\begin{array}{*{20}l} 1 \hfill & { {\text{if}}\,{\text{machine}}\,j\,{\text{is}}\,{\text{assigned}}\,{\text{to}}\,{\text{cell}}\,c} \hfill \\ 0 \hfill & {\text{otherwise}} \hfill \\ \end{array} } \right. $$

The parts travel between two cells (i.e., inter-cell moves) at the time of cross-flow and exceptional element moves. The cost of transporting a part between any two cells depends on their locations in CMS, part weight and quantity. On the assumption that the difference in weights among the parts is negligible, the unit cost of transportation either for cross-flow or for exceptional element inter-cell moves between cell ${\text{c}}^{\prime}$ and cell c are dependent on the location of cells and quantity and is designated as $IC_{{c^{\prime}c}}$. Equation (2) gives the inter-cell movement cost (ICC) considering both cross-flow and exceptional moves.

$$ {\text{ICC}} = \left[ {\mathop \sum \limits_{i = 1}^{n} \mathop \sum \limits_{k = 1}^{{K_{i} }} \mathop \sum \limits_{{\begin{array}{*{20}c} {c^{\prime} = 1} \\ {c^{\prime} \ne c} \\ \end{array} }}^{C} \mathop \sum \limits_{{\begin{array}{*{20}c} {c = 1} \\ {c \ne c^{\prime}} \\ \end{array} }}^{C} IC_{{{\text{c}}^{{\prime }} c}} \times d_{i} \times Y_{{ik.c^{\prime}}} \times Z_{i.c} } \right] $$

(2)

Where,

• $X_{{j_{ik} .c}}$ Binary integer variable that indicates the assignment of machine $j_{ik}$ to cell c

• $$ X_{{j_{ik} .c}} = \left\{ {\begin{array}{*{20}l} 1 \hfill & {{\text{if}}\,{\text{machine}}\,j_{ik} \,{\text{is}}\,{\text{assigned}}\, {\text{to}}\,{\text{cell}}\,c} \hfill \\ 0 \hfill & {\text{otherwise}} \hfill \\ \end{array} } \right. $$

• $Y_{ik.c}$ Binary integer variable that indicates operation O_ik is assigned to cell c

$$ Y_{ik.c} = \left\{ {\begin{array}{*{20}l} 1 \hfill & { {\text{if}}\,{\text{operation}}\, O_{ik} \,{\text{is}}\,{\text{assigned}}\,{\text{to}}\,{\text{cell}}\,c} \hfill \\ 0 \hfill & {\text{otherwise}} \hfill \\ \end{array} } \right. $$

Z_i.c Binary integer variable that indicates the assignment of part i to cell c

$$ Z_{i.c} = \left\{ {\begin{array}{*{20}l} 1 \hfill & {{\text{if}}\,{\text{part}}\,i\,{\text{is}}\,{\text{assigned}}\,{\text{to}}\,{\text{cell}}\,c} \hfill \\ 0 \hfill & {\text{otherwise}} \hfill \\ \end{array} } \right. $$

Suppose, consider a CMS has to be designed for the manufacturing environment that cannot allow either cross-flow inter-cell movements or exceptional element inter-cell movements. Equation (2) when applied to such cases, cannot differentiate the type of inter-cell movement that is whether cross-flow or exceptional element movements. Thus, in order to address the manufacturing environments that cannot facilitate cross-flow or exceptional element inter-cell moves, the inter-cell cost (Equation (2)) is rewritten as Equation (3) which is the sum of two separate terms, one for cross-flow inter-cell move cost (CFC) and another for exceptional element inter-cell move cost (IEC) and are given by Equations (4) and (5), respectively. It is to be noted here that Equations (4) and (5) use different cost terms for cost of moving unit part from cell ‘${\text{c}}^{\prime}$’ to cell ‘c’ that is ${\text{CF}}_{{\text{c}}^{\prime}{\text{c}}}$ and ${\text{EF}}_{{\text{c}}^{\prime}{\text{c}}}$ for cross-flow and exceptional element inter-cell moves, respectively.

$$ {\text{ICC}} = {\text{CFC}} + {\text{IEC}} $$

(3)

Where,

$$ {\text{CFC}} = \left[ {\mathop \sum \limits_{i = 1}^{n} \mathop \sum \limits_{k = 1}^{{K_{i} }} \mathop \sum \limits_{{\begin{array}{*{20}c} {c^{\prime} = 1} \\ {c^{\prime} \ne c} \\ \end{array} }}^{C} \mathop \sum \limits_{{\begin{array}{*{20}c} {c = 1} \\ {c \ne c^{\prime}} \\ \end{array} }}^{C} CF_{{{\text{c}}^{\prime}c}} \times d_{i} \times \left[ {X_{{j_{ik} .c}} \times Y_{{ik.c^{\prime}}} \times Z_{i.c} } \right]} \right] $$

(4)

$$ {\text{IEC}} = \left[ {\mathop \sum \limits_{i = 1}^{n} \mathop \sum \limits_{k = 1}^{{K_{i} }} \mathop \sum \limits_{{\begin{array}{*{20}c} {c^{\prime} = 1} \\ {c^{\prime} \ne c} \\ \end{array} }}^{C} \mathop \sum \limits_{{\begin{array}{*{20}c} {c = 1} \\ {c \ne c^{\prime}} \\ \end{array} }}^{C} \begin{array}{*{20}c} \\ {EF} \\ \end{array}_{{{\text{c}}^{\prime}c}} \times d_{i} \times \left[ { \left( {1 - X_{{j_{ik} .c}} } \right) \times Y_{{ik.c^{\prime}}} \times Z_{i.c} } \right]} \right] $$

(5)

Hence, total cost of operation (TC) of CMS is formulated as the sum of all the above cost elements (i.e., MUC, CFC, IEC) as given in equation (6).

$$ \begin{aligned} {\text{TC}} & = \left( {\mathop \sum \limits_{c = 1}^{C} \mathop \sum \limits_{j = 1}^{m} C_{max} \times X_{j.c} \times MU_{j} } \right) \\ & \quad + \left[ {\mathop \sum \limits_{i = 1}^{n} \mathop \sum \limits_{k = 1}^{{K_{i} }} \mathop \sum \limits_{{\begin{array}{*{20}c} {c^{\prime} = 1} \\ {c^{\prime} \ne c} \\ \end{array} }}^{C} \mathop \sum \limits_{{\begin{array}{*{20}c} {c = 1} \\ {c \ne c^{\prime}} \\ \end{array} }}^{C} CF_{{{\text{c}}^{\prime}c}} \times d_{i} \times \left[ {X_{{j_{ik} .c}} \times Y_{{ik.c^{\prime}}} \times Z_{i.c} } \right]} \right] \\ & \quad + \left[ {\mathop \sum \limits_{i = 1}^{n} \mathop \sum \limits_{k = 1}^{{K_{i} }} \mathop \sum \limits_{{\begin{array}{*{20}c} {c^{\prime} = 1} \\ {c^{\prime} \ne c} \\ \end{array} }}^{C} \mathop \sum \limits_{{\begin{array}{*{20}c} {c = 1} \\ {c \ne c^{\prime}} \\ \end{array} }}^{C} EF_{{{\text{c}}^{\prime}c}} \times d_{i} \times \left[ { \left( {1 - X_{{j_{ik} .c}} } \right) \times Y_{{ik.c^{\prime}}} \times Z_{i.c} } \right]} \right] \\ \end{aligned} $$

(6)

The differentiation of cost terms as ${\text{CF}}_{{\text{c}}^{\prime}{\text{c}}}$ and ${\text{EF}}_{{\text{c}}^{\prime}{\text{c}}}$ has enabled to address different manufacturing environments by the way of assuming different values as given below:

• For manufacturing environment with no cross-flow facility: $CF_{{c^{\prime}c}}$ has assumed a very big value and $EF_{{c^{\prime}c}}$ = $IC_{{{\text{c}}^{\prime}c}}$ in Equation (6).

• For addressing no inter-cell facility environment: $CF_{{c^{\prime}c}}$ = $IC_{{{\text{c}}^{\prime}c}} {\text{and }}EF_{{c^{\prime}c}}$ is assumed a very big value in Equation (6).

The optimization of Equation (6) for minimum total cost will subsequently eliminate cross-flow decisions or exceptional element move decisions based on their cost terms value. Table 1 shows the values of ${\text{CF}}_{{\text{c}}^{\prime}{\text{c}}}$ and ${\text{EF}}_{{\text{c}}^{\prime}{\text{c}}}$ so that the model can be adopted for different manufacturing environments with respect to inter-cell moves.

Table 1 Values of ${\text{CF}}_{{\text{c}}^{\prime}{\text{c}}}$ and ${\text{EF}}_{{\text{c}}^{\prime}{\text{c}}}$ for different CMS model environments.

2.4 Mathematical formulation

The mathematical formulation of the CMS problem is as follows:

$$ \begin{aligned} {\text{Minimize TC}} & = \left( {\mathop \sum \limits_{c = 1}^{C} \mathop \sum \limits_{j = 1}^{m} C_{max} \times X_{j.c} \times MU_{j} } \right) \\ & \quad + \left[ {\mathop \sum \limits_{i = 1}^{n} \mathop \sum \limits_{k = 1}^{{K_{i} }} \mathop \sum \limits_{{\begin{array}{*{20}c} {c^{\prime} = 1} \\ {c^{\prime} \ne c} \\ \end{array} }}^{C} \mathop \sum \limits_{{\begin{array}{*{20}c} {c = 1} \\ {c \ne c^{\prime}} \\ \end{array} }}^{C} CF_{{{\text{c}}^{\prime}c}} \times d_{i} \times \left[ {X_{{j_{ik} .c}} \times Y_{{ik.c^{\prime}}} \times Z_{i.c} } \right]} \right] \\ & \quad + \left[ {\mathop \sum \limits_{i = 1}^{n} \mathop \sum \limits_{k = 1}^{{K_{i} }} \mathop \sum \limits_{{\begin{array}{*{20}c} {c^{\prime} = 1} \\ {c^{\prime} \ne c} \\ \end{array} }}^{C} \mathop \sum \limits_{{\begin{array}{*{20}c} {c = 1} \\ {c \ne c^{\prime}} \\ \end{array} }}^{C} EF_{{{\text{c}}^{\prime}c}} \times d_{i} \times \left[ { \left( {1 - X_{{j_{ik} .c}} } \right) \times Y_{{ik.c^{\prime}}} \times Z_{i.c} } \right]} \right] \\ \end{aligned} $$

(7)

Subject to:

$$ \mathop \sum \limits_{c = 1}^{C} Z_{i.c} = 1 \quad \forall i $$

(8)

$$ \mathop \sum \limits_{i = 1}^{n} Z_{i.c} \ge 1\quad \forall c $$

(9)

$$ \mathop \sum \limits_{c = 1}^{C} X_{j.c} \ge 1\quad \forall j $$

(10)

$$ \mathop \sum \limits_{c = 1}^{C} Y_{ik.c} = 1\quad \forall i,k $$

(11)

$$ Y_{ik.c} \le X_{{j_{ik} .c}} \quad \forall i,k,c $$

(12)

$$ S_{ik} \ge 0\quad \forall i,k $$

(13)

$$ C_{ik} - S_{ik} - \left( {d_{i} \times t_{ik} } \right) = 0\quad \forall i,k $$

(14)

$$ S_{{i\left( {k + 1} \right)}} - C_{ik} \ge 0\quad \forall i,k = 1 \ldots \left( {K_{i} - 1} \right) $$

(15)

$$ \left( { (Y_{ik.c} \times C_{ik} ) - \left( {Y_{pq.c} \times C_{pq} } \right)} \right)A_{ikpq.c} - \left( { (Y_{ik.c} \times C_{ik} ) - \left( {Y_{pq.c} \times C_{pq} } \right)} \right)\left( {1 - A_{ikpq.c} } \right) \ge A_{ikpq.c} \left( {d_{p} \times t_{pq} } \right) + \left( {1 - A_{ikpq.c} } \right)(d_{p} \times t_{pq} ) \forall c,\left( {i,k} \right), \left( {p,q} \right), i \ne p, j_{pq} = j_{ik} $$

(16)

$$ \left( { (Y_{ik.c} \times C_{ik} ) - \left( {Y_{pq.c} \times C_{pq} } \right)} \right)A_{ikpq.c} \ge 0 \forall c,\left( {i,k} \right), \left( {p,q} \right), i \ne p, j_{pq} = j_{ik} . $$

(17)

$$ C_{max} \ge C_{{iK_{i} }} \quad \forall i $$

(18)

$$ X_{j.c} ,Y_{ik.c} ,Z_{i.c} \in \left\{ {0,1} \right\} \quad \forall i,k,j,c $$

(19)

$$ A_{ikpq.c} \in \left\{ {0,1} \right\} \quad \forall \left( {i,k} \right),\left( {p,q} \right),c $$

(20)

where, $A_{ikpq.c}$ Binary integer variable that indicates the precedence relationship of operations O_ik and O_pq that are assigned to cell ‘c’

$$ A_{ikpq.c} = \left\{ {\begin{array}{*{20}l} 1 \hfill & {{\text{if}}\quad (Y_{ik.c} \times C_{ik} ) - \left( {Y_{pq.c} \times C_{pq} } \right) > 0\quad {\text{or}}\quad {\text{if}} \,O_{pq} \,{\text{precedes}}\,O_{ik} } \hfill \\ 0 \hfill & {\text{otherwise}} \hfill \\ \end{array} } \right. $$

Equation (7) gives the objective function and its first term is machine utility cost (MUC) and whereas second and third are cross-flow inter-cell move cost (CFC) and exceptional element inter-cell move cost (IEC), respectively. Constraint 8 assures each and every part i is assigned to only one cell c of C cells. Constraints 9 and 10 ensure that each cell c should have at least one part i and one machine j, respectively. Constraint 11 checks that each operation O_ik is assigned to only one cell. Constraint 12 satisfies the condition that an operation O_ik is assigned to the cell, only when the machine $j_{ik}$ required for that operation is available in that cell and further it checks availability of cross-flow for each part operation. Constraint 13 ensures that start time (S_ik) of an operation (O_ik) is always positive. The condition that the parts are non-preemptive is assured in the constraint 14. In this constraint, the difference between the completion time C_ik and the starting time S_ik of an operation O_ik is equal to its processing time $d_{i} \times t_{ik}$. Constraint 15 ensures that the completion time of an operation O_ik should be equal or less than the start time its next operation i.e., O_ik+1 and hence it checks the precedence relationship. Constraints 16 and 17 control the condition that no two operations are processed simultaneously on the same machine. In constraint 16, the difference between the completion times of two operations O_ik and O_pq (O_pq precedes O_ik) that requires the same machine j available in cell c should be greater than or equal to the total operation time of the later operation. Constraint 17 assures the precedence relationship among operations done on the machine j available in cell c. Constraint 18 evaluates the makespan time (i.e., C_max) which is the maximum completion time of the last operation (i.e., C_iKi) of all the jobs. Constraints 19 and 20 represent binary integer requirements of decision variables and control variable.

3 Solution methodology: Hybrid heuristic SAA embedded with GA

The CF decisions of the part and machine assignment to cells and part operations assignment with alternative routes as a result of cross-flow are 0-1 integer programming and scheduling parameters are discrete in nature. Hence, this model belongs to the combinatorial optimization problem categorized under the class of NP-hard problems. The combinatorial explosion occurs with the increase in the number of machines to be duplicated and thus corresponding increase in the number of possible cross-flows for the part operations. The complexity further increases with the combinatorial nature of scheduling constraints and CF constraints. The CF problems with machine duplications [5, 6] and cell scheduling problems [28, 40] are dealt mostly as separate problems by researchers as these problems when done as a separate entity itself is complex to formulate and solve. Hence, we have proposed a search space reduction by approaching the problem with initial part-machine grouping and evolve machine duplication and operation assignment decisions with cross-flow consideration and find a feasible schedule with the minimum cost of operation. Due to this complex nature, a heuristic approach is proposed to find a near optimal solution in a reasonable computational time. The meta-heuristics are widely used as they rely on randomization to avoid being trapped in local optimum and they are often intelligent search heuristics based on nature and on neighborhood search procedures [41]. The literature addresses the variety of meta-heuristics: Simulated Annealing Algorithm ‘SAA’ [34]; Tabu Search ‘TS’ [35]; Genetic Algorithm ‘GA’ [42] and Artificial Neural Network ‘ANN’ [9]. Zolfaghari and Liang [43] used SAA, GA, and TS for CF problem and concluded that SAA outperforms GA and TS as later two approaches solution quality greatly depend on search parameters and conditions specified whereas in SAA the selection of search parameter is simple. Further, SAA avoids being trapped in local optima by accepting the worst solutions in the initial stages of the search process [40]. However, the efficiency of meta-heuristics, in general, lies with the design of solution improvement methods and search capabilities (i.e., crossover, mutation, perturbation, quenching rate, number of iterations and so on) and no clear distinction is available for adopting a particular methodology. Most often, the methodology has been selected based on the nature and number of solutions of the search space. And also, the algorithms are combined to bring forth added advantages due to hybridization [44, 45]. On these considerations of the simplicity of SAA and the exhaustive search capability of GA, this paper proposes hybrid heuristic (HH) based on SAA-GA for finding an optimal/near optimal solution. The logic of the proposed heuristic is as follows: First, part – machine groups are formed based on minimum exceptional elements (EE) to have minimum EE inter-cell moves. Secondly, the possible machine duplications in the cells are generated to avoid or reduce EE inter-cell moves and to facilitate cross flow leading to reduced make-span. The third part evaluates the different configurations for minimum total cost of operation (TC) based on the decisions on operation assignments (schedule) considering cross-flow using SAA-GA. Finally, the best configuration with respect to minimum TC is sorted from evaluated configurations. Figure 2 outlines the structure of the proposed HH using SAA – GA. This section delineates the proposed HH with an illustration.

Figure 2

Structure of the proposed HH procedure.

3.1 Input module

In this module, the data pertaining to the problem as stated in the problem description are given as input. Table 2 provides part processing data of 6 parts – 6 machines - 2 cells CF problem, which are generated using uniform distribution in the range of 3–12 for processing time (t_ik), 1–6 for machine number of operations and 100–250 for demand (d_i). The machine-wise utility rate of machine ‘j’ per unit time MU_j is determined by spreading the total machine cost over the expected lifetime of the machine ‘j’. Table 3 illustrates the estimation of MU_j per minute for each machine j assuming expected life period as 5 years with 300 working days per year and 16 working hours per day. Table 4 provides per unit cost for exceptional element and cross flow inter-cell moves to the example problem on the assumption that cell layout is linear.

Table 2 Processing characteristics of example problem.

Table 3 Machine utility rate (MU_j).

Table 4 Exceptional element and cross-flow inter-cell move cost for the unit part.

3.2 Part-machine grouping module

The part assignment decisions (Z_i.c) and thus initial machine grouping (X_j.c) without machine duplications are made based on part processing requirements. The proposed heuristic is structured to adapt the part-machine grouping by any one of the effective cell formation methods. Hence, the solution quality is dependent on the quality of adapted cell formation method. For the illustrative problem, rank order clustering (ROC) is used to provide part-machine grouping as ROC is simple and suits smaller size problems. Table 5 shows part-family and machine cell grouping obtained using ROC. The parts 1, 4, 5, machines 1, 3, 5 are assigned to cell 1 and parts 2, 3, 6, machines 2, 4, 6 are assigned to cell 2 (i.e., set of parts in cell 1 (Z_i.1) = {1,4,5}, set of parts in cell 2 (Z_i.2) = {2,3,6}, set of machines in cell 1 (X_j.1) = {1,3,5}, set of machines in cell 2 (X_j.2) = {2,4,6}). It is noted from table 5 that there are 3 exceptional elements (EE) and thus 3 EE inter-cell moves (shown as italic ‘1’) required for the considered cell grouping.

Table 5 Cell formation by ROC method for example problem.

3.3 Generation of alternative machine cell configurations module

This module elaborates a combinatorial design for the generation of various alternative machine cell configuration and thus alternative decisions on machine assignment parameter $({\text{X}}_{{{\text{j}}.{\text{c}}}}).$ The presence of exceptional elements (EE) brings forth the possibilities of certain machines (i.e., exceptional machines) to be duplicated to avoid or reduce exceptional element inter-cell moves. These machine duplications enable generation of various alternative machine cell configuration that is to be evaluated for the optimum total cost of operation and duplications are based on following strategies.

• Full exceptional machine duplications where all the exceptional machines are duplicated in the required cell and hence there is no exceptional element inter-cell movement but can have cross-flow inter-cell movement.

• Partial exceptional machine duplications where exceptional machines are duplicated partially in the required cell and hence there are reduced exceptional element movements and can have cross-flow movement.

• No machine duplication where no machines are duplicated and there is exceptional element movement and no cross-flow movement.

In this approach, the alternative CF are evolved using the enumerative combinatorics which enables the counting of all possible structures of a given kind and size when certain criteria are met. In the combinatorial design of smaller cases, it is possible to count the number of combinations. For the developed model, considering exceptional machine duplications, if there are ‘x’ exceptional machines to be duplicated and considering ‘y’ combinations at a time without repetitions and number of combinations is denoted in elementary combinatorics texts by C(x,y). In smaller enumerative combinatorics cases, the various possible combinations ‘b’ are finite and total ‘B’ combinations are countable using the counting function given by equation (21).

$$ B = \mathop \sum \limits_{y = 0}^{x} C\left( {x,y} \right) = \mathop \sum \limits_{y = 0}^{x} \frac{x!}{{y!\left( {x - y} \right)!}} $$

(21)

For the example problem in table 5, there are 3 EE with 1EE in cell1 and 2EE’s in cell2 and it needs 3 machines that are machine 6 in cell 1 and machine 5 and 3 in cell 2 to be duplicated to eliminate exceptional element inter-cell movements. The proposed model can have combinations of no machine duplication (C(3,0)), all 3 machines (C(3,3)) to be duplicated (i.e., full machine duplication) and 1 or 2 machines (C(3,1), C(3,2)) can be duplicated (i.e., partial machine duplication). Thus, altogether, the given problem, when evaluated by equation (19), can have 8 (i.e., B = 8) possible machine cell configurations and each ‘b’ combination with duplicated machine numbers shown as underlined and italic are given in table 6.

Table 6 Alternate machine cell configurations for example problem.

3.4 Evaluation module

This module evaluates each CF configuration (i.e., known Z_i.c, X_j.c) in terms of total cost of operation (TC) by using the input of cost related data, part processing data. The assignment of operations to the cells (Y_ik.c) and their completion time (C_ik) influence TC. In order to determine them, a SAA integrated with GA is developed. The SAA evolves optimum alternate machine choices along with its optimal schedule generated by GA and evaluates the objective of minimum TC. Figure 3 shows the schematic structure of the HH search process.

Figure 3

Structure of SAA-GA search process of HH.

Step 1 - Read Input data: The SAA-GA heuristic search process starts with reading parts and cost related data given in section 3.1 and cell related data of part assignments (Z_i.c) from table 5 and machine assignment (X_j.c) from table 6. The search process is illustrated by a machine cell configuration with full exceptional machine duplications (i.e., b = 1 in table 6 with part and machine assignments as Z_i.1 = {1,4,5}, Z_i.2 = {2,3,6}, X_j.1 = {1,3,5,6}, X_j.2 = {2,3,4,5,6}).

Step 2 – Identification of operations with alternate machine choices: With the known machine assignment decisions $\left( {{\text{X}}_{{{\text{j}}.{\text{c}}}} } \right)$ and the part assignment decisions (Z_i.c) to the cells ‘c’ and considering cross-flow, the operations that involve the duplicated machines are the one with alternate machine route choices. Table 7 lists all such operations that can have alternate machine assignments and provides alternate route choice numbers.

Table 7 Alternate machine route choices for CF configuration considered.

Step 3 – Initialisation of SAA parameters: The SAA approach requires an initial guess for parameter values and initialization of those values. The initial temperature (T₀) need to be large enough to enable the algorithm to move off a local minimum but small enough to move off a global minimum and also this value is defined based on applications objective value [46] and T₀ is taken as 4500. The number of iterations for each temperature (IT_max) is often related to the search space and in this algorithm and it varies with the number of operations with alternate machine route choices (‘a’) and hence the search space. Thus, IT_max is taken as ‘a’. The search process proceeds until the current temperature (T_i) is above the final temperature (T_f) whose value is 500. Table 8 lists various SAA search parameters value used in this algorithm.

Table 8 SAA search parameters.

Step 4 – Generation of SAA String: The SAA approach requires an initial SAA string (SA_i) to start the search process. In the proposed algorithm, the length of the SAA string is decided by the number of operations with alternate machine choices. If there are ‘a’ operations that have alternate machine choices, the length of the SAA string is taken as ‘a’. Then, the initial SAA String (SA_i) is generated with the string values being alternate machine route choice number and is generated randomly. For instance, string SA_i given below shows a SAA string of length 10 with the alternate route choice number from table 7.

$$ SA_{i} = \left\{ {1,1,2,1,2,2,1,1,2,2} \right\} $$

The fourth value of string SA_i is 1 and the value indicates that the operation O₂₃ is assigned to the machine of route choice number 1 i.e., machine 6 in cell 1 and this particular operation assignment undergoes a cross-flow movement of parts.

Step 5- Fitness Evaluation for SAA by GA based scheduler: After generating a SAA string (SA_i), the string values are decoded using alternate machine route choice number and therefore, operation assignment for operations with alternate machine choices are known (i.e., Y_ik.c are known $\forall$i,k). The cross-flow cost (CFC_i) for the decoded string SA_i can be derived using equation (2). Table 9 gives the decoded string values for the SAA string SA_i shown in step 4.

Table 9 Operation assignment for SA_i string.

It is noted from table 9 that operations O₂₃, O₄₂, O₅₃ has cross-flow movements. As the machine cell configuration (b) is known, the exceptional element inter-cell movement cost (IEC_b) and total machine utility rate (MUR_b) of configuration ‘b’ can be determined. Equation (22) gives the total machine utility rate (MUR).

$$ {\text{MUR}} = \mathop \sum \limits_{{{\text{c}} = 1}}^{\text{C}} \mathop \sum \limits_{{{\text{j}} = 1}}^{\text{m}}\, {\text{X}}_{{{\text{j}}.{\text{c}}}} \times {\text{MU}}_{\text{j}} $$

(22)

For instance, for the considered machine cell configuration of full exceptional machine duplication, there is no exceptional element inter-cell movement and hence IEC_b = 0. The machine assignment of X_j.1 = {1,3,5,6} and X_j.2 = {2,3,4,5,6} for configuration b = 1 enables determination of MUR_b and its value is 10.1. At this stage of evaluation, the machine utility cost (MUC_i) of String SA_i is the only unknown and it requires optimal make-span time (M_i) derived from optimal or near optimal schedule (sch_i) of a string SA_i. The make-span time of the system is the time to complete all the parts in all the cells. In the proposed heuristic approach, the optimal make-span time is found by GA based scheduler proposed by Jawahar et al [47]. The scheduler produces a feasible schedule satisfying the job-shop scheduling constraints and evaluates using makespan time as fitness parameter. The M_i determined by GA based scheduler is utilized for evaluation MUC_i for string SA_i using equation (1). Equation (23) gives the SAA objective function (S_i). Table 10 illustrates the fitness evaluation for string SA_i.

Table 10 Fitness evaluation for string SA_i.

$$ {\text{S}}_{\text{i}} = {\text{MUC}}_{\text{i}} + {\text{CFC}}_{\text{i}} + {\text{IEC}}_{\text{b}} = \left( {{\text{M}}_{\text{i}} \times {\text{MUR}}_{\text{b}} } \right) + {\text{CFC}}_{\text{i}} + {\text{IEC}}_{\text{b}} $$

(23)

Step 6 – Perturbation: In this proposed approach, the perturbation is done to explore the neighborhood of the current solution. The perturbed SAA String (SA_p) is generated by selecting two random integers in the range of 1-‘a’ (a-number of operations with alternate machine choices) and randomly assigning cell identifier to the selected random positions. For instance, the perturbed string SA_p formed from string SA_i is given below. The shown strings choose randomly 4^th and 7^th positions and randomly assign cell identifier as 2 and 1, respectively.

$$ \begin{aligned} {\text{SA}}_{\text{i}} & = \left\{ {1,1,2,1,2,2,1,1,2,2} \right\} \\ {\text{SA}}_{\text{p}} & = \left\{ {1,1,2,2,2,2,1,1,2,2} \right\} \\ \end{aligned} $$

The objective function (S_p) of each perturbated string (SA_p) is evaluated using fitness evaluation detailed in previous step. Table 11 illustrates the fitness evaluation of perturbated string SA_p.

Table 11 Fitness evaluation for string SA_p.

Step 7 - Hill climbing: The global best solution (S_g) and global best schedule (sch_g) are initialized with the initial SAA string values and further solution improvements and their updation with S_g and sch_g are decided in this step. The acceptance probability (P_r) of accepting a poor perturbed solution (S_p) when it is poorer than the current solution (S_i) and thus change in entropy (ΔE) greater than 0 and is given by Equation (24). A random number r is generated in the range of 0< r <1 and if r is less than acceptance probability (P_r), then the solution is accepted and updated as the current solution for the perturbation in next iteration.

$$ {\text{P}}_{\text{r}} = {\text{e}}^{{ - \frac{{\Delta {\text{E}}}}{{{\text{T}}_{\text{i}} }}}} = {\text{e}}^{{ - \frac{{\left( {{\text{S}}_{\text{p}} - {\text{S}}_{\text{i}} } \right)}}{{{\text{T}}_{\text{i}} }}}} $$

(24)

Step 8- Cooling schedule: This algorithm uses the most common cooling schedule of geometric rule for temperature reduction and is given in Equation (25).

$$ {\text{T}}_{\text{i}} = {\text{Q}}_{\text{R}} \times {\text{T}}_{\text{i}} $$

(25)

where Q_R is quenching rate and has the value 0<Q_R<1. The literature has reported that Q_R in the range of [0.8, 0.99] would provide good results [46]. Thus, Q_R is taken as 0.9 in this approach.

Step 9 - Termination criterion: The final temperature value (T_f) is taken as the stopping criterion in the proposed algorithm. Thus, the search process proceeds until the current temperature (T_i) is above the final temperature (T_f).

Step 9 – Output results: After the termination criteria is met, S_g and sch_g are given as an optimal solution. Table 12 shows the optimal cost parameters for the CF configuration with full exceptional machine duplications. Figure 4 shows Gantt chart of the optimal schedule for the CF configuration. The optimal makespan time is found to be 4680 and there is no exceptional element inter-cellular movement as all the exceptional machines are duplicated. It is to be noted from figure 4 that the operation O₁₃ is assigned with cross-flow as even though machine 5 available in cell 1 to which part 1 is assigned. It is also to be noted that if this cross-flow not allowed, make-span time is increased further.

Table 12 Optimal cost for CF configuration with full machine duplication.

Figure 4

Gantt chart for CF configuration with full machine duplication.

3.5 Termination module

In the termination module, the proposed heuristic approach checks for the termination criteria of whether all ‘B’ CF configurations are evaluated. Thus, the evaluation module is repeated for all ‘B’ CF configurations developed in alternative machine cell formation module.

3.6 Output module

The best machine cell configuration with the minimum total cost (TC) is found after sorting all ‘B’ CF configurations based on total cost (TC). Table 13 gives results for each ‘b’ CF configuration.

Table 13 Results for alternate CF configurations of example problem.

The results in table 13 indicates that the optimal machine cell configuration with minimum TC is partial machine duplication of machine 5 in cell 1 and machine 6 in cell 2. It is seen from table 13 that the machine duplications reduces makespan time and thus compensates increased total machine utility rate. It is also noted that cross-flow is preferred only when it reduces makespan and compensates the increase in cross-flow cost. Figure 5 shows the schedule for optimal CF configuration. It is seen from figure 5 that operation O₁₃ has cross-flow, inter-cell movement for operation O₆₂ and optimal makespan time is 4680.

Figure 5

Gantt chart of schedule for Optimal CF configuration.

4 Performance study

The proposed heuristic procedure with the alternate configurations for a particular part-machine incidence matrix is programmed in MATLAB and implemented on HP dx2280 MT model X86 based PC. Table 14 shows the input data of part processing data (Tables A1a –A12a) and cost coefficients like machine utility rate per unit time MU_j (Tables A1b –A12b), inter-cell $IC_{{c^{\prime}c}}$ and cross-flow movement cost per unit $CF_{{c^{\prime}c}}$ (Tables A1c –A12c) and the problem size of the test problems taken from literature. The part-machine incidence matrix indicating the CF stage of the CMS design is adopted as given in literature and the processing characteristics of the processing sequence, processing time and demand (d_i) of the parts are generated for the problems for which such data are not available. The problems are solved using the proposed heuristic approach and mathematical approach by ILOG CPLEX solver (12.6 academic edition) with the branch limits of 10⁷ and 10⁸. Table 15 shows the optimal CF solution for literature source data (i.e., without machine duplication), heuristic and mathematical approaches with its cost components for each problem. Besides, the solutions of the approaches are compared in terms of relative percentage of deviation (RPD) of a solution from the best CF solution (TC_best), given by Equation (26). Table 16 gives the comparison of CF solutions in terms of total cost of operation (TC), RPD and computational time. The TC_best is shown in bold format in table 16.

$$ {\text{RPD}} = \frac{{{\text{TC}} - {\text{TC}}_{\text{best}} }}{{{\text{TC}}_{\text{best}} }} $$

(26)

Table 14 Literature problem and input data.

Table 15 Cost components and CF solution for source data, heuristic approach, and mathematical programming approach.

Table 16 Comparison of the CF solutions.

The results shown in table 15 reveal that the integrated CF and scheduling decisions with cross-flow have resulted in the minimized operational cost of CMS. The comparison of CF solutions in terms of RPD (shown in table 16) reveals the following:

• CPLEX gives the best solution to the problems 1–4, the problems those with the number of decision variables and constraints are less than 100 and 500, respectively.

• When the number of variables is around 200–300, and the number of constraints are between 1000 and 2000 (problems 5–8), mixed responses are witnessed.

• The proposed heuristic provides better solutions than CPLEX solutions to the problems 9 and 10, where the number of decision variables is in the order of 500 and the number of constraints is around 500 and 4000, respectively.

• When the number of decision variables and constraints are greater than 1000 and 10000 (problem 11 and 12), CPLEX does not produce any results stating ‘search space exceeded’, whereas the proposed HH is capable of providing solutions.

Further, the computational time of CPLEX shows an exponential increase in the computational study and not able to provide a solution at all for larger problems (problems 11and 12). The lesser computational time experienced with the heuristic, compared to CPLEX solver, is owing to the reduced search space resulted due to the fixation of the part and machine assignment and machine duplications to exceptional elements. Though the problem is solved in the design phase for which computational time is least important, the solution approach has to produce near-optimal solutions to the problem that has problem sizes of real manufacturing scenario. Thus, it can be concluded that the proposed HH is computationally efficient and can be useful to find solutions closer to optimal for the problems of the dimension of 500 decision variables and 1000 constraints, which is the case with most of the industrial cases. CPLEX can be used for the smaller size problems (i.e., the number of decision variables less than 500) due to lesser search space.

5 Model validity

The model features are validated by studying the effect of integration, machine duplication, and association of scheduling and cross-flow.

5.1 Effect of integration

The proposed CMS design model integrates the structural design issue decisions of cell formation with operational issue decisions of scheduling under machine duplication and cross-flow considerations. The proposed objective criterion uses the new cost parameter of machine utility cost (MUC) to integrate CF and scheduling. The MUC justifies the feasibility of machine duplication. The effect of integration is studied by comparing the objective criterion of the following cases:

• The operational cost of the CF decisions (i.e., part and machine assignment decisions) as given in source literature problems is shown in table 14. As these literature problems do not have associated scheduling, the optimal schedule decisions are generated using SAA-GA module of HH. Further, these problems have not considered machine duplications and hence, have no cross-flow facilitations. These make model be without machine duplication and cross-flow. The objective values of this model (i.e., without machine duplication and cross-flow) are given as ‘source data total cost (TC)’ values in table 16.

• The minimum operational cost of each problem given in table 14 evolved by optimizing the CF configuration considering machine duplication strategy along with the association of scheduling under cross-flow considerations. Thus, the proposed model is with machine duplication and cross-flow facilitation. The best cost solutions are given by either proposed HH solutions or ILOG CPLEX solver and are shown in table 16 (shown as bold font).

Figure 6 shows the comparison of the proposed model’s best objective values with objective values for literature CF decisions. This comparison reveals that the inclusion of scheduling under machine duplication and cross-flow environments could evolve optimized minimum cost grouping and operation assignment decisions. This proves that integration brings forth the effective realization of CMS advantages. Further, the simultaneous approach of design and operational decisions enable designers to design better performing efficient and effective cells.

Figure 6

Comparison of literature grouping data with the proposed model grouping.

5.2 Effect of association of scheduling and cross-flow

The proposed model allows cross-flow inter-cell movement under machine duplication environment. This cross-flow improves scheduling flexibility, reduces makespan and hence reduces operating cost. Hence, cross-flow increases machine utilization and can justify added machine investment due to machine duplication. This altogether results in better performing cells that have minimum operating cost. The effect of cross-flow movement is studied by evaluating the optimal operation assignment decisions given in figure 5. Figure 7 shows the optimal schedule for CMS environment with machine duplication and no cross-flow. The cross-flow operation O₁₃ that is assigned to machine 5 in cell 2 is shifted to machine 5 in cell 1 as shown in figure 7. It is noted that shifting of cross-flow operation O₁₃ results in the increase of makespan from 4680 to 5100 and leads to increased operating cost. This reveals that association of scheduling and cross-flow gives cost advantageous optimal decisions.

Figure 7

Optimal CF and scheduling with no cross-flow considerations.

5.3 Effect of machine duplication

The model considers machine duplication and allows duplication only in other cells. This strategy is studied by evaluating the example problem considering the machine duplication in the same cell and is compared with the operating cost of the optimal configuration shown in figure 5. Figure 8 shows the schedule for CF configuration with machine 5 being duplicated in the same cell of cell 1. It is seen that shifting machine number 5 from cell 2 to cell 1 makes the operation O₂₁ as inter-cell move and raises inter-cell move cost. However, the cross-flow move of operation O₁₃ is eliminated. But even though cross-flow is avoided, the inter-cell move cost is comparatively more in this case and hence leads to an increase in operating cost. However, these comparisons are data dependent and hence future research has to consider machine duplication in the same or other cells.

Figure 8

Optimal decisions when machine duplication allowed in the same cell.

5.4 Discussions

Table 17 consolidates the cost comparison of various CMS environment cases discussed above. The cases considered are with and without machine duplication, machine duplication in same and other cell and with and without cross-flow. The comparison of the four cases shown in table 17 reveals that:

Table 17 Cost comparison for different CMS environment cases.

• The machine duplication even though increases machine investment cost (i.e., here MUR increased from 7.3 to 8.6 for cases of without and with machine duplication, respectively as shown in table 17), the additional cost can be justified by reduced makespan time (i.e., reduced from 5650 to 5100) and reduced inter-cell movement cost (i.e., reduced from 5300 to 1800). Altogether, the operating cost is reduced from 46545 to 45660.

• The comparison of cases 2 and 4 (shown in table 17) that consider no cross-flow (i.e., case 2) and cross-flow considerations reveals that cross-flow reduces the makespan time from 5100 to 4680 and reduces operating cost from 45660 to 43548. Thus, cross-flow gives scheduling flexibility, enhances machine utilization, justifies machine duplication and finally reduces the cost of operation of CMS.

• On considering cases 3 and 4 of table 17 which deal with machine duplication in same cell (case no. 3) and machine duplication in other cell (case no. 4), it is seen that for this example problem there is an increase in inter-cell movement cost from 1800 to 3800 and hence increase in cost of operation. However, this comparison is data dependent.

The above discussions on model validity can be summarized as follows:

• The model evolves cost advantageous decisions of integrated CF and scheduling.

• Machine duplications are done only when the additional machine investment cost is lesser than machine utility cost and inter-cell cost.

• The cross-flow facilitates routing flexibility and reduces operating cost.

Thus, the proposed model is a better representation of a practical CMS manufacturing environment. The model assists the designers to design efficient and effective cells.

6 Conclusions

In this paper, a CMS design model integrating design and operational issues is proposed. A cell formation (CF) model is developed based on cell scheduling (CS) of part operations. The model is facilitated with machine duplications and enhances scheduling flexibility by permitting cross-flow. The proposed integrated approach is vital for a CMS design to represent the practical CMS environment. The model is mathematically formulated with the objective of minimizing total cost of operation (TC) which comprises of machine utility cost and two types of inter-cell costs namely cross-flow inter-cell movement cost and exceptional element inter-cell movement cost.

A hybrid heuristic (HH) that includes SAA embedded with GA scheduler is proposed and illustrated with an example. The HH identifies exceptional elements (EE) for a cell grouping and develops alternate machine cell configurations. The HH analyses each alternate configurations by using SAA which optimizes operation assignment considering alternate machine routings and GA which generates the optimal schedule for operation assignment decisions by SAA. The computational analysis is done with 12 literature problems that are solved using the proposed HH and CPLEX mathematical programming solver. From the comparisons of HH and CPLEX solutions in terms of relative percentage of deviation (RPD) and computational time, it is concluded that the proposed HH is computationally efficient and able to find solution closer to optimal for large-sized problems (in the dimension of 500 decision variables and 1000 constraints). The computational capability of HH is due to reduced search space for large-sized problems caused by fixing part and machine assignment and analyzing only machine duplications of exceptional elements.

The model features of integrated CF and CS decisions under machine duplications and cross-flow are compared with the grouping decisions of literature problem with the strategy of no machine duplications. The comparison reveals that the proposed model could evolve better cell grouping decisions. Thus it can be inferred that the proposed model identifies cost advantageous decisions and thus provides an improved CMS design that has minimized operational cost.

The heuristic algorithm efficiency is limited by the method adopted for part-machine grouping and for scheduling. The heuristic approach is relevant when part-machine grouping has limited EE and hence grouping has computable alternate machine cell configurations. In future research, meta-heuristics can be used for part and machine assignment decisions to improve the computational efficiency of larger size problems. The other algorithms hybridization like SAA and PSO, GA and PSO are to be evaluated for improved computation. The model can be extended by allowing machine duplications to have more than one machine-type in each cell, considering intra-cell movement cost and lot splitting.