# A goal programming approach to the cell formation problem.

INTRODUCTION

Cellular manufacturing (CM) is the application of group technology (GT) principles to production. Specifically, the objective of CM is to achieve efficiencies in production by exploiting similarities inherent in the production of parts. Thus, firms adopting CM seek to obtain many of the efficiencies associated with mass production in less repetitive batch environments. To achieve these benefits, groups of functionally dissimilar machines are located in close proximity to one another and are dedicated to the production of a set of parts with similar processing requirements. These groups of machines are referred to as machine cells, or simply cells, and the sets of parts with similar processing requirements are referred to as part families.

There has been a large amount of research conducted recently in the area of CM (for example, see Wemmerlov and Hyer (1986), where over 70 contributions to the literature are classified). As Vakharia (1986) noted, however, the focus of this research has been on the development of techniques to identify part families and/or machine cells, i.e., cell formation procedures, and little research has been for investigating the appropriateness of these techniques. This problem is further compounded because many of the techniques developed to date do not accurately capture many of the realities of the cell formation problem. For example, many of these procedures employ surrogate measures of the objectives that were easily measurable rather than direct measures of the objectives associated with the adoption of CM. To illustrate, many cell formation procedures are based on the assumption that parts that require the same set of equipment have similar processing requirements. Hence, these procedures are for identifying part families based on similarities in the set of machines the parts require in their processing. It is suggested here that a more direct approach for identifying part families is to group parts together based on similarities in setups and tooling. Thus, a primary objective of this paper is to develop a cell formation procedure that accurately and realistically addresses more facets of the cell formation problem.

To achieve this goal, the objectives for adopting a cellular layout must first be defined. A distinction is often made between design objectives and performance objectives. Design objectives are used to guide the cell formation process, while performance objectives are associated with expected benefits. Throughout this paper the term objective is used to refer to design objectives. It is worth noting, however, that a given objective may be both a design and performance objective. For example, reductions in setup times can be used to guide the cell formation process. In addition, reduced setup times can be considered a benefit of CM.

In the next section several design objectives of CM are discussed. Then relevant prior research is briefly reviewed. Three goal programming models that realistically capture the cell formation problem are then presented. Subsequently, an approach for solving the goal programs is discussed. Finally, the paper ends with conclusions and a discussion of areas for future research.

OBJECTIVES OF CELLULAR MANUFACTURING

Before procedures can be developed for appropriately addressing the cell formation problem, the objectives for adopting CM must be clearly defined. Table 1 is a summary of several of the objectives associated with CM classified into four major categories. Many of the objectives associated with adopting a cellular layout are situation dependent and therefore the list in Table 1 is generic and is not intended to be exhaustive.

The first major objective listed in Table 1 is to reduce setup times. It is worth noting that setup reductions in this paper refer to reducing the time spent on setups as opposed to reducing the time per setup. In other words, setup reductions for our purposes refer to reductions accomplished by sequencing and not reductions due to improving the change-over process.

There are numerous benefits associated with reducing setup times. For example, reducing setup times effectively increases the productive capacity of the plant because more time is available to engage in productive operations. also, reductions in setup times permit reductions in lot sizes and the adoption of just-in-time. Further, smaller lot sizes result in shorter lead times and reduced work-in-process inventory levels. More accurate forecasts and even competitive advantages can result from shorter lead times. Similarly, opportunities to improve the production process and improve the quality level often result from reductions in work-in-process inventory.

[TABULAR DATA OMITTED]

A second common objective of CM is to produce parts within a single cell. Achieving this significantly simplifies shop floor control. Further, the potential to increase the accountability, responsibility, and autonomy of the workers is enhanced. For example, workers in a cell can be held accountable for product quality when the product is produced cell complete. This is in contrast to the functional layout where parts are processed in many different departments and where workers in ne department can blame workers in other departments for poor quality. Also, lead times can be reduced by overlapping operations, i.e., sending parts ahead to the next operation before all parts in the batch are completed at the current machine, because all necessary equipment is located together in close proximity when parts are produced cell complete.

Finally, two additional general objectives associated with CM are to minimize the investment in new equipment and to maintain acceptable utilization levels. Caution should be exercised to avoid overly emphasizing the machine utilization objective. For example, Shafer and Meredith (1990) argued that shop performance is improved when lead times and work-in-process inventory levels are reduced regardless of the level of machine utilization. In fact, emphasis upon machine utilization may very often be in direct conflict with one of the most basic objectives of a firm-making a profit (Goldratt and Cox (1986)).

OVERVIEW OF MATHEMATICAL PROGRAMMING APPROACHES

TO CELL FORMATION

Before presenting the new goal programming formulations, the mathematical programming formulations that have been developed to date will be overviewed. Kusiak (1987), employed the p-median O/1 integer programming formulation to identify part families. The p-median approach involved initially selecting p of the parts to serve as medians or seeds for the clusters. Subsequently, the remaining parts were assigned to the seed parts such that the sum of part similarly in each part family was maximized. Part similarly between two parts was defined as the number of machines the two parts had in common in their processing. A significant contribution of this approach was that it was one of the first procedures developed to process a similarity matrix using mathematical programming as opposed to hierarchical cluster analysis. Also, the author illustrated how the formulation could be extended to consider situations for which alternate part routings existed. A major limitation of this approach was that only part families were identified and that a second ancillary procedure was needed to identify machine cells.

Choobineh (1988) developed a 0/1 integer programming formulation for which the cost of producing a part in each cell and the cost of purchasing new equipment was minimized. A major contribution of this formation was that the funds available for the purchase of new equipment was considered. Also, the formulation contained constraints to ensure that the capacity of each machine in each cell was not exceeded. A major limitation of the formulation was that some of the coefficients in the model were not known until after the problem was solved. For example, [C.sub.fk] was a coefficient in the objective function and was defined as the cost of producing part f in cell k. Clearly, this parameter will depend on the solution found, i.e., the type of equipment assigned to each cell and how the parts were assigned to the cell.

Co and Araar (1988) present a 0/1 integer programming model to minimize the deviation between the workload assigned to each machine and the capacity of each machine. This model was solved individually for each machine type. The most significant limitation of this model was that two parts that required similar processing in terms of tooling and setups could be assigned to different machines in order to achieve a balance of capacity for each machine type.

Gunasingh and Lashkari (1989) presented a 0/1 integer programming model with two alternative objective functions: 1) to maximize similarity between machines and parts or 2) to minimize the cost of machines less savings in intercellular movements. These authors made two significant contributions. First, similarity was based on tooling. Second, the authors distinguished between two situations: 1) reorganizing an existing system, and 2) setting up an entirely new system. Additionally, cell size limits were considered in the model. One noteworthy limitation, however, was that an upper limit on purchases was specified for each machine type instead of specifying a total budget for all new equipment purchases. This approach restricted flexibility because unused funds available for one machine type could not be used to purchase other machine types.

Shtub (1989) illustrated how the cell formation problem can be formulated as a general assignment problem. Specifically, the formulation was for minimizing the cost of assigning parts to cells such that minimum and maximum usage levels for each cell were achieved.

Wei and Gaither (1990) presented the first 0/1 integer programming model for minimizing the cost associated with intercellular transfers. Intercellular transfers occur for two reasons: 1) the part was an exceptional part, or 2) the cell did not have sufficient capacity to process all parts assigned to it. Furthermore, limits on cell size were considered in the model. The major limitations associated with this formulation were occasional oversimplications. For example, parts were randomly assigned to machines when multiple machines were available. Thus, two parts having identical processing requirements could potentially be assigned to two different machines. As another example, a parameter [r.sub.ij] was defined as the total hours of machine i required to produce the part j. Given that setup times can vary depending on the sequence in which the parts were processed in, this parameter can not be known until after the part families were defined and the processing sequences were determined.

