Division of Research Graduate School of Business Administration The University of Michigan May 1983 Revised May 1984 Revised February 1985 A HIERARCHICAL APPROACH TO SOLVING MACHINE GROUPING AND LOADING PROBLEMS OF FLEXIBLE MANUFACTURING SYSTEMS WORKING PAPER NO. 331-C KATHRYN E. STECKE Graduate School of Business Administration The University of Michigan Ann Arbor, Michigan European Journal of Operational Research, 1985, forthcoming.

ABSTRACT A flexible manufacturing system (FMS) is an integrated system of computer numerically controlled (CNC) machine tools, each having an automatic tool interchange capability, and all connected by an automated material handling system. One or more computers control most real-time functions. Flexible manufacturing is realized to be an efficient alternative to conventional manufacturing that allows simultaneous machining of small to medium batches of a variety of part types. Parts can flow through the system in unit batch sizes. These systems typically machine five to forty different part types. In managing these systems, technological requirements indicate that several decisions must be made prior to system start-up. With these requirements in mind, previous research has defined a set of production planning problems, providing a conceptual framework to aid an FMS manager in setting up his/her system to enable efficient production. Several approaches have been taken to solve several of these problems and we describe those here. The main focus in this paper is on only two of these planning problems, the machine grouping and loading problems. In brief, the FMS machine grouping problem is to partition the mi machine tools of type i into gi groups to maximize expected production, subject to FMS technological and capacity constraints. Machines in a group are identically tooled and hence can perform the same operations during production. The FMS loading problem is to allocate operations and associated tooling of a selected set of part types among the machine groups, according to some appropriate (system dependent) loading objective, also subject to technological and capacity constraints.

This paper ties some previous results together by suggesting a hierarchical approach to solve actual grouping and loading problems. Both problems are first defined at an aggregated level of detail and in the context of a queueing network model. At this level, much information is suppressed. However, the robustness of the model allows the application of the obtained theoretical results to a lower level in the hierarchy that considers all details of these problems. In addition, results obtained using the aggregate model can be used as input to the detailed models. Here, the grouping and loading problems are formulated in all detail as nonlinear integer programs, using all available and required information. The use of these models to solve realistic machine grouping and loading problems is then described. Finally, future research needs are suggested.

1. INTRODUCTION A flexible manufacturing system consists of a set of computer numerically controlled machine tools and auxiliary equipment (such as inspection, washing, and queueing stations) that are all connected by automated material handling. The main applications to date have been metal-cutting operations, having midvolume and batch production. Incoming castings for parts, either prismatic or rotational, are first fixtured and palletized, and then input onto the material handling system to be routed through the FMS for various machining, refixturing, and inspection operations. One or more computers, interconnected via some hierarchical control structure, coordinate most real-time functions. These include downloading the appropriate part programs to control the metal-cutting and metal-removing operations of the machine tools, as well as controlling part movements and cutting tool interchanges. Examples and descriptions of existing flexible systems can be found in Stecke [1977], Stecke and Solberg [1981b], Cavaille et al. [1981], Barash [1982], and Stecke and Browne [1985]. Each machine tool has a limited-capacity tool magazine that stores all of the cutting tools required to perform all operations that might be performed at that machine tool. The very quick, automated tool interchange capability implies that there is no need to consider a machine set-up time between consecutive operations to be performed at the same machine tool. In addition, a part cannot be routed to a particular machine tool unless it is one of the machine types capable of performing that part's next operation and all cutting tools necessary to perform that next operation have previously been loaded into the machine tool's tool magazine. These technological and computer requirements indicate a natural separation of the FMS management functions concerned with running the system into

