# A volume and material handling cost based heuristic for designing cellular manufacturing cells.

EXECUTIVE SUMMARY

One of the major problems in a group technology or cellular manufacturing environment is the formation of part groups and machine cells. Because of the combinatorial nature of the cell formation problem, it is difficult to solve the problem optimally. Most of the procedures related to cell design in cellular manufacturing operate on the part-machine incidence matrix in an attempt to identify block diagonality. If complete block diagonality does not exist, the decision about cell configuration is left to the subjective judgement of the designer. These procedures are also generally based on part routing only, and do not consider part volume and material handling costs.

In this paper we develop an integer programming model, as well as a heuristic to effectively assign machines to cells. In these procedures we consider component volumes, costs related to movement of components between and within cells, and penalty for not using all machines in a cell visited by a component. Since the integer programming formulation becomes large even for small problems, an efficient heuristic is developed to solve larger problems. The heuristic solutions to 180 randomly generated small problems were compared against the optimal solutions obtained by the integer programming model. The heuristic has been found to identify optimal solutions in all 180 cases.

This heuristic is also compared to several well known algorithms on 900 larger test problems. These problems were generated to cover a wide range of environmental situations such as varying levels of block diagonality in the part-machine incidence matrix, and diversity in the component volumes and material handling costs. In 99% of the problems our heuristic generated solutions which are better or as good as the best solution obtained by other algorithms. Further, in situations where complete block diagonality in the part-machine incidence matrix did not exist, our heuristic produced even better results. Since the maximum number of iterations required in our heuristic is the number of machines in the problem, the heuristic is computationally efficient.

INTRODUCTION

Many manufacturing situations involve production of parts requiring similar processing. Cellular manufacturing (CM) techniques attempt to group machines into cells to provide an efficient production process. Recently, CM has received considerable attention among academicians and practitioners interested in improving the productivity of small to medium-sized batch production (Greene and Sadowski (1984), Hyer and Wemmerlov (1982), Mosier and Taube (1985), Suresh and Meredith (1985)). CM offers a number of advantages as compared to traditional manufacturing (e.g., job shops, assembly lines). These include lower inventories and lead times, reduced throughput time, increased flexibility, and easier shop floor control (Hyer (1984)).

Because of the combinatorial nature of the cell formation problem, the computational difficulty grows exponentially with increasing problem size. In the past decade numerous techniques have been developed to solve this problem. Prominent among them are standardized coding and classification schemes, Production Flow Analysis (PFA) by Burbidge (1989), Bond Energy Algorithm (BEA) by McCormick, Schweitzer, and White (1972), Direct Clustering Algorithm (DCA) by Chan and Milner (1982), and Wemmerlov (1984), Rank Order Clustering (ROC) algorithms by King (1980) and King and Nakornchai (1982), and Efficient Clustering Algorithm (ECA) by Morris (1988). Other algorithms used mathematical programming (Dahel (1988), Kumar and Vannelli (1984), Robinson and Duckstein (1986), Steudel and Ballakur (1987), Wu, Venugopal and Barash (1986)), graph theory (Askin and Chiu (1990)), and set theory (Purcheck (1985)).

Most cell design methodologies can be classified into two categories. The first category includes such algorithms as ROC, BEA, DCA. These algorithms generally utilize row and column operations of the zero-to-one part-machine incidence matrix (King and Nakornchai (1982)), sometimes using a surrogate measure of similarity index (Kennedy (1972)) between rows and columns. The objective is to attain block diagonality or near block diagonality as the situation permits. If block diagonality exists in the part-machine incidence matrix, then most of these algorithms have, been found to identify the block diagonal solution (Morris (1988)). If block diagonality does not exist, these algorithms attempt to rearrange the rows and columns of the part-machine incidence matrix to obtain near block diagonal solutions. In the latter situation, the decision about cell configuration is left to the subjective judgement of the designer. The second category of algorithms based on mathematical programming, graph theory, and set theory, become computationally intractable with increasing problem size.

Most of the above mentioned algorithms use only part routing information for cell design decisions, and do not consider any costs. This may be a very simplistic approach because factors such as component volume, intra-cell and inter-cell material handling costs may significantly impact the performance of a cell. Askin and Chiu (1990) used inter-cell material handling cost and developed a graph-theoretic algorithm based on Kernigham and Lin's (1970) heuristic on partitioning a graph. However, their method does not consider intra-cell material handling cost, and the stopping condition for the iterative procedure is imposed exogenously.

In this paper, we develop a computationally simple heuristic to solve the cell design problem. Since our heuristic considers the volume, and material handling costs we name it the volume and material handling cost (VMC) heuristic. The heuristic is based on an iterative procedure which successively combines machines to form cells until no more cost reduction is attainable. The heuristic solutions were first compared to the optimal solutions obtained from a mixed integer programming model for 180 small, randomly generated problems. The heuristic identified the optimal solution in all of these 180 small test problems. Next the heuristic was tested against ROC, DCA, ECA, and BEA algorithms on 900 larger test problems. In 99% of these test problems, solutions generated by the proposed heuristic were at least as good as those obtained by using other algorithms. Further, in situations where block diagonality of the part-machine incidence matrix did not exist, our heuristic produced even better results. It can be inferred from a recent study by Wemmerlov and Hyer (1989) that in most United States industrial applications, complete block diagonality does not exist. Hence, from a practical viewpoint, our heuristic may be useful to managers. Furthermore, the heuristic is computationally simple, because the upper bound on the number of required iterations is limited by the number of machines in the problem.

COST FACTORS INVOLVED IN CELL DESIGN

The primary objective of the cell design problem is to group various operations physically in proximity so that similar components can be processed without much material handling and with minimal setup overhead. The major cost factors which are directly associated with the cell design problem are the following:

1) Inter-cell material handling. This cost is incurred when a product needs to travel from one cell to another. When a cell does not provide all the operations needed by a particular part, it must be transported to another cell. It accrues from two sources. First, the cost of physical transportation to a machine belonging to another cell. Since the marginal cost of transportation per unit distance is minimal, this is not dominant. Second, and more important, is the cost of the coordinating effort. Each shipment between cells involves scheduling of machines and material handlers, delays, additional record keeping and setups. Consequently inter-cell material handling cost is specified on a per unit basis in this paper.

2) Intra-cell material handling. This cost is incurred when a component departs a machine and goes to another machine in the same cell. This cost accrues as a result of the material handling effort in transporting parts between machines in a cell. Usually these machines are located close to one another, so that distance travelled is not large. Consequently, this cost too, is specified on a per unit basis in this paper.

3) Cost for skipping a machine in a cell. This cost accrues when a part does not visit all the machines within a cell. Every time a part skips a machine, some special handling occurs. This can result in the need for additional material handling equipment, larger lot sizes, higher inventories, delays, and lower machine utilization due to scheduling difficulties. Consequently, this cost is specified on a per unit per machine skipped basis.

These costs may be independent of one another since they are driven by different factors. However, total inter-cell material handling cost will reduce, while total intra-cell material handling cost, and total skipping cost will increase as machines are grouped into cells. The objective of cell formation is to minimize the sum of these costs.

Intra-cell and inter-cell material handling costs are functions of engineering design and accounting data, including transfer batch sizes, type of material handling system, distance moved, and size and weight of the components. Intuitively there are interactions among these factors, and it is difficult to determine these costs accurately before solving the specific layout design problem. In this paper we treat the cell design problem independent of the specific layout design problem. In most cases, workable estimates of these cost factors may be obtained from past experience. Further, in the cell design problem the exact costs are not as critical as their relative values.

The skipping cost can be treated as a management parameter which can be associated with desired cell size, and expected machine utilization. In a particular environment, management may wish to conduct sensitivity analysis using different subjective values of skipping cost to obtain alternative solutions. These solutions can then be evaluated against the desired objectives of cell size and machine utilization.

With the above perspective on various costs associated with a CM cell design, we now present an optimization model followed by our heuristic. In these procedures we assume that part operations have already been assigned to machines. Secondly, we assume that only one machine of each type is required.

FORMULATION OF OPTIMIZATION MODEL

The decision variables in this model are [X.sub.jk] which allocates the machines to cells. These allocations are made in a manner that will minimize the total cost consisting of machine skipping, intra-cell, and inter-cell material handling costs. Table 1 presents a list of notations used in this paper. In the following formulation, subscript i refers to parts (1 ,...,[n.sub.p]), subscript j refers to machines (1 ,...,[n.sub.m]), and subscript k refers to cells (1 ,...,[n.sub.m]).

[Mathematical Expression Omitted]

Subject to:

[Mathematical Expression Omitted]

Discussion of Formulation

The objective function calls for the minimization of total cost consisting of intra-cell and inter-cell material handling and skipping costs. The constraints in the above formulation ensure that each part and each machine is assigned exactly to one cell and all part movements are accounted for.

The objective function consists of three components. The first component of the objective function (1.1) determines the total intra-cell cost. Here we use two variables, [D.sub.ik] and [Y.sub.ik] . [D.sub.ik] denotes the number of machines that part i requires in cell k and is defined in constraint (2.0). [Y.sub.ik] indicates whether part i visits cell k and is defined in (3.0).

The second component of the objective function (1.2) determines the total inter-cell cost. Here we use a variable [F.sub.i] which denotes the total number of inter-cell movements for part i. It is defined in constraint (4.0), and is the difference between total number of part movements and the number of intra-cell movements less 1.

