Designing multi-product lines: job routing in cellular manufacturing systems.
An operation sequence-based method which integrates intra-cell layout cost with cell formation to minimize the total cost of the materials flow and machine investment is developed here for designing a cellular manufacturing system. The method comprises three distinct approaches: part-family
1. Introduction
The Cellular Manufacturing System (CMS) is an application of Group Technology (GT) which is viewed as an efficient manufacturing philosophy. The main mechanism of CMS is to partition parts that have similar attributes to form part-families, and also to group machines together to form machine-cells, according to the requirements of each part family. A cellular manufacturing system is a medium-volume/medium-variety production system that can adapt to a versatile market and the rapid development of technology. With the rapid development of technology and short life cycles of new products in the present competitive market, the CMS approach has attracted the attention of many researchers and practitioners because of its practical utility.
The most important problem in the design of cellular manufacturing systems is the cell formation problem. In general, three main objectives exist in the cell formation procedure: [1] part family formation; [2] machine cells formation; and [3] the allocation of families to the machine cells. There are many factors that are involved when the cells are created, these include the machine requirement, machine setup times, utilization, workload, alternative routings, machine capacities, operation sequences, setup cost, and cell layout [1-4]. In the last three decades, a lot of methods have addressed the cell formation problems that have been developed by researchers based on these factors. Past research has mainly focused on the machine requirement factor. Typically, there are two kinds of methods developed to deal with this problem: the binary machine-part matrix method and the clustering method. The binary machine-part matrix method was first explored by King [5] and King and Nakornchai [6] and is the most cited research work in this field. The clustering method is based on the machine requirement similarity coefficient of the parts which was first explored by McAuley [7]. The basic mechanism of this method is to group together these parts that have the highest value of the machine requirements similarity coefficient to form the cells. The operation sequence, an ordering of the machines on which the part is sequentially processed [1], is ignored by these two kinds of methods. Tam [8] notes that these methods have the single objective of increasing the production effectiveness by grouping parts that require similar machinery resources and manufacturing them in "self-sufficient" cells, however the use of these methods cannot guarantee a reduction of the routing time between manufacturing cells. Different facets of the bottleneck problem in cellular manufacturing systems have been addressed in the current literature [9-14].
The fulfillment of the purpose and objectives of the group technology task in a production system is dependent on the choice of the machines and the impact of the materials flow [15]. However, the sole consideration of machine requirements can reflect only on the choice of the machines. It is obvious that the impact of the materials flow is not considered when only the machine requirements are considered. Therefore, in recent years, many researchers emphasize operation sequence, a very important factor in the manufacturing system, because it can reflect not only the machine requirements of the parts but also the flow pattern of those parts. However, the parts do not show a direct operational relationship with the machines; in fact each part has a set of operations that relate directly to the machine [8,16]. Therefore, consideration of the operation sequences in the cell formation problem is realistic to successfully integrate the choice of machine and the impact of the materials flow in GT.
1.1. Background literature
Choobineh [15] has proposed a two-procedure cell formation method in order to minimize the material handling cost and streamline the material flow in each cell. Based on operation sequence similarity coefficients, the parts are partitioned in the first stage of this method to form part-families. In the second stage, he proposed an integer-programming model that specified the number of cells, the type and the number of machines in each cell, and the assignment of the part families to the cells. Akturk et al. [17] have presented a new multi-objective model that considered manufacturing attributes and operation sequences, and developed a dissimilarity coefficient based on the operation sequences. Wu and Salvendy (4] have described a network analysis method for the cell formation problem by using a undirected graph (network) to model the problem by considering the operation sequences. They used the Ford-Fulkerson algorithm to partition the network to minimize interaction between cells, and later further simplifie d it in order to reduce the computational time.
Selvam and Balasubramanian [18] have developed a heuristic to group those parts that have approximately the same operation sequences, to minimize the materials handling and machine idle capacity costs. The operation sequences similarity index matrix and its computation method are presented, and the parts are grouped according to this similarity index matrix. Tam [8] has developed a new similarity coefficient based on the operation sequences by using the concept of Levenshtein's distance between two sentences. The parts are then grouped to form part families by using the k-Nearest-Neighbor (kNN) clustering method. Tam also explained the relationship between the part, operation, and machine, and emphasized the importance of operation sequences in cell formation problems.
Logendran [19] has indicated the impact of the sequence of the operations and layout in the cell formation problem and proposed a model to form the cells by evaluating the intercell and intracell moves with the operation sequences. He also evaluated inter-cell movements considering the layout of cells. Logendran [20] has also proposed a two-phase algorithm to address the problem of duplicating bottleneck machines under budgetary limitations. The model considered the cost of intercell movements, but the cost due to machine investment was ignored, i.e., the tradeoff between the inter-cell movement and the machine investment costs were not considered. Irani et al. [21,22] have provided a virtual cell concept that exploits layout issues and inter-cell flows for the machine-sharing problem. Seifoddini [23] has presented a cost-based method to deal with the duplication of bottleneck machines, in which both inter-cell movement and machine investment costs were considered, but the solution could not be guaranteed to be optimal because of the lack of a mathematical model. The issues relating to linear or row layout have also been addressed in the literature [2,24-30].
The cell formation problem is computationally complex, and even under fairly restrictive conditions it is known to be NP-complete [31]. Consequently, most research efforts have focused on developing heuristics rather than devising optimal solution techniques. Vakharia and Wemmerlov [1] have focused on the cell formation problem with three interrelated issues: part families identification, cell equipment (machines) and their mutual allocation to each other. While achieving these goals, they recognized several other objectives and constraints that become important in cellular manufacturing. These are cell independence, cell flexibility, inter-and within-cell layout, cell size, cell utilization level, and additional investment. Cellular manufacturing is one of the foundations of just-in-time systems. It is clearly evident that simplified flows are of great concern in industrial applications. A flowline-type cell reduces material handling, eases conveyor use, transfers batches well, improves visible control, and eases monitoring of the flows.
A few previous papers have addressed the integration of cell formation, intra-cell layout and material flow problems based on operation sequence. Vakharia and Wemmerlov (V&W) [1] have proposed a four-stage material flow approach based on operation sequences to integrate the intra-cell layout and the material flows in cell formation problems by using clustering technology. They presented a methodology first to accumulate the data on the operations sequences of jobs, forecast demand, estimated processing times, machine capacity and capability, and investment for new equipment. Second, they analyzed the data to identify single and dual operations, and separating the backtracking of operations. Third, parts are grouped to reduce the problem size by reducing the number of operations sequences and finally, the composite operation sequences, in conjunction with the order of similarity, are considered for forming the lines. In this approach, the part families are formed based on an operation sequences similarity coe fficient; then, machines are assigned to each part family and the intracell layout is determined considering the machine load. The V&W method operates in a sequential fashion with alternative paths created different stopping rule parameters or by imposing restriction on cell size, utilization or investment. Queueing or simulation models could supplement the dynamic perspective of the static solutions to this problem.
Important issues such as inter- and intra-cell material flows and the machine investment costs are not considered simultaneously by most researchers. Other factors such as cell size and budgetary limitations for machines are also conveniently ignored on the excuse of its growing complexity to solve large instances of the problem. The purpose of this paper is to develop an operation sequence-based method to prescribe a Cellular Manufacturing System (CMS) that considers materials flows, machine investment cost, and other important factors such as cell size and budgetary limitations for machines to integrate cell formation and intra-cell layout configuration. Since part of the proposed study overlaps with that of Vakharia and Wemmerlov [1], solutions of the V&W method can be used as a base for comparison with the solutions of the proposed model, especially in order to evaluate the models with respect to final assignment of parts and machines in a cell, savings in material flow and related costs.
The paper is organized in the following steps. The cell formation problem and the basic methodology are discussed in Section 2. A three-phase operation sequence-based cell formation methodology is developed in this research and the part-family formation problem of it is discussed in Section 3. The second phase of the problem, which assigns machines to part families is explained in Section 4, followed by the intra-cellular layout problem in Section 5, and applications and implication of the results of this study are discussed in Section 6. A conclusion with an indication of future research is presented in Section 7.
2. The problem and basic methodology
In a Multi-Product Flowline (MPF), there are four types of flow movements: in-sequence, by-pass movement, backtracking movement and repeat operation [29,30,32-35]. In-sequence operations are those operations that are in the same relative order of the machines in a production line. Of these four movements, in-sequence flow is the most desirable because of its unidirectional movement. By-pass flow does not violate the direction of flow although it creates sequence jumping that may complicate the flow. When the sequence of operations for a job does not specify a machine located downstream with respect to its current location, the job has to backtrack (travel upstream) in order to complete the required operation. Due to variations in the number of operations in the operation sequences and in the operations themselves, it is unlikely that a routing (sequence of workstations/machines) will accommodate all the sequences without incurring backtracking movements. Backtracking flow is the least desirable movement since it complicates the flow and violates the flow direction. A repeat operation can be treated as an aggregate operation, and thus can be ignored in flowline analysis.
Given a set of parts with their operation sequences, and a set of machines to perform these operations, the cell formation and intra-cell layout (CM&IL) problem discussed here is to develop an approach to form part-families and machine-cells, and to determine intra-cell layout in order to minimize the materials flow cost and the machine investment cost in a manufacturing system.
The process of designing the cellular manufacturing system is decomposed into three phases: (a) part-family formation -- those parts with a similar operation sequence are grouped into the same part family in order to make the intra-cell machine arrangement easier so as to minimize the intra-cell backtracking flow cost; (b) the machine cell formation problem assigns machines to each part-family to form the cell so as to minimize the total cost of the inter-cell movement and the machine investment cost; and (c) the intra-cell layout design phase in which the machines are arranged in a linear layout so as to minimize the intra-cell backtracking cost. In this method, part demand, cell size, and financial limitations are also considered to influence the decision.
The methodology for designing the cellular manufacturing system is composed of three phases, all of which are inherently based on the operation the sequences. In the first phase, that deals with part-family formation, a clustering procedure based on the operation sequence similarity coefficient is applied to form the part-family that maximizes the operation sequence similarity between the parts and minimizes the backtracking operations in each part-family. The result of this phase makes the operation sequence pattern in each part-family cohesive and builds a good foundation for the intra-cell layout design for each cell. Ho et al. [35] have also stated that the main purpose of intra-cell design is to achieve a logical layout configuration in which the materials flow is mostly in sequence and unidirectional. The purpose of this phase is to consider the operation sequence pattern and materials flow during the cell formation procedure instead of considering them after cell formation.
In the second phase, machines corresponding to the operations of parts in each cell are allocated to each cell so as to minimize the sum of the machine investment cost and the inter-cell flow cost, because the inter-cell flows between cells are related with the machine assignments. If a machine which is needed to perform an operation on the parts in a part-family is not assigned into that part-family, an inter-cell flow will be incurred, and a machine is needed to complete the processing. However, at the same time, because this machine is not assigned to the part family, the corresponding machine investment cost is saved by this machine assignment. Therefore, this phase finds a machine assignment that minimizes both machine investment cost and inter-cell flow cost.
In the third phase, the machines that have been assigned to each cell in the second phase are assigned to the locations in each cell to form flowline(s) in order to minimize the intra-cell flow cost. Actually, this phase can be treated as a multi-product flowline design problem the purpose of which is to find an intra-cell layout for each cell in order to minimize the intra-cell flow cost, especially, the backtracking flow cost, in each cell.
2.1. Notation
The following notation will be used to formulate the problems or to interpret the results:
[C.sub.j] = set of parts in the part-family j (j = 1,2,...,K);
[C.sub.p] = material handling cost for intra-cell backtracking of part p (dollars/unit distance);
[c.sub.p] = average cost of inter-cell movement for part p (p = 1,2,...,[N.sub.B]) ($/unit flow);
[d.sub.ikjh] = backtracking distance between machine i at location k and machine j at location h;
[d.sub.ikjh] = {k - h, if h [less than or equal to] k, 0 otherwise;
[D.sub.p] = demand of part p (units/period);
F = desired number of part-families that a designer expects to form;
[F.sub.B] = number of cells that need the bottleneck machines, [F.sub.B] [less than or equal to] F;
[F.sub.c] = the cardinality of cell c, [F.sub.c] = \ [M.sub.c] \, i.e., number of machines in cell c;
[F.sub.i] = the set of part-families that need machine i;
[I.sub.ij] = potential inter-cell movement cost of part-family j due to bottleneck machine i;
[J.sub.j] = job or part j (j = 1,2,...,N);
K = number of part families;
L = annual budget outlay for the bottleneck machines (dollars/year);
M = total number of machines;
[M.sub.B] = number of bottleneck machines;
[M.sub.c] = final set of machines in cell c;
[M.sub.max] = maximum number of machines in one cell;
[[M.sup.0].sub.c] = original set of machines assigned cell c;
[[M.sup.B].sub.c] = set of duplicated machines for cell c;
[[m.sup.p].sub.ij] = number of movements part p requires from machine i to machine j;
N = total number of parts;
[N.sub.B] = number of parts that need the bottleneck machines;
[N.sub.j] = total number of machines assigned to the part-family j;
[N.sub.p] = total number of operations of part p;
[[N.sup.S].sub.pq] = number of in-sequence operations of part p (p = 1,...,N; p [not equal to] q) to part q;
[n.sub.ip] = number of movements made by the operation sequence of part p to bottleneck machine i (i = 1,2,...,[M.sub.B];
[Q.sub.i] = number of part-families which need machine i;
[R.sub.i] = annual cost of buying and maintaining a bottleneck machine i (i = 1,2,...,[M.sub.B];
S = an N x N similarity coefficient matrix of N parts;
[S.sub.pq] = similarity coefficient of part p to part q , [S.sub.pq] = [[N.sup.S].sub.pq]/[N.sub.p];
U = set of non-bottleneck machines;
[U.sub.max] = maximum number of parts allowed in a part-family;
[V.sub.ij] = potential benefit of assigning bottleneck machine i to the part-family j;
[w.sub.pq] = {1 if part p is assigned to family q, 0 otherwise;
[x.sub.iK] = {1 if machine i is assigned to the location k, 0 otherwise;
[y.sub.ij] = {1 if bottleneck machine i (i = 1,2,...,[M.sub.B]) is assigned to part-family j (j = 1,2,...,[F.sub.B], 0 otherwise
3. Part-family formation
In-sequence operations are those operations that are in the same relative order in the operation sequence of one part with respect to the operation sequence of another part. For example, if the operation sequences of parts 1 and 2 are 1-2-3 and 1-3-2, respectively, the in-sequence operations of part 1 to part 2 are operations 1 and 2. Similarly, the in-sequence operations of part 2 to part 1 are operations 1 and 3.
3.1. Part similarity coefficient evaluation
A clustering procedure based on this similarity coefficient can maximize the total in-sequence flow in a part family. An operation sequence-based similarity coefficient of part p to part q, [S.sub.pq], is developed here and it is defined as:
[S.sub.pq] = [[N.sup.S].sub.pq]/[N.sub.p]. (1)
For example, the operation sequence similarity coefficient between two parts is determined here. Assume two jobs, [J.sub.1]: 1-3 and [J.sub.2]: 1-2-3 in Fig. 1. From the definition, [N.sub.1] = 2, [[N.sup.S].sub.12] = 2. Therefore, [S.sub.12] = ([[N.sup.S].sub.12]/[N.sub.1]) = (2/2) = 1.0 which means that part 1 is completely in sequence with part 2.
3.2. Part-family formation
An operation sequence-based clustering procedure can form part-families so as to maximize the total operation sequence similarity coefficients between any pair of parts in each part family. The operation sequence similarity coefficient developed here encourages the grouping of any two parts in the sequence of their operations. Therefore, the total operation sequence similarity coefficient between any two parts in each cell can be maximized by grouping those parts that have similar operation sequences, this results eventually in the minimization of the backtracking flow that exists in each part-family. This objective can be achieved by extending the modified p-median model developed by Wang and Roze [36] to capture the operation sequence similarity to form the part-families as
Problem (SC): [Z.sub.SC] = Max [[[sigma].sup.N].sub.p=1] [[[sigma].sup.N].sub.q=1] [S.sub.pq][w.sub.pq], (2)
[[[sigma].sup.N].sub.q=1] [w.sub.pq] = 1, p = 1,2,...,N, (2a)
[[[sigma].sup.N].sub.q=1] [w.sub.qq] = F, (2b)
[[[sigma].sup.N].sub.p=1] [w.sub.pq] [less than or equal to] [U.sub.max][w.sub.qq], q = 1,2,...,N, (2c)
[w.sub.pq] = (0,1), for part p and q, (2d)
where [w.sub.pq] = 1 if part p is assigned to a part family containing part q or 0 otherwise, N is the total number of parts, F is the desired number of part-families that a designer expects to form, and [U.sub.max] is the maximum number of parts allowed for each part-family, and usually [U.sub.max] [greater than or equal to] [N/F].
In Problem (SC), the objective function maximizes the total operation sequence similarity coefficients among the parts in each cell. Constraint (2a) ensures that a part can be assigned exactly to one part family, constraint (2b) specifies the required number of part family, constraint (2c) ensures that part i belongs to part family j only when this part family is formed, and constraint (2d) ensures integrality of the decision variable. The p-median model is a linear binary integer-programming problem for which an efficient approach to solve optimally exists, but with some modifications. Cell formation techniques for jobs with operation times and routings, and several models on measuring the grouping efficiency of part families are discussed in detail in the literature [16,37-40].
Example 1: Part-family formation
Assume a problem with data shown in Table 1. This problem has 19 parts and 12 machines. Nineteen parts can be grouped into a specified number of part-families by applying Algorithm 1 in the following steps:
Step 1: Using the definition [S.sub.pq] = [[N.sup.S].sub.pq]/[N.sub.p] in Equation (1), the operation sequence similarity coefficient matrix S = [[S.sub.pq]; p, q = l,2,...,19] for the given parts in Table 1 is computed as shown in Fig. 2.
Step 2: Suppose three part-families are expected to be formed, i.e., F = 3, and the maximum number parts allowed in one part family is 8, i.e., [U.sub.max] = 8.
Step 3: The p-median model can be constructed based on these data. The computation results in the following optimal solutions (with [[sigma].sub.q=3,8,16][w.sub.qq] = 3):
(1) [w.sub.13] = 1, [w.sub.23] = 1, [w.sub.33] = 1, [w.sub.43] = 1, [w.sub.53] = 1, [w.sub.10,3] = 1,
(2) [w.sub.68] = 1, [w.sub.78] = 1, [w.sub.88] = 1, [w.sub.98] = 1, [w.sub.11,8] = 1, and
(3) [w.sub.12,16] = 1, [w.sub.13,16] = 1, [w.sub.14,16] = 1, [w.sub.15,16] = 1, [w.sub.16,16] = 1, [w.sub.17,16] = 1, [w.sub.18,16] = 1, [w.sub.19,16] = 1.
Step 4: The binary variables [w.sub.pq] (p, q = 1,2,...,19) yield the following three part-families:
Part family 1: {1,2,3,4,5,10},
Part family 2: {6,7,8,9,11}, and
Part family 3 : {12,13,14,15,16,17,18,19}.
4. Machine assignment to part-families
In order to minimize the total cost of inter-cell flow and machine investment, the machines are allocated to each part family to form the cells in this phase. If all machines that one part-family needs to process the parts are grouped with this part family, there will be no inter-cell flow, but more money may be needed for the required number of machines to reduce the inter-cell flow cost. On the other hand, if all machines that one part-family needs to process the parts in it are not assigned to it, there will be some inter-cell flows from this part-family. This will save on the machine investment cost but will, on the contrary, incur more inter-cell flow cost. Therefore, the purpose of this phase is to find the machine assignment for each part family that minimizes the total intra-cell flow cost and the machine investment cost.
After the part-families have been formed, the machines that are involved in the CMS can be classified into two kinds: (1) a bottleneck machine; and (2) a non-bottleneck machine. A non-bottleneck machine is a machine that is required by only one part family whilst a bottleneck machine is a machine that is required by more than one part family. The assignment of the non-bottleneck machines can be done easily by assigning them to the part family that requires them.
One of each type of the bottleneck machines should be assigned to one part family that requires this bottleneck machine to make the CMS initially feasible. The part family to which the first bottleneck machine is assigned is termed here as the original part family of this type of bottleneck machine. After identifying the original part family for each bottleneck machine, a right set of bottleneck machines needs to be identified for duplication under various constraints such as investment, number of each bottleneck machine, and cell size. Based on the above information, two problems should be considered to make a decision on the assignment of the bottleneck machine(s):
Problem A: how to find the original part family for each bottleneck machine first, and
Problem B: what bottleneck machine(s) should be duplicated under different constraints.
In order to solve Problems A and B for the assignment of the bottleneck machines efficiently, two new concepts are introduced into the machine assignment phase. The first concept is the potential inter-cell movement cost of a part-family due to a bottleneck machine, and the second concept is the potential benefit in assigning a bottleneck machine to a part family.
The first concept is based on the fact that the inter-cell movement is from a cell to a bottleneck machine that is not assigned in the stated cell. This idea can establish relationships between inter-cell movements and bottleneck machines. The potential inter-cell movement cost of part-family j due to bottleneck machine i, [I.sup.ij], is defined as:
[I.sub.ij] = [[sigma].sub.p[epsilon][C.sub.j]] [C.sub.p][D.sup.p][n.sub.ip]. (3)
Based on the concept of the potential inter-cell movement cost of a part-family due to a bottleneck machine, the potential benefit of assigning bottleneck machine i to part-family j can be defined as:
[V.sub.ij] = [I.sub.ij] - [R.sub.i]. (4)
It is obvious that the part-family which has the largest potential benefit due to each bottleneck machine should be chosen as the original part-family for this bottleneck machine because it can gain the largest benefit. Based on this concept, Problem B can be modeled and solved easily for the assignment of bottleneck machine(s).
Assume [y.sub.ij] = 1 if bottleneck machine i (i = l,2,..., [M.sub.B]) is assigned to part-family j (j = 1,2,..., [F.sub.B]) or 0 otherwise. If bottleneck machine i is assigned to part-family j, the annual cost of buying and maintaining machine i is given by [R.sub.i] [y.sub.ij]. Hence, [[[sigma].sup.[F.sub.B]].sub.j=1] [[[sigma].sup.[M.sub.B]].sub.i=1] [R.sub.i] [y.sub.ij] is the total investment cost for bottleneck machines. If a bottleneck machine is duplicated and included within a family to avoid the inter-cell movement, then [y.sub.ij] = 1, i.e., (1- [y.sub.ij]) =0. Thus, for [n.sub.ij] movements made by the operation sequence of part p to bottleneck machine i (i = 1,2,..., [M.sub.B]), the inter-cell movement cost [[[sigma].sup.[F.sub.B]].sub.j=1] [[[sigma].sup.[M.sub.B]].sub.i=1] [[[sigma].sup.[N.sub.B]].sub.p=1] [C.sub.p] [n.sub.ip] [D.sub.p] (1 - [y.sub.ij]). Therefore, the total cost (i.e., investment cost for the bottleneck machines plus the inter-cell movement cost) can be presented as:
Z = [[[sigma].sup.[F.sub.B]].sub.j=1] [[[sigma].sup.[M.sub.B]].sub.i=1] [R.sub.i] [y.sub.ij] + [[[sigma].sup.[F.sub.B]].sub.j=1] [[[sigma].sup.[M.sub.B]].sub.i=1] [[[sigma].sup.[N.sub.B]].sub.p=1] [C.sub.p] [n.sub.ip] [D.sub.p] (1 - [y.sub.ij]), (5)
which needs to be minimized as:
Z = Min([[[sigma].sup.[F.sub.B]].sub.j=1] [[[sigma].sup.[M.sub.B]].sub.i=1] [R.sub.i][y.sub.ij] + [[[sigma].sup.[F.sub.B]].sub.j=1] [[[sigma].sup.[M.sub.B]].sub.i=1] [[[sigma].sup.[N.sub.B]].sub.p=1] [C.sub.p][n.sub.ip][D.sub.p] (1 - [y.sub.ij])), (5a)
= Max [[[sigma].sup.[P.sub.B]].sub.j=1] [[[sigma].sup.[M.sub.B]].sub.i=1] ([[[sigma].sup.[N.sub.B]].sub.p=1] [C.sub.p][n.sub.ip][D.sub.p] - [R.sub.i]) [y.sub.ij]
- [[[sigma].sup.[P.sub.B]].sub.j=1] [[[sigma].sup.[M.sub.B]].sub.i=1] [[[sigma].sup.[N.sub.B]].sub.p=1] [C.sub.p][n.sub.ip][D.sub.p], (5b)
= Max [[[sigma].sup.[P.sub.B]].sub.j=1] [[[sigma].sup.[M.sub.B]].sub.i=1] [V.sub.ij][y.sub.ij] - [[[sigma].sup.[P.sub.B]].sub.j=1] [[[sigma].sup.[M.sub.B]].sub.i=1] [[[sigma].sup.[N.sub.B]].sub.p=1] [C.sub.p][n.sub.ip][D.sub.p]. (5c)
The quantity [[[sigma].sup.[N.sub.B]].sub.p=1] [C.sub.p][n.sub.ip][D.sub.p] is the total cost due to movements of all parts to bottleneck machine i. From the definition in Equation (3), [[[sigma].sup.[P.sub.B]].sub.j=1] [[[sigma].sup.[M.sub.B]].sub.i=1] [[[sigma].sup.[N.sub.B]].sub.p=1] [C.sub.p][n.sub.ip][D.sub.p] is the total potential inter-cell movement cost of all the part-families to all the bottleneck machines and this quantity is constant for a problem. The objective function which minimizes the total cost of inter-cell movements and bottleneck machine investment in Equation (5) is transformed to an objective function that maximizes the total benefit of assigning and duplicating all the bottleneck machines to all the part-families. Therefore, the bottleneck machine assignment and duplication problem can be model as a linear integer programming problem with consideration of the financial limitation and the cell size constraints as follow:
(BMA): [Z.sub.EMA] = Max [[[sigma].sup.[M.sub.B]].sub.i=1] [[[sigma].sup.[F.sub.B]].sub.j=1] [V.sub.ij][y.sub.ij], (6)
Subject to
[[[sigma].sup.[M.sub.B]].sub.i=1] [[[sigma].sup.[F.sub.B]].sub.j=1] [R.sub.i][y.sub.ij] [less than or equal to] L, (6a)
[[[sigma].sup.[M.sub.B]].sub.i=1] [y.sub.ij] [less than or equal to] [M.sub.max] - [N.sub.j], j = 1,2,...,[F.sub.B], (6b)
[y.sub.ij] = (0,1), for all i and j. (6c)
The model is tested and validated through exemplification later on.
In this model, the objective function maximizes the total benefit of duplicating the bottleneck machines to the part-families, i.e., minimizes the total machine investment cost and inter-cell layout flow cost. Constraint (6a) ensures that the total bottleneck machine investment cost does not exceed the specified budget for the machine investment. The constraint (6b) ensures that the number of machines, which are assigned into a part family, cannot exceed the cell size specified by the designer. Constraint (6c) ensures integrality of the decision variable.
The machine assignment phase consists of two steps: the bottleneck machine assignment and the non-bottleneck machine assignment. In the bottleneck machine assignment, there are also two steps - one is to decide the original part-family for each bottleneck machine, the other is to decide the optimal duplication of bottleneck machines under several constraints (BMA model). The detail steps of the machine assignment phase are presented in Algorithm 1:
Algorithm 1: Machine Assignment Procedure
Step 0. Initialization
(1) Assume [N.sub.j] is the number of machines assigned to part-family j (j = 1,2,...,K). Set [N.sub.j] = 0 for j = 1, 2, ... ,K.
(2) Set the non-bottleneck machine set U = [phi];
(3) Set the bottleneck machine set B = [phi].
Step 1. Classify the machines to non-bottleneck machines or bottleneck machines:
For all i = 1,2,...,M (total number of machines),
(1) Set counter [Q.sub.i] = 0 (where [Q.sub.i] is the number of part families in set [F.sub.i])
(2) For all j = l,2,...,K,
If part-family [C.sub.j] requires machine i then
(a) Put j into [F.sub.i], where [F.sub.i] is a set of part families that require machine i
(b) Set [Q.sub.i] = [Q.sub.i] + 1;
(3) If [Q.sub.i]= 1,
then put i into the non-bottleneck machine set U,
else put i into the bottleneck machine set B.
Step 2. Assign the non-bottleneck machines to the part-families that require them:
(a.) Assign machine i [epsilon] U to the corresponding part-family j [epsilon] [F.sub.i]
(b) Set [N.sub.j] = [N.sub.j] + 1;
Step 3. Compute the potential inter-cell movement costs and benefits of the part-families due to each bottleneck machine, and find the feasible part-families for duplication:
For all i [epsilon] B
(1) For each part-family j [epsilon] [F.sub.i]
(a) Compute the potential cost of inter-cell movement for machine i as:
[I.sub.ij] = [[sigma].sub.p[epsilon][C.sub.j]] [c.sub.p][n.sub.ip][D.sub.p]
(b) Compute the potential saving of adds machine i in part-family j as:
[V.sub.ij] = [I.sub.ij] - [R.sub.i],
(4) If [V.sub.ij][less than or equal to]0 then delete j from set [F.sub.i]
Step 4. Find the original part family for each bottleneck machine and assign one machine bottleneck machine to the original part family:
(1) For all i [epsilon] B
(a) Assign machine i to part family j [epsilon] [F.sub.i] that has the maximum [I.sub.ij] and [N.sub.j] [less than] [M.sub.max].
(b) Set [N.sub.j] = [N.sub.j] + 1
(c) Delete j from set [F.sub.i]
(2) For all i [epsilon] B
If [F.sub.i] = [phi], then delete i from set B
Step 5. Decide the duplication of the bottleneck machine under the financial limitation and the cell size constraints by solve the BMA model:
(1) Construct BMA model for all i [epsilon] B;
(2) Solve the model and deduce the decision on bottleneck machines.
Step 6. Stop.
Example 2: Assign machine to part-families
After part-families are formed, the machines are assigned to each part family to form the cell by applying Algorithm 1. The result from Example 1 is used here as an input to complete machine assignment to part families.
Step 0: The number of part families formed is K = 3. Thus set [N.sub.j] = 0 for j = 1,2,3. Set U = [phi], and B = [phi].
Step 1: The 12 machines in Table 1 and the three part-families formed in Phase 1 yield the results shown in Table 2 in which the non-bottleneck machine set U = {3,5,11,12} and the bottleneck machine set B = {1,2,4,6,7,8,9,1O}.
Step 2: Since a machine in set U is needed by one part-family, the machines are assigned directly to a part-family that needs it. So assign machine 3 to part family 2, machine 5 to part family 2, machine 11 to part family 3, machine 12 to part family 3. This assignment is shown in Table 3.
Step 3: The bottleneck machines are now assigned to a part family where they are needed. In this step, inter-cell movement costs and potential benefits of the part-families due to each bottleneck machine are computed by applying Equation (4) and using the investment data in Table 4. The results are shown in Table 5. Because [V.sub.22] = 0 [less than or equal to] 0, [V.sub.72] = -18 [less than or equal to] 0, [V.sub.10,2] = -8 [less than or equal to] 0, then, delete part-family 2 from [F.sub.2], [F.sub.7], and [F.sub.10]. The updated [F.sub.i] values are shown in Table 6.
Step 4: In this step, each bottleneck machine i is assigned to their original part-family which has the maximum potential benefit due to this bottleneck machine, and the original part-family from [F.sub.i] is deleted. Thus assign machine 1 to part-family 1, machine 2 to part-family 1, machine 4 to part-family 1, machine 6 to part-family 2, machine 7 to part-family 3, machine 8 to part-family 1, machine 9 to part-family 1, machine 10 to part-family 3. Then these original part-families are deleted from the corresponding [F.sub.i] The final results are shown in Table 7, and the updated [F.sub.i] is shown in Table 8. Because [F.sub.2] [phi], machine 2 from the bottleneck machine set B is deleted. Thus the updated bottleneck machine set B = {1,4,6,7,8,9,10}.
Step 5: The decision on the duplication of the bottleneck machines under the financial limitation and the cell size constraints by solving the BMA model in the final step. Suppose the budget for duplicating the bottleneck machines is L = $90, and the cell size of each cell is [M.sub.max] = 6 machines. Therefore, for [N.sub.1] = 5, [N.sub.2] = 3 and [N.sub.3] = 4, the BMA model can be constructed as:
(BMA): Max [Z.sub.BMA] = [20.sub.[y.sub.13]] + [12.sub.[y.sub.42]] + [10.sub.[y.sub.61]] + [20.sub.[y.sub.63]] + [67.sub.[y.sub.71]] + [14.sub.[y.sub.82]] + [24.sub.[y.sub.92]] + [10.sub.[y.sub.10,1]],
Subject to:
[20.sub.[y.sub.13]] + [20.sub.[y.sub.42]] + [10.sub.[y.sub.61]] + [10.sub.[y.sub.63]] + [20.sub.[y.sub.71]] + [10.sub.[y.sub.82]] + [10.sub.[y.sub.92]] + [10.sub.[y.sub.10,1]] [less than or equal to] 90,
[y.sub.61] + [y.sub.71] + [y.sub.10,1] [less than or equal to] 1,
[y.sub.42] + [y.sub.82] + [y.sub.92] [less than or equal to] 3,
[y.sub.13] + [y.sub.63] [less than or equal to] 2,
[y.sub.ij] = (0,1) for all applicable i,j.
This binary linear integer programming model is solved and the optimal solution is given by [y.sub.13] = 1, [y.sub.42] = 1, [y.sub.63] = 1, [y.sub.71] = 1, [y.sub.82] = 1, and [y.sub.92] = 1 which validates the BMA model. These results are interpreted as: duplicate machine 1 for part family 3, machine 4 for part-family 2, machine 6 for part-family 3, machine 7 for part-family 1, machine 8 for part-family 2, and machine 9 for part-family 2.
If [M.sub.c] and [[M.sup.0].sub.c] are the final and original set of machines assigned to machine-cell c, and [[M.sup.B].sub.c] is the set of duplicated machines for cell c, then the updated machine-cells are [M.sub.c] = [[M.sup.0].sub.c] [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] [[M.sup.B].sub.c] for c = 1,2,...,F. Hence, [M.sub.1] = [[M.sup.0].sub.1] [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] [[M.sup.B].sub.1] = (1,2,4,8,9) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (7), [M.sub.2] = (3,5,6) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (4,8,9) and [M.sub.3] = (7,10,11,12) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (1,6). The machine and part family grouping results are shown in Table 9.
5. Intra-cell layout
The part-families are formed and the machines are assigned to each part family to form the cells. In this phase, the intra-cell layout of each cell is determined to construct the flowline in order to minimize the intra-cell back-tracking flow cost in each cell. The model for this phase is presented as follow:
For cell c (c = 1,2,...,F):
[Z.sub.ICL] = Min [[sigma].sub.i[epsilon][M.sub.c]] [[sigma].sub.j[epsilon][M.sub.c]] [[sigma].sub.p[epsilon][N.sub.c]] [C.sub.p][D.sub.p][[m.sup.p].sub.ij] [[[sigma].sup.[F.sub.c]].sub.k=1] [[[sigma].sup.[F.sup.c]].sub.h=1] [d.sub.ikjh][x.sub.ik][x.sub.jh], (7)
Subject to
[[sigma].sub.i[epsilon][M.sub.c]] [x.sub.ik] = 1, k = 1,2,...,K, (7a)
[[[sigma].sup.[F.sub.c]].sub.k=1] [x.sub.ik] = 1, I [epsilon] [M.sub.c], (7b)
[x.sub.ik] = (0,1), for all i,k. (7c)
In this model, the objective function is to minimize the intra-cell backtracking flow cost in each cell. The constraint (7a) ensures that each location must have only one machine cell assigned while the constraint (7b) ensures that each machine cell must be assigned to one location. This Quadratic Assignment Problem (QAP) is difficult to solve optimally for a large instance. Therefore, a simple heuristic is developed to obtain an acceptable solution for this problem in a reasonable time.
In order to minimize the time consuming effort, this phase is split into two steps. The first step selects a main part for each cell and treats its operation sequence as the initial flowline for the cell. Some adjusting on the initial flowline is done in the second step according to the operation sequences of the other parts and the total cost. The use of this strategy reduces the computational effort to some extent.
(a) Select the main part and the initial intra-cell layout (flowline) for a cell
Based on the similarity coefficient, a part, which is the most similar one to all other parts in a cell, is selected as the main part. The operation sequence of the main part is treated as the initial layout of a flowline in the cell. The main part of cell j (j = 1,2,...,K) is selected according to the following criteria:
Main part = [[J.sup.main].sub.j]
={q:max{[S.sub.q] = [[sigma].sub.p[epsilon][C.sub.j]] [S.sub.pq], [For all] q [epsilon] [C.sub.j]}},
j = 1,2,...,K, (8)
where [C.sub.j] is the set of parts in cell j.
(b) Determine the final intra-cell layout (flowline)
The initial layout is then adjusted by adding or eliminating machines according the operation sequences of the other parts in the same cell. The purpose of adjusting this is to minimize the total cost of materials flow and the machine investment. The details of this heuristic procedure is given Algorithm 2.
Algorithm 2: Intra-cell layout design
For each cell do the following:
Step 1. Initial layout:
(a) Compute [S.sub.q], the sum of operation sequence similarity coefficient values for each part, that is, [S.sub.q] = [[sigma].sub.p[epsilon][C.sub.j]] [S.sub.pq], [For all] q [epsilon] [C.sub.j], j = 1,...,K and choose the part that has the maximum value, as the main part of this cell.
(b) Set initial flowline of this cell according to the operation sequence of the main part.
Step 2. Adjusting the initial layout:
(a) Delete the machines that are contained in the initial flowline but are not assigned in the corresponding cell by Phase 2.
(b) Add machines that have been assigned into a cell by Phase 2 but are not contained in the initial flowline.
Example 3: Intra-cell layout design
In order to implement the cellular manufacturing system, an intra-cell layout of each cell is aimed in this phase at forming a multi-product flowline by applying Algorithm 3.
Step 1: Initial layout
(a) For each part q in a cell, compute [S.sub.q], the sum of the operation sequence similarity coefficients of each part in the same cell to the part q. For part family [C.sub.1] with parts {1,2,3,4,5,10}, the similarity coefficient are computed using Equation (1) and the [S.sub.pq] (p,q=1,2,3,4,5,l0) values are computed as the matrix S([C.sub.1]) in Equation (9).
S([C.sub.1]) =
1 2 3 4 5 10
1 0 0.75 1 0.75 0.50 0.50
2 0.50 0 0.67 0.50 0.33 0.67
3 0.67 0.67 0 0.67 0.50 0.50 ,(9)
4 0.75 0.75 1 0 0.75 0.50
5 0.40 0.40 0.60 0.60 0 0.20
10 0.50 1 0.75 0.50 0.25 0
[S.sub.q] 2.82 3.57 4.02 [*] 3.02 2.33 2.37
where [S.sub.3] = max{2.82, 3.57, 4.02, 3.02, 2.33, 2.37} = 4.02. Since [S.sub.3] is the largest one among [S.sub.q] in cell 1, part 3 is chosen as the main part of cell 1.
Similarly for cell 2 with [C.sub.2] = {6, 7, 8, 9, 11}:
S([C.sub.2]) =
6 7 8 9 11
6 0 0.60 0.60 0.60 0.20
7 0.75 0 1.00 1.00 0.25
8 0.43 0.57 0 0.86 0.14 ,(10)
9 0.50 0.67 1.00 0 0.17
11 1.00 1.00 1.00 1.00 0
[S.sub.q] 2.68 2.84 3.60 [*] 3.46 0.76
in which [S.sub.8] = max{[S.sub.6],[S.sub.7],[S.sub.8],[S.sub.9],[S.sub.11]} = 3.60 and thus, part 8 is chosen as the main part of cell 2. Likewise for cell 3 with [C.sub.3] = {12, 13, 14,15,16,17,18, 19}:
S([C.sub.3]) =
12 13 14 15 16 17 18 19
12 0 0.67 0.67 0.67 0.67 1.00 0.33 0.33
13 1.00 0 0.50 1.00 1.00 1.00 0 0.50
14 0.67 0.33 0 0.67 0.67 0.67 0.67 0
15 0.33 0.33 0.33 0 1.00 0.33 0.33 0.17 ,(11)
16 0.33 0.33 0.33 1.00 0 0.33 0.33 0.17
17 1.00 0.67 0.67 0.67 0.67 0 0.33 0.33
18 0.33 0 0.67 0.67 0.67 0.33 0 0
19 1.00 1.00 0 1.00 1.00 1.00 0 0
[S.sub.q] 4.66 3.33 3.17 5.68 [*] 5.68 [*] 4.66 1.99 1.50
[S.sub.15] = [S.sub.16] = max{[S.sub.12],[S.sub.13],[S.sub.14],[S.sub.15],[S.sub.16],[S.sub.17] ,[S.sub.18],[S.sub.19]} = 5.68. Therefore, either part 15 or 16 can be chosen as the main part of the cell 3. Suppose part 15 chosen as the main part of cell 3.
(b) According to the operation sequence of the main part in each cell, the initial flowlines are given as:
For cell 1, [[J.sup.Main].sub.1] = [J.sub.3] : 1-2-4-7-8-9
For cell 2, [[J.sup.Main].sub.2] = [J.sub.8] : 3-5-2-6-4-8-9
For cell 3, [[J.sup.Main].sub.3]= [J.sub.15] : 1-7-11-10-11-12
Step 2: Adjusting the initial layout:
(a) The initial flowline of each cell is now adjusted according to the machine assignment and operation sequences of other parts in each cell. In this step, the machines that are contained in the initial flowline of each cell but are not assigned to this cell are deleted from the initial flowline. Machine 2 is not assigned to cell 2 even though the initial flowline for cell 2 is configured as [[J.sup.Main].sub.2] : 3-5-2-6-4-8-9. Therefore, machine 2 is deleted from [[J.sup.Main].sub.2] Thus, the modified flowline for cell 2 is 3-5-6-4-8-9.
(b) In this step, a machine that has been assigned to a cell but is not included in the initial flowline is added to the flowline according to the operation sequences of the other parts in the cell. In this example, machine 6 has been assigned to cell 3 but it is not included in [[J.sup.Main].sub.3] 1-7-11-10-11-12. From the operation sequences of the parts that are assigned in cell 3, machine 6 is needed in the operation sequence of part 18. According to the operation sequence of part 18, machine 6 should be assigned to the location before the machine 7. Thus, the final flowline of the cell 3 is adjusted to 1-6-7-11-10-12. Therefore, the final multi-product flowlines for each cell are:
Cell 1: 1-2-4-7-8-9,
Cell 2: 3-5-6-4-8-9, and
Cell 3 : 1-6-7-11-10-12.
The computational results in the first two phases and the adjustment in the third phase lead to the cell formation and intra-cell layout for each cell in a cellular manufacturing system. These final results of the three-phase method are shown in Table 10 and the corresponding line configurations of these results given in Fig. 3 indicate the within-cell movements and the dotted line configurations indicate the inter-cell movements of the parts.
6. Comparison of the results
In order to see the effect of the prescription on the performance of the three-phase procedure against existing research results, the computational results of Vakharia and Wemmerlov [1] are taken as a first comparative basis. Due to the lack of other data on operation sequence based cell formation and layout design, this side source is treated as a major base line both in terms its quality and technical contents.
The information on parts and number of parts, machines and number of machines, the main part and its operation sequence, initial and final configuration of the flowlines for respective cells obtained by the three-phase method are provide in Table 10. These results are based on the V&W data [1]. Hence, the Vakharia and Wemmerlovs final solution is shown in Table 11.
Comparison of total costs
The machine investment, inter-cell flow cost, intra-cell backtracking cost and the total cost for this cellular manufacturing system by the three-phase method are evaluated and reported in Table 12. Using the same cost data for each part to evaluate the Vakharia and Wemmerlov [1] example, the machine investment, inter-cell flow cost, intra-cell backtracking cost and the total cost of their result can also be obtained as shown in Table 13. The overall performance of the three-phase method and the Vakharia and Wemmerlov method [1] are compared in Table 14.
It is observed in Table 14 that both approaches form three cells. However, some noticeable differences exist in the cost structure. Because the cost factors are considered for machine assignment, the number of machine units that are used in the cellular manufacturing system designed by the three-phase method is less than that obtained via the V&W method. Therefore, there is a noticeable difference between the machine investment of the two methods. The machine investment in the three-phase method is almost 20% less than the one obtained using the Vakharia and Wemmerlov method. In the three-phase method, inter-cell flow is considered with the machine assignment. Therefore, although the number of machines is less the inter-cell flow cost in the three-phase method is still less than the inter-cell flow cost in the Vakharia and Wemmerlov method. Only the intra-cell backtracking flow cost in the three-phase method is little higher. However, it is noticeable that the total cost of the three-phase method is much low er than the one of the V&W method. It is obvious that the new method is reasonable to consider the cost factors in the procedure of designing the cellular manufacturing system.
7. Applications and implication
The job routing and machine location problem in a manufacturing cell for multiple products is complex in nature, particularly when compounded by looping back to previous stations. This situation also applies to the study of capital requirements to reduce the need for duplicate facilities of in-line systems, which are best suited for high volume production. This research addressed some important issues relevant to needs and technological development in many industries. Industries are currently increasing their efforts to incorporate modern techniques in their present setup to cope with the growth and development of technology, and the short life-cycles of new products. This research has a significant impact on the development of flexible manufacturing systems in small and medium size industries both operationally and economically.
In a multi-product manufacturing environment, similar products are usually grouped together to form part-families along with the set of required machines, and these machines are then assigned to locations along a transporter line within each cell to form a flowline. Each of these cells/lines may be dedicated to a process, a subset of jobs completely or partially, depending on whether the operation sequences of jobs are partitioned for processing on a single or multiple lines.
A one-dimensional layout can be applied in a number of situations. Designers tend to arrange machines along a straight line since, Automated Guided Vehicles (AGVs) which are primarily used on shop floors for materials transportation, are most efficient while moving along straight paths. The production lines may be called either a single- or double-row layout depending on whether the machines are located on one side or both sides of a material handling track. Kouvelis et al. [24] have reported that both the single- and double-row layouts of machines have been extensively implemented, and descriptions of such implementations as well as pictorial representations can be found in, among others, Maleki [41] [for a single-row layout, see page 70 (Fritz Werner Machine Tools Corporation) and page 184 (Kearney and Trecker Corporation, KTC), and for double-row, see page 124 (KTC)], Luggen [42], Dupont-Gatelmand [43], and Singh and Rajamani [44]. Related case studies are also available for teaching purposes [45-47].
Another application in which such a problem exists is the placement of dies in a series of bending presses in a sheet metal fabrication line (American Steel Products, LA and also Godrej & Boyce Filing Cabinet Manufacturing Plant, Bombay) such that metal sheets flow smoothly along the line for different bending and riveting operations. Many firms in the electronic industry such as Motorola, LTV, Lucent Technologies and Texas Instruments are also experiencing problems involving backtracking of jobs in many semi-automatic insertion lines. Martin Marietta's Michoud Assembly Facility in New Orleans, LA which has several work centers on multiple lines for producing external tanks for space shuttle, is also experiencing similar problems.
An application that involves two-dimensional flow is the 'top side surface mounting' operation in a Printed Circuit Board (PCB) assembly line in an electronic industry in Shreveport, LA. Inter-cell flows of materials are also a major concern in this industry. Forward and backtracking flows of surface mounting operations are separately performed by two programmed robots which move along straight paths on two sides of the circuit board. The objective is to place different parts in 37 slots (along the straight path) on either side of the PCB while minimizing the one-directional, two-way distance for each of the two robots that pick parts from feeders and fix them on the board. The concept of minimization of backtracking can be extended to problems involving both back and forward flows of a set of jobs, that is, when the bi-directional flow has a significant impact on the material handling systems. Changing grippers in robot arms and programs and cutting tools in CNC machines in a multi-product line are also exa mples of bi-directional flow control problems. Many such problems are seen in modular manufacturing cells in a telephone manufacturing plant in Shreveport, LA where more than 200 varieties of telephone sets are manufactured.
Instead of transporting a job to a machine which may be far away from the current machine where the job is being processed, it may be economical to transport the job to a separate line (to complete the remaining sequence of operations) to minimize the travel. Therefore, by incorporating the inter-line (inter-cell) movements of a subset of jobs, or a part of the sequence of a job, the concept of backtracking can also be extended to a multiline (multi-cell) manufacturing system (see Fig. 4). The number in a box in Fig. 4 indicates the machine number in a 3-line layout representation of a multi-product flowline problem. The flow of jobs may occur in any direction along the production line or across the path of the transporter so as to ease the load or reduce the strain on the material handling system. Backtrack minimization has been identified as an important objective in a number of applications. Depending on the flexibility and storage features of the material handling system, it might be possible to accommod ate the back flow of jobs although it is not desirable, since a secondary handling system may be needed for this purpose.
An existing system was simulated with 100 jobs to study the effect of backtracking and bi-directional flow on an intra-cell layout with 10, 15 and 20 machines. Three performance criteria, transporter utilization, machine utilization and the makespan of completed jobs were tested, and the simulated results are reported in Table 15. Transporter utilization and makespan are thought to decrease due to the elimination of unnecessary moves, and consequently, the machine utilization, on the other hand, should increase for a reduction in waiting time. All data in Table 15 confirm this claim except in one case where the machine utilization under the prescription of minimizing backtracking for 10-machine problem barely fell below that in the existing system, and this abnormality is not a major surprise statistically. The overall performance of the prescribed layout is quite satisfactory. More detailed analysis of this type of simulation is reported by Sarker [48].
The utility of this research is in the formation of product families in a manufacturing system that handles a medium volume of specialty products with linear and/or assembly type of operation sequences over a planning horizon. There is a trend towards less costly mid-range placement systems. There is also a trend towards modularity, which allows smaller systems to be configured as a group and towards systems that meet the flexibility required for fine-pitch. So, an improvement in these or similar operations, resulting from the application of these results, will generate millions of dollars in savings. This will enable specialty products and related industries to be more efficient in production and more competitive in international markets.
8. Conclusion
Cell formation and intra-cell layout are two important problems in designing a cellular manufacturing system. The operation sequence has a significant impact on designing an efficient cellular manufacturing system. In this paper, a three-phase operation sequence and cost based method which integrates the cell formation and the intra-cell layout to minimize the total cost of the materials flow and the machine investment is developed for designing a cellular manufacturing system.
As opposed to traditional clustering technique in cellular manufacturing system with binary data, the three-phase method incorporates the operation sequences of jobs and other factors such as material flows, machine investment cost, cell size, and budgetary limitation for machines. The three-phase procedure (part family formation, machine cell formation and inter-cell layout design) presents a solution procedure for such a composite problem in cellular manufacturing. The solution obtained by this method may be significantly different from the solutions obtained by other methods for imposing these constraints to capture a more realistic scenario. The solution of this method is indicative of its relative performance over other existing methods.
This research leads to efficient cell formations, better job routing, scheduling and process control, and eventually produces an improvement in system performance measures such as machine utilization, transporter utilization, throughput rate and makespan of jobs. While many industries are currently reorganizing their layouts to reap the benefits of modern technology and thus gain a competitive edge, the application of the proposed methodology will help redesign the layouts efficiently and economically.
In this research only operation sequences, irrespective of the operation times, are considered as a basis for a cell formation problem. Thus problems associated with operation times and sequences may be considered in further research. Alternative routing of the operation sequence of parts can also be considered in extending this research. The proposed method can also be improved by considering the capacity constraints and idle time costs for the machines, and the limitation on the number of machine types.
Acknowledgment
The authors are thankful to the anonymous referees for their constructive comments and suggestions. This research was supported by National Science Foundation grant number DMII: 96-22306.
Biographies
Bhaba Sarker is currently an Associate Professor at the Department Industrial & Manufacturing Systems Engineering, Louisiana State University, Baton Rouge, LA. He obtained a B.A. degree in Mathematics from Dhaka University, a BSME degree from BUET (Dhaka), an M.Tech. in IE & OR from IIT (Kharagpur), an M.S. in Eng. Admin and I.Engr degrees from Syracuse University and a Ph.D. from Texas A&M University. Earlier he taught at several other schools including The University of Texas at Austin and Texas A&M University at College Station. He also worked with the World Bank and U.S. Army Corps of Engineers besides his other appointments abroad. Bhaba Sarker was the recipient of Best Dissertation Awards from DSI (1990), IIE (1991), and POMS (1990). He has published more than 60 papers in refereed journals and currently serves on four Editorial Boards including IIE Transactions. He is a member of DSI, IIE, IEEE, INFORMS, and POMS. He is currently working in the area of production and manufacturing systems and supply ch ain management.
Yi Xu is a graduate student at the Department of Industrial and Manufacturing Systems Engineering, Louisiana State University, Baton Rouge, LA. He obtained a B.Sc. degree in Automatic Control in 1993 and an MS. degree in Management Science in 1996 from Beijing University of Aeronautics and Astronautics, Beijing, P.R. China. His research interests are in the areas of modeling and analysis of manufacturing systems, production planning and control, and inventory theory.
Contributed by the Feature Applications and Technology Management Department
Department of Industrial and Manufacturing Systems Engineering, Louisiana State University, Baton Rouge, LA 70803-6409, USA E-mail: bsar@lsu.edu
References
(1.) Vakharia, A,J. and Wemmerlov, U. (1990) Designing a cellular manufacturing system: a materials flow approach based on operation sequences. IIE Transactions, 22(1), 84-97.
(2.) Askin, R.G. and Zhou, M. (1998) Formation of independent flow-lines cells based on operation requirements and machine capabilities. IIE Transactions on Design and Manufacturing, 30(4), 319-329.
(3.) Verma, P. and Ding, F.Y. (1995) A sequence-based materials flow procedure for designing manufacturing cells. International Journal of Production Research, 33(12), 3267-3281.
(4.) Wu, N. and Salvendy, G. (1993) Modified network approach for the design of cellular manufacturing systems. International Journal of Production Research, 31(6), 1409-1421.
(5.) King, J.R. (1980) Machine-component grouping in PFA: an approach using a rank-order clustering algorithm. International Journal of Production Research, 18(2), 213-232.
(6.) King, J.R. and Nakornchai, V. (1982) Machine-component group formation in group technology: review and extensions. International Journal of Production Research, 20(2), 117-133.
(7.) McAuley, J. (1972) Machine grouping for efficient production. Production Engineer, 51(2), 53-57.
(8.) Tam, K.Y. (1990) An operation sequence based similarity coefficient for part families formations. Journal of Manufacturing Systems, 9(1), 55-68.
(9.) Mosier, C. and Taube, L. (1985) The facets of group technology and their impacts on implementation: a state-of-the art survey. OMEGA: International Journal of Management Science, 13(5), 381-391.
(10.) Suresh, N.C. and Meredith, J,R. (1985) Achieving factory automation through group technology principles. Journal of Operation Management, 5(2), 151-167.
(11.) Chu, C.-H (1989) Cluster analysis in manufacturing cellular formation. OMEGA: International Journal of Management Science, 17(3), 289-295.
(12.) Kusiak, A. (1992) Branching algorithms for solving the group technology problem. Journal of Manufacturing Systems, 10(4), 332-343.
(13.) Parkin, R.E. and Li, M.-L. (1997) The multi-dimensional aspects of a group technology algorithm. International Journal of Production Research, 35(8), 2345-2358.
(14.) Seifoddini, H. and Djassemi, M. (1997) Determination of a flexibility range for cellular manufacturing systems under product mix variations. International Journal of Production Research, 35(12), 3349-3366.
(15.) Choobineh, F. (1988) A framework for the design of cellular manufacturing systems. International Journal of Production Research, 26(7), 1161-1172.
(16.) Sarker, B.R. and Li, K. (1997) Simultaneous route selection and cell formation: a mixed-integer programming time-cost model. Integrated Manufacturing Systems, 8(6), 374-377.
(17.) Akturk, M.S. and Balkose, H.O. (1996) Part-machine grouping using a multi-objective cluster analysis. International Journal of Production Research, 34(8), 2299-2315.
(18.) Selvam, R.P. and Balasubramanian, K.N. (1985) Algorithmic grouping of operation sequences. Engineering Costs and Production Economics, 9(2), 125-134.
(19.) Logendran, R. (1991) Impact of sequence of operations and layout of cells in cellular manufacturing. International Journal of Production Research, 29(2), 375-390.
(20.) Logendran, R. (1992) A model for duplicating bottleneck machines in the presence of budgetary limitations in cellular manufacturing. International Journal of Production Research, 30(3), 683-694.
(21.) Irani, S.A., Cohen, P.H. and Cavalier, T.M. (1992) Design of cellular manufacturing systems. Transaction of the ASME, 114, 352-361.
(22.) Irani, S.A., Cavalier, T.M. and Cohen, P.H. (1993) Virtual manufacturing cells: exploiting layout design and intercell flows for the machine sharing problem. International Journal of Production Research, 31(4), 791-810.
(23.) Seifoddini, H. (1989) Duplication process in machine cells formation in group technology. IIE Transactions, 21(4), 382-388.
(24.) Heragu, 5.5. (1994) Exact solution approaches for the single-row layout problem, in Proceedings of the 3rd Industrial Engineering Research Conference, L. Burke and J. Jackman (eds), IIE, Norcross, GA. pp. 582-587.
(25.) Kouvelis, P., Chiang, W.-C. and Yu, G. (1995) Optimal algorithm for row layout problems in automated manufacturing systems. IIE Transactions, 27(1), 99-104.
(26.) Sarker, B.R., Wilhelm, W.E. and Hogg, G.L. (1994) Measures of backtracking and bi-directional flow in one dimensional machine location problems. Production Planning & Control, 5(3), 282-291.
(27.) Sarker, BR., Wilhelm, W.E. and Hogg, G.L. (1994) Backtracking and its amoebic properties in one-dimensional machine location problems. Journal of the Operational Research Society, 45(9), 1024-1039.
(28.) Sarker, B.R., Wilhelm, W.E., Hogg, G.L. and Han, M.H. (1995) Backtracking of jobs in one-dimensional machine location problems. European Journal of Operational Research, 85(3), 593-609.
(29.) Sarker, B.R., Wilhelm, W.E. and Hogg, G.L. (1998) One-dimensional machine location problems in a multi-product flowline with equidistant locations. European Journal of Operational Research, 105(3), 401-426.
(30.) Sarker, B.R., Wilhelm, W.E. and Hogg, G.L. (1998) Locating sets of identical machines in a linear layout. Annals of Operations Research, 77(1), 183-207.
(31.) Ballakur, A. (1985) An investigation of part family/machine group formation in designing a cellular manufacturing systems. PhD thesis, University of Wisconsin, Madison, WI.
(32.) Sarker, B.R. and Yu, J. (1994) A twophase procedure for duplicating bottleneck machines in linear layout, cellular manufacturing system. International Journal of Production Research, 32(9), 2049-2066.
(33.) Nori, V.S. and Sarker, B.R. (1997) Reducing work-in-process movements of multiple products in one-dimensional layout problems. Journal of the Operational Research Society, 48(4), 412-422.
(34.) Sarker, B.R. and Xu, Y. (1998) Operations sequences-based cell formation methods: a critical survey. Production Planning & Control, 9(8), 771-783.
(35.) Ho, Y., Lee, C. and Moodie, C.L. (1993) Two sequence-pattern, matching-based, flow analysis methods for multi-flowlines layout design. International Journal of Production Research, 31(7), 1557-1578.
(36.) Wang, J. and Roze, C. (1997) Formation of machine cells and part families: a modified p-media model and a comparative study. International Journal of Production Research, 35(5), 1259-1286.
(37.) Sarker, B.R. and Balan, CV. (1996) Cell formation with operations times for even distribution of workloads. International Journal of Production Research, 34(5), 1447-1468.
(38.) Sarker, B.R. and Li, 7. (1998) Measuring matrix-based cell formation with alternative routings. Journal of the Operational Research Society, 49(9), 953-965.
(39.) Sarker, BR. and Mondal, S. (1999) Grouping efficiency measures in cellular manufacturing: a survey and critical review. International Journal of Production Research, 37(2), 285-314.
(40.) Sarker, B.R. (1996) The resemblance coefficients in group technology: a survey and comparative study of relational metrics. Computers & Industrial Engineering, 30(1), 103-116.
(41.) Maleki, R.A. (1991) Flexible Manufacturing Systems. Prentice Hall, Englewood Cliffs, NJ.
(42.) Luggen, W.L. (1991) Flexible Manufacturing Cells and Systems, Prentice-Hall, Englewood Cliffs, NJ, p. 90.
(43.) Dupont-Gatelmand, C. (1982) A survey of flexible manufacturing systems. Journal of Manufacturing Systems, 1(1), 1-15.
(44.) Singh, N. and Rajamani, D. (1996) Cellular Manufacturing Systems: Design, Planning and Control, Chapman & Hall, London.
(45.) Pilton Manufacturing Corporation (1986) Illinois Institute of Technology case, Chicago, IL.
(46.) Yamazaki, M. (1986) Harvard Business School Case No 9-686-083.
(47.) Hitachi-Seiki (1986) Harvard Business School Case No 9-686-104.
(48.) Sarker, B.R. (1989) The amoebic matrix and onedimensional machine location problems, Ph.D. dissertation, Department of Industrial Engineering, Texas A& M University, College Station, TX 77843, December 1989.
Relevant data of the 19-part problem [*]
Part P Operation sequence Demand Average cost of
of part p (batches/day) bracktracking of part p
[D.sub.p] ($/unit flow)
1 1-4-8-9 2 1
2 1-4-7-4-8-7 3 1
3 1-2-4-7-8-9 1 2
4 1-4-7-9 3 2
5 1-6-10-7-9 2 2
6 6-10-7-8-9 1 1
7 6-4-8-9 2 2
8 3-5-2-6-4-8-9 1 2
9 3-5-6-4-8-9 1 1
10 4-7-4-8 2 1
11 6 3 2
12 11-7-12 1 1
13 11-12 1 1
14 11-7-10 3 2
15 1-7-11-10-11-12 1 3
16 1-7-11-10-11-12 2 2
17 11-7-12 1 1
18 6-7-10 3 2
19 12 2 1
Part P Average cost of inter-
cell flow of part p
([c.sub.p] $/unit flow)
1 5
2 2
3 15
4 10
5 10
6 2
7 10
8 10
9 2
10 5
11 10
12 5
13 5
14 10
15 20
16 10
17 2
18 10
19 5
(*.)Vakharia and Wemmerlov [1]
Similarity coefficient of 19 parts (Table 1).
1 2 3 4 5 6 7 8 9 10 11 12 13 14
1 0 0.75 1 0.75 0.50 0.50 0.75 0.75 0.75 0.50 0 0 0 0
2 0.50 0 0.67 0.50 0.33 0.33 0.33 0.33 0.33 0.67 0 0.17 0 0.17
3 0.67 0.67 0 0.67 0.50 0.50 0.50 0.67 0.50 0.50 0 0.17 0 0.17
4 0.75 0.75 1 0 0.75 0.50 0.50 0.50 0.50 0.50 0 0.25 0 0.25
5 0.40 0.40 0.60 0.60 0 0.80 0.40 0.40 0.40 0.20 0.20 0.2 0 0.2
6 0.40 0.40 0.60 0.40 0.80 0 0.60 0.60 0.60 0.40 0.20 0.2 0 0.2
7 0.75 0.50 0.75 0.50 0.50 0.75 0 1 1 0.50 0.25 0 0 0
8 0.43 0.29 0.57 0.29 0.29 0.43 0.57 0 0.86 0.29 0.14 0 0 0
9 0.50 0.33 050 0.33 0.33 0.50 0.67 1 0 0.33 0.17 0 0 0
S = 10 0.50 1 0.75 0.50 0.25 0.50 0.50 0.50 0.50 0 0 0.25 0 0.25
11 0 0 0 0 1 1 1 1 1 0 0 0 0 0
12 0 0.33 0.33 0.33 0.33 0.33 0 0 0 0.33 0 0 0.67 0.67
13 0 0 0 0 0 0 0 0 0 0 0 1 0 0.50
14 0 0.33 0.33 0.33 0.33 0.33 0 0 0 0.33 0 0.67 0.33 0
15 0.17 0.33 0.33 0.33 0.33 0.17 0 0 0 0.17 0 0.33 0.33 0.33
16 0.17 0.33 0.33 0.33 0.33 0.17 0 0 0 0.17 0 0.33 0.33 0.33
17 0 0.33 0.33 0.33 0.33 0.33 0 0 0 0.33 0 1 0.67 0.67
18 0 0.33 0.33 0.33 0.67 0.67 0.33 0.33 0.33 0.33 0.33 0.33 0 0.67
19 0 0 0 0 0 0 0 0 0 0 0 1 1 0
15 16 17 18 19
1 0.25 0.25 0 0 0
2 0.33 0.33 0.17 0.17 0
3 0.33 0.33 0.17 0.17 0
4 0.50 0.50 0.25 0.25 0
5 0.40 0.40 0.20 0.40 0
6 0.20 0.20 0.20 0.40 0
7 0 0 0 0.25 0
8 0 0 0 0.14 0
9 0 0 0 0.17 0
S = 10 0.25 0.25 0.25 0.25 0
11 0 0 0 1 0
12 0.67 0.67 1 0.33 0.33
13 1 1 1 0 0.50
14 0.67 0.67 0.67 0.67 0
15 0 1 0.33 0.33 0.17
16 1 0 0.33 0.33 0.17
17 0.67 0.67 0 0.33 0.33
18 0.67 0.67 0.33 0 0
19 1 1 1 0 0
Categorization of bottleneck and non-bottleneck machines
Machine I 1 2 3 4 5 6 7 8 9 10 11 12
[F.sub.i] 1,3 1,2 2 1,2 2 1,2,3 1,2,3 1,2 1,2 1,2,3 3 3
[Q.sub.i] 2 2 1 2 1 3 3 2 2 3 1 1
Machine set B B U B U B B B B B U U
[F.sub.i] = the set of part-families which need machine i.
[Q.sub.i] = number of part-families which need machine i.
U = non-bottleneck machine set.
B = bottleneck machine set.
Assigning the non-bottleneck machines to part family
Pat-family j 1 2 3
Machines assigned none 3, 5 11, 12
Number of machines assigned [N.sub.j] 0 2 2
Data for the machines
Machine i 1 2 3 4 5 6 7 8 9 10 11 12
Cost of machine i ($) 20 10 15 20 10 10 20 10 10 10 50 20
Potential profit ($) of assigning a machine to a part-family
Part family Bottleneck
machine
1 2 4 6 7 8 9 10
[F.sub.1] 61 [*] 5 [*] 67 [*] 10 67 21 [*] 65 [*] 10
[F.sub.2] - 0 12 54 [*] -18 14 24 -8
[F.sub.3] 20 - - 20 87 [*] - - 90 [*]
(*.)The maximum one in each column
Bottleneck machines and corresponding part-families
Machine i 1 2 4 6 7 8 9 10
[F.sub.i] 1, 3 1 1, 2 1, 2, 3 1, 3 1, 2 1, 2 1, 3
Machine assigned to part family
Part-family j 1 2 3
Machines assigned to 1, 2, 4, 8, 9 3, 5, 6 7, 10, 11, 12
machine-cell [[M.sup.0].sub.j]
Number of machines 5 3 4
assigned [N.sub.j]
Assigning bottleneck machine(s) to part family
Machine i 1 2 4 6 7 8 9 10
[F.sub.i] 3 [] 2 1, 3 1 2 2 1
[[]Represents [empty set]]
Solutions of the BMA model
Cell 1 Cell 2 Cell 3
Parts 1, 2, 3, 4, 5, 10 6, 7, 8, 9, 11 12, 13, 14, 15, 16, 17, 18, 19
Machines 1, 2, 4, 7, 8, 9 3, 4, 5, 6, 8, 9 1, 6, 7, 10, 11, 12
Main part and flowline configuration by three-phase method
Description Cell 1 Cell 2
Number of parts 6 5
Parts 1, 2, 3, 4, 5, 10 6, 7, 8, 9, 11
Number of machines 6 6
Machines 1, 2, 4, 7, 8, 9 3, 4, 5, 6, 8, 9
Main part 3 8
Main part's operation sequence 1-2-4-7-8-9 3-5-2-6-4-8-9
Initial flowline 1-2-4-7-8-9 3-5-2-6-4-8-9
Final configuration of three-phase methods 1-2-4-7-8-9 3-5-6-4-8-9
Description Cell 3
Number of parts 8
Parts 12, 13, 14, 15, 16, 17, 18, 19
Number of machines 6
Machines 1, 6, 7, 10, 11, 12
Main part 15
Main part's operation sequence 1-7-11-10-11-12
Initial flowline 1-7-11-10-11-12
Final configuration of three-phase methods 1-6-7-11-10-12
Flowline configuration of Vakharia and Wemmerlov [1]
Description Cell 1
Number of parts 8
Parts 1, 3, 4, 5, 6, 7, 8, 9
Number of machines 10
Machines 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
Modified final flowline 1-3-5-2-6-10-4-7-8-9
Description Cell 2 Cell 3
Number of parts 9 2
Parts 11, 12, 13, 14, 15, 16, 17, 18, 19 2, 10
Number of machines 10 5
Machines 6, 7, 10, 11, 12 1, 4, 7, 11, 10
Modified final flowline 11-6-7-10-12 1-11-4-10-7
Cost evaluation of the three-phase procedure
Machine Inter-cell Intra-cell Total
investment flow backtracking ($)
($) cost ($) flow cost ($)
Cell 1 90 40 6 136
Cell 2 75 14 0 89
Cell 3 130 0 15 145
Total ($) 295 54 21 370
Cost evaluation of the Vakharia and Wemmerlov [1]
model
Description Machine Inter-cell Within cell Total
investment flow cost backtracking ($)
($) ($) flow cost ($)
Cell 1 135 0 0 135
Cell 2 110 40 14 164
Cell 3 120 16 5 141
Total ($) 365 56 19 440
Cost evaluation of the present method versus that of
the Vakharia and Wemmerlov [1] models
Description Vakharia and Three-phase
Wemmerlov method
Number of cells 3 3
Number of machine units 20 18
Machine investment ($) 365 295
Inter-cell flow cost ($) 56 54
Intra-cell backtracking flow 19 21
cost ($)
Total cost ($) 440 370
Impact of proposed layout on an existing system [48]
Performance Number of Existing Layout design Layout design by
Measures machines system by minimizing minimizing
backtracking bi-directional flow
Transporter utilization 10 0.765 0.735 0.760
15 0.867 0.770 0.770
20 0.887 0.810 0.780
Machine utilization 10 0.789 0.785 0.816
15 0.680 0.689 0.816
20 0.707 0.707 0.711
Makespan 10 808 813 790
15 825 799 783
20 830 809 805
In addition, make sure to read these articles:
- Horizontal equity and family tax treatment: the orphan child of tax policy.
- The family as cornerstone of the good life and the good society: family life in the...
- MULTI-MACHINE LOAD SYSTEM.
- Pallet pool pumps up productivity
- Getting cells in place
- Cell manufacturing: the hard part is to get people in step with the program.
- CELL CULTURE.
- Operations improvement now.
- Experimental results.
- REDEFINING THE PART FAMILY
- When cells make sense
- Using volume and economies of scale to benefit long-term productivity.
- 'Braking' from tradition at Arvin Merator
- Lower Costs in Motion
Email
Digg It
del.icio.us
Related Resources
Press Releases
- Nextel Raised Nearly $600,000 in 2004 to Benefit Military Families via the American Red Cross.
- AssureImmune, an Adult Stem Cell Collection andPreservation Company, Launches Premier Services in SouthFlorida.
- Monmouth Medical Center, in Partnership with LifebankUSA(R), Launches Program for Placental and Cord Blood Stem Cell Banking.