Askin and Chiu (1990) presented a 0/1 integer programming formulation that was for considering four cost categories: 1) machine cost, 2) group cost, i.e., the overhead associated with establishing a cell, 3) tooling cost, and 4) intercellular transfer cost. In addition, cell size limits and limits on worker hours were considered in the formulation.

Finally, while not a mathematical programming formulation, the heuristic based approach developed by Askin and Subramanian (1987) is worth noting because it considers many of the cellular manufacturing objectives. Specifically, setup costs, variable production costs, inventory costs, material handling costs, and machine costs are considered.

In Table 2 is a summary of the mathematical programming approaches developed for the cell formation problem. The first two columns in Table 2 identify the procedures and summarize the objective functions, respectively. The next seven columns evaluate the procedures on seven criteria. The last column in Table 2 summarizes the limitations of the procedures. Note that only askin and Chiu (1990) and Gunasingh and Lashkari (1989) consider the trade-off of duplicating equipment versus intercellular transfers. Furthermore, none of the procedures are for considering the reality that setup times can depend on the sequence in which the parts are produced. The goal programming models and the two-stage heuristic solution procedure for the goal programming models presented in the next sections are also listed in Table 2. The Goal Programming Models 1-3 address six of the seven criteria listed in Table 2. Previously, the largest number of criteria addressed by a single model was four, i.e., the model developed by Wei and Gaither (1990). The first stage of the heuristic procedure considers the same four criteria as the Wei and Gaither (1990) model. The major difference between the Wei and Gaither (1990) model and the stage 1 model is that Wei and Gaither minimize the cost associated with intercellular transfers while the stage 1 model minimizes machine purchase cost. After the stage 1 model is presented, however, it is demonstrated how marginal analysis can be used in conjunction with the stage 1 model to trade off the cost of additional equipment versus intercellular transfers.

NEW GOAL PROGRAMMING FORMULATIONS FOR THE

CELL FORMATION PROBLEM

In this section a new mathematical programming approach is presented. There were several reasons for developing this new formulation. First, before procedures can be developed to solve the cell formation problem, the problem must be defined (including the objectives, the constraints, and the situation). The language of mathematics is useful for this purpose. For example, the situation of the firm adopting CM is rarely considered by current cell formation

[TABULAR DATA OMITTED]

procedures. As previously mentioned, one notable exception is given by Gunasingh and Lashkari (1989) who distinguished between two situations. In this paper three situations are distinguished: 1) setting up an entirely new system and purchasing all new equipment, 2) reorganizing the system using only existing equipment, and 3) reorganizing the system using existing equipment and some new equipment. We assume that in all three situations the parts and their routings already exist.

Another important reason for the development of this cell formation procedure was to directly address as many of the design objectives of CM as possible and to realistically capture the constraints. Four design objectives are directly addressed in the formulation to be presented: 1) minimizing setup time, 2) minimizing intercellular movements, i.e., producing parts cell complete, 3) minimizing the investment in new equipment, and 4) maintaining acceptable machine utilization levels. Further, this is the first mathematical programming formulation that considers the issue of sequence dependent setups. Specifically, the sequence the parts are processed in is considered in the proposed formulation and is used as a measure of part similarity.

The following assumptions were made in the development of the model:

1. Each part has a fixed routing and alternative routings for the parts do not xist.

2. The processing times for each part at each machine are known.

3. The demand for each part is known.

4. The capacity and cost of each machine is known.

5. A given machine type can be placed in more than one cell.

6. The sequence in which the parts are processed affects setup times.

7. At least one machine of each type must be available.

8. Each part is produced on every production cycle. This assumption simplifies the calculation of total setup time for all parts, because once a sequence is developed it does not have to be modified due to one or more parts not being produced on a given production cycle.

9. Only one batch is processed in a cell at any given time. In other words, once a batch is finished in a cell, the equipment in the cell is set up for the next batch which is then processed in the cell.

The proposed goal programming models combine the p-median formulation with the traveling salesman problem (TSP). The p-median portion is for identifying part families and the TSP formulation is for developing a sequence for processing the parts within each family such that formulation is for developing a sequence for processing the parts within each family such that setup times are minimized. Classically, the TSP refers to the problem of finding the shortest route for a salesman who must visit a number of cities such that all cities are visited and that the salesman ends up where he started. For the present purpose, the TSP is used to develop a sequence for processing the parts such that all parts are processed and that total setup time is minimized. The formulations are now presented in detail.

Notation

Indexing sets: i,j = 1,...,n part type f = 1,...,n part family/machine cell r = 1,...,m machine type g = 1,...,4 goal number

Decision variables (lower case):

[Mathematical Expression Omitted] [Mathematical Expression Omitted]

[n.sub.rf] = Number of machines of machine type r assigned to part family f, integer.

[a.sub.r] = Number of machines of type r to acquire, integer.

[b.sub.if] = Variables introduced in constraints to exclude subtours in the processing sequence for each part family.

[d.sup.+.sub.grf], [d.sup.-.sub.grf] = Positive and negative deviational variables for goal g associated with machine type r in family f. If r and f are omitted from the subscript then only one deviational variable is needed for the goal.

Parameters (upper case):

[S.sub.ijr] = Time to set up machine r for part j given machine r is set up to process part i (hours).

[S.sub.ojr] = Time to set up machine r for part j when machine r is not set up to process any particular part (hours).

[S.sub.ij] = Total time to set up equipment for part j given equipment was setup for part i. Set to M if part i and j do not have any machines in common (hours).

[Mathematical Expression Omitted]

[Mathematical Expression Omitted] M = Large number.

[C.sub.r] = Capacity of each machine of machine type r (in hours/year).

[P.sub.r] = Purchase price of one machine of machine type r.

F = Funds available for equipment purchases.

[T.sub.ir] = Processing time for part i on machine type r.

[D.sub.i] = Annual demand of part i.

[Q.sub.i] = Lot size of part i.

[N.sub.r] = Number of machines of type r the firm already has.

[W.sup.+.sub.g], [W.sup.-.sub.g] = Priority weights for various goals in the objective function.

K = Number of part families/cells to form.

LP, UP = Loewr and upper bounds on the number of parts per family, respectively.

LM, UM = Lower and upper bounds on the number of machines per cell, respectively.

GOAL PROGRAMMING MODEL 1: PURCHASE ALL NEW EQUIPMENT

[Mathematical Expression Omitted]

S.T.

[Mathematical Expresison Omitted]

The deviations from four goals are minimized in the objective function: 1) the amount setup times exceed zero, 2) the capacity utilitzation in each cell, 3) the funds available to purchase new equipment, and 4) the number of intercellular moves. The first four sets of constraints are associated with these goals, respectively.

In (2), [d.sup.+.sub.1] represents the amount of time setup operations across all parts and machines exceeds the goal of zero time for setup operations. Note that (2) is only an approximation of setup times. It is exact for the situation where all equipment requirements for each part family are contained in a single cell and, therefore, no intercellular moves are required, that all parts are produced on each production cycle, and furthermore, that only one batch at a time is processed through each cell as done by Morris and Tersine (1989). In other words, each cell processes one batch at a time and when a batch is finished, the equipment in the cell is set up for the next batch.