The third component (1.3) determines the total skipping cost. In this expression we introduce an integer variable [G.sub.ijk] which is defined as:

[G.saub.ijk] = (1-[a.sub.ij])[X.sub.jk] [Y.sub.ik]

[G.sub.ijk] will be 1 if [a.sub.ij] = 0, [X.sub.jk] = 1. and [Y.sub.ik] = 1. Clearly, [G.sub.ijk] will be 1 if machine j is assigned to cell k, and part i must visit cell k (since cell k contains some machines needed by part i) but does not require machine j. The above expression for [G.sub.ijk] is nonlinear and is being linearized using constraints (5.0) and (6.0).

Constraint (7.0) ensures that each machine is assigned to exactly one cell. Constraint (8.0) defines [X.sub.jk] and [Y.sub.ik] as 0-1 integer variables.

This integer program will have nm(np + nm) integer variables and at most (3[n.sub.m.sup.2][n.sub.p] + [n.sub.m][n.sup.p] + [n.sub.m] + [n.sub.p]) constraints depending on the density of the part-machine incidence matrix. For example, the number of constraints implicit in (3.0) would not be [n.sub.m.sup.2] [n.sub.p] since many [a.sub.ij]'s would be zeros. Similarly, in the cases of (5.0) and (6.0) there would be fewer constraints since they will appear only if [a.sub.ij] is zero. The number of cells required, [n.sub.c] is bounded by the value of [n.sub.m] and its optimal value will be determined by the integer program. For example, for a 9 part x 9 machine problem we would have 162 integer variables and at most 2367 constraints. It is apparent that large problems cannot be easily solved using this optimization model. Consequently, an effective heuristic is needed to solve large problems. In the next section we describe the VMC heuristic.

DESCRIPTION OF THE VMC HEURISTIC

The VMC heuristic attempts to form machine cells in a way that total cost consisting of material handling costs and skipping costs is minimized. It starts with an initial solution consisting of [n.sub.m] cells with one machine in each cell. This solution will result in the maximum possible inter-cell material handling cost and minimum amount of intra-cell material handling and machine skipping cost.

VMC is an iterative procedure. In each iteration, two cells are merged in order to extract a cost reduction. As cells are merged, inter-cell material handling costs will decrease, and the intra-cell material handling and machine skipping costs will increase. The heuristic is designed to trade off higher intra-cell movement and skipping costs with lower inter-cell movement cost in order to reach a better solution. Given the starting solution of [n.sub.m] cells, we attempt to identify the pair of cells which, when merged, will result in the greatest reduction in total cost. This pair of cells is then merged to make a new cell. This procedure is repeated until there is no pair of cells which improves the solution. The steps of the heuristic are presented below:

STEP O: [n.sup.c] = [n.sup.m]

STEP 1a: k = e + 1 STEP 1B: Let S be the change in skipping cost when cell k and cell e are combined. Hence,

STEP 2: e = e + 1, if e = [n.sub.c], then go to Step 3, otherwise go to Step 1a. STEP 3: [r.sub.xy] = Min [[r.sub.ab.]], a = 1,2,3,...,[n.sub.c]-1; b = a + 1,a + 2,...,[n.sub.c]; STEP 4: [SIZE.sub.x] = [SIZE.sub.x] + [SIZE.sub.u]; [C.sub.x] = [C.sub.x] U [C.sub.y]

STEP 5: [Mathematical Expression Omitted]

STEP 6: k = k + 1

STEP 7: Stop.

Since the number of cells decreases by 1 in each iteration, VMC will converge and the maximum number of iterations needed for convergence would be bounded by [n.sub.m]. Each of these iterations contains at most [n.sub.m.sup.2] sub-iterations each consisting of [n.sub.p] computations. Consequently, the computational complexity of this heuristic is O(n.sub.m.sup.3][n.sup.p]. The pairwise cost increase matrix R is similar to the similarity matrix used by a number of researchers. Each entry [r.sub.ij] in this matrix may be considered as the bond between partition i and partition j. However, in the case of VMC, the affinities are expressed directly in terms of cost savings (which was not the case in most previous work).

PERFORMANCE OF VMC HEURISTIC COMPARED TO OPTIMAL SOLUTIONS

In order to evaluate the performance of this heuristic against the optimal solution, we randomly generated 180 small (9 part 9 machine) test problems emulating the experimental conditions employed in this research (discussed later). The Integer Program (IP) was solved by using LINDO. Due to the limits imposed by the software and in order to avoid excessive computational time, the integer program was formulated by limiting the maximum number of cells allowed to 5.

In all 180 test problems, the heuristic solutions were at least as good as the IP solutions. In five cases however, the heuristic solutions were found to be superior. Analysis of these cases revealed that the heuristic formed more than five cells, whereas the IP formulation being restricted to a maximum of five cells could not find lower cost solutions.

AN EXAMPLE

To illustrate the heuristic let us consider an example with 24 parts and 20 machines. The incidence matrix, volume of parts to be processed, and inter-cell and intra-cell material handling costs for each part are shown in Table 2. The incidence matrix is obtained from Morris (1988). In this example the incidence matrix can be characterized as randomized block diagonal with exception (discussed in the next section.) The volumes and inter-cell material handling costs have been randomly generated from U(10,590), and U(.50,11.50), respectively. Intra-cell handling cost is assumed to be 10% of inter-cell handling cost. Machine skipping cost is assumed to be 1.0/unit/machine skipped.

[TABULAR DATA OMITTED]

We start with 20 cells, one machine in each cell. The V matrix representing the volume of each part being processed through these cells is constructed. Now we construct the symmetric Marginal Cost Increase matrix R. The matrix is shown in Table 3. A negative entry in this matrix, say [r.sub.4,14] signifies that combining cell 4 and cell 14 to form a new cell will lower total operating cost by 7837. We combine cell 4 and cell 14 into one cell since this produces the highest savings and construct the new V matrix (shown in Table 4.) Computationally, it is simple to reconstruct the V matrix. We replace column 4 with the union of current column 4 and column 14. Then the original column 14 is deleted.

[TABULAR DATA OMITTED]

The heuristic required 16 such iterations to converge. The pairwise cost increase matrix in iteration 15 and 16, as well as the cell contents are shown in Table 5 and Table 6. As can be observed in Table 6, the heuristic solution is:

Cell 1: (1 13 15 19 10)

Cell 2: (2 8 16 5 12)

Cell 3: (3 11 9 6 17 20)

Cell 4: (4 14 18 7)

For this configuration the costs are computed as:

Total intra-cell handling cost = 9943

Total inter-cell handling cost = 7902

[TABULAR DATA OMITTED]

Morris has documented the ROC, DCA, BEA and ECA solutions for this incidence matrix. The VMC solution as shown above is same as those of ROC, ECA, and BEA. The DCA solution is different and more costly for this volume and cost configuration. It needs to be mentioned here that the solutions for the other algorithms were obtained by Morris without the knowledge of cost and volume parameters.

GENERATION OF TEST PROBLEMS

In order to test the performance of VMC, 900 test problems were generated. To generate these test problems we considered the following factors:

Characteristics of the Part-Machine Incidence Matrix

Conventional cell design algorithms have often been tested with the criteria of their abilities to permute the rows and columns of a part incidence matrix to a complete or nearly complete block diagonal matrix. Morris (1988) has shown that most of these algorithms are able to identify complete block diagonality given that it exists. However, the algorithms have been shown to perform differently in cases where complete block diagonality does not exist. In order to test various heuristics for different types of part-machine incidence matrices, Morris constructed incidence matrices of three types:

1) Randomized Block Diagonal (RBD). These part-machine incidence matrices were constructed by randomly rearranging the rows and columns of complete block diagonal matrices.

2) Randomized Block Diagonal with Exception (RBDE). These part-machine incidence matrices were constructed by randomly rearranging the rows and columns of matrices where 10% of the parts required routing to two or more cells.

3) Randomized Minimal Block Diagonal (RMBD). These part-machine incidence matrices were constructed by randomly rearranging the rows and columns of matrices where 20% of the parts required routing to two or more cells.

In this paper we have used the same part incidence matrices developed by Morris (1988).

Component Mix Characteristics

VMC is expected to be sensitive to the composition of the components in volume and material handling costs. We characterize the component mix as follows:

1) Homogeneous, where the volumes and material handling costs of all components are similar. In these experiments, the volume of individual parts and material handling costs are chosen from U(200,400) and U(5,7), respectively.

2) Diverse, where the volumes and material handling costs of the components vary significantly. In these experiments the parameters used are U(10,590) and U(.5,11.5), respectively

Size of the Part-Machine Incidence Matrix

Five sizes of part-machine incidence matrices were used in these experiments. These combined with the three types of part-machine incidence matrices discussed above, resulted in fifteen matrices. The problem sizes are 24x20, 40x25, 40x30, 40x35, 70x25. Other relevant parameters, such as matrix densities, minimum and maximum number of machines per cell in the matrices before randomization appear in Table 7.

Machine Skipping Cost

Another factor of significant interest in our experiment is the machine skipping cost. High level of skipping cost will tend to group the machines into many small but compact cells. We assume that the specific level of skipping cost is directed by the environment itself. However, in order to study the behavior of our heuristic, we solved each problem at three levels of skipping cost. The levels are .05, 1.0, and 1.50.

