Network flow procedures for the analysis of cellular manufacturing systems.

1. Introduction

In a traditional manufacturing process layout, machines are assembled together to devise independent machining centers with functionally identical machines in each group. In this type of layout design, a batch of parts requiring a known sequence of operations is routed through

the associated machine centers according to the specified sequence. A cellular layout, in contrast, is an arrangement of different machines into manufacturing cells on the basis of similar processing requirements to produce one or more families of parts. Machines within a cell work only on those parts that belong to the family or families assigned to the cell. Through the simplification of operational routings, cellular manufacturing systems have been identified as systems that can produce a family of similar parts more economically owing to the significant reduction in material handling and setup costs (Burbidge, 1975).

According to recent surveys (Kusiak, 1990), a 20-60% reduction in production lead time can be related to reduction in setup time. These surveys also indicate that a 15% space saving, and a 20-88% reduction in material handling efforts can be achieved by implementing manufacturing cells. Moreover, because cellular manufacturing focuses on the simplification of material flow, it makes it easier to schedule parts and track the status of shop orders. However, a comprehensive approach covering all important variations of the cell formation process has not yet been achieved. The proposed methodology represents a significant step in this direction.

Network-flow models and solution techniques can be of great value in the design, improvement, and rationalization of complex large-scale systems. The advantages of using network models include the accurate representation of real-world systems, as well as the relatively high computational efficiency of network algorithms. This article develops a network-flow-based procedure for grouping the machines of a manufacturing system into cells, and the parts to be processed into families, in such a way that the overall intercellular flow of parts is minimized. To develop a meaningful comprehensive cell formation approach, the following two important cases are considered:

Case 1: restricted number of cells and unrestricted cell size;

Case 2: restricted number of cells and restricted cell size.

Because the total number of inter-machine part moves is constant for a given set of parts to be manufactured, it follows that the number of part moves between cells increases as the number of machine cells is increased, ranging from a minimum of zero, when there is only one cell, to a maximum when there is one machine in each cell (a situation hardly considered to be practical). The proposed models actually consider the number of cells as a parameter that can be easily varied to determine the most appropriate number of cells in a specific application. This number usually depends on space limitation on the shop floor, the number of tools required for processing each part, scheduling considerations, capital availability, and other relevant factors.

The general claim that it is easier to control production in a cell than in a functional layout is valid only if the cell itself is not too large. Additionally, most analytical procedures currently available allow the creation of cells consisting of a single machine. For this reason, in Case 2 both lower and upper bounds are considered on the number of machines in any cell. After identifying the machines in each cell, parts are integrated into part families subject to a part family size constraint.

A 0-1 integer programming formulation known as the p-median model (Kusiak, 1987; Mulvey and Crowder, 1979) can be used to solve the problem described in Case 1. A generalized form of the p-median model that imposes a limit on the cell size is formulated as a 0-1 quadratic programming model (Kumar et al., 1986) for Case 2. Additionally, a 0-1 integer programming model is formulated to represent the part family formation problem. In small-to-medium size problems, these integer programming formulations can be solved by means of standard general-purpose simplex-based procedure. In large problems, however, more efficient special-purpose methodologies are generally required. A state-of-the-art optimization procedure known as the relaxation algorithm (Bertsekas and Tseng, 1989) is used in this article for enhancing the computational efficiency of the proposed methodology.

The cell formation problem is conceptually as well as computationally complex (NP-complete (Mulvey and Crowder, 1979)). This problem is actually related to cluster analysis and network partitioning. Although the operations research and manufacturing system analysis disciplines have contributed a large number of efficient heuristics and optimization procedures for group analysis using a machine-part matrix, relatively little attention has been paid to the consideration of the operation sequences of the parts being considered.

Most algorithms using a machine-part matrix have been developed on the basis of matrix-arrangement methods, methods based on similarity coefficients, graph theoretic methods, mathematical programming methods, or artificial intelligence methods. Kennedy (1974) and Kusiak (1990) have conducted extensive bibliographical surveys of cluster analysis and related machine/part grouping applications. Most of the available solution procedures are computationally inefficient or infeasible for large-scale industrial applications.

The remaining portion of this section provides bibliographical references, along with a short description, for some relevant procedures related to the problem under consideration in this article. One of the best known approaches for clustering machines (parts) into cells (families) is the p-median model. The measure of effectiveness in this model is the maximization of the total sum of similarity values for objects placed together in groups or clusters, under the condition that each object is assigned exactly once to a cluster, and assuming that the number of clusters (p) is known. Mulvey and Crowder (1979) developed a Lagrangean relaxation methodology for solving this model (a 0-1 linear integer programming model). In their algorithm, a subgradient method is employed for determining lower bounds, and a simple search procedure for determining upper bounds. The identification and verification of a converged optimal solution may become computationally inefficient or even impossible in large-scale applications. The p-median model has also been solved by Jensen (1969) using dynamic programming. The value of the approach in part-family formation has been recognized by Kusiak (1987). Although the number of calculations required is substantially less than that of total enumeration, the dynamic programming approach may actually require more computer memory.

The p-median model does not allow the control of the size of each cluster (for example, number of machines in a cell). To consider meaningful applications where the size of the cells may be restricted, a 0-1 quadratic programming model was recommended by Kumar et al. (1986). The eigenvector approach due to Barnes (1982) was modified to approximate the global solution of their model.