In constraints (3) the capacity requirements for each machine in each cell are compared to the capacity available. The deviational variable for spending less than the available funds in constraint (4), i.e., [d.sup.-.sub.3], was included to keep the model as generic as possible. In the typical situation there would be no penalty and [W.sup.-.sub.3]=0. Constraint (5) is for calculating the number of intercellular moves by subtracting the number of operations completed within the cells from the total number of operations. Also [W.sup.+.sub.4] can be interpreted as the added cost or penalty, for moving a part between cells are opposed to moving the part within a cell. In (6), [x.sub.ijf] is trapped to the appropriate value. Constraints (7)-(9) correspond to the p-median formulation (for example, see Kusiak (1987)). Constraint (7) is for ensuring that each part is assigned to exactly one part family. Constraints (8) and (9) are included to ensure that the specified number of part families/machine cells are formed. Constraint (10) trap [v.sub.irf] to the appropriate value. Adding constraints (11) and (12) ensures that [e.sub.rf] = 1 whenever [n.sub.rf] [is greater than or equal to] 1.

Constraint sets (13)-(16) correspond to the linear programming formulation for the TSP and are used to develop the processing for the parts within each family. Specifically, constraints (13) are included to ensure that each part in a given part family precedes exactly, one other part in the processing sequence. Likewise, constraints (14) are added to ensure that each part in a given family follows exactly one other part in the processing sequence. Constraints (15) are for specifying that one part can precede the processing of another part only if the two parts are in the same family. Constraints (16) are used to preclude subtours in the processing sequence for the parts in each part family (Wagner (1969)). Note that the [[Sigma]x.sub.if] terms correspond to the number of parts in family in (16). Constraints (17) and (18) are included to ensure that the number of parts assigned to each family is within an upper and lower bound specified by management. Likewise, constraints (19) and (20) are added to restrict the number of machines in each cell to management specified limits. Constraints (17) through (20) are included because firms may have a priori bounds for cell and part family sizes. If management does not have a priori bounds for the cell and part family sizes, respectively, these contraints can be omitted. Constraints (21) are for ensuring that at least one of each machine type is purchases. Finally, constraints (22), through (24) are added to guarantee integrality and non-negativity. The above formulation has [3n.sup.3.+n.sup.2.+2n.sup.2.m+mn] zero-one variables, mn integer variables, 2mn+4 continuous variables, and [3n.sup.3-.2n.sup.2.+2n.sup.2.m+3mn+9n+m+4 linear constraints.

GOAL PROGRAMMING MODEL 1: USE ONLY EXISTING EQUIPMENT

[Mathematical Expression Omitted]

S.T.

[Mathematical Expression Omitted]

plus constrains (2), (3), and (6) through (20) from Goal Progamming Model 1.

Model 2 differs in only a few ways from the previous model. First, since only existing equipment is used, the goal associated with funds available to purchase new equipment is not needed. Second, constraint (26) replaced constraint (4) to ensure that the total number of machines of each type assigned to the cells equals the number of machines of that type available. Lastly, constraint (21) from Model 1 is not needed.

GOAL PROGRAMMING MODEL 3: CAN ADD SOME NEW EQUIPMENT TO

EXISTING EQUIPMENT

[Mathematical Expression Omitted]

S.T.

[Mathematical Expression Omitted]

plus constraints (2), (3), and (5) through (24) from Goal Programming Model 1.

This model differs in only a couple of ways from Model 1. First, the cost of acquiring new machiens (32) is based on only a subset of the machines. Second, constraint (33) is added to ensure that the number of machines assigned to cells equals the number of machines previously available plus the number of machines acquired.

HEURISTIC SOLUTION PROCEDURE

The number of 0/1 integer variables in Goal Programming Models 1 to 3 makes them very difficult to solve at present given the state-of-the-art in mathematical programming software and computer hardware. For example, the Model 1 formulation for a small problem consisting of 6 machines, 12 parts, and 3 part families would require 7,128 0/1 variables, 72 general integer variables, and 6,094 linear constraints. In addition to bigger and faster computers and better mathematical programming algorithms and software, solving the goal programming models would also probably require decision support software that could interface with existing corporate databases and thereby reduce the effort needed to obtain the parameter information. Also, such a decision support system should include matrix generator routines to assist the user in formulating the problem. Until these developments occur, however, the goal programming formulations can only be solved heuristically. Thus, in the remainder of this section a heuristic procedure for solving Model 1 is presented.

To solve Model 1 it was partitioned into two simpler subproblems and solved in successive stages. In the first stage a modified version of the p-median formulation is used to determine the part families and machine cells. In this stage machine cost and capacity is considered. Also, marginal analysis can be performed at this stage to determine if additional equipment is justified based on the savings resulting from fewer intercellular transfers. Then, for each part family identified in stage 1, a TSP formulation is solved to determine the processing sequence of the parts in the family (Foo and Wager (1983)).

The modified p-median formulation to be solved in stage 1 is the following:

MIN Z = [Mathematical Expressions Omitted]

S.T. [Mathematical Expressions Omitted]

This formulation is used to define part families and machine cells such that the investment in equipment is minimized. Note that for the modified p-median formulation, the subscript f goes up to K instead of n and that constraint (8) has been relaxed. This is because we are only interested in determining the members of the K clusters and not the medians of the clusters. Constraints (38) and (39) are included to restrict the number of parts assigned to each family and guarantee that the number of non-empty clusters can be controlled. The implication of all this is that the number of [x.sub.if] variables may be reduced from [n.sup.2] to nK. In addition, the integer requirement of the [n.sub.rf] variables has been relaxed. Constraints (36) are to ensure that there is enough aggregate capacity for each machine type. Constraints (37) are to guarantee that each part is assigned to exactly one part family. Constraints (19) and (20) could also be added to this formulation if it is desired to restrict cell size. The above formulation has nK 0/1 variables, mK continuous variables, and mK + 2K + n linear constraints and therefore should be solvable for moderately sized problems.

Several constraints from Model 1 were not needed in the above formulation. Constraints (6) in Model 1 were used to trap the [x.sub.ijf] variables to the appropriate values. Since the [x.sub.ijf] variables are not needed in the above formulation, constraints (6) are not required either. A similar argument exists for the [y.sub.irf] variables and constraints (10) in Model 1. In addition, since the [e.sub.rf] variables are not used in the above formulation, constraints (11) and (12) are not required.

Although the stage 1 model presented above is a simplification of Model 1, it does make a contribution in its owns right. First, as noted above, the number of 0/1 integer variables in the p-median formulation has been reduced. Secondly, it appears to be the first mathematical formulation that forms part families and machine cells such that machine costs are minimized.

In the second stage, the following model proposed by Foo and Wager (1983) is solved for each part family defined in stage 1:

MIN Z = [Mathematical Expressions Omitted]

S.T.

[Mathematical Expressions Omitted]

[b.sub.i] - [b.sub.j] + [Pg.sub.ij] [is less than or equal to] P-1, i = 2,3,...,n j = 2,3,...,n (j [is not =] i) [Mathematical Expressions Omitted]

The objective function is for minimizing the total setup time associated with processing all parts in the family. Constraints (42) and (43) are for ensuring that each part precedes exactly one part and that each part follows exactly one part, respectively. Note, since this model is solved for each part family, the subscript f was not needed. Lastly, constraints (44) are added to preclude subtours with the parameters P defined to be the number of parts in the part family. The above formulations has [P.sup.2] 0/1 variables, n continuous variables, and 2n + (n-1)(n-2) linear constraints.

NUMERICAL EXAMPLE

In this section the two-stage solution procedure is illustrated with a numerical example. The example corresponds to a situation where three part families are to be formed and there are twelve parts, and six machine types. Additional data are given in Figure 1.

To obtain solutions, the zero-one optimization methods (ZOOM) package (Marsten (1981), (1987)), was run on a VAX 8650. The stage 1 model had 36 0/1 integer variables, 18 continuous variables, and 36 linear constraints. The stage 2 models had 16 0/1 variables, 4 continuous variables, and 14 linear constraints.

The solution to the stage 1 model placed parts 1, 9, 11, and 12 in part family 1. Likewise, part family 2 contained parts 5, 6, 7, and 8, and part family three contained parts 2, 3, 4, and 10. The parameters LP and UP were set to 3 and 5, respectively.

Table 3 is a summary of the machine assignment results from the stage 1 solution. Specifically, the numbers not in parentheses in Table 3 are the actual values for the [n.sub.rf] variables. The last column represents the minimum number of each machine required and is calculated by summing up the [n.sub.rf] values in each row and rounding up to the first integer value. The numbers in parentheses in Table 3 represent one way the machines can be assigned to cells based on the stage 1 solution. The actual machine assignments were based on the heuristic of sequentially assigning the number of machines listed in the last column to the part families with the largest requirements.

[TABULAR DATA OMITTED]

Based on the machine assignments shown in Table 3, parts in family 2 can be completely processed in a single cell, while one or more parts in families 1 and 3 processing outside of their primary cell. Examining Figure 1 reveals that part 1 requires an operation on machine 2 and part 10 requires processing on machine 6. Thus, two of the 12 parts require a single operation outside of their primary cell representing 2 out of the 35 operations.

Marginal analysis can quickly be performed to determine if it is justified to invest in additional equipment to eliminate these intercellular transfers. First, from the data in Figure 1 it is easily determined that 500 batches of part 1 and part 10 are processed per year. Since each of these parts requires one machine outside of their primary cell, we can assume 500 intercellular transfers are needed for each of these parts. As was noted previously, part 1 requires machine 2 and part 10 requires machine 6. The costs of these two machines is $33,000 and $52,000, respectively. Define [I.sub.1] and [I.sub.10] to be the penalty or incremental cost associated with moving part 1 and part 10 outside their primary cells, respectively. Given this information, it is justified to purchase additional machinery provided the savings from fewer intercellular transfers exceed the cost of the additional equipment. Mathematically.

[500I.sub.1] [is greater than or equal to]33,000 (46) [500I.sub.10] [is greater than or equal to]52,000 (47)

Note that employing this type of analysis does not determining the exact quantities of [I.sub.1] and [I.sub.10]. Rather, it must only be determined whether [I.sub.1] is greater or less than $66 and whether [I.sub.10] is greater or less than $104.

Table 4 is a summary of the results obtained when the stage 2 model was solved for each of the part families identified in stage 1. For example, referring to part family 1, the parts should be processed in the sequence of part 1, 9, 12, and 11. Using this sequence results in a total setup time of 10.75 hours. The worst sequence (i.e., 1, 9, 11, and 12) requires 12.70 hours and the average setup time over all possible sequences is 11.83 hours. Across all three part families, the processing sequence determined using the stage 2 model was 38.16% lower than the worst sequence and 22.90% lower than a randomly selected sequence.

SUMMARY AND CONCLUSIONS

In this paper four important design objectives associated with adopting a cellular layout were defined. To help clarify the cell formation problem, the language of mathematics was used and three new goal programming formulations were presented. Although the goal programming formulations are difficult to solve, they do make a contribution in the respect that the objectives and constraints of the cell formation problem are clearly defined. As a solution approach, a two-stage heuristic procedure was presented to the goal programming formulations.

Additional research is needed in several areas. First, research focusing on other ways to solve the proposed formulations (e.g., relaxing the integer constraints, simulated annealing, tabu search, cutting plane algorithms, Lagrangian relaxation of some constraints, and/or other heuristic solution procedures) is needed. Also, there are now alternative mathematical programming formulations available in the literature. Research comparing those alternative formulations would be useful. Lastly, the goal programming models can be extended to consider additional objectives such as tooling cost and alternate part routing. Conducting research along these lines would do much to bridge the gap between academic research and real-world practice and could eventually lead to the desirable result of research leading industry practice.

REFERENCES

Askin, R.G., and S.P. Subramanian. "A Cost-Based Heuristic for Group Technology Configuration." International Journal of Production Research, vol. 25, no. 1, 1987, 101-113.

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, 1990, 1555-1572.

Choobineh, F. "A Framework for the Design of Cellular Manufacturing Systems." International Journal of Production Research, vol. 26, no. 7, 1988, 1161-1172.

Co., H.C. and A. Araar. "Configuring Cellular Manufacturing Systems." International Journal of Production Research, vol. 26, no. 9, 1988, 1511-1522.

Foo, F.C., and J.G. Wager, "Set-up Times in Cyclic and Acyclic Group Technology Scheduling Systems." International Journal of Production Research, vol. 21, no. 1, 1983, 63-73.

Goldratt, E.M., and J. Cox. The Goal. New York; North River Press. 1986.

Gunasingh, K.R., and R.S. Lashkari. "Machine Grouping Problem in Cellular Manufacturing Systems - An Integer Programming Approach." International Journal of Production Research, vol. 27, no. 9, 1989, 1465-1473.

Kusiak, A. "The Generalized Group Technology Concept." International Journal of Production Research, vol. 25, no. 4, 1987, 561-569.

Marsten, R.E. "The Design of the XMP Linear Programming Library." ACM Transactions of Mathematical Software, vol. 7, no. 4, 1981, 481-497.

Marsten, R.E. Users Manual for ZOOM/XMP. Tucson, AZ: University of Arizona, 1987.

Morris, J.S., and R.J. Tersine. "A Comparison of Cell Loading Practices in Group Technology." Journal of Manufacturing and Operations Management, vol. 2, no. 4, 1989, 299-313.

Shafer, S.M. and J.R. Meredith. "An Empirically-Based Simulation Study of Cellular Versus Functional Layouts." Working Paper, University of Miami, Coral Gables, FL 33124-9145, 1990.

Shtub, A. "Modelling Group Technology Cell Formation as a Generalizd Assignment Problem." International Journal of Production Research, vol. 27, no. 5, 1989, 775-782.

Vakharia, A.J. "Methods of Cell Formation in Group Technology: A Framework for Evaluation." Journal of Operations Management, vol. 6, no. 3, 1986, 257-271.

Wagner, H.M. Principles of Operations Research With Applications to Managerial Decisions. New Jersey: Prentice Hall, 1969.

Wei, J.C., and N. Gaither. "An Optimal Model for Cell Formation Decisions." Decision Sciences, vol. 21, no. 2, 1990, 416-433.

Wemmerlov, U., and N.L. Hyer. "Procedures for the Part Family/Machine Group Identification Problem in Cellular Manufacturing." Journal of Operations Management, vol. 6, no. 2, 1986, 125-147.

Cellular manufacturing (CM) is the application of group technology (GT) principles to production. Specifically, the objective of CM is to achieve efficiencies in production by exploiting similarities inherent in the production of parts. Thus, firms adopting CM seek to obtain many of the efficiencies associated with mass production in less repetitive batch environments. To achieve these benefits, groups of functionally dissimilar machines are located in close proximity to one another and are dedicated to the production of a set of parts with similar processing requirements. These groups of machines are referred to as machine cells, or simply cells, and the sets of parts with similar processing requirements are referred to as part families.

There has been a large amount of research conducted recently in the area of CM (for example, see Wemmerlov and Hyer (1986), where over 70 contributions to the literature are classified). As Vakharia (1986) noted, however, the focus of this research has been on the development of techniques to identify part families and/or machine cells, i.e., cell formation procedures, and little research has been for investigating the appropriateness of these techniques. This problem is further compounded because many of the techniques developed to date do not accurately capture many of the realities of the cell formation problem. For example, many of these procedures employ surrogate measures of the objectives that were easily measurable rather than direct measures of the objectives associated with the adoption of CM. To illustrate, many cell formation procedures are based on the assumption that parts that require the same set of equipment have similar processing requirements. Hence, these procedures are for identifying part families based on similarities in the set of machines the parts require in their processing. It is suggested here that a more direct approach for identifying part families is to group parts together based on similarities in setups and tooling. Thus, a primary objective of this paper is to develop a cell formation procedure that accurately and realistically addresses more facets of the cell formation problem.

To achieve this goal, the objectives for adopting a cellular layout must first be defined. A distinction is often made between design objectives and performance objectives. Design objectives are used to guide the cell formation process, while performance objectives are associated with expected benefits. Throughout this paper the term objective is used to refer to design objectives. It is worth noting, however, that a given objective may be both a design and performance objective. For example, reductions in setup times can be used to guide the cell formation process. In addition, reduced setup times can be considered a benefit of CM.

In the next section several design objectives of CM are discussed. Then relevant prior research is briefly reviewed. Three goal programming models that realistically capture the cell formation problem are then presented. Subsequently, an approach for solving the goal programs is discussed. Finally, the paper ends with conclusions and a discussion of areas for future research.

OBJECTIVES OF CELLULAR MANUFACTURING

Before procedures can be developed for appropriately addressing the cell formation problem, the objectives for adopting CM must be clearly defined. Table 1 is a summary of several of the objectives associated with CM classified into four major categories. Many of the objectives associated with adopting a cellular layout are situation dependent and therefore the list in Table 1 is generic and is not intended to be exhaustive.

The first major objective listed in Table 1 is to reduce setup times. It is worth noting that setup reductions in this paper refer to reducing the time spent on setups as opposed to reducing the time per setup. In other words, setup reductions for our purposes refer to reductions accomplished by sequencing and not reductions due to improving the change-over process.

There are numerous benefits associated with reducing setup times. For example, reducing setup times effectively increases the productive capacity of the plant because more time is available to engage in productive operations. also, reductions in setup times permit reductions in lot sizes and the adoption of just-in-time. Further, smaller lot sizes result in shorter lead times and reduced work-in-process inventory levels. More accurate forecasts and even competitive advantages can result from shorter lead times. Similarly, opportunities to improve the production process and improve the quality level often result from reductions in work-in-process inventory.

[TABULAR DATA OMITTED]

A second common objective of CM is to produce parts within a single cell. Achieving this significantly simplifies shop floor control. Further, the potential to increase the accountability, responsibility, and autonomy of the workers is enhanced. For example, workers in a cell can be held accountable for product quality when the product is produced cell complete. This is in contrast to the functional layout where parts are processed in many different departments and where workers in ne department can blame workers in other departments for poor quality. Also, lead times can be reduced by overlapping operations, i.e., sending parts ahead to the next operation before all parts in the batch are completed at the current machine, because all necessary equipment is located together in close proximity when parts are produced cell complete.

Finally, two additional general objectives associated with CM are to minimize the investment in new equipment and to maintain acceptable utilization levels. Caution should be exercised to avoid overly emphasizing the machine utilization objective. For example, Shafer and Meredith (1990) argued that shop performance is improved when lead times and work-in-process inventory levels are reduced regardless of the level of machine utilization. In fact, emphasis upon machine utilization may very often be in direct conflict with one of the most basic objectives of a firm-making a profit (Goldratt and Cox (1986)).

OVERVIEW OF MATHEMATICAL PROGRAMMING APPROACHES

TO CELL FORMATION

Before presenting the new goal programming formulations, the mathematical programming formulations that have been developed to date will be overviewed. Kusiak (1987), employed the p-median O/1 integer programming formulation to identify part families. The p-median approach involved initially selecting p of the parts to serve as medians or seeds for the clusters. Subsequently, the remaining parts were assigned to the seed parts such that the sum of part similarly in each part family was maximized. Part similarly between two parts was defined as the number of machines the two parts had in common in their processing. A significant contribution of this approach was that it was one of the first procedures developed to process a similarity matrix using mathematical programming as opposed to hierarchical cluster analysis. Also, the author illustrated how the formulation could be extended to consider situations for which alternate part routings existed. A major limitation of this approach was that only part families were identified and that a second ancillary procedure was needed to identify machine cells.

Choobineh (1988) developed a 0/1 integer programming formulation for which the cost of producing a part in each cell and the cost of purchasing new equipment was minimized. A major contribution of this formation was that the funds available for the purchase of new equipment was considered. Also, the formulation contained constraints to ensure that the capacity of each machine in each cell was not exceeded. A major limitation of the formulation was that some of the coefficients in the model were not known until after the problem was solved. For example, [C.sub.fk] was a coefficient in the objective function and was defined as the cost of producing part f in cell k. Clearly, this parameter will depend on the solution found, i.e., the type of equipment assigned to each cell and how the parts were assigned to the cell.

Co and Araar (1988) present a 0/1 integer programming model to minimize the deviation between the workload assigned to each machine and the capacity of each machine. This model was solved individually for each machine type. The most significant limitation of this model was that two parts that required similar processing in terms of tooling and setups could be assigned to different machines in order to achieve a balance of capacity for each machine type.

Gunasingh and Lashkari (1989) presented a 0/1 integer programming model with two alternative objective functions: 1) to maximize similarity between machines and parts or 2) to minimize the cost of machines less savings in intercellular movements. These authors made two significant contributions. First, similarity was based on tooling. Second, the authors distinguished between two situations: 1) reorganizing an existing system, and 2) setting up an entirely new system. Additionally, cell size limits were considered in the model. One noteworthy limitation, however, was that an upper limit on purchases was specified for each machine type instead of specifying a total budget for all new equipment purchases. This approach restricted flexibility because unused funds available for one machine type could not be used to purchase other machine types.