For each of the fifteen matrices, we then have two levels of component mix and three levels of skipping cost. This results in 90 problem types. Each problem type is replicated ten times by randomly generating volume and material handling costs from their respective distributions. This results in 900 problem instances.

RESULTS AND DISCUSSION

Algorithms like ROC, BEA, DCA, and ECA do not consider the volume of parts and associated material handling cost factors. In this context a comparison of VMC with these algorithms may not be completely justified. However, the procedures to incorporate cost and volume information to these algorithms for improving the solutions are not clearly known. It is our intention to identify situations where there may be benefits in using procedures that explicitly utilize volume and material handling cost information.

The 900 problem instances were solved using VMC. The costs of these solutions were computed and averaged over the ten replications to obtain the average cost for each problem type.

Morris (1988) presented the cell configurations for the 15 part-machine incidence matrices using ROC, BEA, DCA, and ECA procedures. Recall that these procedures do not use volume and material handling cost information to identify cells. When block diagonality exists, these procedures provide unambiguous solutions. However, under RBDE and RMBD this does not happen. Morris developed a policy for cell formation based upon a trade-off between the number of cells and the number of parts travelling between cells (exceptions). The policy used was to form a cell consisting of at least two parts and two machines. These cells were formed such that the number of parts visiting more than one cell is less than 10% for RBDE problems and less than 20% for RMBD problems. The average total cost for Morris' solutions were obtained by applying the 10 replications of material handling cost and volume at each level of component mix and machine skipping cost.

Tables 8, 9 and 10 present the average total cost achieved by ROC, BEA, DCA, and ECA expressed as a percent of the corresponding VMC solutions. Twelve protected t-tests were conducted on the data in Tables 8 to 10. In each case the 30 values for each heuristic were averaged to test the following hypotheses.

Hypothesis Set I

HO: The performance of VMC is the same as the performance of the other heuristics. ([mu] =

100)

HI: The performance of VMC is better ([mu] > 100).

It was found that the VMC performs significantly better than all other heuristics for each type of part-machine incidence matrix at .9999 confidence level. It may have been expected that VMC solutions for RBD part machine incidence matrices would be identical to those found by the other procedures. While the other procedures did find the block diagonal solutions to these RBD problems, VMC often found an alternative non-block diagonal lower cost solutions. An example of such an occurrence is illustrated in the Appendix.

Furthermore, it is expected that when the component mix is diverse, VMC should produce greater savings. The following hypotheses were tested for each type of part-machine incidence matrix by comparing the values in Tables 8- 1 0 for the diverse and homogeneous cases for each problem size and skipping cost.

Hypothesis Set 2

HO: Diversity of component mix does not effect savings achieved by using VMC.

HI: Greater savings will be achieved by VMC in diverse component mix situations.

For each type of part-machine incidence matrix, the null hypotheses were rejected at a .99 confidence level.

To explore the effect of block diagonality of the part-machine incidence matrix, the following hypotheses were tested:

Hypothesis Set 3a

HO: The savings produced by VMC in RBDE is same as those produced by VMC in RBD.

HI: Greater savings are achieved in case of RBDE.

Hypothesis Set 3b

HO: The savings produced by VMC in RMBD is same as those produced by VMC in

RBDE.

HI: Greater savings are achieved in case of RMBD.

For these tests, each value in Table 8 was compared to the corresponding value in Table 9 for the hypothesis set 3a, and each value in Table 9 was compared to the corresponding value in Table 10 for the hypothesis set 3b. In both cases the null hypotheses were rejected at 0.99 confidence level. This implies that as block diagonality diminishes, VMC can be expected to produce progressively better cost solutions than the other procedures tested.

Since the other heuristics do not consider machine skipping cost, it is expected that VMC will provide better solutions when larger values of this cost are used. This is because penalties for ignoring machine skipping cost increase as this cost increases. This was confirmed at a .99 confidence level.

It was also found that the VMC solution was better than the solution for all the other heuristics for each problem size. Table 11 shows the percent improvement that VMC achieved over the best performing algorithm for each type of problem. The highest improvement achieved was 20.57%, and the worst was -1.07%.

We conclude that VMC can be expected to outperform the other heuristics, as evidenced by 88 of the 90 problem types considered, especially when complete block diagonality does not exist and component mix is diverse.

In addition to the above experiments, we compared the average number of machines per cell formed by the VMC with those of other algorithms. In order to do this we computed the average number of machines per cell for VMC for each level of problem size, skipping cost and component mix. We also computed the average number of machines per cell over all other algorithms for each problem size. These data are shown in Table 12. It can be observed that the VMC solution is sensitive to the level of skipping cost and component mix. As expected, the number of machines per cell decreases as skipping cost increases for VMC solutions. Further, the range of cell sizes obtained at different levels of skipping cost and component mix for VMC are within reasonable limits and contain the average cell sizes for other algorithms. Consequently, the decision makers may apply VMC for an acceptable range of skipping cost values to design cells.

Since the integer programming model developed earlier in this paper cannot be applied for solving large problems, the optimal solutions to these 900 test problems are unknown. Although the VMC has been observed to perform better than other heuristics, its solutions cannot be compared with optimal solutions. In this regard, we attempted to develop a pseudo lower bound to a given problem instance. Recall that all part-incidence matrices for these test problems were generated by randomizing the column and rows of block diagonal parent matrices, and by incorporating exceptions to obtain RBDE and RMBD problems. The pseudo lower bound solution was assumed to be the block diagonal solution (the exceptions were ignored in the case of RBDE and RMBD). The total cost of the block diagonal solution was compared to the cost of the VMC solution. These comparisons appear in Table 13. The lower bound is not a strict bound since there are cases when lower cost solutions can be found. However, it does seem to provide some insights to the performance of VMC - especially in the case of RBDE and RMBD problems. It can be seen from Table 13 that in the case of RBD, VMC provides solutions at least as good as the pseudo lower bound. However, in the case of RBDE and RMBD the VMC solutions are inferior. Further, the performance of VMC with RMBD seems to be inferior to its performance with RBDE. This is probably the result of a bias in the pseudo lower bound since it ignores exceptional operations, and therefore, material handling and skipping costs.

Finally, the VMC was also tested for the problem documented by Burbidge (1989, p. 62) - a commonly referenced problem in this area. The VMC was found to produce better cost solutions compared to those provided by Burbidge for all levels of our experimental settings.

CONCLUSION

In this paper we have developed a computationally simple heuristic for solving the cell design problem with volume and material handling costs. To evaluate the effectiveness of this heuristic for small problems we compared its solutions against optimal solutions obtained from an integer program. In all these 180 randomly generated small test problems, the heuristic was found to identify the optimal solutions. For larger problems, the performance of this heuristic has been evaluated by comparing its solutions to those of Rank Order Clustering, Bond Energy, Efficient Clustering and Direct Clustering algorithms on 900 randomly generated test problems. These problems were generated using three types of part-machine incidence matrices. These are:

a) Randomized Block Diagonal

b) Randomized Block Diagonal with Exception

c) Randomized Minimal Block Diagonal.

It was found that as the block diagonal nature of the part-machine incidence matrix deteriorated, the proposed heuristic's solutions produced better results as compared to the other procedures. In a typical GT application an average of 74% of operations on a part are performed within a single cell (Wemmerlov and Hyer (1989)). This implies that in practice, complete block diagonality does not always exist. In these cases, the proposed heuristic may be useful.

ACKNOWLEDGMENTS

This research was partially funded by the Information Systems and Operations Management Department's Academic Challenge Grant at the University of Toledo. We would also like to acknowledge three anonymous reviewers whose constructive comments enhanced the quality of this paper.

REFERENCES

Askin R.G., and K.S. Chiu. "A Graph Partitioning Procedure for Machine Assignment and Cell Formation in Group

Technology." International Journal of Production Research, vol. 28, no. 8, August 1990, 1555-1572. Burbidge, J.L. Production Flow Analysis for Planning Group Technology. Oxford: Clarendon Press, 1989. Chan, H.M., and D.A. Milner. "Direct Clustering Algorithm for Group Formation in Cellular Manufacturing." Journal

of Manufacturing Systems, vol. 1, No. 1, 1982, 65-75. Dahel, N.E. An Optimization Framework for the Cellularization of Manufacturing Systems. Unpublished Ph.D.

Dissertation, Illinois Institute of Technology, Chicago, IL, May 1988. Greene, T.J., and R.P Sadowski. "A Review of Cellular Manufacturing Assumptions, Advantages and Design

Techniques." Journal of Operations Management, vol. 4, no. 2, February 1984, 85-97. Hyer, N.L., and U. Wemmerlov. "MRP/GT: A Framework for Production Planning and Control of Cellular

Manufacturing." Decision Sciences, vol. 13, 1982, 681-701. Hyer, N. L. "The Potential of Group Technology for U. S. Manufacturing." Journal of Operations Management, vol. 4,

no. 3, May 1984, 183-202. Kennedy, J.A. "A Review of Some Cluster Analysis Methods." AIIE Transactions, vol. 6, no. 3, 1972, 216-227. Kernigham, B.W, and S. Lin. "An Efficient Heuristic Procedure for Partitioning Graphs." The Bell System Journal,

1970, 291-307. King, J.R. "Machine Component Grouping in Production Flow Analysis." International Journal of Production

Research, vol. 18, no. 2, 1980, 213-232. King, J.R., and V. Nakornchai. "Machine Component Group Formation in Group Technology: Review and Extensions."