-2 - two distinct, but related, activities: first, the system has to be "set up" (cutting tools loaded,...) before production can start; then, the real-time, on-line control of part input, movement, and machining can occur. This paper is concerned mainly with the first activity, that of setting up an FMS in a good way, to allow efficient manufacturing and to utilize the system's capacity. Managing an FMS can be more complicated than the management of a conventional manufacturing system because there are many more manufacturing and routing options and other factors to consider. The machine tools are quite versatile and several part types can be machined simultaneously. In addition, each individual part, even those of the same part type, can have several routes through the system. Parts do not have to be machined in batches. At the same time, the machining process could and should be nearly as efficient as a well-balanced, automated transfer line. In its entirety, the FMS set-up problem is intractable. However, with efficient and flexible production in mind, the following FMS production planning problems have been defined (Stecke [1983a]): 1. Part type selection: From a set of part types, each having production requirements, determine a subset for immediate and simultaneous processing. 2. Machine grouping: Partition the machines tools of each machine type into machine groups such that each machine in a particular group is able to perform the same set of operations. 3. Production ratios: Determine the relative ratios at which the part types selected in problem (1) will be produced. 4. Resource allocation: Allocate the limited numbers of pallets and fixtures of each fixture type among the selected part types.

-3 - 5. Loading: Allocate the operations and associated cutting tools of the selected set of part types among the machine groups subject to the technological and capacity constraints of the FMS. Unlike the very infrequent set-up of a transfer line (usually only during the design and layout of the line), the above planning decisions can be made often (say every one to three weeks). Reconfiguring the machines and reloading the magazines might occur, for example, whenever the production requirements are complete for some part type. (This would free up space in a tool magazine for other cutting tools.) Reloading is also required when a rush order arrives that needs to be expedited or sometimes when a new part type is to begin production. (Space may need to be found in a tool magazine somehow, perhaps by reallocating operations and reshuffling tool assignments.) Cutters might also be changed around if the part type mix is changed and sometimes when a breakdown occurs. To begin the planning process, production requirements are given for several of the part types that are produced on the FMS. These requirements are determined either from customer orders or forecasted demand. The usual case is that all required part types cannot be simultaneously produced on the system. There is not enough space in the tool magazines to hold all required cutting tools. Hence the part types have to be partitioned into batches, each of which is machined one at a time. Then the first planning problem (1) is to select the part types to be produced in the next batch, over some time period. Whitney and Gaul [1984] suggest a heuristic approach to select the part types for each batch. When one batch of selected part types is complete, the next begins. One method of determining the relative production ratios (problems (3) and (4)) at which the part types should be on the system can use the mean

-4 - value analysis (MVA) technique which analyzes a queueing network model. See Cavaille and Dubois [1982] and Suri and Hildebrant [1984]. A multiple class model is used to provide the steady state expected production for each of several part types. A complimentary model to use to help answer the same questions ((3) and (4)) is a Petri net. See Dubois and Stecke [1983]. A Petri net is a deterministic model that can also analyze some transient and steady state effects. Both models account for the congestion as parts compete for the same limited resources (i.e., machine tools). MVA assumes random operation times while a Petri net requires deterministic processing times. Use of both models would provide bounds on the requirements specifications to operate the FMS efficiently. The remainder of this paper focuses on a different two of these planning problems, the machine grouping problem (2) and the loading problem (5), at several levels of detail. The grouping problem is a different sort of problem because in the past, even for non-automated systems, each operation was usually assigned to one and only one machine tool. However, pooling machines into groups allows alternative routes for parts and can increase all system performance measures. The approach to solve the loading problem was usually to attempt to achieve the best balance of workload (operations to be performed) among the machine tools. However, an FMS is an integrated system of very versatile CNC machine tools. It seemed desirable to devise new loading and scheduling policies that could utilize the available flexibilities to the system's advantage so that machine utilization, production, and overall efficiency could increase. With these goals in mind, various FMS loading objectives and control strategies were developed and applied to data from an existing FMS, with interesting results. As measured by the production rate and machine utilizations, several