Shtub (1989) illustrated how the cell formation problem can be formulated as a general assignment problem. Specifically, the formulation was for minimizing the cost of assigning parts to cells such that minimum and maximum usage levels for each cell were achieved.

Wei and Gaither (1990) presented the first 0/1 integer programming model for minimizing the cost associated with intercellular transfers. Intercellular transfers occur for two reasons: 1) the part was an exceptional part, or 2) the cell did not have sufficient capacity to process all parts assigned to it. Furthermore, limits on cell size were considered in the model. The major limitations associated with this formulation were occasional oversimplications. For example, parts were randomly assigned to machines when multiple machines were available. Thus, two parts having identical processing requirements could potentially be assigned to two different machines. As another example, a parameter [r.sub.ij] was defined as the total hours of machine i required to produce the part j. Given that setup times can vary depending on the sequence in which the parts were processed in, this parameter can not be known until after the part families were defined and the processing sequences were determined.

Askin and Chiu (1990) presented a 0/1 integer programming formulation that was for considering four cost categories: 1) machine cost, 2) group cost, i.e., the overhead associated with establishing a cell, 3) tooling cost, and 4) intercellular transfer cost. In addition, cell size limits and limits on worker hours were considered in the formulation.

Finally, while not a mathematical programming formulation, the heuristic based approach developed by Askin and Subramanian (1987) is worth noting because it considers many of the cellular manufacturing objectives. Specifically, setup costs, variable production costs, inventory costs, material handling costs, and machine costs are considered.