International Journal of Production Research, vol. 20, no. 2, 117-133, 1982. Kumar, K.R., and A. Vannelli. "Efficient Algorithms for Grouping Component-processor Families." IBM Research

Report No. RC 10636, IBM T. J. Watson Research Center, New York, 1984. Morris, J. S. Forming Cellular Layout in GT: A Simulation Evaluation of Alternative Approaches. Unpublished doctoral

dissertation, The University of Oklahoma, Norman, OK, 1988. McCormick, W.T., P.J. Schweitzer, and T. White. "Problem Decomposition and Data Recognition by a Clustering

Technique." Operations Research, vol. 20, 1972, 993-1009. Mosier, C., and L. Taube. "The Facets of Group Technology and Their Impacts on implementation - A State-of-the-Art

Survey." Omega, vol. 13, no. 5, September-October 1985, 381-391. Purcheck, G. "Machine-Component Group Formation: An Heuristic Method for Flexible Production Cells and Flexible

Manufacturing Systems." International Journal of Production Research, vol. 23, no. 5, September-october 1985, 911-943. Robinson, D., and L. Duckstein. "Polyhedral Dynamics As a Tool for Machine-Part Group Formation." International

Journal of Production Research, vol. 24, January-February 1986, 81-97. Steudel, J.H., and A. Ballakur. "A Dynamic Programming Based Heuristic for Machine Grouping in Manufacturing Cell

Formation." Computers and Engineering, vol. 12, no. 3, 1987, 215-222. Suresh, N.C., and J.R. Meredith. "Achieving Factory Automation through Group Technology Principles." Journal of

Operations Management, vol. 5, no. 2, February 1985, 151-167. Wemmerlov, U. "Comments on the Direct Clustering Algorithm for Group Formation in Cellular Manufacture."

Journal of Manufacturing Systems, vol. 3, no. 1, 1984, vii-ix. Wemmerlov, U., and N.L. Hyer. "Cellular Manufacturing in the U.S. Industry: A Survey of Users." International

Journal of Production Research, vol. 27, no. 9, September 1989, 1511-1530. Wu, H.L., R. Venugopal, and M. Barash. "Design of a Cellular Manufacturing Systems: A Syntactic Pattern

Recognition Approach." Journal of Manufacturing Systems, vol. 5, no. 2, 1986, 81-87.

APPENDIX

AN RBD PROBLEM WHERE THE BLOCK DIAGONAL

SOLUTION IS NOT THE LOWEST COST SOLUTION

Here we document an instance of a RBD problem where the block diagonal solution is not necessarily the lowest cost solution. The part-machine incidence matrix and other parameters for this problem are shown in Table Al. The block diagonal and VMC solutions to this problem, and related costs appear in Table A2. The block diagonal solution was identified by ROC, BEA, DCA and ECA algorithms. In this case the VMC heuristic has identified a non-block diagonal lower cost solution.

[TABULAR DATA OMMITTED]

One of the major problems in a group technology or cellular manufacturing environment is the formation of part groups and machine cells. Because of the combinatorial nature of the cell formation problem, it is difficult to solve the problem optimally. Most of the procedures related to cell design in cellular manufacturing operate on the part-machine incidence matrix in an attempt to identify block diagonality. If complete block diagonality does not exist, the decision about cell configuration is left to the subjective judgement of the designer. These procedures are also generally based on part routing only, and do not consider part volume and material handling costs.

In this paper we develop an integer programming model, as well as a heuristic to effectively assign machines to cells. In these procedures we consider component volumes, costs related to movement of components between and within cells, and penalty for not using all machines in a cell visited by a component. Since the integer programming formulation becomes large even for small problems, an efficient heuristic is developed to solve larger problems. The heuristic solutions to 180 randomly generated small problems were compared against the optimal solutions obtained by the integer programming model. The heuristic has been found to identify optimal solutions in all 180 cases.

This heuristic is also compared to several well known algorithms on 900 larger test problems. These problems were generated to cover a wide range of environmental situations such as varying levels of block diagonality in the part-machine incidence matrix, and diversity in the component volumes and material handling costs. In 99% of the problems our heuristic generated solutions which are better or as good as the best solution obtained by other algorithms. Further, in situations where complete block diagonality in the part-machine incidence matrix did not exist, our heuristic produced even better results. Since the maximum number of iterations required in our heuristic is the number of machines in the problem, the heuristic is computationally efficient.

INTRODUCTION

Many manufacturing situations involve production of parts requiring similar processing. Cellular manufacturing (CM) techniques attempt to group machines into cells to provide an efficient production process. Recently, CM has received considerable attention among academicians and practitioners interested in improving the productivity of small to medium-sized batch production (Greene and Sadowski (1984), Hyer and Wemmerlov (1982), Mosier and Taube (1985), Suresh and Meredith (1985)). CM offers a number of advantages as compared to traditional manufacturing (e.g., job shops, assembly lines). These include lower inventories and lead times, reduced throughput time, increased flexibility, and easier shop floor control (Hyer (1984)).

Because of the combinatorial nature of the cell formation problem, the computational difficulty grows exponentially with increasing problem size. In the past decade numerous techniques have been developed to solve this problem. Prominent among them are standardized coding and classification schemes, Production Flow Analysis (PFA) by Burbidge (1989), Bond Energy Algorithm (BEA) by McCormick, Schweitzer, and White (1972), Direct Clustering Algorithm (DCA) by Chan and Milner (1982), and Wemmerlov (1984), Rank Order Clustering (ROC) algorithms by King (1980) and King and Nakornchai (1982), and Efficient Clustering Algorithm (ECA) by Morris (1988). Other algorithms used mathematical programming (Dahel (1988), Kumar and Vannelli (1984), Robinson and Duckstein (1986), Steudel and Ballakur (1987), Wu, Venugopal and Barash (1986)), graph theory (Askin and Chiu (1990)), and set theory (Purcheck (1985)).

Most cell design methodologies can be classified into two categories. The first category includes such algorithms as ROC, BEA, DCA. These algorithms generally utilize row and column operations of the zero-to-one part-machine incidence matrix (King and Nakornchai (1982)), sometimes using a surrogate measure of similarity index (Kennedy (1972)) between rows and columns. The objective is to attain block diagonality or near block diagonality as the situation permits. If block diagonality exists in the part-machine incidence matrix, then most of these algorithms have, been found to identify the block diagonal solution (Morris (1988)). If block diagonality does not exist, these algorithms attempt to rearrange the rows and columns of the part-machine incidence matrix to obtain near block diagonal solutions. In the latter situation, the decision about cell configuration is left to the subjective judgement of the designer. The second category of algorithms based on mathematical programming, graph theory, and set theory, become computationally intractable with increasing problem size.

Most of the above mentioned algorithms use only part routing information for cell design decisions, and do not consider any costs. This may be a very simplistic approach because factors such as component volume, intra-cell and inter-cell material handling costs may significantly impact the performance of a cell. Askin and Chiu (1990) used inter-cell material handling cost and developed a graph-theoretic algorithm based on Kernigham and Lin's (1970) heuristic on partitioning a graph. However, their method does not consider intra-cell material handling cost, and the stopping condition for the iterative procedure is imposed exogenously.

In this paper, we develop a computationally simple heuristic to solve the cell design problem. Since our heuristic considers the volume, and material handling costs we name it the volume and material handling cost (VMC) heuristic. The heuristic is based on an iterative procedure which successively combines machines to form cells until no more cost reduction is attainable. The heuristic solutions were first compared to the optimal solutions obtained from a mixed integer programming model for 180 small, randomly generated problems. The heuristic identified the optimal solution in all of these 180 small test problems. Next the heuristic was tested against ROC, DCA, ECA, and BEA algorithms on 900 larger test problems. In 99% of these test problems, solutions generated by the proposed heuristic were at least as good as those obtained by using other algorithms. Further, in situations where block diagonality of the part-machine incidence matrix did not exist, our heuristic produced even better results. It can be inferred from a recent study by Wemmerlov and Hyer (1989) that in most United States industrial applications, complete block diagonality does not exist. Hence, from a practical viewpoint, our heuristic may be useful to managers. Furthermore, the heuristic is computationally simple, because the upper bound on the number of required iterations is limited by the number of machines in the problem.

COST FACTORS INVOLVED IN CELL DESIGN

The primary objective of the cell design problem is to group various operations physically in proximity so that similar components can be processed without much material handling and with minimal setup overhead. The major cost factors which are directly associated with the cell design problem are the following:

1) Inter-cell material handling. This cost is incurred when a product needs to travel from one cell to another. When a cell does not provide all the operations needed by a particular part, it must be transported to another cell. It accrues from two sources. First, the cost of physical transportation to a machine belonging to another cell. Since the marginal cost of transportation per unit distance is minimal, this is not dominant. Second, and more important, is the cost of the coordinating effort. Each shipment between cells involves scheduling of machines and material handlers, delays, additional record keeping and setups. Consequently inter-cell material handling cost is specified on a per unit basis in this paper.

2) Intra-cell material handling. This cost is incurred when a component departs a machine and goes to another machine in the same cell. This cost accrues as a result of the material handling effort in transporting parts between machines in a cell. Usually these machines are located close to one another, so that distance travelled is not large. Consequently, this cost too, is specified on a per unit basis in this paper.