-5 - objectives performed much better than that of balancing the workload, despite the fact that they produced highly unbalanced systems (Stecke [1977], Stecke and Solberg [1981b]). Such results encouraged subsequent research by the author and others (for example, see Kusiak [1983]) to investigate FMS grouping and loading problems. Various approaches, models, results, and solutions are coordinated in this paper. In the following section, the hierarchy of problems, models, and solutions is presented. First, aggregate grouping and loading problems are defined and some previous results are reviewed. Then, similar information is provided for detailed grouping and loading problems. The interface between theoretical results and solutions at the aggregate level and the detailed level models is also given in ~2. The use of the aggregate level model and results and the detailed level models to solve realistic grouping and loading problems is described in ~3. Suggestions for future research and further refinements are provided in ~4. 2. THE HIERARCHY 2.1 Aggregate and Detailed Level Models At an aggregate level, a single class closed queueing network (CQN) model of multiple server queues (machines) is used to represent an FMS. This model requires only aggregate input requirements to output average values (mean production rate and mean queue lengths, for example). This model is useful for several reasons. First, it considers congestion resulting when different parts are competing for the same machine tool. Second, CQN models have been shown to be robust, even when they require distributional assumptions and queue disciplines quite different from the actual system distributions and queue disciplines. (See, for example, Giammo [1976],

-6 - Lipsky and Church [1977], Rose [1976], Solberg [1977], and Suri [1983].) The observed robustness of steady-state results is surprising also because the model requires that most information be aggregated into average processing times and relative visit frequencies of the parts for each machine tool (or machine group). Within the framework of a CQN, the measure used here to evaluate solutions to the grouping and loading problems is the expected production rate. Then at the detailed level, the FMS grouping and loading problems are formulated in all detail as nonlinear mixed integer programs. This model is useful for several reasons. First, it allows consideration of all available FMS information, such as the actual processing time, cutting tools required, and tool slots required for each operation, while considering all relevant constraints. Second, it can result in an optimum solution. Third, heuristic approaches can be developed that are based on the MIPs. The measure used to evaluate solutions is the production rate. At each level, suppose that it has already been decided which part types (and also their relative production ratios) shall be simultaneously machined over the next production period. Pallets and fixtures of each fixture type have also been allocated among the part types to result in revised relative production ratios. 2.2 Aggregate Problems and Results The information that is suppressed at the aggregate level includes the actual deterministic operation times, cutting tools and tool slots required, and machine types required. It is assumed at the aggregate level using the CQN model, without loss of generality for the purposes here, that there is a single part type and a single machine type. Grouping and loading are performed

-7 - within each machine type. The generalizations will be described. The aggregate grouping and loading problems are now defined. Aggregate Grouping Problem: Partition the m machine tools into g machine groups to maximize expected production. Machine tools in the same machine group are said to be pooled, are identically tooled, and are therefore physically capable of performing the same set of operations during real-time control. Pooling, in conjunction with real-time, on-line control, implies that a part whose next operation requires one of these pooled machine tools need find only one machine free. As a result, many regular system performance measures can only improve, relative to a system with no pooling. Also, pooling machines provides redundancy in the case of machine breakdowns. Aggregate Loading Problem: Allocate a total, fixed amount of work among a system of (grouped) machines to maximize expected production. The workload assigned by parts to each machine group i is proportional to the relative frequency of visits by parts to group i multiplied by the average processing time of an operation performed by a machine tool in group i. These parameters are very easy to calculate. Then the performance measure using the CQN model, the expected production, Pr(g,n;S,X), is defined as a function of g (the number of groups); n (the number of parts or pallets); S (a partition of a m machine tools into g groups) = [sl,s2,...,s ], where s. is the number of machine tools in group i; and X (an allocation of work among the machine groups) = [x1,x2,...,xg] where x. is the workload assigned to group i. (See Stecke and Solberg [1981a] for additional details.) The optimal S (the best grouping) and the optimal X (the best loading) are determined.