In Table 2 is a summary of the mathematical programming approaches developed for the cell formation problem. The first two columns in Table 2 identify the procedures and summarize the objective functions, respectively. The next seven columns evaluate the procedures on seven criteria. The last column in Table 2 summarizes the limitations of the procedures. Note that only askin and Chiu (1990) and Gunasingh and Lashkari (1989) consider the trade-off of duplicating equipment versus intercellular transfers. Furthermore, none of the procedures are for considering the reality that setup times can depend on the sequence in which the parts are produced. The goal programming models and the two-stage heuristic solution procedure for the goal programming models presented in the next sections are also listed in Table 2. The Goal Programming Models 1-3 address six of the seven criteria listed in Table 2. Previously, the largest number of criteria addressed by a single model was four, i.e., the model developed by Wei and Gaither (1990). The first stage of the heuristic procedure considers the same four criteria as the Wei and Gaither (1990) model. The major difference between the Wei and Gaither (1990) model and the stage 1 model is that Wei and Gaither minimize the cost associated with intercellular transfers while the stage 1 model minimizes machine purchase cost. After the stage 1 model is presented, however, it is demonstrated how marginal analysis can be used in conjunction with the stage 1 model to trade off the cost of additional equipment versus intercellular transfers.

NEW GOAL PROGRAMMING FORMULATIONS FOR THE