3) Cost for skipping a machine in a cell. This cost accrues when a part does not visit all the machines within a cell. Every time a part skips a machine, some special handling occurs. This can result in the need for additional material handling equipment, larger lot sizes, higher inventories, delays, and lower machine utilization due to scheduling difficulties. Consequently, this cost is specified on a per unit per machine skipped basis.

These costs may be independent of one another since they are driven by different factors. However, total inter-cell material handling cost will reduce, while total intra-cell material handling cost, and total skipping cost will increase as machines are grouped into cells. The objective of cell formation is to minimize the sum of these costs.

Intra-cell and inter-cell material handling costs are functions of engineering design and accounting data, including transfer batch sizes, type of material handling system, distance moved, and size and weight of the components. Intuitively there are interactions among these factors, and it is difficult to determine these costs accurately before solving the specific layout design problem. In this paper we treat the cell design problem independent of the specific layout design problem. In most cases, workable estimates of these cost factors may be obtained from past experience. Further, in the cell design problem the exact costs are not as critical as their relative values.

The skipping cost can be treated as a management parameter which can be associated with desired cell size, and expected machine utilization. In a particular environment, management may wish to conduct sensitivity analysis using different subjective values of skipping cost to obtain alternative solutions. These solutions can then be evaluated against the desired objectives of cell size and machine utilization.

With the above perspective on various costs associated with a CM cell design, we now present an optimization model followed by our heuristic. In these procedures we assume that part operations have already been assigned to machines. Secondly, we assume that only one machine of each type is required.

FORMULATION OF OPTIMIZATION MODEL

The decision variables in this model are [X.sub.jk] which allocates the machines to cells. These allocations are made in a manner that will minimize the total cost consisting of machine skipping, intra-cell, and inter-cell material handling costs. Table 1 presents a list of notations used in this paper. In the following formulation, subscript i refers to parts (1 ,...,[n.sub.p]), subscript j refers to machines (1 ,...,[n.sub.m]), and subscript k refers to cells (1 ,...,[n.sub.m]).

[Mathematical Expression Omitted]

Subject to:

[Mathematical Expression Omitted]

TABLE 1 NOTATIONS [n.sub.m] = number of machines [n.sub.p] = number of parts [n.sub.c] = number of cells A = part-machine incidence matrix where the entry [a.sub.ij] = 1, if part i needs machine j = 0, otherwise [a.sub.i] = inter-cell material handling cost for part i ($/unit) [B.sub.s] = intra-cell material handling cost for part i ($/unit) Q = part quantity vector, where the entry [q.sub.i] is the number of units of part i that need to be processed. [C.sub.k] = the set of machines in cell k [SIZE.sub.k] = number of machines in cell k V = Part-Cell-Volume matrix where the entry [v.sub.ik] represents the quantity of part i to be produced in cell k. R = Pairwise Cost Increase matrix where the entry [r.sub.ek] denotes the net increase in cost if cell e is combined with cell k to form a new cell. = Machine skipping cost ($/unit/machine skipped) [X.sub.jk] = 1, if machine j is assigned to cell k = 0, otherwise [Y.sub.ik] = 1, if part i visits cell k = 0, otherwise [D.sub.ik] = the number of machines needed by part i in cell k [F.sub.i] = number of inter cell movements for part i [G.sub.ijk] = 1, if part i visits cell k and does not need machine j, and machine j is assigned to cell k = 0, otherwise.

Discussion of Formulation

The objective function calls for the minimization of total cost consisting of intra-cell and inter-cell material handling and skipping costs. The constraints in the above formulation ensure that each part and each machine is assigned exactly to one cell and all part movements are accounted for.

The objective function consists of three components. The first component of the objective function (1.1) determines the total intra-cell cost. Here we use two variables, [D.sub.ik] and [Y.sub.ik] . [D.sub.ik] denotes the number of machines that part i requires in cell k and is defined in constraint (2.0). [Y.sub.ik] indicates whether part i visits cell k and is defined in (3.0).

The second component of the objective function (1.2) determines the total inter-cell cost. Here we use a variable [F.sub.i] which denotes the total number of inter-cell movements for part i. It is defined in constraint (4.0), and is the difference between total number of part movements and the number of intra-cell movements less 1.

The third component (1.3) determines the total skipping cost. In this expression we introduce an integer variable [G.sub.ijk] which is defined as:

[G.saub.ijk] = (1-[a.sub.ij])[X.sub.jk] [Y.sub.ik]

[G.sub.ijk] will be 1 if [a.sub.ij] = 0, [X.sub.jk] = 1. and [Y.sub.ik] = 1. Clearly, [G.sub.ijk] will be 1 if machine j is assigned to cell k, and part i must visit cell k (since cell k contains some machines needed by part i) but does not require machine j. The above expression for [G.sub.ijk] is nonlinear and is being linearized using constraints (5.0) and (6.0).

Constraint (7.0) ensures that each machine is assigned to exactly one cell. Constraint (8.0) defines [X.sub.jk] and [Y.sub.ik] as 0-1 integer variables.

This integer program will have nm(np + nm) integer variables and at most (3[n.sub.m.sup.2][n.sub.p] + [n.sub.m][n.sup.p] + [n.sub.m] + [n.sub.p]) constraints depending on the density of the part-machine incidence matrix. For example, the number of constraints implicit in (3.0) would not be [n.sub.m.sup.2] [n.sub.p] since many [a.sub.ij]'s would be zeros. Similarly, in the cases of (5.0) and (6.0) there would be fewer constraints since they will appear only if [a.sub.ij] is zero. The number of cells required, [n.sub.c] is bounded by the value of [n.sub.m] and its optimal value will be determined by the integer program. For example, for a 9 part x 9 machine problem we would have 162 integer variables and at most 2367 constraints. It is apparent that large problems cannot be easily solved using this optimization model. Consequently, an effective heuristic is needed to solve large problems. In the next section we describe the VMC heuristic.

DESCRIPTION OF THE VMC HEURISTIC

The VMC heuristic attempts to form machine cells in a way that total cost consisting of material handling costs and skipping costs is minimized. It starts with an initial solution consisting of [n.sub.m] cells with one machine in each cell. This solution will result in the maximum possible inter-cell material handling cost and minimum amount of intra-cell material handling and machine skipping cost.

VMC is an iterative procedure. In each iteration, two cells are merged in order to extract a cost reduction. As cells are merged, inter-cell material handling costs will decrease, and the intra-cell material handling and machine skipping costs will increase. The heuristic is designed to trade off higher intra-cell movement and skipping costs with lower inter-cell movement cost in order to reach a better solution. Given the starting solution of [n.sub.m] cells, we attempt to identify the pair of cells which, when merged, will result in the greatest reduction in total cost. This pair of cells is then merged to make a new cell. This procedure is repeated until there is no pair of cells which improves the solution. The steps of the heuristic are presented below:

STEP O: [n.sup.c] = [n.sup.m]

[C.sub.k] {k}, k = 1,2,3... ,[n.sup.c] [SIZE.sub.k] = 1, k = 1,2,...,[n.sub.c] [V.sub.ik] = [a.sub.ik] [q.sub.i], i = 1,2,3,...,[n.sub.p], k = 1,2,3,. ..,[n.sub.c] e = 1

STEP 1a: k = e + 1 STEP 1B: Let S be the change in skipping cost when cell k and cell e are combined. Hence,

[Mathematical Expression Omitted] Let H be the change in intra-cell cost and M be the change in inter-cel l cost due to combining cells k and e. Hence, If [V.sub.ik] = 0 or [V.sub.ie] = 0 then H = 0 and M = 0, otherwise, [Mathematical Expression Omitted] Now compute [r.sub.ek], the total increase in cost due to combining cel ls e and k. [r.sub.ek] = S + H - M k = k + 1, if k > [n.sub.c], then go to Step 2, otherwise go to Step 1b .

STEP 2: e = e + 1, if e = [n.sub.c], then go to Step 3, otherwise go to Step 1a. STEP 3: [r.sub.xy] = Min [[r.sub.ab.]], a = 1,2,3,...,[n.sub.c]-1; b = a + 1,a + 2,...,[n.sub.c]; STEP 4: [SIZE.sub.x] = [SIZE.sub.x] + [SIZE.sub.u]; [C.sub.x] = [C.sub.x] U [C.sub.y]

[V.sub.ix] = [V.sub.ix] U [V.sub.iy], i = 1,2,...,[n.sub.p] [SIZE.sub.q] = [SIZE.sub.q + 1], [C.sub.q] = [C.sub.q + 1], [V.sub.iq] = [V.sub.iq + 1], q = y + 1,y + 2,...,[n.sub.c]-1 [n.sub.c] = [n.sub.c] - 1, e = 1, k = x, go to Step 5.

STEP 5: [Mathematical Expression Omitted]

If [V.sub.ik] = 0 or vie = 0 then H = 0 and m = 0, [Mathematical Expression Omitted] [r.sub.ek] = S + H - M e = e + 1, if e = k, then go to Step 6, otherwise for to Step 5.

STEP 6: k = k + 1

[Mathematical Expression Omitted] If [V.sub.ik] = 0 or [V.sub.ie] = 0 then H = 0 and M = 0, otherwise [Mathematical Expression Omitted] [r.sub.ek] = S + H - M if k = [n.sub.c], then go to Step 3, otherwise go to Step 6.

STEP 7: Stop.