-8 - Some previous mathematical programming results are used in conjuction with the CQN model to solve these aggregate problems. First, symmetric functions (Berge [1963]) and symmetric mathematical programming (Greenberg and Pierskalla [1970]) are applied to obtain some theoretical results concerning the optimality of balancing workloads (see Stecke and Morin [1985]). Then, CAN-Q (Solberg [1980]), a computer program that uses an efficient algorithm of Buzen [1971] to solve product-form CQNs to obtain steady-state measures, is used to provide some theoretical and operational results. The aggregate solutions that can be used (Stecke and Solberg [1985]) are now summarized. Aggregate Grouping Solution: All possible partitions of m machine into g groups are ordered according to expected production. In particul i. Fewer groups are better; i.e., pool as much as possible. ii. If constraints define that g groups of m machine tools are requ then the more unbalanced configuration provides the larger maxi expected production. The mathematical statements of these results are now provided. The maci groups are ordered according to increasing size, that is, s < s2 <... Define: maximum Pr(g,n;[s1,...,s ],X) to be the maximum expected produc X g from the particular configured system, where X = [x1,...,x ] and S = [S1,...,s ]. Then for any integers, i and k > 0, we have that: 1) maximum Pr(g,n;[sl,...,si+ k,...,s - k],X) is strictly less than X g maximum Pr(g,n;[sl,...,si,...,s ],X); X 2) Pr(g,n;[sl,...,si+ k,...,s - k),S) is strictly greater than Pr(g,n;[sl,...,s ],S); tools ar, lired,.mum line < s. _ g:tion

-9 - 3) maximum Pr(g,n;[sl,...,s,... s,... sg],X) is strictly greater than maximum Pr(g,n;[sl,...,si+ k,..,sj,.,s ],X), X for s + k = s + k =... = '. f or si i+l J Aggregate Loading Solution: The solution is a set of optimal allocation ratios, x*x*...,x*, or the theoretically best ratios at which the g groups should be assigned work so as to maximize the expected production of the FMS. In particular, 1. If all groups contain the same number of machine tools, then a balanced workload per machine is optimal. 2. For a system of unequally sized machine groups (the better configuration), unbalancing the assigned workload per machine is optimal. In addition, if a perfect "unbalance" is not possible, then it is better to overload the larger group than otherwise. 2.3 Detailed Problems and Solutions The detailed problems consider the actual FMS factors and constraints such as tool magazine capacity, integrality of the decision variables, processing times, and machine type requirements. The cutting tools and tool slots required for each operation need to be known in order to use the additional available magazine storage capacity that is obtained from avoiding the unnecessary duplication of cutting tool assignments as well as the tool slot overlap of some larger cutting tools. The detailed problems are now defined. Detailed Grouping Problem: Partition the m machines into g groups subject to technological and capacity constraints of the FMS so as to maximize expected production. Detailed Loading Problem: Allocate the operations and associated cutting tools of a selected set of part types among the machine groups subject to the technological and capacity constraints of the FMS and according to some loading objective.

-10 - These problems are formulated in all detail as nonlinear mixed integer programs (Stecke [1983a]). The solution procedures are now outlined in brief. Detailed Grouping Solution: First, a nonlinear mixed integer problem can be solved to find the minimum number of machine tools of each machine type i, g., that are required to perform all operations of the chosen set of part types. Then the aggregate grouping solution is used to determine immediately the partition of the m machine tools into gi groups that theoretically maximizes expected production subject to the FMS constraints. The solution to the nonlinnear MIP also provides a feasible loading of operations and tools on each machine tool. Detailed Loading Solution: The solution is an assignment of the operations and associated tools to machine groups. Table 1 suggests six possible loading objectives, each applicable to different types of flexible manufacturing systems. The applicability of each depends on the particular manufacturing situation and problem specifics. TABLE 1 LOADING OBJECTIVES 1. Balance the assigned machine processing times. 2. Minimize the number of movements from machine to machine, or equivalently, maximize the number of consecutive operations on each machine. 3. Balance the workload per machine for a system of groups of pooled machines of equal sizes. 4. Unbalance the workload per machine for a system of groups of pooled machines of unequal sizes. 5. Fill the tool magazines as densely as possible. 6. Maximize the number of operation assignments.