CELL FORMATION PROBLEM

In this section a new mathematical programming approach is presented. There were several reasons for developing this new formulation. First, before procedures can be developed to solve the cell formation problem, the problem must be defined (including the objectives, the constraints, and the situation). The language of mathematics is useful for this purpose. For example, the situation of the firm adopting CM is rarely considered by current cell formation

[TABULAR DATA OMITTED]

procedures. As previously mentioned, one notable exception is given by Gunasingh and Lashkari (1989) who distinguished between two situations. In this paper three situations are distinguished: 1) setting up an entirely new system and purchasing all new equipment, 2) reorganizing the system using only existing equipment, and 3) reorganizing the system using existing equipment and some new equipment. We assume that in all three situations the parts and their routings already exist.

Another important reason for the development of this cell formation procedure was to directly address as many of the design objectives of CM as possible and to realistically capture the constraints. Four design objectives are directly addressed in the formulation to be presented: 1) minimizing setup time, 2) minimizing intercellular movements, i.e., producing parts cell complete, 3) minimizing the investment in new equipment, and 4) maintaining acceptable machine utilization levels. Further, this is the first mathematical programming formulation that considers the issue of sequence dependent setups. Specifically, the sequence the parts are processed in is considered in the proposed formulation and is used as a measure of part similarity.

The following assumptions were made in the development of the model:

1. Each part has a fixed routing and alternative routings for the parts do not xist.

2. The processing times for each part at each machine are known.

3. The demand for each part is known.

4. The capacity and cost of each machine is known.

5. A given machine type can be placed in more than one cell.

6. The sequence in which the parts are processed affects setup times.

7. At least one machine of each type must be available.

8. Each part is produced on every production cycle. This assumption simplifies the calculation of total setup time for all parts, because once a sequence is developed it does not have to be modified due to one or more parts not being produced on a given production cycle.

9. Only one batch is processed in a cell at any given time. In other words, once a batch is finished in a cell, the equipment in the cell is set up for the next batch which is then processed in the cell.

The proposed goal programming models combine the p-median formulation with the traveling salesman problem (TSP). The p-median portion is for identifying part families and the TSP formulation is for developing a sequence for processing the parts within each family such that formulation is for developing a sequence for processing the parts within each family such that setup times are minimized. Classically, the TSP refers to the problem of finding the shortest route for a salesman who must visit a number of cities such that all cities are visited and that the salesman ends up where he started. For the present purpose, the TSP is used to develop a sequence for processing the parts such that all parts are processed and that total setup time is minimized. The formulations are now presented in detail.

Notation

Indexing sets: i,j = 1,...,n part type f = 1,...,n part family/machine cell r = 1,...,m machine type g = 1,...,4 goal number

Decision variables (lower case):

[Mathematical Expression Omitted] [Mathematical Expression Omitted]

[n.sub.rf] = Number of machines of machine type r assigned to part family f, integer.

[a.sub.r] = Number of machines of type r to acquire, integer.

[b.sub.if] = Variables introduced in constraints to exclude subtours in the processing sequence for each part family.

[d.sup.+.sub.grf], [d.sup.-.sub.grf] = Positive and negative deviational variables for goal g associated with machine type r in family f. If r and f are omitted from the subscript then only one deviational variable is needed for the goal.

Parameters (upper case):

[S.sub.ijr] = Time to set up machine r for part j given machine r is set up to process part i (hours).

[S.sub.ojr] = Time to set up machine r for part j when machine r is not set up to process any particular part (hours).

[S.sub.ij] = Total time to set up equipment for part j given equipment was setup for part i. Set to M if part i and j do not have any machines in common (hours).

[Mathematical Expression Omitted]

[Mathematical Expression Omitted] M = Large number.

[C.sub.r] = Capacity of each machine of machine type r (in hours/year).

[P.sub.r] = Purchase price of one machine of machine type r.

F = Funds available for equipment purchases.

[T.sub.ir] = Processing time for part i on machine type r.

[D.sub.i] = Annual demand of part i.

[Q.sub.i] = Lot size of part i.

[N.sub.r] = Number of machines of type r the firm already has.

[W.sup.+.sub.g], [W.sup.-.sub.g] = Priority weights for various goals in the objective function.

K = Number of part families/cells to form.

LP, UP = Loewr and upper bounds on the number of parts per family, respectively.

LM, UM = Lower and upper bounds on the number of machines per cell, respectively.

GOAL PROGRAMMING MODEL 1: PURCHASE ALL NEW EQUIPMENT

[Mathematical Expression Omitted]

S.T.

[Mathematical Expresison Omitted]

The deviations from four goals are minimized in the objective function: 1) the amount setup times exceed zero, 2) the capacity utilitzation in each cell, 3) the funds available to purchase new equipment, and 4) the number of intercellular moves. The first four sets of constraints are associated with these goals, respectively.

In (2), [d.sup.+.sub.1] represents the amount of time setup operations across all parts and machines exceeds the goal of zero time for setup operations. Note that (2) is only an approximation of setup times. It is exact for the situation where all equipment requirements for each part family are contained in a single cell and, therefore, no intercellular moves are required, that all parts are produced on each production cycle, and furthermore, that only one batch at a time is processed through each cell as done by Morris and Tersine (1989). In other words, each cell processes one batch at a time and when a batch is finished, the equipment in the cell is set up for the next batch.