Since the number of cells decreases by 1 in each iteration, VMC will converge and the maximum number of iterations needed for convergence would be bounded by [n.sub.m]. Each of these iterations contains at most [n.sub.m.sup.2] sub-iterations each consisting of [n.sub.p] computations. Consequently, the computational complexity of this heuristic is O(n.sub.m.sup.3][n.sup.p]. The pairwise cost increase matrix R is similar to the similarity matrix used by a number of researchers. Each entry [r.sub.ij] in this matrix may be considered as the bond between partition i and partition j. However, in the case of VMC, the affinities are expressed directly in terms of cost savings (which was not the case in most previous work).

PERFORMANCE OF VMC HEURISTIC COMPARED TO OPTIMAL SOLUTIONS

In order to evaluate the performance of this heuristic against the optimal solution, we randomly generated 180 small (9 part 9 machine) test problems emulating the experimental conditions employed in this research (discussed later). The Integer Program (IP) was solved by using LINDO. Due to the limits imposed by the software and in order to avoid excessive computational time, the integer program was formulated by limiting the maximum number of cells allowed to 5.

In all 180 test problems, the heuristic solutions were at least as good as the IP solutions. In five cases however, the heuristic solutions were found to be superior. Analysis of these cases revealed that the heuristic formed more than five cells, whereas the IP formulation being restricted to a maximum of five cells could not find lower cost solutions.

AN EXAMPLE

To illustrate the heuristic let us consider an example with 24 parts and 20 machines. The incidence matrix, volume of parts to be processed, and inter-cell and intra-cell material handling costs for each part are shown in Table 2. The incidence matrix is obtained from Morris (1988). In this example the incidence matrix can be characterized as randomized block diagonal with exception (discussed in the next section.) The volumes and inter-cell material handling costs have been randomly generated from U(10,590), and U(.50,11.50), respectively. Intra-cell handling cost is assumed to be 10% of inter-cell handling cost. Machine skipping cost is assumed to be 1.0/unit/machine skipped.

[TABULAR DATA OMITTED]

We start with 20 cells, one machine in each cell. The V matrix representing the volume of each part being processed through these cells is constructed. Now we construct the symmetric Marginal Cost Increase matrix R. The matrix is shown in Table 3. A negative entry in this matrix, say [r.sub.4,14] signifies that combining cell 4 and cell 14 to form a new cell will lower total operating cost by 7837. We combine cell 4 and cell 14 into one cell since this produces the highest savings and construct the new V matrix (shown in Table 4.) Computationally, it is simple to reconstruct the V matrix. We replace column 4 with the union of current column 4 and column 14. Then the original column 14 is deleted.

[TABULAR DATA OMITTED]

The heuristic required 16 such iterations to converge. The pairwise cost increase matrix in iteration 15 and 16, as well as the cell contents are shown in Table 5 and Table 6. As can be observed in Table 6, the heuristic solution is:

Cell 1: (1 13 15 19 10)

Cell 2: (2 8 16 5 12)

Cell 3: (3 11 9 6 17 20)

Cell 4: (4 14 18 7)

For this configuration the costs are computed as:

Total intra-cell handling cost = 9943

Total inter-cell handling cost = 7902

Total machine skipping cost = 18630 Total cost = 36475

[TABULAR DATA OMITTED]

Morris has documented the ROC, DCA, BEA and ECA solutions for this incidence matrix. The VMC solution as shown above is same as those of ROC, ECA, and BEA. The DCA solution is different and more costly for this volume and cost configuration. It needs to be mentioned here that the solutions for the other algorithms were obtained by Morris without the knowledge of cost and volume parameters.

GENERATION OF TEST PROBLEMS

In order to test the performance of VMC, 900 test problems were generated. To generate these test problems we considered the following factors:

Characteristics of the Part-Machine Incidence Matrix

Conventional cell design algorithms have often been tested with the criteria of their abilities to permute the rows and columns of a part incidence matrix to a complete or nearly complete block diagonal matrix. Morris (1988) has shown that most of these algorithms are able to identify complete block diagonality given that it exists. However, the algorithms have been shown to perform differently in cases where complete block diagonality does not exist. In order to test various heuristics for different types of part-machine incidence matrices, Morris constructed incidence matrices of three types:

1) Randomized Block Diagonal (RBD). These part-machine incidence matrices were constructed by randomly rearranging the rows and columns of complete block diagonal matrices.

2) Randomized Block Diagonal with Exception (RBDE). These part-machine incidence matrices were constructed by randomly rearranging the rows and columns of matrices where 10% of the parts required routing to two or more cells.

3) Randomized Minimal Block Diagonal (RMBD). These part-machine incidence matrices were constructed by randomly rearranging the rows and columns of matrices where 20% of the parts required routing to two or more cells.

In this paper we have used the same part incidence matrices developed by Morris (1988).

Component Mix Characteristics

VMC is expected to be sensitive to the composition of the components in volume and material handling costs. We characterize the component mix as follows:

1) Homogeneous, where the volumes and material handling costs of all components are similar. In these experiments, the volume of individual parts and material handling costs are chosen from U(200,400) and U(5,7), respectively.

2) Diverse, where the volumes and material handling costs of the components vary significantly. In these experiments the parameters used are U(10,590) and U(.5,11.5), respectively

Size of the Part-Machine Incidence Matrix

Five sizes of part-machine incidence matrices were used in these experiments. These combined with the three types of part-machine incidence matrices discussed above, resulted in fifteen matrices. The problem sizes are 24x20, 40x25, 40x30, 40x35, 70x25. Other relevant parameters, such as matrix densities, minimum and maximum number of machines per cell in the matrices before randomization appear in Table 7.

TABLE 7 PARAMETERS USED TO GENERATE INCIDENCE MATRICES(*) Problem Size Parameter 24x20 40x25 40x30 45x35 70x25 Matrix Density (%) 15 14 12 11 13 Min. # of Machines per Cell 4 4 4 4 4 Max. # of Machines per Cell 6 9 8 14 9 (*) Using the block diagonal pattern in each problem size.

Machine Skipping Cost

Another factor of significant interest in our experiment is the machine skipping cost. High level of skipping cost will tend to group the machines into many small but compact cells. We assume that the specific level of skipping cost is directed by the environment itself. However, in order to study the behavior of our heuristic, we solved each problem at three levels of skipping cost. The levels are .05, 1.0, and 1.50.

For each of the fifteen matrices, we then have two levels of component mix and three levels of skipping cost. This results in 90 problem types. Each problem type is replicated ten times by randomly generating volume and material handling costs from their respective distributions. This results in 900 problem instances.

RESULTS AND DISCUSSION

Algorithms like ROC, BEA, DCA, and ECA do not consider the volume of parts and associated material handling cost factors. In this context a comparison of VMC with these algorithms may not be completely justified. However, the procedures to incorporate cost and volume information to these algorithms for improving the solutions are not clearly known. It is our intention to identify situations where there may be benefits in using procedures that explicitly utilize volume and material handling cost information.

The 900 problem instances were solved using VMC. The costs of these solutions were computed and averaged over the ten replications to obtain the average cost for each problem type.

Morris (1988) presented the cell configurations for the 15 part-machine incidence matrices using ROC, BEA, DCA, and ECA procedures. Recall that these procedures do not use volume and material handling cost information to identify cells. When block diagonality exists, these procedures provide unambiguous solutions. However, under RBDE and RMBD this does not happen. Morris developed a policy for cell formation based upon a trade-off between the number of cells and the number of parts travelling between cells (exceptions). The policy used was to form a cell consisting of at least two parts and two machines. These cells were formed such that the number of parts visiting more than one cell is less than 10% for RBDE problems and less than 20% for RMBD problems. The average total cost for Morris' solutions were obtained by applying the 10 replications of material handling cost and volume at each level of component mix and machine skipping cost.

Tables 8, 9 and 10 present the average total cost achieved by ROC, BEA, DCA, and ECA expressed as a percent of the corresponding VMC solutions. Twelve protected t-tests were conducted on the data in Tables 8 to 10. In each case the 30 values for each heuristic were averaged to test the following hypotheses.