-11 - Each objective in Table 1 defines a nonlinear integer problem that has been mathematically formulated. Situations in which each might be applicable are described in ~3. Several methods have been proposed to solve the nonlinear integer problems. First, since the nonlinear terms are products of 0-1 integer variables, one method suggested to solve these problems exactly involves manually linearizing the nonlinear terms. Several linearization methods were examined and one was chosen to apply to data from an existing FMS. Several problems were solved in reasonable time (minutes) using a standard MIP code. The solutions demonstrate the value of considering tool duplication and tool slot overlap to allow additional magazine storage capacity despite the consequential increase in the size of the linear integer programs (Stecke [1983a]). The need was recognized for a specialized, self-contained, more efficient, computerized algorithm to quickly retool an FMS as often as was required. Subsequently, an efficient branch and bound approach was suggested for a subset of the loading objectives of Table 1, in particular, the balancing objectives, with or without pooling (Berrada and Stecke [1983]). The branch and bound algorithm can solve most FMS loading problems in a reasonable amount of CPU time. However, for large loading problems, heuristics should be used to find good solutions. Whitney and Gaul [1984] provide a heuristic approach for a balancing loading objective, while Stecke and Talbot [1983] suggest heuristics for several of the loading objectives. 3. IMPLEMENTATION Some of the queueing network results can be applied directly to the detailed problems. Otherwise, an aggregate level CQN problem is solved to provide some of the input for the detailed formulations. Since the grouping

-12 - problem naturally precedes the loading problem in practice (operations are assigned to groups of machines), it is solved first in the suggested hierarchical procedure. It may be possible to solve the grouping and loading problems together. Alternatively, iteration between the two problems may be required to converge to good working solutions. Recall that for the part types under consideration for simultaneous machining, the machine type, tools and tool sizes, and processing time required for each operation are known. 3.1 Realistic Grouping Problems The procedure to follow to solve real FMS grouping problems is now provided. Step 1. For each machine type, determine both the total operation time requirement and an upper bound on the total number of tool slots required. The latter is found by summing the number of tool slots required by all cutting tools for all operations that require that machine type. This number is an upper bound because neither tool duplication nor tool overlap is accounted for yet. Dividing the latter by the number of slots in each tool magazine, and rounding the fraction up, gives an upper bound on the number of machine tools of each type needed to perform all required operations. a) If each upper bound on the number of required machines of each machine type equals the minimum number of required machines of each machine type (gi), go to Step 2. (For each machine type, the factors necessary to determine whether the upper bound is minimum include: the number of slots in the remainder of the

-13 - above quotient, the amount of cutting tool duplication, and even the number of large tools.) b) For any upper bound that might be larger than the minimum number of machines for a machine type, say i, the nonlinear formulation for grouping (see Stecke [1983a]) can be applied to find the minimum number of required machines (gi). Step 2. The aggregate grouping solution immediately provides the optimal partition of the mi machine tools of type i into gi groups that maximizes expected production. An additional, useful output from the first step is a candidate loading, which is a feasible assignment of the operations and cutting tools among the gi machine groups that conforms to the maximal pooling constraints that are also found. 3.2 Realistic Loading Problems The aggregate loading solutions, obtained through the use of the CQN model, relate only to the first, third, and fourth objectives of Table 1, the balancing or unbalancing objectives. These three objectives are discussed shortly. We also describe how the aggregate results can be used and we describe procedures to use to provide solutions at the aggregate level; both serve as input to the detailed formulations dictated by these three objectives. The nonlinear integer problems derived from objectives 2, 5, and 6 are also discussed. First, various situations in which each loading objective is applicable are described. 3.2.1 Applicability of Each Loading Objective. The aggregate grouping solution indicates that it is best to pool as much as possible. In addition, if maximum pooling is not technologically feasible,