In constraints (3) the capacity requirements for each machine in each cell are compared to the capacity available. The deviational variable for spending less than the available funds in constraint (4), i.e., [d.sup.-.sub.3], was included to keep the model as generic as possible. In the typical situation there would be no penalty and [W.sup.-.sub.3]=0. Constraint (5) is for calculating the number of intercellular moves by subtracting the number of operations completed within the cells from the total number of operations. Also [W.sup.+.sub.4] can be interpreted as the added cost or penalty, for moving a part between cells are opposed to moving the part within a cell. In (6), [x.sub.ijf] is trapped to the appropriate value. Constraints (7)-(9) correspond to the p-median formulation (for example, see Kusiak (1987)). Constraint (7) is for ensuring that each part is assigned to exactly one part family. Constraints (8) and (9) are included to ensure that the specified number of part families/machine cells are formed. Constraint (10) trap [v.sub.irf] to the appropriate value. Adding constraints (11) and (12) ensures that [e.sub.rf] = 1 whenever [n.sub.rf] [is greater than or equal to] 1.

Constraint sets (13)-(16) correspond to the linear programming formulation for the TSP and are used to develop the processing for the parts within each family. Specifically, constraints (13) are included to ensure that each part in a given part family precedes exactly, one other part in the processing sequence. Likewise, constraints (14) are added to ensure that each part in a given family follows exactly one other part in the processing sequence. Constraints (15) are for specifying that one part can precede the processing of another part only if the two parts are in the same family. Constraints (16) are used to preclude subtours in the processing sequence for the parts in each part family (Wagner (1969)). Note that the [[Sigma]x.sub.if] terms correspond to the number of parts in family in (16). Constraints (17) and (18) are included to ensure that the number of parts assigned to each family is within an upper and lower bound specified by management. Likewise, constraints (19) and (20) are added to restrict the number of machines in each cell to management specified limits. Constraints (17) through (20) are included because firms may have a priori bounds for cell and part family sizes. If management does not have a priori bounds for the cell and part family sizes, respectively, these contraints can be omitted. Constraints (21) are for ensuring that at least one of each machine type is purchases. Finally, constraints (22), through (24) are added to guarantee integrality and non-negativity. The above formulation has [3n.sup.3.+n.sup.2.+2n.sup.2.m+mn] zero-one variables, mn integer variables, 2mn+4 continuous variables, and [3n.sup.3-.2n.sup.2.+2n.sup.2.m+3mn+9n+m+4 linear constraints.

GOAL PROGRAMMING MODEL 1: USE ONLY EXISTING EQUIPMENT

[Mathematical Expression Omitted]

S.T.

[Mathematical Expression Omitted]

plus constrains (2), (3), and (6) through (20) from Goal Progamming Model 1.

Model 2 differs in only a few ways from the previous model. First, since only existing equipment is used, the goal associated with funds available to purchase new equipment is not needed. Second, constraint (26) replaced constraint (4) to ensure that the total number of machines of each type assigned to the cells equals the number of machines of that type available. Lastly, constraint (21) from Model 1 is not needed.

GOAL PROGRAMMING MODEL 3: CAN ADD SOME NEW EQUIPMENT TO

EXISTING EQUIPMENT

[Mathematical Expression Omitted]

S.T.

[Mathematical Expression Omitted]

plus constraints (2), (3), and (5) through (24) from Goal Programming Model 1.

This model differs in only a couple of ways from Model 1. First, the cost of acquiring new machiens (32) is based on only a subset of the machines. Second, constraint (33) is added to ensure that the number of machines assigned to cells equals the number of machines previously available plus the number of machines acquired.

HEURISTIC SOLUTION PROCEDURE

The number of 0/1 integer variables in Goal Programming Models 1 to 3 makes them very difficult to solve at present given the state-of-the-art in mathematical programming software and computer hardware. For example, the Model 1 formulation for a small problem consisting of 6 machines, 12 parts, and 3 part families would require 7,128 0/1 variables, 72 general integer variables, and 6,094 linear constraints. In addition to bigger and faster computers and better mathematical programming algorithms and software, solving the goal programming models would also probably require decision support software that could interface with existing corporate databases and thereby reduce the effort needed to obtain the parameter information. Also, such a decision support system should include matrix generator routines to assist the user in formulating the problem. Until these developments occur, however, the goal programming formulations can only be solved heuristically. Thus, in the remainder of this section a heuristic procedure for solving Model 1 is presented.

To solve Model 1 it was partitioned into two simpler subproblems and solved in successive stages. In the first stage a modified version of the p-median formulation is used to determine the part families and machine cells. In this stage machine cost and capacity is considered. Also, marginal analysis can be performed at this stage to determine if additional equipment is justified based on the savings resulting from fewer intercellular transfers. Then, for each part family identified in stage 1, a TSP formulation is solved to determine the processing sequence of the parts in the family (Foo and Wager (1983)).

The modified p-median formulation to be solved in stage 1 is the following:

MIN Z = [Mathematical Expressions Omitted]

S.T. [Mathematical Expressions Omitted]

This formulation is used to define part families and machine cells such that the investment in equipment is minimized. Note that for the modified p-median formulation, the subscript f goes up to K instead of n and that constraint (8) has been relaxed. This is because we are only interested in determining the members of the K clusters and not the medians of the clusters. Constraints (38) and (39) are included to restrict the number of parts assigned to each family and guarantee that the number of non-empty clusters can be controlled. The implication of all this is that the number of [x.sub.if] variables may be reduced from [n.sup.2] to nK. In addition, the integer requirement of the [n.sub.rf] variables has been relaxed. Constraints (36) are to ensure that there is enough aggregate capacity for each machine type. Constraints (37) are to guarantee that each part is assigned to exactly one part family. Constraints (19) and (20) could also be added to this formulation if it is desired to restrict cell size. The above formulation has nK 0/1 variables, mK continuous variables, and mK + 2K + n linear constraints and therefore should be solvable for moderately sized problems.

Several constraints from Model 1 were not needed in the above formulation. Constraints (6) in Model 1 were used to trap the [x.sub.ijf] variables to the appropriate values. Since the [x.sub.ijf] variables are not needed in the above formulation, constraints (6) are not required either. A similar argument exists for the [y.sub.irf] variables and constraints (10) in Model 1. In addition, since the [e.sub.rf] variables are not used in the above formulation, constraints (11) and (12) are not required.

Although the stage 1 model presented above is a simplification of Model 1, it does make a contribution in its owns right. First, as noted above, the number of 0/1 integer variables in the p-median formulation has been reduced. Secondly, it appears to be the first mathematical formulation that forms part families and machine cells such that machine costs are minimized.

In the second stage, the following model proposed by Foo and Wager (1983) is solved for each part family defined in stage 1:

MIN Z = [Mathematical Expressions Omitted]

S.T.

[Mathematical Expressions Omitted]

[b.sub.i] - [b.sub.j] + [Pg.sub.ij] [is less than or equal to] P-1, i = 2,3,...,n j = 2,3,...,n (j [is not =] i) [Mathematical Expressions Omitted]

The objective function is for minimizing the total setup time associated with processing all parts in the family. Constraints (42) and (43) are for ensuring that each part precedes exactly one part and that each part follows exactly one part, respectively. Note, since this model is solved for each part family, the subscript f was not needed. Lastly, constraints (44) are added to preclude subtours with the parameters P defined to be the number of parts in the part family. The above formulations has [P.sup.2] 0/1 variables, n continuous variables, and 2n + (n-1)(n-2) linear constraints.

NUMERICAL EXAMPLE

In this section the two-stage solution procedure is illustrated with a numerical example. The example corresponds to a situation where three part families are to be formed and there are twelve parts, and six machine types. Additional data are given in Figure 1.

To obtain solutions, the zero-one optimization methods (ZOOM) package (Marsten (1981), (1987)), was run on a VAX 8650. The stage 1 model had 36 0/1 integer variables, 18 continuous variables, and 36 linear constraints. The stage 2 models had 16 0/1 variables, 4 continuous variables, and 14 linear constraints.

The solution to the stage 1 model placed parts 1, 9, 11, and 12 in part family 1. Likewise, part family 2 contained parts 5, 6, 7, and 8, and part family three contained parts 2, 3, 4, and 10. The parameters LP and UP were set to 3 and 5, respectively.

Table 3 is a summary of the machine assignment results from the stage 1 solution. Specifically, the numbers not in parentheses in Table 3 are the actual values for the [n.sub.rf] variables. The last column represents the minimum number of each machine required and is calculated by summing up the [n.sub.rf] values in each row and rounding up to the first integer value. The numbers in parentheses in Table 3 represent one way the machines can be assigned to cells based on the stage 1 solution. The actual machine assignments were based on the heuristic of sequentially assigning the number of machines listed in the last column to the part families with the largest requirements.

[TABULAR DATA OMITTED]

Based on the machine assignments shown in Table 3, parts in family 2 can be completely processed in a single cell, while one or more parts in families 1 and 3 processing outside of their primary cell. Examining Figure 1 reveals that part 1 requires an operation on machine 2 and part 10 requires processing on machine 6. Thus, two of the 12 parts require a single operation outside of their primary cell representing 2 out of the 35 operations.

Marginal analysis can quickly be performed to determine if it is justified to invest in additional equipment to eliminate these intercellular transfers. First, from the data in Figure 1 it is easily determined that 500 batches of part 1 and part 10 are processed per year. Since each of these parts requires one machine outside of their primary cell, we can assume 500 intercellular transfers are needed for each of these parts. As was noted previously, part 1 requires machine 2 and part 10 requires machine 6. The costs of these two machines is $33,000 and $52,000, respectively. Define [I.sub.1] and [I.sub.10] to be the penalty or incremental cost associated with moving part 1 and part 10 outside their primary cells, respectively. Given this information, it is justified to purchase additional machinery provided the savings from fewer intercellular transfers exceed the cost of the additional equipment. Mathematically.

[500I.sub.1] [is greater than or equal to]33,000 (46) [500I.sub.10] [is greater than or equal to]52,000 (47)

Note that employing this type of analysis does not determining the exact quantities of [I.sub.1] and [I.sub.10]. Rather, it must only be determined whether [I.sub.1] is greater or less than $66 and whether [I.sub.10] is greater or less than $104.

Table 4 is a summary of the results obtained when the stage 2 model was solved for each of the part families identified in stage 1. For example, referring to part family 1, the parts should be processed in the sequence of part 1, 9, 12, and 11. Using this sequence results in a total setup time of 10.75 hours. The worst sequence (i.e., 1, 9, 11, and 12) requires 12.70 hours and the average setup time over all possible sequences is 11.83 hours. Across all three part families, the processing sequence determined using the stage 2 model was 38.16% lower than the worst sequence and 22.90% lower than a randomly selected sequence.

TABLE 4 PROCESSING SEQUENCE FOR PARTS IN THE PART FAMILIES DETERMINED IN STAGE 1 Processing Total Worst Average Part Family Sequence Setup Time Setup Time Setup Time 1 1,9,12,11 10.75 12.70 11.83 2 5,8,6,7 5.20 8.25 7.10 3 2,3,10,4 7.55 10.40 9.22

SUMMARY AND CONCLUSIONS

In this paper four important design objectives associated with adopting a cellular layout were defined. To help clarify the cell formation problem, the language of mathematics was used and three new goal programming formulations were presented. Although the goal programming formulations are difficult to solve, they do make a contribution in the respect that the objectives and constraints of the cell formation problem are clearly defined. As a solution approach, a two-stage heuristic procedure was presented to the goal programming formulations.

Additional research is needed in several areas. First, research focusing on other ways to solve the proposed formulations (e.g., relaxing the integer constraints, simulated annealing, tabu search, cutting plane algorithms, Lagrangian relaxation of some constraints, and/or other heuristic solution procedures) is needed. Also, there are now alternative mathematical programming formulations available in the literature. Research comparing those alternative formulations would be useful. Lastly, the goal programming models can be extended to consider additional objectives such as tooling cost and alternate part routing. Conducting research along these lines would do much to bridge the gap between academic research and real-world practice and could eventually lead to the desirable result of research leading industry practice.

REFERENCES

Askin, R.G., and S.P. Subramanian. "A Cost-Based Heuristic for Group Technology Configuration." International Journal of Production Research, vol. 25, no. 1, 1987, 101-113.

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, 1990, 1555-1572.

Choobineh, F. "A Framework for the Design of Cellular Manufacturing Systems." International Journal of Production Research, vol. 26, no. 7, 1988, 1161-1172.

Co., H.C. and A. Araar. "Configuring Cellular Manufacturing Systems." International Journal of Production Research, vol. 26, no. 9, 1988, 1511-1522.

Foo, F.C., and J.G. Wager, "Set-up Times in Cyclic and Acyclic Group Technology Scheduling Systems." International Journal of Production Research, vol. 21, no. 1, 1983, 63-73.

Goldratt, E.M., and J. Cox. The Goal. New York; North River Press. 1986.

Gunasingh, K.R., and R.S. Lashkari. "Machine Grouping Problem in Cellular Manufacturing Systems - An Integer Programming Approach." International Journal of Production Research, vol. 27, no. 9, 1989, 1465-1473.

Kusiak, A. "The Generalized Group Technology Concept." International Journal of Production Research, vol. 25, no. 4, 1987, 561-569.

Marsten, R.E. "The Design of the XMP Linear Programming Library." ACM Transactions of Mathematical Software, vol. 7, no. 4, 1981, 481-497.

Marsten, R.E. Users Manual for ZOOM/XMP. Tucson, AZ: University of Arizona, 1987.

Morris, J.S., and R.J. Tersine. "A Comparison of Cell Loading Practices in Group Technology." Journal of Manufacturing and Operations Management, vol. 2, no. 4, 1989, 299-313.

Shafer, S.M. and J.R. Meredith. "An Empirically-Based Simulation Study of Cellular Versus Functional Layouts." Working Paper, University of Miami, Coral Gables, FL 33124-9145, 1990.

Shtub, A. "Modelling Group Technology Cell Formation as a Generalizd Assignment Problem." International Journal of Production Research, vol. 27, no. 5, 1989, 775-782.

Vakharia, A.J. "Methods of Cell Formation in Group Technology: A Framework for Evaluation." Journal of Operations Management, vol. 6, no. 3, 1986, 257-271.

Wagner, H.M. Principles of Operations Research With Applications to Managerial Decisions. New Jersey: Prentice Hall, 1969.

Wei, J.C., and N. Gaither. "An Optimal Model for Cell Formation Decisions." Decision Sciences, vol. 21, no. 2, 1990, 416-433.

Wemmerlov, U., and N.L. Hyer. "Procedures for the Part Family/Machine Group Identification Problem in Cellular Manufacturing." Journal of Operations Management, vol. 6, no. 2, 1986, 125-147.

Printer friendly Cite/link Email Feedback | |

Title Annotation: | Special Issue on Group Technology and Cellular Manufacturing |
---|---|

Author: | Shafer, Scott M.; Rogers, David F. |

Publication: | Journal of Operations Management |

Date: | Jan 1, 1991 |

Words: | 5981 |

Previous Article: | Production flow analysis for planning group technology. |

Next Article: | A comparative evaluation of nine well-known algorithms for solving the cell formation problem in group technology. |

Topics: |