TABLE 8 COMPARISON OF TOTAL COST EXPRESSED AS A PERCENTAGE OF VMC COST FOR ALL ALGORITHMS BY PROBLEM TYPE: RBD INCIDENCE MATRIX(*) Prob. Component Skip Cost Algorithms Size Mix ROC DCA BEA ECA Homogeneous .05 100 100 100 100 1.00 100 100 100 100 1.50 100 100 100 100 24x20 .05 100 100 100 100 Diverse 1.00 101 101 101 101 1.50 102 102 102 102 Homogeneous .05 100 100 100 100 1.00 100 100 100 100 1.50 100 100 100 100 40x25 Diverse .05 100 100 100 100 1.00 101 101 101 101 1.50 103 103 103 103 Homogeneous .05 100 100 100 100 1.00 100 100 100 100 1.50 99 99 99 99 40x30 .05 100 100 100 100 Diverse 1.00 102 102 102 102 1.50 103 103 103 103 Homogeneous .05 100 100 100 100 1.00 100 100 100 100 1.50 103 103 103 103 45x35 Diverse .05 100 100 100 100 1.00 103 103 103 103 1.50 108 108 108 108 Homogeneous .05 100 100 100 100 1.00 100 100 100 100 1.50 101 101 101 101 70x25 .05 100 100 100 100 Diverse 1.00 101 101 101 101 1.50 102 102 102 102 (*) Percent of Cost = Average Total Cost of Algorithm/Average Total Cost of VMC Solution x 100 TABLE 9 COMPARISON OF TOTAL COST EXPRESSED AS A PERCENTAGE OF VMC COST FOR ALL ALGORITHMS BY PROBLEM TYPE: RBDE INCIDENCE MATRIX(*) Prob. Component Skip Cost Algorithms Size Mix ROC DCA BEA ECA Homogeneous .05 110 116 110 110 1.00 100 155 100 100 1.50 100 163 100 100 24x20 .05 120 128 120 120 Diverse 1.00 103 160 103 103 1.50 108 177 108 108 Homogeneous .05 137 100 152 106 1.00 124 181 110 100 1.50 124 196 106 101 40x25 Diverse .05 140 101 156 111 1.00 125 182 111 102 1.50 129 203 110 105 Homogeneous .05 106 112 132 100 1.00 241 350 104 139 1.50 270 400 101 149 40x30 .05 108 116 137 101 Diverse 1.00 249 361 107 144 1.50 287 423 107 159 Homogeneous .05 106 101 101 101 1.00 113 171 110 110 1.50 120 189 117 117 45x35 Diverse .05 110 103 104 104 1.00 117 174 113 113 1.50 128 199 124 124 Homogeneous .05 106 103 106 106 1.00 100 267 100 100 1.50 102 300 102 102 70x25 .05 108 106 108 108 Diverse 1.00 102 273 102 102 1.50 105 309 105 105 (*) Percent of Cost = Averacre Total Cost of Alciorithm/Average Total Cost of VMC Solution x 100 TABLE 10 COMPARISON OF TOTAL COST EXPRESSED AS A PERCENTAGE OF VMC COST FOR ALL ALGORITHMS BY PROBLEM TYPE: RMBD INCIDENCE MATRIX(*) Prob. Component Skip Cost Algorithms Size Mix ROC DCA BEA ECA Homogeneous .05 141 100 160 115 1.00 160 197 113 129 1.50 174 225 115 141 24x20 .05 137 100 161 121 Diverse 1.00 167 208 119 137 1.50 191 247 126 155 Homogeneous .05 129 100 166 124 1.00 107 217 106 100 1.50 110 247 105 104 40x25 Diverse .05 129 101 167 126 1.00 109 229 109 103 1.50 113 262 109 107 Homogeneous .05 101 101 151 101 1.00 277 277 101 277 1.50 335 335 103 335 40x30 .05 105 105 156 105 Diverse 1.00 289 289 105 289 1.50 355 355 109 355 Homogeneous .05 115 106 155 115 1.00 112 258 113 113 1.50 123 307 119 125 45x35 Diverse .05 120 107 163 118 1.00 118 267 118 118 1.50 132 322 127 132 Homogeneous .05 128 100 162 128 1.00 102 221 130 102 1.50 107 258 137 107 70x25 .05 125 100 156 125 Diverse 1.00 104 230 131 104 1.50 109 267 138 109 (*) Percent of Cost = Averacte Total Cost of Algorithm/Average Total Cost of VMC Solution x 100

Hypothesis Set I

HO: The performance of VMC is the same as the performance of the other heuristics. ([mu] =

100)

HI: The performance of VMC is better ([mu] > 100).

It was found that the VMC performs significantly better than all other heuristics for each type of part-machine incidence matrix at .9999 confidence level. It may have been expected that VMC solutions for RBD part machine incidence matrices would be identical to those found by the other procedures. While the other procedures did find the block diagonal solutions to these RBD problems, VMC often found an alternative non-block diagonal lower cost solutions. An example of such an occurrence is illustrated in the Appendix.

Furthermore, it is expected that when the component mix is diverse, VMC should produce greater savings. The following hypotheses were tested for each type of part-machine incidence matrix by comparing the values in Tables 8- 1 0 for the diverse and homogeneous cases for each problem size and skipping cost.

Hypothesis Set 2

HO: Diversity of component mix does not effect savings achieved by using VMC.

HI: Greater savings will be achieved by VMC in diverse component mix situations.

For each type of part-machine incidence matrix, the null hypotheses were rejected at a .99 confidence level.

To explore the effect of block diagonality of the part-machine incidence matrix, the following hypotheses were tested:

Hypothesis Set 3a

HO: The savings produced by VMC in RBDE is same as those produced by VMC in RBD.

HI: Greater savings are achieved in case of RBDE.

Hypothesis Set 3b

HO: The savings produced by VMC in RMBD is same as those produced by VMC in

RBDE.

HI: Greater savings are achieved in case of RMBD.

For these tests, each value in Table 8 was compared to the corresponding value in Table 9 for the hypothesis set 3a, and each value in Table 9 was compared to the corresponding value in Table 10 for the hypothesis set 3b. In both cases the null hypotheses were rejected at 0.99 confidence level. This implies that as block diagonality diminishes, VMC can be expected to produce progressively better cost solutions than the other procedures tested.

Since the other heuristics do not consider machine skipping cost, it is expected that VMC will provide better solutions when larger values of this cost are used. This is because penalties for ignoring machine skipping cost increase as this cost increases. This was confirmed at a .99 confidence level.

It was also found that the VMC solution was better than the solution for all the other heuristics for each problem size. Table 11 shows the percent improvement that VMC achieved over the best performing algorithm for each type of problem. The highest improvement achieved was 20.57%, and the worst was -1.07%.

TABLE 11 PERCENTAGE IMPROVEMENT IN TOTAL COST BY VMC HEURISTIC OVER THE BEST OF OTHER ALGORITHMS(*) Prob. Component Skip Cost Part-machine Incidence Matrix Size Mix RBD RBDE MBD Homogeneous .05 0.00 8.82 0.00 1.00 0.00 0.00 11.75 1.50 0.00 -0.42 13.21 24x20 .05 0.00 16.30 0.00 Diverse 1.00 0.59 2.93 15.11 1.50 1.99 6.70 19.88 Homogeneous .05 0.00 0.00 0.00 1.00 0.01 0.12 0.30 1.50 0.40 1.06 3.58 40x25 0.05 0.00 0.99 0.71 Diverse 1.00 1.35 1.83 2.62 1.50 2.52 5.04 6.04 Homogeneous 0.05 0.00 0.00 1.22 1.00 0.00 3.62 0.97 1.50 -1.07 0.91 2.55 40x30 .05 0.00 0.78 4.54 Diverse 1.00 1.49 6.72 4.74 1.50 2.49 6.62 7.87 Homogeneous 0.05 0.00 0.07 5.43 1.00 0.05 8.91 10.39 1.50 2.47 14.43 15.92 45x35 0.05 0.00 1.02 6.58 Diverse 1.00 2.84 11.20 13.24 1.50 7.06 18.89 20.57 Homogeneous 0.05 0.00 2.85 0.00 1.00 0.05 0.12 1.94 1.50 0.83 1.72 6.29 70x25 .05 0.00 4.39 0.27 Diverse 1.00 0.87 1.48 3.81 1.50 1.78 4.29 8.23 (*) % improvement = (Cost of best solution of others - VMC Cost) /Cost of best solution of others x 100

We conclude that VMC can be expected to outperform the other heuristics, as evidenced by 88 of the 90 problem types considered, especially when complete block diagonality does not exist and component mix is diverse.

In addition to the above experiments, we compared the average number of machines per cell formed by the VMC with those of other algorithms. In order to do this we computed the average number of machines per cell for VMC for each level of problem size, skipping cost and component mix. We also computed the average number of machines per cell over all other algorithms for each problem size. These data are shown in Table 12. It can be observed that the VMC solution is sensitive to the level of skipping cost and component mix. As expected, the number of machines per cell decreases as skipping cost increases for VMC solutions. Further, the range of cell sizes obtained at different levels of skipping cost and component mix for VMC are within reasonable limits and contain the average cell sizes for other algorithms. Consequently, the decision makers may apply VMC for an acceptable range of skipping cost values to design cells.

TABLE 12 AVERAGE CELL SIZE FOR VMC AND OTHER ALGORITHM'S SOLUTIONS Prob. Component Skip Cost Algorithms Size Mix VMC OTHER Homogeneous .05 10.0 1.00 5.0 1.50 3.7 24x20 5.6 0.05 9.0 Diverse 1.00 4.1 1.50 3.0 Homogeneous .05 9.9 1.00 5.7 1.50 4.3 40x25 6.7 0.05 8.5 Diverse 1.00 5.1 1.50 3.8 Homogeneous 0.05 8.7 1.00 5.7 1.50 4.7 40x30 8.6 .05 8.6 Diverse 1.00 4.9 1.50 4.1 Homogeneous .05 11.5 1.00 6.1 1.50 4.3 45x35 9.1 0.05 11.0 Diverse 1.00 4.6 1.50 3.4 Homogeneous 0.05 9.0 1.00 5.4 1.50 4.2 70x25 6.82 0.05 8.9 Diverse 1.00 4.8 1.50 4.1