-14 - the best partition of m machines into g groups is known. However, if many different cutting tools are needed to manufacture the current set of operations, then perhaps no pooling is possible. At the same time, there may be enough spare storage capacity in some tool magazines to allow several operations to be assigned to more than one machine tool. We call such multiple operation assignments: partial pooling. The motivation for the fifth and sixth objectives is that via some partial pooling, they allow an increase in system flexibility (even when no pooling of machines is possible) by providing alternative routes for at least some of the parts through the FMS. The second objective, to minimize movements, is very different from the others. The idea here is for a particular part to remain at its current machine as long as that machine tool can perform the next consecutive operation(s), rather than to move it for the purpose of better balancing the machine workloads. By remaining on the same machine, unnecessary travel time (to a next required machine) and waiting time (for the potentially busy next machine to become free) are saved. This objective can be seen to be applicable when travel time is long relative to processing time and also when the material handling system is a bottleneck. In addition, it has previously been demonstrated that minimizing movements proved better than balancing when both objectives were applied using data from an existing FMS. In this case, the transporters did not slow down the operation, travel time was short relative to operation time, and often travel could occur while the next machine was completing its current operation. Minimizing movements was shown to be superior even though the resultant system was highly unbalanced and there was no pooling (Stecke [1977]). In general, additional system performance benefits can also be realized when the objective of minimizing movements is applied in conjunction with pooling objectives.