Seiffodini and Wolfe (1986) have proposed a similarity-coefficient-based clustering procedure that allows the consideration of the duplication of bottleneck machines. Their duplication procedure is based on inter-cell part flows and continues until the flow decreases to a specified value. Additionally, Vannelli and Ravikumar (1986) have developed a methodology that aids in the identification of bottleneck machines, using an algorithm due to Lee et al. (1979) to determine cut-nodes in the partition of a bipartite graph representing parts and machines.

Vakharia and Wemmerlov (1990) recommend a clustering procedure based on a similarity coefficient that is determined from the operational sequences of the parts to be manufactured. In their procedure, parts having single and dual operations are identified and removed to reduce the problem size. Once this is accomplished, a clustering procedure is performed using the similarity coefficient. The merging process stops when the measure of effectiveness exceeds a specified threshold value.

More recently, Askin and Chiu (1990) have proposed a mathematical model and solution procedure for group technology, based on a heuristic algorithm developed by Kernighan and Lin (1970) for partitioning a network into subnetworks, essentially using pairwise interchanges of nodes assuming that the size of a subnetwork is fixed.

It should be mentioned that the similarity measure can in some cases vary rather significantly, as for example when adding parts having identical manufacturing routings. Seifoddini and Wolfe (1986) as well as Chen and Guerrero (1994) have studied some limitations inherent to the use of similarity coefficients. In particular, Chen and Guerrero (1994) have also devised an approach to overcome a number of these limitations.

The fundamental purpose of this article is to develop a network-flow-based methodology that overcomes a number of limitations inherent in currently available procedures. Section 2 presents the network methodology for each phase. A capacitated-circulation network model is formulated and the corresponding network flow methodology is developed by means of a relaxation method. The network methodology is illustrated with an example in Section 3. A large-scale industrial application of the proposed methodology is summarized in Section 4. A discussion of the computational efficiency and the optimality of solutions is given in Section 5. Conclusions of the article are presented in Section 6.

2. Network-Flow-Based Methodology

The proposed network methodology for solving machine and part grouping consists of three phases: (a) preprocessing phase for computing a functional relationship between machines for a network modeling of the problem; (b) partitioning phase for manufacturing cell formation; and (c) part family identification phase.

2.1. Preprocessing Phase and Network Modeling

The process of designing a cellular manufacturing system is essentially based on the recognition and use of the production requirements for the machines to be grouped as independent cells. The proposed methodology requires as basic input information one of the following two options: (1) a machine-part matrix A = [[a.sub.ij]] indicating which machines are needed for processing each part (in this matrix an entry [a.sub.ij] = 1 if machine j is required to process part i; and [a.sub.ij] = 0, otherwise) or (2) generic routings that specify operation sequences and production quantity for each part. The fundamental difference between the information provided by options (1) and (2) is that option (1) indicates an unordered listing of the machines required to process each part, whereas option (2) identifies an ordered sequence of the machines needed for processing each part.

The preprocessing phase, which can be thought of as a phase before partitioning, should be conducted on the basis of either the machine-part matrix (option 1) or the part flows between machines resulting from the given operation sequences (option 2). The relationship between machines can be established in terms of a generic distance parameter when using the machine-part matrix as input, or in terms of arc weights representing material flow between machines when using operation sequences as input.

When the analysis is conducted on the basis of the machine-part matrix, preprocessing results in the computation of distance parameters that can be viewed as machine similarity coefficients. The concept used in the definition of similarity follows. Let [x.sub.i] and [x.sub.j] be two binary column vectors from the machine-part matrix:

[x.sub.i] = [[[a.sub.1i], [a.sub.2i], ..., [a.sub.[N.sub.i]]].sup.T],

[x.sub.j] = [[[a.sub.1j], [a.sub.2j], ..., [a.sub.[N.sub.j]]].sup.T],

where N is the number of parts. A valid distance function for these vectors is the Hamming metric defined as follows (Kusiak, 1987):

[d.sub.ij] = [summation of] [Rho]([a.sub.ki], [a.sub.kj]) where k = 1 to N (1)

where