Since the integer programming model developed earlier in this paper cannot be applied for solving large problems, the optimal solutions to these 900 test problems are unknown. Although the VMC has been observed to perform better than other heuristics, its solutions cannot be compared with optimal solutions. In this regard, we attempted to develop a pseudo lower bound to a given problem instance. Recall that all part-incidence matrices for these test problems were generated by randomizing the column and rows of block diagonal parent matrices, and by incorporating exceptions to obtain RBDE and RMBD problems. The pseudo lower bound solution was assumed to be the block diagonal solution (the exceptions were ignored in the case of RBDE and RMBD). The total cost of the block diagonal solution was compared to the cost of the VMC solution. These comparisons appear in Table 13. The lower bound is not a strict bound since there are cases when lower cost solutions can be found. However, it does seem to provide some insights to the performance of VMC - especially in the case of RBDE and RMBD problems. It can be seen from Table 13 that in the case of RBD, VMC provides solutions at least as good as the pseudo lower bound. However, in the case of RBDE and RMBD the VMC solutions are inferior. Further, the performance of VMC with RMBD seems to be inferior to its performance with RBDE. This is probably the result of a bias in the pseudo lower bound since it ignores exceptional operations, and therefore, material handling and skipping costs.

TABLE 13 COMPARISON OF VMC SOLUTIONS AGAINST PSEUDO-LOWER BOUNDS BASED ON BLOCK DIAGONAL SOLUTIONS' Prob. Component Skip Cost Part-Machine Incidence Matrix Size Mix RBD RBDE MBD Homogeneous .05 100 131 138 1.00 100 131 170 1.50 100 129 163 24x20 0.05 100 128 140 Diverse 1.00 99 133 166 1.50 97 125 153 Homogeneous .05 100 128 138 1.00 100 125 148 1.50 100 122 140 40x25 0.05 100 128 138 Diverse 1.00 99 125 144 1.50 97 119 136 Homogeneous 0.05 100 128 145 1.00 100 129 163 1.50 101 127 151 40x30 0.05 100 124 140 Diverse 1.00 99 125 156 1.50 98 120 142 Homogeneous .05 100 129 145 1.00 100 115 136 1.50 98 107 122 45x35 0.05 100 127 143 Diverse 1.00 97 113 131 1.50 93 103 116 Homogeneous 0.05 100 132 139 1.00 100 132 159 7Ox25 1.50 99 129 149 .05 100 129 140 Diverse 1.00 99 130 153 1.50 98 125 144 (*) Performance ratio = Cost of VMC Solution/Cost of block diagonal matrix solution x 100

Finally, the VMC was also tested for the problem documented by Burbidge (1989, p. 62) - a commonly referenced problem in this area. The VMC was found to produce better cost solutions compared to those provided by Burbidge for all levels of our experimental settings.

CONCLUSION

In this paper we have developed a computationally simple heuristic for solving the cell design problem with volume and material handling costs. To evaluate the effectiveness of this heuristic for small problems we compared its solutions against optimal solutions obtained from an integer program. In all these 180 randomly generated small test problems, the heuristic was found to identify the optimal solutions. For larger problems, the performance of this heuristic has been evaluated by comparing its solutions to those of Rank Order Clustering, Bond Energy, Efficient Clustering and Direct Clustering algorithms on 900 randomly generated test problems. These problems were generated using three types of part-machine incidence matrices. These are:

a) Randomized Block Diagonal

b) Randomized Block Diagonal with Exception

c) Randomized Minimal Block Diagonal.

It was found that as the block diagonal nature of the part-machine incidence matrix deteriorated, the proposed heuristic's solutions produced better results as compared to the other procedures. In a typical GT application an average of 74% of operations on a part are performed within a single cell (Wemmerlov and Hyer (1989)). This implies that in practice, complete block diagonality does not always exist. In these cases, the proposed heuristic may be useful.

ACKNOWLEDGMENTS

This research was partially funded by the Information Systems and Operations Management Department's Academic Challenge Grant at the University of Toledo. We would also like to acknowledge three anonymous reviewers whose constructive comments enhanced the quality of this paper.

REFERENCES

Askin R.G., and K.S. Chiu. "A Graph Partitioning Procedure for Machine Assignment and Cell Formation in Group

Technology." International Journal of Production Research, vol. 28, no. 8, August 1990, 1555-1572. Burbidge, J.L. Production Flow Analysis for Planning Group Technology. Oxford: Clarendon Press, 1989. Chan, H.M., and D.A. Milner. "Direct Clustering Algorithm for Group Formation in Cellular Manufacturing." Journal

of Manufacturing Systems, vol. 1, No. 1, 1982, 65-75. Dahel, N.E. An Optimization Framework for the Cellularization of Manufacturing Systems. Unpublished Ph.D.

Dissertation, Illinois Institute of Technology, Chicago, IL, May 1988. Greene, T.J., and R.P Sadowski. "A Review of Cellular Manufacturing Assumptions, Advantages and Design

Techniques." Journal of Operations Management, vol. 4, no. 2, February 1984, 85-97. Hyer, N.L., and U. Wemmerlov. "MRP/GT: A Framework for Production Planning and Control of Cellular

Manufacturing." Decision Sciences, vol. 13, 1982, 681-701. Hyer, N. L. "The Potential of Group Technology for U. S. Manufacturing." Journal of Operations Management, vol. 4,

no. 3, May 1984, 183-202. Kennedy, J.A. "A Review of Some Cluster Analysis Methods." AIIE Transactions, vol. 6, no. 3, 1972, 216-227. Kernigham, B.W, and S. Lin. "An Efficient Heuristic Procedure for Partitioning Graphs." The Bell System Journal,

1970, 291-307. King, J.R. "Machine Component Grouping in Production Flow Analysis." International Journal of Production

Research, vol. 18, no. 2, 1980, 213-232. King, J.R., and V. Nakornchai. "Machine Component Group Formation in Group Technology: Review and Extensions."

International Journal of Production Research, vol. 20, no. 2, 117-133, 1982. Kumar, K.R., and A. Vannelli. "Efficient Algorithms for Grouping Component-processor Families." IBM Research

Report No. RC 10636, IBM T. J. Watson Research Center, New York, 1984. Morris, J. S. Forming Cellular Layout in GT: A Simulation Evaluation of Alternative Approaches. Unpublished doctoral

dissertation, The University of Oklahoma, Norman, OK, 1988. McCormick, W.T., P.J. Schweitzer, and T. White. "Problem Decomposition and Data Recognition by a Clustering

Technique." Operations Research, vol. 20, 1972, 993-1009. Mosier, C., and L. Taube. "The Facets of Group Technology and Their Impacts on implementation - A State-of-the-Art

Survey." Omega, vol. 13, no. 5, September-October 1985, 381-391. Purcheck, G. "Machine-Component Group Formation: An Heuristic Method for Flexible Production Cells and Flexible

Manufacturing Systems." International Journal of Production Research, vol. 23, no. 5, September-october 1985, 911-943. Robinson, D., and L. Duckstein. "Polyhedral Dynamics As a Tool for Machine-Part Group Formation." International

Journal of Production Research, vol. 24, January-February 1986, 81-97. Steudel, J.H., and A. Ballakur. "A Dynamic Programming Based Heuristic for Machine Grouping in Manufacturing Cell

Formation." Computers and Engineering, vol. 12, no. 3, 1987, 215-222. Suresh, N.C., and J.R. Meredith. "Achieving Factory Automation through Group Technology Principles." Journal of

Operations Management, vol. 5, no. 2, February 1985, 151-167. Wemmerlov, U. "Comments on the Direct Clustering Algorithm for Group Formation in Cellular Manufacture."

Journal of Manufacturing Systems, vol. 3, no. 1, 1984, vii-ix. Wemmerlov, U., and N.L. Hyer. "Cellular Manufacturing in the U.S. Industry: A Survey of Users." International

Journal of Production Research, vol. 27, no. 9, September 1989, 1511-1530. Wu, H.L., R. Venugopal, and M. Barash. "Design of a Cellular Manufacturing Systems: A Syntactic Pattern

Recognition Approach." Journal of Manufacturing Systems, vol. 5, no. 2, 1986, 81-87.

APPENDIX

AN RBD PROBLEM WHERE THE BLOCK DIAGONAL

SOLUTION IS NOT THE LOWEST COST SOLUTION

Here we document an instance of a RBD problem where the block diagonal solution is not necessarily the lowest cost solution. The part-machine incidence matrix and other parameters for this problem are shown in Table Al. The block diagonal and VMC solutions to this problem, and related costs appear in Table A2. The block diagonal solution was identified by ROC, BEA, DCA and ECA algorithms. In this case the VMC heuristic has identified a non-block diagonal lower cost solution.

[TABULAR DATA OMMITTED]

TABLE A2 BLOCK DIAGONAL AND VMC SOLUTIONS TO THE PROBLEM PRESENTED IN TABLE Al BLOCK DIAGONAL SOLUTION VMC SOLUTION CELL NO. MACKINES MACHINES 1 8 2 16 12 5 8 2 16 12 5 2 20 6 17 3 11 9 20 6 17 3 11 9 3 18 14 7 4 18 14 7 4 4 13 19 1 10 15 13 19 1 15 5 10 Inter-Cell Cost: 0 706 Intra-Cell Cost: 6543 6472 Skipping Cost: 14004 12578 Total Cost: 20547 19756 (**) Skipping cost was assumed to be $1.00/machine/unit.

Printer friendly Cite/link Email Feedback | |

Author: | Ahmed, Mesbah U.; Ahmed, Nazim U.; Nandkeolyar, Udayan |
---|---|

Publication: | Journal of Operations Management |

Date: | Oct 1, 1991 |

Words: | 7911 |

Previous Article: | Measurement of manufacturing flexibility: a value based approach. |

Next Article: | Load smoothing by the planning and order review/release systems: a simulation experiment. |

Topics: |