-15 - 3.2.2 Relationship between the Aggregate and Detailed Loading Problems. There is a relationship between the two aggregate and detailed levels for both the balancing objectives, 1 and 3, and the unbalancing objective, 4. If the aggregate grouping solution is a balanced configuration of groups, then a balanced loading per machine is also optimal. Then the loading problem is solved by using the nonlinear formulation associated with objective 1 or 3. This nonlinear integer formulation for balancing can be solved either by linearizing (see Stecke [1983a]) or by branch and bound (see Berrada and Stecke [1983]) for optimal solution methods. For very large problems, heuristics can be used (see Stecke and Talbot [1983] and Whitney and Gaul [1984]. If the aggregate grouping solution is an unbalanced configuration, then the optimal allocation ratios, xt, must be determined before the unbalancing loading objective 4 can be applied. The determination of the optimal allocation ratios is now described. To simplify notation, it can be assumed without loss of generality that there is only one machine type, since the algorithm is applied identically for each machine type. Similarly, it is assumed without loss of generality that there are n identical parts or pallets in the system. If n has not yet been determined, the algorithm can be applied once, for a specified, relevant range of n, to also help determine the appropriate number of pallets that should be in the system. In general, the problem is to determine the minimum number of pallets (in-process inventory) required to maintain desired production ratios. See Shanthikumar and Stecke [1984]. In the following, since the configuration of machine tools into groups is unbalanced, si * sj, for some i and j.

-16 - Algorithm to Determine the Optimal Allocation Ratios 1. Order the g machine groups so that s1 < s2 <.. s g. 2. A balanced allocation is X = [s1,s2,..,s ]. For each i, the "direction" (either less than, greater than, or equal to s.) of each optimal allocation ratio, x*, is known (Stecke and Solberg [1985]). Then, if the middle machine tool (m/2) is in group i, a reasonable initial starting point in the search for the optimal ratios is, for some S > 0, [X, * * *,Xg] = [1 - (1-i)e,...,s i -, Si, si+ + e, si+2 +2~,...,s + (g- i)E]. 3. Fix g-2 of the xk. Vary xi and xj, i < j. The production function, Pr(g,n;S,X), is evaluated along the hyperplane xi = Xk x. =K x k=1 k k~i,j for a range of xi and xj, such that xi/si e [a,l) and xj/sj E (k-a, k-l], for some fixed a < 1 (i.e., a =.7). The maximum expected production on the hyperplane is found. Many production functions can be evaluated in seconds of CPU time by using a computer program that is a variation of Solberg's CAN-Q [1980]. (A listing of the adapted program can be found in Stecke and Solberg [1981a], which also provides several examples that demonstrate the use of the program.) 4. The optimal allocation ratios that produce the maximum expected production have been found for the particular hyperplane. The computer program also provides sensitivity information on the change in the expected production that would result from a change

-17 - in a workload parameter. This indicates both a direction and magnitude of a possible change to use in the search for the optimal xi's. This sensitivity information is used to choose a different g-2 of the xk to fix. Return to Step 3. Continue to search along different hyperplanes until the sensitivity analysis indicates that the optimum allocation ratios, x*, have been determined. Since the production function, Pr(g,n;S,X), monotonically increases and then decreases as a function of X, it is possible to develop a computer program to search for the unique, optimal allocation ratios. See Stecke and Solberg [1981a, 1985] and Stecke [1983b] for information on such properties of the production function. 3.2.3 Aggregate Results as Input for the Detailed Loading Models. When the optimal allocation ratios, x*, are determined, they are used in the nonlinear objective function formulated from the fourth loading objective, unbalancing. Each loading objective in Table 1 gives rise to a different nonlinear integer program. The mathematical formulations, given in Stecke [1983a], can be solved either using an available mixed integer code (after linearizing) or directly, which yields the optimal allocation of operations and cutting tools among the machine groups of the flexible manufacturing system. If the appropriate loading objective is balancing, then the branch and bound algorithm (Berrada and Stecke [1983]) can be used. 4. FUTURE RESEARCH At present, the Algorithm to find the optimal allocation ratios, which is described in ~3.2.2, is implemented by first running the computer program and then using the output to determine which variables to fix and vary subsequently. However, it would be relatively straightforward to close the loop

-18 - and to automatically find these optimal ratios, by imbedding an appropriate search strategy into the closed queueing network program. The solution methodologies reported here are mostly optimum-producing. The nonlinear integer problems have been solved for real grouping and loading problems, defined from real data, on a large computer system (CDC 6600). A standard mixed integer code was used. However, real-time FMS control requires very quick solutions to these planning problems. Most companies do not have a mixed integer code available. Also, these problems would be solved often enough to warrent a special code that is self contained. Such a code does exist for a balancing loading objective, and is needed for the other loading objectives. Future research needs include the development of efficient heuristic algorithms that provide good solutions to FMS grouping and loading problems. This is especially true if larger flexible systems are to be developed having more part numbers introduced. Some heuristics development has taken place, mostly for the balancing objective of the FMS loading problem. All of these procedures should be executable on minicomputers that are now available in essentially real-time. Additional research is also required to determine efficient means to solve all of the planning problems. Most of the software that exists to run these highly automated systems is not very good and is not very flexible.1 1This research was supported in part by the National Science Foundation Grant No. ECS 8406407 and by a grant from the Ford Motor Company, Dearborn Michigan.

-19 - REFERENCES Barash, Moshe M. "Computerized Manufacturing Systems for Discrete Products." Ch. VII-9 in The Handbook of Industrial Engineering, (edited by Gavriel Salvendy), John Wiley & Sons, Inc., New York, NY (1982). Berge, Claude. Topological Spaces. New York: Macmillan, 1963. Berrada, Mohammed and Stecke, Kathryn E. "A Branch and Bound Approach for Machine Loading in Flexible Manufacturing Systems." Working Paper No. 329, Graduate School of Business Administration, The University of Michigan, Ann Arbor, MI, April 1983. Buzen, Jeffrey P. "Queueing Network Models of Multiprogramming." Ph.D. Dissertation, Harvard University, Cambridge, MA, May 1971. Cavaille, Jean-Bernard and Dubois, Didier. "Heuristic Methods Based on Mean-Value Analysis for Flexible Manufacturing Systems Performance Evaluation." In Proceedings of the 21st IEEE Conference on Decision and Control, pp. 1061-1065. Orlando, FL, December 1982. Cavaille, Jean-Bernard, Forestier, J. P. and Bel, Gerard. "A Simulation Program for Analysis and Design of a Flexible Manufacturing System." In Proceedings of the IEEE Conference on Cybernetics and Society, pp. 257-259. Atlanta, GA, October 1981. Dubois, Didier and Stecke, Kathryn E. "Using Petri Nets to Represent Production Process." In Proceedings of the 22nd IEEE Conference on Decision an Control, San Antonio, TX, December 14-16, 1983. Giammo, T. "Validation of a Computer Performance Model of the Exponential Queueing Network Family." Acta Informatica 17, No. 2 (1976), pp. 137-152 Greenberg, Harvey J. and Pierskalla, William P. "Symmetric Mathematical Programs." Management Science 16, No. 5 (January 1970), pp. 309-312. Kusiak, Andrew. "Loading Models in Flexible Manufacturing Systems." Working Paper #05/83, Department of Industrial Engineering, Technical University of Nova Scotia, Halifax, Nova Scotia, Canada, March 1983. Lipsky, L. and Church, J. D. "Applications of a Queueing Network Model for a Computer System." Computing Surveys 9 (1977), pp. 205-221. Rose, C. A. "Validation of a Queueing Model with Classes of Customers." In Proceedings of the International Symposium on Computer Performance Modeling, Measurement, and Evaluation, pp. 318-325. Cambridge, MA: Harvard University, 1976. Shanthikumar, J. George and Stecke, Kathryn E. "Reducing Work-In-Process Inventory in Certain Classes of Flexible Manufacturing Systems." Working Paper No. 407, Graduate School of Business Administration, The University of Michigan, Ann Arbor, MI, December 1984.

-20 - Solberg, James J. "A Mathematical Model of Computerized Manufacturing Systems." In Proceedings of the 4th International Conference on Production Research. Tokyo, Japan: August 1977. Solberg, James J. "CAN-Q User's Guide." Report No. 9 (Revised), NSF GRANT No. APR74 15256, School of Industrial Engineering, Purdue University, W. Lafayette, IN, July 1980. Stecke, Kathryn E. "Experimental Investigation of a Computerized Manufacturing System." Master's Thesis, Purdue University, W. Lafayette, IN, December 1977. Stecke, Kathryn E. "Formulation and Solution of Nonlinear Integer Production Planning Problems for Flexible Manufacturing Systems." Management Science 29, No. 3 (March 1983a), pp. 273-288. Stecke, Kathryn E. "On the Nonconcavity of Throughput in Certain Closed Queueing Networks." Working Paper No. 356, Graduate School of Business Administration, The University of Michigan, Ann Arbor, MI, December 1983b. Stecke, Kathryn E. and Browne, Jim. "Variations in Flexible Manufacturing Systems According to the Relevant Types of Automated Materials Handling." Material Flow (June-July, 1985), forthcoming. Stecke, Kathryn E. and Morin, Thomas L. "Optimality of Balancing Workloads in Certain Types of Flexible Manufacturing Systems." European Journal of Operational Research 20, No. 1 (1985). Stecke, Kathryn E. and Solberg, James J. "The CMS Loading Problem." Report No. 20, NSF Grant No. APR 74 15256, School of Industrial Engineering, Purdue University, W. Lafayette, IN, February 1981a. Stecke, Kathryn E. and Solberg, James J. "Loading and Control Policies for a Flexible Manufacturing System." International Journal of Production Research 19, No. 5 (September-October, 1981b), pp. 481-490. Stecke, Kathryn E. and Solberg, James J. "The Optimality of Unbalancing Both Workloads and Machine Group Sizes in Closed Queueing Networks of Multiserver Queues." Operations Research (1985), forthcoming. Stecke, Kathryn E. and Talbot, F. Brian. "Heuristic Loading Algonithms for Flexible Manufacturing Systems." In Proceedings of the Seventh International Conference on Production Research, Windsor, Ontario, Canada, August 22-24, 1983. Suri, Rajan. "Robustness of Queueing Network Formulas." Journal of the Association for Computing Machinery 30, No. 3 (July 1983), pp. 564-594. Suri, Rajan and Hildebrant, Richard R. "Modeling Flexible Manufacturing Systems Using Mean Value Analysis." Journal of Manufacturing Systems 3, No. 1 (January 1984), pp. 27-38.

-21 -Whitney, Cynthia K. and Gaul, Thomas S. "Sequential Decision Procedures for Batching and Balancing in FMSs." In Proceedings of the First ORSA/TIMS Special Interest Conference on Flexible Manufacturing Systems: Operations Research Models and Applications, pp. 243-248. Ann Arbor, MI, August 15-17, 1984.