[Rho]([a.sub.ki], [a.sub.kj]) = {1, if [a.sub.ki] = [a.sub.kj], {0, otherwise.

The measure defined in (1) is a symmetric function whose value is large when [x.sub.i] and [x.sub.j] are similar, which means that machines i and j have a strong relationship because they process parts requiring similar machine operations. Based on this measure, a machine similarity matrix D = [[[d.sub.ij]].sub.M x M] can be constructed, where M is the number of machines. The machine similarity network with nodes representing machines and arc weights representing machine similarities can then be derived.

The basic concept used in the computation of material flow between machines i and j on the basis of operation sequences and part volumes follows. We consider again M machines and N parts. Let [Mathematical Expression Omitted] be defined as follows:

[Mathematical Expression Omitted]

Additionally, let [v.sub.k] be the production volume of the kth part. The total material flow for all N parts between machine i and machine j can now be computed as:

[Mathematical Expression Omitted]

From the computation of the [q.sub.ij] values in terms of (2), a material flow matrix Q = [[[q.sub.ij]].sub.M x M] can be defined. On the basis of Q, the intermachine material flow network is obtained.

2.2. Cell formation phase

After representing the problem as a network model based on either matrix D, or matrix Q, network partitioning procedures are developed to form machine cells by grouping those nodes strongly related to one another for each case mentioned in Section 1. The network partitioning problem can be stated as follows. Let G be a network of M nodes. These nodes can be considered as the members of the set N = {1,2, ..., M}. Let [c.sub.ij] (i,j = 1, ..., M) be the weight of arc (i,j) in G, and let p be a positive integer indicating the number of components into which the network is partitioned. A p-partitioning of network G is obtained by deleting arcs of G resulting in p disconnected subnetworks [G.sub.i] (i = 1, ..., p). Each subset [G.sub.i] has a set of nodes [V.sub.i] such that [Mathematical Expression Omitted]. When lower and upper bounds l and u are defined on the size (number of nodes) of a subnetwork, a partition is admissible if l [less than or equal to] [absolute value of [V.sub.i]] [less than or equal to] u (i = 1, ..., p), where [absolute value of V] stands for the size of a set V. It is desired to find a feasible p-partitioning such that the sum of weights (costs) of the interconnections (arcs) between the p sub-networks is minimal. The set of arcs deleted is known as a cutset.

The objective of cell formation is to minimize intercellular interactions (which will probably reduce the setup times and material handling costs). To meet this objective, machines with strong relationships (high similarity in option 1, or large number of part moves between them in option 2) should be grouped together and machines with weak relationships (low similarity or small number of part moves) should be separated. This article shows how a partitioning of nodes (machines) in the network can be achieved by a minimum-cost network-flow approach. The similarity measurement in option 1 or the number of part moves in option 2 corresponding to any two machines is used as the per-unit flow cost. The minimum-cost approach ensures that all machines with strong relationships with one another will be put together in the same machine cell.

The objective of the network partitioning problem for Case 1 is to maximize the total of similarity coefficients (option 1) or inter-cell part flows (option 2) subject to a specified number of machine cells. This problem can be formulated as follows (Mulvey and Crowder, 1979):

[Mathematical Expression Omitted]

subject to

[summation of] [x.sub.ij] where j [element of] N = 1 i= 1, ..., M; (4)

[summation of] [x.sub.ij] where j [element of] N = p; (5)

[x.sub.ij] - [x.sub.jj] [less than or equal to] 0, i,j = 1, ..., M, j [not equal to] i; (6)

[x.sub.ij] [element of] {0, 1}, i,j= 1, ..., M; (7)

where

[x.sub.ij] = {1 if machine i is assigned to cell j, {0 otherwise,

and p is the desired number of machine cells. The coefficient [c.sub.ij] in the objective function (3) denotes the distance parameter ([d.sub.ij]) or the number of part moves ([q.sub.ij]) between machines i and j. Constraint set (4) ensures that each machine belongs to exactly one cell. Constraint (5) specifies the desired number of machine cells. Constraint set (6) ensures that machine i belongs to cell j only when this cell is formed. Constraint (7) imposes a binary condition (0 or 1).

As can be seen, the p-median model does not consider the cell size. A generalized form of the p-median model is possible, to impose a limit on the cell size. The resulting formulation is a 0-1 quadratic programming model. Let p be the number of desired cells and l and u be lower and upper bounds on the total number of machines in each cell. With this notation, a 0-1 quadratic programming formulation for the problem under consideration is (Kumar et al., 1986):

[Mathematical Expression Omitted]

subject to

[summation of] [x.sub.ij] where j = 1 to p = 1 i = 1, ..., M; (9)

l [less than or equal to] [summation of] [x.sub.ij] where i = 1 to M [less than or equal to] u, j = 1, ..., p; (10)

[x.sub.ij] [element of] {0, 1}, for all i,j; (11)

where

[x.sub.ij] = {1 if machine i is in cell j, {0 otherwise.

This formulation maximizes the sum of all the arc weights that belong to the p cells. Since arc (i,j) in cell [G.sub.l] (l = 1, ..., p) is represented by the product [x.sub.il][x.sub.jl], arc (i,j) is included in cell [G.sub.l] if and only if [x.sub.il] = [x.sub.jl] = 1. Constraint set (9) ensures that each machine is in exactly one cell, and constraint set (10) restricts the number of machines in each cell.

The network-flow approach for Cases 1 and 2 is discussed as follows. The main idea behind the network solution procedure is the formulation of a bipartite network that assigns machines to other machines. In addition to the source and sink nodes, this network has two 'columns' of nodes with as many nodes in each column as there are machines. The arcs for this network are determined by whether or not two given machines are connected in the original network developed in the preprocessing phase. After transforming the bipartite network into a capacitated circulation network to choose p subsets representing p cells, the machines are allocated to cells subject to a constraint on cell size. The network-flow problems for the two cases considered in this article can be solved by a relaxation algorithm. The relaxation method is a dual ascent procedure; it works on the dual formulation trying to improve the value of the dual solution at every iteration for minimal-cost network-flow problems. The computerized version of this procedure is known as RELAXT-III (Bertsekas and Tseng, 1990).

Each node i in the original network G = (N, A), where N is the set of nodes and A is the set of arcs, is split into two nodes [i.sub.a] and [i.sub.b] to convert the original network into a bipartite network G[prime] = (N[prime], A[prime]). In this network each original arc (i,j) will correspond to an arc ([i.sub.a],[j.sub.b]). A circulation network representation for the problem under consideration is shown in Fig. 1. In this bipartite network model, the flow on arc (S, [i.sub.a]) is always one so that each source node [i.sub.a] cart supply one unit of flow to one destination node [j.sub.b] by the flow conservation condition. The 'cost' of shipping one unit of flow from node [i.sub.a] to node [j.sub.b] is -[c.sub.ij], where [c.sub.ij] or c(i,j) is the weight of arc (i,j) in the original network. The change in sign is due to the transformation of a maximization problem into a minimization problem. The parameters (upper bound, lower bound and cost) of arc ([j.sub.b], T) are set to [[infinity], 0, 0] to allow each demand node [j.sub.b] to receive as much flow as needed. The parameters of arc ([i.sub.a],[j.sub.b]) for i = j are set to [1, 0, 0]. To form a closed-loop system, the return arc is added connecting node T to node S with arc parameters [M, M, 0]. In the output of the minimum-cost algorithm the demand nodes with positive flow from source nodes are included in the set {[j[prime].sub.b]} and the number of nodes in this set is denoted by p[prime]. If p[prime] [less than] p, the upper bound of each arc ([j.sub.b], T) is reset to [Epsilon] = [M/p], where [a] indicates the smallest integer no less than a, and then the mini-mum-cost problem is solved again. After this, the number of nodes in the set {[j.sub.b][prime]} will be greater than or equal to the desired value of p.

Once the set of demand nodes {[j[prime].sub.b]} is identified, surplus demand nodes are eliminated by the following rule. The cost parameters (-[c.sub.ij]) on the arcs ([i.sub.a],[j[prime].sub.b]) with positive flow are summed for each node [j[prime].sub.b], and then the p smallest costs and their corresponding p demand nodes represented by the set [Mathematical Expression Omitted] are identified. The elimination of demand nodes [Mathematical Expression Omitted] is performed by switching the upper bound from [infinity] or [Epsilon] to zero on arcs ([j[prime].sub.b], T). By resetting these upper bounds to zero no flow from source nodes can be sent along these arcs. The upper and lower bounds of arcs ([Mathematical Expression Omitted], T) are set to u and l for the cell-size restriction case (Case 2). For the no-restriction scenario (Case 1), if the upper bound of each arc [Mathematical Expression Omitted] was initially [Epsilon], now it must be changed to [infinity]. Otherwise, these changes on upper bounds are not required. Finally, the lower bound of each arc ([i.sub.a], [Mathematical Expression Omitted]) for i = j is set to one. The network algorithm is then applied to reroute the flow along those nodes being eliminated. At the end of the procedure, only p demand nodes representing p cells receive positive flow from the source nodes. The proposed algorithm consists of the following six steps.

Algorithm

Step 1: Network transformation procedure: for node i [element of] N, create two nodes [i.sub.a], [i.sub.b] [element of] N[prime] and for arc (i,j) [element of] A, create a directed arc ([i.sub.a], [j.sub.b]) [element of] A[prime]. Construct a capacitated-circulation network G[prime] = (N[prime], A[prime]) by adding a super source node S, a super sink node T, the return arc (T, S), and a capacity cost triplet for each arc in A[prime].

Step 2: Identification of minimal cost arc flows: solve the transformed network by using the relaxation algorithm and identify the demand node set {[j[prime].sub.b]} = {[j.sub.b] [where] f([i.sub.a], [j.sub.b]) = 1}, where [f.sub.ij] or f(i, j) is the flow along arc (i,j).

Step 3: Computation of the total cost for each demand node: compute the sum of costs on each demand node [j[prime].sub.b]:

S([j[prime].sub.b]) = [summation over [i.sub.a]] f([i.sub.a], [j.sub.b])c([i.sub.a], [j.sub.b]).

Step 4: Selection of the p demand nodes having the p smallest sums of costs: for a given p, order the S([j[prime].sub.b])'s as [S.sub.1] [less than or equal to] [S.sub.2] [less than or equal to] ... [less than or equal to] [S.sub.p] and find demand node set [Mathematical Expression Omitted]. If p[prime] [less than] p, go to Step 2 after resetting the upper bound of each arc ([j.sub.b], T) from [infinity] to [Epsilon]. Otherwise go to Step 5.

Step 5: Parameter change procedure: for Case 2, remove all arcs ([j[prime].sub.b], T) with [Mathematical Expression Omitted] by setting their upper bounds to zero, and reset the parameters of all arcs ([Mathematical Expression Omitted], T) to [u, l, 0]. For Case 1, if the upper bound of each arc ([Mathematical Expression Omitted], T) was initially [Epsilon], now it must be changed to [infinity]. Otherwise, these changes on upper bounds are not required. Finally, the lower bound of each arc ([i.sub.a], [Mathematical Expression Omitted]) for i = j is set to one.

Step 6: Identification of cells: solve the modified minimal-cost problem and identify the machine cells by tracing positive flows from the source node to the demand node.

When ties exist between the costs associated with some of the demand nodes in Step 4, the selection of the pth node may involve a choice between multiple options. The selection of the most appropriate node, however, is not a combinatorial difficult decision. To illustrate this, suppose that the costs at those nodes receiving positive flow, arranged in a non-decreasing order, are [C.sub.1], [C.sub.2], ..., [C.sub.d]. If p [less than or equal to] d, we must choose the nodes associated with [C.sub.1], [C.sub.2], ..., [C.sub.p]. However, if [C.sub.p + q] = [C.sub.p] for q = 1, 2, ..., Q, then each of the choices for node p should be considered independently of the other choices for executing Steps 5 and 6. At the end of this, the node associated with the most attractive solution is chosen.

A special case of the cell formation problem under consideration occurs when no desired number of machine cells is stipulated in advance, and no limits are imposed on cell size. The fundamental network modeling concept for this case is to generate closed chains from the solution of the capacitated circulation network forcing one unit of flow to go through each node of the similarity network exactly once. The main difference between this case and the other two is the requirement for a number of closed chains that contain all nodes (machines) of the network. The number of closed chains is equal to the number of machine cells, and those nodes in the same closed chain represent machines in the same cell. A detailed development of this methodology can be found in Lee and Garcia-Diaz (1993a,b).

In realistic situations, both multi-functional machines and multiple identical machines may exist. In the case of multi-functional machines, which in a number of industrial applications are usually required by a large number of parts, perhaps the most practical strategy is to design a separate cell (core manufacturing facility) for each of these machines. On the other hand, the consideration of identical machines in the cell formation process is possible within the scope of the proposed network approach, following either of the two heuristic procedures outlined below. The first procedure is used when it is desired that all identical machines of a given type be in the same cell. Otherwise, the second procedure is used.

Procedure 1

* All identical machines of a particular type are represented by a single machine in the network-flow approach. These machines along with the non-duplicated machines are then assigned to the cells by the network solution methodology.

* Parts are then assigned to the cells by the part family determination procedure.

* On the basis of the required workload, and as an effort to promote balanced cell formation, additional identical machines of each type are included in the cell containing machines representing multiple identical machines of the type being considered. If some inter-cell part flow associated with the identical machines still exists, additional machines, if available, should be included in the cell.

Procedure 2

* From the operation sequences determine the total processing time [T.sub.i] required from all machines of type i (i = 1,2, ..., t). Let [n.sub.i] be the number of identical machines of type i. Therefore the time for each machine type i can be calculated as [t.sub.i] = [T.sub.i]/[n.sub.i].

* Consider machine type i. We assume that all parts can be considered in a given order k = 1, 2, ..., K. Now we can start scanning parts in this order and calculate the cumulative time for the operation processed by machines of type i. When the cumulative processing time reaches the value [t.sub.i] or a value close to it, the first machine of type i is labeled [i.sub.1]. Similarly, when the cumulative value reaches the value approximately equal to 2[t.sub.i], the second machine of type i is labeled [i.sub.2], and so on. This procedure can be repeated for all types of machines.

* Assign machines to cells by using the network partitioning methodology.

2.3. Part family formation phase

Once machine cells have been identified by the network partitioning procedure, the corresponding part families can be determined by assigning parts to cells according to two alternative criteria. The first criterion allocates the parts on the basis of only the type of operations required by each part. The second criterion allocates the parts on the basis of both the type of operations and the processing time required for each machine. In this case, cell utilization is considered along with inter-cell part flows.

When the first criterion is used, a suitability index [s.sub.ik] can be computed as the Hamming distance between part i and cell k after representing the part and the cell as binary vectors. In this case the suitability index associated with part i and cell k is obtained from (1) by defining [s.sub.ik] = [d.sub.ik], [Rho]([a.sub.mi], [a.sub.mk]), and m = 1, 2, ..., M. This is a symmetric function that takes on low values when parts and cells are not very suitable, and increasing values as the degree of suitability increases. Alternatively, when the second criterion is used, the suitability index is redefined as the fraction of the processing time of part i that occurs in cell k. In symbols,

[s.sub.ik] [summation over l] [t.sub.ikl]/[summation over l] [t.sub.il], (12)

where [t.sub.il] is the processing time for operation l of part i, and [t.sub.ikl] is the processing time for operation l of part i required to be performed in cell k. Eqn (12) quantifies the suitability of a part and a cell in terms of machine requirements of the part and the utilization of the cell. A higher utilization is achieved when a part is assigned to a cell containing required machines with longer processing times.

As an illustration of the two criteria considered before, suppose that the following two binary vectors represent the machine requirements of part i and the machine capabilities of cell k:

[P.sub.i] = [100101001001000],

[C.sub.k] = [110101000001000].

Part i has the operation sequence 1-4-6-9-12 and cell k consists of machines 1, 2, 4, 6, and 12 in a system consisting of 15 machines. From (1), we obtain [s.sub.ik] = 13. Now, if in addition to the above information it is assumed that the processing times are 5, 10, 15, 20, and 8, for machines 1, 4, 6, 9, and 12, respectively, from (12) we obtain [s.sub.ik] = (5 + 10 + 15 + 8)/(5 + 10 + 15 + 20 + 8) = 0.655.

A 0-1 integer programming model is formulated to maximize the sum of suitability values between all parts and cells:

[Mathematical Expression Omitted]

subject to

[summation of] [x.sub.ik] where k = 1 to p = 1, i = 1, ..., N; (14)

[l.sub.k] [less than or equal to] [summation of] [x.sub.ik] [less than or equal to] [u.sub.k] where i = 1 to N, k = 1, ..., p; (15)

[x.sub.ik] [element of] {0, 1}, i, k; (16)

where [s.sub.ik] is the suitability measurement between part i and cell k here computed as either a Hamming metric or the fraction shown in (12). The objective function in (13) maximizes the sum of suitability measurements between all parts and cells. Constraint set (14) ensures that each part is assigned to one cell. Constraint set (15) imposes the part family size restriction. Constraint (16) meets the integrality requirement. The solutions to the model are the values of the variables [x.sub.ik] (0 or 1), which indicate whether or not part i is assigned to cell k.

This problem can be equivalently formulated as a transportation network having supply nodes with one unit of supply and demand nodes with specified upper and lower bounds on demands. The set of supply nodes corresponds to the set of parts, and the set of demand nodes represents the machine cells. The supply and demand nodes are connected by arcs with the negative of suitability values as the per-unit flow costs as shown in Fig. 2. The solution of this model is performed through the relaxation network algorithm. This solution allows the identification of a feasible assignment of parts to machine cells satisfying the restriction on part family size.

3. An illustrative example

As an illustrative example, 16 parts with operational sequences on 12 machines and production volumes as given in Table 1 will be considered. The network representation of the problem is shown in Fig. 3. The value assigned to the arcs represents the number of part moves between machines computed with (2). It is desired to find three cells (p = 3) with lower and upper bounds on size restriction equal to l = 2 and u = 4 for Case 2. As indicated before, there is no restriction on cell size for Case 1.

The original network of Fig. 3 is transformed into the capacitated-circulation network shown in Fig. 4a. After application of the network algorithm, seven demand nodes resulted with positive flows ([f.sub.ij] = 1). Three demand nodes (3, 4, and 7) are selected after computing the associated costs as shown in Fig. 4b. Four demand nodes are eliminated by resetting the upper bound [infinity] to zero on arcs ([j[prime].sub.b], T). Also, the lower bound on each arc ([i.sub.a], [Mathematical Expression Omitted]) for i = j is set to one. After this, the network flow algorithm is used again. The final solution is shown in Fig. 4c, which consists of three cells with nodes (1, 4, 6, 8), (7, 9, 10, 11) and (2, 3, 5, 12). For the unrestricted cell-size consideration, the same procedure is applied, except that the upper bound on each arc ([Mathematical Expression Omitted], T) is not changed from [infinity]. Three cells with nodes (1, 4, 6, 8), (7, 9, 10, 11, 12) and (2, 3, 5) are identified by tracing positive flows from the source to the demand nodes as shown in Fig. 4d. Table 2 shows the composition of the three cells and the corresponding binary vector representations for Case 2.

The suitability measurements between the parts and the cells were computed on the basis of the binary vector representation of parts and cells and used as the negative of per-unit cost of flow in the minimum-cost network-flow model. The lower and upper limits on the part family size were set to two and six, respectively. The minimum-cost network-flow algorithm was applied to get the optimal part groupings. The solution was obtained by tracing arcs (i,j) with a positive flow [f.sub.ij] = 1, which means that part i is assigned to cell j. The resulting solutions are given in Table 3. This table also shows the part family configuration when there are no restrictions on the part family size obtained by setting l = 0 and u = [infinity].

Table 1. The sequence of operations of the part

No.   Operation sequence   Quantity   Vector representation

1     14-8-9               2          (1 0 0 1 0 0 0 1 1 0 0 0)
2     1-2-6-4-8-7          3          (1 1 0 1 0 1 1 1 0 0 0 0)
3     1-2-3-4-7-8-9        1          (1 1 1 1 0 1 1 1 0 0 0 0)
4     1-4-7-9              3          (1 0 0 1 0 0 1 1 0 0 0 0)
5     1-6-10-7-9           2          (1 0 0 0 0 1 1 0 1 1 0 0)
6     6-10-7-8-6           1          (0 0 0 0 0 1 1 1 0 1 0 0)
7     6-4-8-7              2          (0 0 0 1 0 1 1 1 0 0 0 0)
8     3-5-2-6-4-6          5          (0 1 1 1 1 1 0 0 0 0 0 0)
9     3-5-2-6-4-8          1          (0 1 1 1 1 1 0 1 0 0 0 0)
10    3-12-4-8             2          (0 0 1 1 0 0 0 1 0 0 0 1)
11    11-7-12-11           1          (0 0 0 0 0 0 1 0 0 0 1 1)
12    11-10-7-12           1          (0 0 0 0 0 0 1 0 0 1 1 1)
13    11-7-10              3          (0 0 0 0 0 0 1 0 0 1 1 0)
14    11-10-9              1          (0 0 0 0 0 0 0 0 1 1 1 0)
15    11-7-12-10           1          (0 0 0 0 0 0 1 0 0 1 1 1)
16    6-7-10               3          (0 0 0 0 0 1 1 0 0 1 0 0)

4. Industrial application

The network-flow-based methodology has been applied to an industrial company with production plants located in two different cities (Plant A and Plant B) in Pennsylvania. The production facilities include approximately 150 machines, such as lathes, drills, presses, and other machines to manufacture hydraulic cylinders and pistons, power transmission gears, links, and other mechanical parts. About 40 000 parts are in process and 5500 unique operation routings of parts are used for the production of a lift and hoist.

The data required for the analysis included: (1) the list of machines and their locations (plants), and (2) unique operation sequences with the production quantities for each part. Plant A has 44 machines, and Plant B has 99 machines. The collected data were initially prepared to eliminate purchasing and single-operation parts, as well as non-machining operations such as dispatching, assembly, packing and storage from the part routing list. After this initial preparation, the preprocessing phase of the proposed network procedure was executed to compute the number of inter-machine part moves. The total number of part moves for Plant A and Plant B turned out to be 6487 and 54 674, respectively. Table 4 summarizes some characteristics of the industrial data to be investigated.

Table 2. Machine cell compositions

Cell     Machines     Vector representation

1        1,4,6,8      (1 0 0 1 0 1 0 1 0 0 0 0)
2        7,9,10,11    (0 0 0 0 0 0 1 0 1 1 1 0)
3        2,3,5,12     (0 1 1 0 1 0 0 0 0 0 0 1)

To determine the number of cells and the cell size for Cases 1 and 2, the average number of operations, as well as the minimum and maximum numbers of operations, for each part were obtained as shown in Table 4. For example, as Plant A has 44 machines and the average number of operations for parts manufactured in this plant is 7, the number of cells for this plant can be about 6. In addition, the minimum and maximum numbers of operations on the parts are 2 and 10, respectively. These values can be used for lower and upper bounds on the cell size for Case 2.

Owing to the large size of the problem, it is difficult to present the entire list of machine cells and part families. The suitability measure between the part and the cell was computed by the Hamming metric because the processing time of each operation was not provided. The final results for machine cell and part family formation are shown in Table 5. This table shows the number of cells, number of part moves within cells, cell efficiency (the ratio of the total number of part moves within cells to the total number of part moves in the system) to evaluate the solutions obtained, part family size, and total computing time required for cell and part family formation. The cell efficiency for Case 1 is slightly higher than that of Case 2 for the same number of desired cells, owing to the relaxation of cell size restrictions. It is noted that cell efficiency decreases as the number of cells increases.

Table 3. Result of the illustrative example

Cell   Machines Parts (l = 2, u = 6)     Parts (no restriction)

1      1,4,6,8        1,2,3,4,6,7        1,2,3,4,6,7,9,10
2      7,9,10,11      5,12,13,14,15,16   5,11,12,13,14,15,16
3      2,3,5,12       8,9,10,11          8
Table 4. Important characteristics of industrial data

                                  Plant A      Plant B

Number of machines                    44            99
Number of parts                     3803        25 303
Number of operation sequences       1001         4 236
Number of part moves                6487        54 674
Average number of operations           7             8
Minimum number of operations           2             3
Maximum number of operations          10            12

Once cells had been identified, parts were allocated to those cells to form part families considering a part family size restriction. Table 5 shows the upper and lower bounds on the part family size used in the computer runs of the network methodology. As shown in this table, the total computing time of 35 seconds for Plant A and 130 seconds for Plant B indicates that the methodology is [TABULAR DATA FOR TABLE 5 OMITTED] attractive for solving a real industrial problem.

5. Computational experience

The purpose of this section is to show the computational performance of the network approach. The optimality [TABULAR DATA FOR TABLE 6 OMITTED] and near-optimality of solutions and the applicability of the network procedure to large-scale problems are discussed. A FORTRAN code that has the RELAX procedure as a subroutine was used for solving the network flow problem. The Hyper LINDO program was used for solving the p-median model. Both codes were run on an IBM/PC AT computer. Thirty runs of LINDO's optimal simplex-based linear integer programming (LIP) algorithm and of the heuristic network approach procedure developed in this article were conducted to assess the near-optimality of the network solutions. For this purpose, 30 problems were randomly generated with M (number of nodes) being set to 10, 15, 20, 25 and 30, and p set to 2, 3, 4 and 6 for Case 1. The maximum value considered for M was equal to 30 because this corresponds to at most 900 arcs and the largest number of integer variables allowed by the LIP algorithm in Hyper LINDO is 1000.

Table 6 summarizes the objective function value and computational time (in seconds) for the 30 problems under discussion. It is noted that the network approach yields near-optimal solutions differing by an average of less than 5 % from the optimal value. However, the running time for the LIP procedure seems to increase almost exponentially. For a model with a large number of machines, it can be expected that the LIP procedure would take an enormous amount of computer time for both program execution and input data storage. The network procedure, however, does not seem to have these limitations.

To demonstrate the applicability of the network procedure to large-scale networks, 30 additional randomly generated problems with M, the number of nodes, taking values from 100 to 1000 and arc density equal to 0.5 were solved by using the network heuristic procedure. Here, the arc density is defined as the actual number of arcs divided by the number of arcs in a totally connected network with the same number of nodes. The 'arc costs' were generated randomly according to a uniform discrete distribution between 1 and 100. Table 7 summarizes the computational results for the network approach with the following information: number of nodes; number of subnetworks (p); the upper and lower bounds on the subnetwork size; and running (CPU) time in seconds. By setting the upper bound to [infinity] and the lower bound to zero, the solution for Case 1 can be obtained. As the number of the machines increases, the computational behavior of the network procedure is superior to that of the LIP procedure for Case 1, as shown in Figure 5, which shows the average computing time on an arithmetic scale as a function of the number of machines up to 500 on a logarithmic scale.

6. Summary and conclusions

Network-flow-based procedures have been developed for solving a 0-1 linear programming model and a 0-1 quadratic programming formulation for the cell formation problems, as well as a 0-1 integer programming formulation for the family formation. The concept of using a circulation network for the cell and part family formation problem is a new approach. The efficient approximate procedure developed in this article was evaluated empirically by comparing its solutions with those obtained from an optimal procedure. On the basis of the comparative study, the network approach yielded near-optimal solutions differing from the optimal value by an average of less than 5%. Once machine cells are identified, optimal part families are formed by using a transportation-type network model.

Table 7. Computational results of network procedure for
large-scale problems

Run   No. of nodes     p      l        u          Time (seconds)

1      100               5    10       20         24.67
2                       10     5       15         24.78
3                       10     0    [infinity]    24.62
4      200              10    10       30         35.16
5                       20     5       15         35.21
6                       20     0    [infinity]    35.22
7      300              10    10       40         51.69
8                       15     5       30         51.74
9                       30     0    [infinity]    51.75
10     400              15    10       30         74.38
11                      20    15       40         74.27
12                      40     0    [infinity]    75.15
13     500              10    30       60         97.06
14                      20    15       30         96.94
15                      50     0    [infinity]    97.38
16     600              20    10       40         140.76
17                      30    10       30         140.93
18                      60     0    [infinity]    140.56
19     700              20    20       40         186.93
20                      10    50       80         187.25
21                      70     0    [infinity]    186.75
22     800              20    30       50         232.32
23                      40    10       30         231.57
24                      80     0    [infinity]    232.07
25     900              30    10       40         285.30
26                      20    20       50         286.14
27                      90     0    [infinity]    285.51
28    1000              15    10      100         351.74
29                      30    20       50         350.06
30                     100     0    [infinity]    351.25

The proposed methodology can be used considering as part of the input data the machine-part matrix or the operational sequences of the parts to be manufactured. Multiple identical machines can be considered by initially representing them as individual machines and then placing the required number of available machines in the corresponding cell, or by evenly distributing the workload of each machine type between all available machines, and then considering them as different machines in the network model.

The two most important features of the proposed methodology are its modeling flexibility and its highly efficient computational performance. In addition, it is mentioned that the input data storing requirements are significantly reduced by exploiting the efficient data structure of the network model. Computational results indicate that the proposed approach is appropriate for solving large-scale industrial problems including up to several hundred machines and several thousands of parts, in a microcomputer environment. The computer running time of about 200 seconds for the cell and part family formation case in a industrial problem considering 150 machines and 5500 operation sequences seems to be attractive. The network approach is both effective in finding partitions and efficient in solving large-scale problems.

The single most relevant contribution of this article is the provision of a network-flow approach to cellular manufacturing. When available mathematical programming approaches, such as integer programming or quadratic assignment models, are used for solving the same problems as considered in this article, the computational requirements associated with the available procedures preclude their application in large-scale problems. However, our computational analysis shows that the network procedure can be used for solving cell formation problems of realistic size.

The network model assumes that all machines are different. Although Fig. 3 depicts a one-to-one machine operation mapping, two heuristic procedures were developed to consider the more general case where there are multiple identical machines. These heuristic procedures were designed to be used in conjunction with the network approach, because it cannot recognize identical machines itself. As a result of this simplification, the appropriateness, computational efficiency, and data storage minimal requirements of the network procedure can be extended to the case where there are multiple machines of the same kind. It is envisaged, as it is usually the case, that the network model will serve as the main optimizer in a more elaborate system that considers other measures of effectiveness and constraints not directly incorporated in the network representation.

The similarity coefficients recommended and used in this article are widely used in this research area. It would certainly be of benefit to have more robust similarity coefficients; however, it is not the focus of the article to develop such measures. Indeed, the proposed network approach is designed to use as arc parameters any kind of similarity values.

References

Askin, R.G. and Chiu, K.S. (1990) A graph partitioning procedure for machine assignment and cell formation in group technology. International Journal of Production Research, 28, 1555-1572.

Barnes, E.R. (1982) An algorithm for partitioning the nodes of a graph. SIAM J. of Algebraic and Discrete Methods, 3, 541-550.

Bertsekas, D. and Tseng, P. (1989) Relaxation methods for minimum cost ordinary and generalized network flow problems. Operations Research, 36, 93-114.

Bertsekas, D. and Tseng, P. (1990) RELAXT-III: a new and improved version of the RELAXT code. Laboratory for Information and Decision System Report LIDS-P-1990, MIT, Cambridge, MA.

Burbidge, J.L. (1975) The Introduction of Group Technology, John Wiley and Sons, New York.

Chen, H.G. and Guerrero, H. (1994) A general search algorithm for cell formation in group technology. International Journal of Production Research (forthcoming).

Jensen, R.E. (1969) A dynamic programming algorithm for cluster analysis. Operations Research, 12, 1034-1057.

Kennedy, J.M. (1974) A review of some cluster analysis methods. AIIE Transactions, 6, 216-227.

Kernighan, B.W. and Lin, S. (1970) An efficient heuristic procedure for partitioning graph. Bell System Technical Journal, 49, 291-307.

Kumar, K.R., Kusiak, A. and Vannelli, A. (1986) Grouping of parts and components in flexible manufacturing systems. European Journal of Operational Research, 24, 387-397.

Kusiak, A. (1987) The generalized group technology concept. International Journal of Production Research, 25, 561-569.

Kusiak, A. (1990) Intelligent Manufacturing Systems, Prentice-Hall, Englewood Cliffs, New Jersey.

Lee, H. and Garcia-Diaz, A. (1993a) A network flow approach to solve clustering problems in group technology. International Journal of Production Research, 31, 603-612.

Lee, H. and Garcia-Diaz, A. (1993b) Machine-part grouping in cellular manufacturing for minimizing inter-cell material flows, in Proceedings of the 2nd Industrial Engineering Research Conference, Los Angeles, CA, pp. 197-201.

Lee, J. G., Vogt, W. G. and Mickle, M. H. (1979) Optimal decomposition of large scale networks. IEEE Transactions on System, Man and Cybernetics, 9, 369-375.

Mulvey, J.M. and Crowder, H.P. (1979) Cluster analysis: an application of Lagrangean relaxation. Management Science, 25, 329-340.

Seifoddini, H. and Wolfe, P.M. (1986) Application of the similarity coefficient method in group technology. IIE Transactions, 18, 271-277.

Vakharia, A.J. and Wemmerlov, U. (1990) Designing a cellular manufacturing system: a material flow approach based on operation sequences. IIE Transactions, 22, 84-97.

Vannelli, A. and Ravikumar, K. (1986) A method for finding minimal bottleneck cells for grouping part-machine families. International Journal of Production Research, 24, 387-400.

Biographies

Dr. Alberto Garcia-Diaz is professor of industrial engineering at Texas A&M. His research interests include network analysis, operations research in transportation planning, and statistical design and analysis of experiments. He received his M.Sc. and Ph.D. degrees from the University of Illinois at Urbana Champaign. Currently he is a member of IIE, INFORMS, and Alpha Pi Mu. He is author or coauthor of two textbooks and approximately fifty technical articles.

Dr. Hongchul Lee is an assistant professor at the Industrial Engineering Department in Korea University. His area of specialization is manufacturing systems analysis. His research areas include neural networks, network analysis, and operations research. He is a member of IIE and INFORMS. He received his Ph.D. degree from Texas A&M University.