Division of Research Graduate School of Business Administration The University of Michigan April 1983 Revised Dec. 1984 Revised Oct. 1985 A BRANCH AND BOUND APPROACH FOR MACHINE LOAD BALANCING IN FLEXIBLE MANUFACTURING SYSTEMS Working Paper No. 329-C Mohammed Berrada Centre d'Etudes et de Recherches de Toulouse Toulouse, France Kathryn E. Stecke The University of Michigan Ann Arbor, Michigan Management Science, forthcoming, 1986

I

ABSTRACT A flexible manufacturing system (FMS) is an integrated system of computer numerically controlled machine tools connected with automated material handling. A set of production planning problems for FMSs has been defined (Stecke [1983]), and this paper considers one called the loading problem. This problem involves assigning to the machine tools, operations and associated cutting tools required for part types that have been selected to be produced simultaneously. The part types will be machined during the upcoming production period (say, of one to three weeks duration on average) and according to a prespecified part mix. This assignment is constrained by the capacity of each machine's tool magazine as well as by the production capacities of both the system, and each machine type. There are several loading objectives that are applicable in a flexible manufacturing situation. This paper considers the most commonly applied one, that of balancing the workload on all machines. This paper first discusses a nonlinear integer mathematical programming formulation of the loading problem. The problem is formulated in all detail. Then an efficient solution procedure is proposed and illustrated with an example. Computational results are provided to demonstrate the efficiency of the suggested special-purpose procedures.

A flexible manufacturing system (FMS) can be thought of as an automated job shop consisting of computer numerically controlled machine tools, each with automatic tool-changing capabilities. A computer also controls the movements of parts between machines tools via some material handling system such as wireguided carts or conveyors. Descriptions of particular FMSs can be found in Stecke (1977), Cavaill6, Forestier, and Bel (1981), Stecke and Solberg (1981a), Barash (1982), and Stecke and Browne (1985). The cutting tools required for all operations that might be performed by a particular machine tool are stored in that machine's limited-capacity tool magazine. The technological sophistication of the automatic tool-changing devices virtually eliminates set-up time between consecutive operations for each machine tool. However, a careful system set-up is required before production begins, to best utilize potential production capacity. This planning phase involves several production planning problems (see Stecke (1983)). In brief, these problems are to: (1) select compatible part types for simultaneous machining for the upcoming time period; (2) partition machines into machine groups, each of which can perform the same operations; (3) determine production ratios at which the part types should follow; (4) determine minimum inventory requirements (pallets and fixtures) to maintain the production ratios; (5) allocate operations and cutting tools to the limited capacity tool magazines. This paper focuses on the fifth problem, called the FMS loading problem. To expound a bit, this problem is to assign to the machines, the operations of the selected part types and the tools necessary to perform these operations, subject to the FMS technological and capacity constraints and according to some loading objective, in a way that will best utilize the machines, or maximize production, when the system is running. Once this problem is solved and the cutting tools are loaded into their assigned tool magazine(s), then the system is ready to begin production.

-2 - Such loading problems associated with conventional manufacturing systems require consideration of lot-sizing (because of long set-up times) or assembly line balancing (during the design phase of a production line). The latter sorts of loading problems may require solution only once a year. However, because of FMS capabilities and flexibility, the FMS loading problem need not be restricted by these considerations. Also, this problem requires frequent solution (which can range from about a week to say three weeks). In particular, a new FMS loading problem has to be solved whenever: production orders change; or a part type finishes its requirements (space in the tool magazine is now free for other part types/cutting tools); or a new part type is to begin production (its cutting tools now have to fit in the tool magazines somehow); or when a machine tool goes down, to name a few situations. Because the technology associated with FMSs is still relatively new, various aspects of the FMS loading problem have only recently been studied. See, for example, Stecke (1977, 1983, 1985b), Stecke and Solberg (1981b, 1985), Stecke and Schmeiser (1982), Kusiak (1983), and Stecke and Morin (1985). There are different loading objectives that can be followed, each applicable in different situations. This paper focuses on the loading objective of balancing the workload on all machines, while assigning each operation to only one machine. While somewhat restrictive for an FMS, it nevertheless is the most studied and applied objective, with conventional manufacturing methods as well as flexible manufacturing. There is a very large literature on assembly line balancing and balancing workloads in job shops and FMSs. Balancing is appropriate for a flexible assembly system and an automated transfer line. In these systems, parts flow unidirectionally from machine to machine, sometimes skipping machines. Stecke and Morin (1985) have shown that if each operation is assigned to only one machine, balancing workload per machine

-3 - maximizes expected production. Stecke and Solberg (1985) show that if functionally similar machines are pooled into machine groups** of equal size, then balancing workloads again maximizes expected production. Shanthikumar and Stecke (1986) show that balancing workloads also minimizes work-in-process inventory in FMSs that contain only one machine in a group. This is observed in Stecke (1985a). We note that if an FMS is very reliable, sometimes it can be treated deterministically and operated as a transfer line between periods of change (such as when a new part type is to be introduced for machining or an old part type has completed its production requirements or a breakdown has occurred). Minimal redundancy in machine assignments might be allowed. In some systems, there is no capacity available to allow pooling. A balancing objective is relevant in such situations. However, Stecke and Solberg (1985) show that for a more flexibly-operated system having real-time control, in addition to advantages gained by pooling machines into groups, performance is theoretically further improved by unbalanced rather than balanced partitions of machines into groups. Moreover, for these better unbalanced partitions, expected production is maximized by a particular unbalanced assignment of workload per machine. We shall discuss pooling further in ~5. Other loading objectives have also proved to perform better than balancing with respect to achieving maximum production for certain types of FMSs (see Stecke and Solberg (1981b)). For example, if travel time from machine to machine is long relative to processing time, or if the transporter mechanism is a bottleneck, then minimizing the number of movements can be a better objective than balancing. In fact, the objective of minimizing movements has **Machines in a machine group are said to be pooled, are identically tooled, and are assigned the same operations.

-4 - proven better than balancing for a particular FMS, even when travel time was not long and carts were not bottlenecks (see Stecke and Solberg (1981b)). In Stecke (1983), both the grouping problem (how to best partition m machines into g groups) and the loading problem are defined and mathematically formulated as nonlinear integer programming problems. The nonlinear terms result, in part, from considering the possiblility of assigning several operations, having some common tools, to the same machine. Several loading objectives, each applicable to different types of FMSs, are also defined and formulated. The approach taken to solve these problems was to linearize the nonlinear terms. Several linearization methods were applied (those of Balas (1964), Glover (1975), and Glover and Woolsey (1973, 1974)). The linearizations resulted in much larger constraint formulations. Then the linearized formulations were applied to data from an existing FMS and run to optimality, taking minutes on a CDC 6600 using a standard MIP code. The nonlinear integer formulations can handle any reasonably-sized FMS loading problem. However, in addition to the computer time, the manual linearization process is too time-consuming and unwieldy to warrant frequent application. The procedure could not be easily implemented by management. In addition, the linearized integer problems get large quickly. Either a nonlinear integer code or an integer code (if linearization is performed) is needed. What is required is an efficient and easy to use optimum-producing code. The advent of these new technologies provides opportunities for operations researchers to develop efficient tools that an FMS manager can use to solve his/her everyday production planning and operating problems. It is this goal —to develop a usable, efficient, specialized and self-contained procedure to solve a particular version of the FMS loading problem —that spurred the research presented here. The approach taken in this paper is to bypass the manual linearization step, and to solve the nonlinear problems directly and automatically. A

-5 - sequence of subproblems is defined. In brief, each subproblem is solved by an efficient branch and bound procedure that first solves a simple, relaxed assignment problem, then checks for feasibility, and finally modifies the assignment to correct violated constraints. The modification of the assignment is obtained by solving very small integer problems via branch and backtrack for each machine where a constraint is violated. The optimum solution to the relaxed problem provides a lower bound to the original problem that is used both to fathom nodes in the binary enumeration tree and to select a node for further branching. An intelligent selection criterion is used to choose the most suitable branching variable. Only one of the loading objectives of Stecke (1983) is used, that of balancing the assigned workload on each machine tool. Each operation is assigned to only one machine tool. This is by far the most widely applied loading objective. The paper is organized as follows. In ~1, the nonlinear integer formulation of the particular FMS loading problem, which is to balance the assigned workload on each machine tool, is reviewed. The proposed solution method is described in detail in ~2. An example that illustrates the procedure is provided in ~3, while computational results are given in ~4. ~5 summarizes the results of the paper and discusses the extension of the procedures to another loading objective. 1. MATHEMATICAL FORMULATION After the variables and notation are defined, the constraints and objective function of the considered FMS loading problem will be reviewed. 1.1 Variables and Parameters The subscripts, some preliminary input parameters, and the decision variables of the FMS loading problem are provided in Table I. Additional notation will be provided as required, when the solution procedure is described.

-6 - TABLE I Notation Parameters and Subscripts: I = {i I i=l,...,b} = set of operations J = {j | j=l,...,m} = set of machine tools Pij= processing time of operation i on machine tool j d. = number of slots required in a tool magazine for holding the cutting tools of operation i t. = capacity of the tool magazine of machine tool j ik = number of slots saved as a result of having common tools when operations i and k are assigned to the same machine tool = count of the number of spaces (slots) occupied by the tools contained in the intersection of the sets of tools required by operations i and k wB = number of slots saved when the operations in subset B are assigned to the same machine tool P = index set of compatible part types that are to be produced simultaneously on the system of machine tools in the upcoming production period aki = production ratio (relative to the remaining part types in P-{k}) at which operation i of part type k will be produced r. = relative workload, or utilization, of machine tool j Decision Variables:, if operation i is assigned to machine tool j; ij =, otherwise.

-7 - 1.2 Constraint Formulations The constraints of the loading problem are as follows. First, each operation must be assigned to at least one machine tool of the machine type required by the operation. Throughout, each operation is assigned to only one machine tool. Then m i xij = 1, i=l,...,b. (1) j=l It follows that x.. = 0 if operation i cannot be performed by the machine Ij type specified by machine tool j. In this case, Pij = C. Second, the tool magazine capacity constraints, which relate the number of tool slots required by the operations assigned to each machine tool to the total number of slots in each machine's tool magazine, in their simplest form, are b E dixij < tj, j=,..,m. i=l However, this capacity constraint is only sufficient to insure that the tools required by the operations that are assigned to machine tool j can all be contained in its tool magazine. If the tools that are common to several operations and the slots that are saved by a suitable positioning of the tools are taken into consideration (see Figure 1 to demonstrate the latter), the capacity constraints are then more accurately expressed by: b i dixij + TC (x) < tj, j=l,...,m (2) where b TCj(x) = I (-1)P I w xij p=2 VB CI ieB 31BI=p

-8 - or = I (-1)iB wB min{xij}, j=l,...,m. (3) VBCI B ieB j 3 |B|~2 Note that TC.(x) < 0, for all j. The nonlinear terms of equation (3) arise J - from the tool slot overlap. For example, if you've taken out common tools from all pairs of 3 operations, some tools may have been taken out too much and so have to be put back in. 0> ^TOOL SLOTS ~p O 0 TOOL [0)o MAGAZINE 0 TOOLS FIGURE 1. Tool Magazine. A third constraint type is required to specify the relative workload assigned to machine tool j: b rj = aiijxj, j=l,...,m. i=l Throughout, the subscript k is dropped from the production ratios aki. These are relative ratios at which the selected part types are to be maintained during production. Methods to help determine these, for situations of both dependent and independent demand, are provided in Stecke (1985a). When all r. are equal, the system is perfectly balanced. However, perfect balance is usually impossible to attain because of the discreteness of the processing times. Finally, there are the integrality constraints: x.. = 0 or 1, for all i, j. (4) 13

-9 - 1.3 Problem Formulation The production rate of a particular type of FMS, a deterministic transfer line, is limited by the throughput of the bottleneck machine, which is specified by the largest r.. This is the intuition behind the common belief that balancing workloads corresponds to maximizing the production rate. The approach taken here to balance the FMS is to minimize the workload of the bottleneck machine. Let 6 be an upper bound on the machine workloads. Then the problem is to find {xijli=l,...,b, j=l,...,m} to: Problem (P) minimize 6 subject to (1), (2), (3), (4), and b aiPijxij 6, j=l,...,m.(5) i=l J 1 2. SOLUTION METHOD The solution procedure can be summarized as follows. In ~2.1, a sequence of subproblems is defined by fixing the maximum workload, 6, (in equation (5)) to be 6 for each subproblem Z. The sequence of solutions converges to an an e-optimal assignment. If 6* is the optimal solution of problem (P), then an s-optimal solution, 6, is such that J6* - 6 | < E. To decrease the size of the subsequent problems, we set 6 to be the midpoint of an interval that contains the optimal 6 of Problem (P). Then a check is made to see if 6 is greater (or not) then 6,. The solution of each subproblem is used to decrease the interval size: depending on this solution, either the lower bound increases or both the lower bound increases and the upper bound decreases. An efficient branch and bound procedure is developed in ~2.2 to solve each subproblem optimally. First, a relaxed integer problem is solved (in ~2.2.1) and feasibility is checked. Then the assignment is modified in the least-cost way for violated

-10 - constraints by using a branch and backtrack procedure on very small singlemachine integer problems. The optimal solution of this relaxed problem provides a lower bound on the solution of the original problem to allow node selection and fathoming. Finally, the criterion for selecting the branching variable is described in ~2.2.2. 2.1 Subproblem Generation Problems (Pg) are a sequence of subproblems, each finding a feasible solution of (P), that converges to an e-optimal solution to Problem (P). Rather than settling for an arbitrary feasible solution, the procedure uses an auxiliary objective function for each subproblem, to find a solution that allows a maximum reduction of the interval containing 6P in the subsequent subproblem. Also, each subproblem, (P6), is defined by a fixed workload upper bound, 6,. Problem (P ) is reformulated from Problem (P) as follows. For a fixed 6, maximizing (6 - rj) for all j can be achieved by m m b maximizing (mS - I rj) <===> minimizing )] i ap..x.ij j=l 3 j=l i=1 J 1 Thus, the problem is to find x.. to: Problem (P ) m b minimize Z = a. iijxij j=l i=l subject to (1), (2), (3), (4), and b aiPijij < 6' j=1,..*., m. (5') The subproblems are generated as follows. Let LV and UV be a lower bound and upper bound, respectively, of 6.. (Initially, LV = 0 and UV =.)

-11 - Fix 6 = (UV + LV)/2. (Initially, 60 = co.) An optimal solution to Problem (Pa.) is found. If a solution exists, then UV is updated to equal the largest machine workload associated with this solution. The auxiliary objective helps to reduce this largest machine workload. Also, LV is set equal to m m I r./m, if I r./m > LV. The reasoning behind this updating of LV is j- J j=1 j provided in Appendix C. If a feasible solution does not exist, then LV is updated to equal 6%. The procedure is terminated when the difference between UV and LV is smaller than ~. An e-optimal solution is sufficient because: 1. processing times are allocated among machines in discrete quantities; and 2. processing times may fluctuate slightly because of behavioral anomalies and because of adaptive processing capabilities of machine tools. e is set equal to min {a.p../m}. The choice of c is motivated as follows. Li,j Let x and x' be two feasible solutions of Problem (P). The distance between x and x', as measured by the objective function of Problem (PBQ), can be evaluated as: d(x,x') = Imax rj(x) - max r.(x')l. J j J Define e* as: ~* = min {d(x,x') I x,x' are such that d(x,x') > 0}, when (P) is feasible. Since the set of feasible solutions is finite, e* is greater than zero (unless all feasible solutions are optimal!). Clearly, for all e < e*, an e-optimal solution is optimal if one exists. Increasing the number of machines tends to increase the number of feasible solutions, and hence decrease e*. To account for this,

-12 - E = min {a.pij/m} i,j 1 provides a reasonable heuristic approximation of e*. An accurate value of ~* is very difficult to calculate, and unnecessary in any case. The generation of subproblems required to solve the FMS loading problem is precisely described by the following algorithm. The Solution Algorithm STEP 1. INITIALIZATION: Set LV = 0, UV = c, Z = 0, 6 = <, and aiPij = min { ap-. i,j STEP 2. SOLUTION: Find an optimal solution, x, of Problem (PS ) (to be described in ~2.2). STEP 3. UPDATE BOUNDS: If a solution exists, set UV = max {rj} and m LV = Max {LV, ( I r)/m}; j=1 otherwise, set LV = 6k. STEP 4. CHECK STOPPING THRESHOLD: If UV- LV > e, set 6+1 = (UV + LV)/2 and go to STEP 2; otherwise, go to STEP 5. STEP 5. STOP: If at =, then no solution exists; otherwise, the solution found last is s-optimal. The initialization of 60 to be infinity is equivalent to dropping the utilization constraint (5) of Problem (P5 ), which allows an initial test for problem feasibility.

-13 - 2.2 Solving Subproblem (P6 ) Finding a feasible solution to an integer problem is as computationally complex as finding an optimal solution (Karp [1975]). However, stopping an optimization problem early with a feasible solution is actually much quicker in practice. Hence, it might seem that finding a feasible solution of (P6 ), without updating LV, could suffice in STEP 2. However, computational experience has indicated that, in this case, the number of generated subproblems (P6 ) is very large and most of them are infeasible, i.e., time-consuming to deal with. It would be much more efficient to find optimal solutions. Decreasing the size of interval [LV, UV] is then important. Consequently, many subproblems (Ph) (mostly the infeasible ones) are no longer considered (because of the improved LV). This is proven in Appendix C. Problems somewhat similar to (P6 ) have been considered by Sandi (1975), Ross and Soland (1975), Caie, Linden, and Maxwell (1980), and Graves and Lamar (1981). The main difference here is the inclusion of the highly nonlinear terms in TC (x) of constraint (3). (P ) is solved via branch and bound (see Garfinkel and Nemhauser (1972) and Salkin (1975)). The binary enumeration tree for the branch and bound procedure consists of nodes which are partial assignments. At each node, a lower bound of the objective function is obtained by solving very small zeroone problems. At every step, the node with the least lower bound is selected from the list of dangling nodes for further branching. 2.2.1 Calculation of the Lower Bound at Node K during Solution of a Relaxation of Problem (P ) Let FK be the set of operations that have been assigned at node K: FK = {ieI ) there exists j.iJ such that xK. = 1}, 10i

-14 - K K where x is the partial solution at node K. Z(xK) is the value of the partial solution. We consider the nonlinear tool magazine capacity constraints, (2) and (3), and the workload constraints, (5), to be the "complicating" constraints of Problem (P6 ), and the remaining constraints, (1) and (4), to be "easy" constraints. Our relaxation of Problem (P ) consists of dropping the complicatting constraints. Thus at node K the relaxed problem is the following simple integer program: Problem (P R)K ~ --- —-— 6 R —) m minimize Z = a p a p x j=l ie(I-FK) a ij ij m K subject to xi. = 1, ie(I-FK) (1) j=1 x.. = 0 or 1, jeJ and ie(I-F ). (4) 13 The solution to problem (P. R)K is that each unassigned operation is assigned to the machine tool which results in the least load. A solution (x*K) of (P6 R)K is easily found for each unassigned operation ie(I-F ) from the index j.iJ such that: aij = min {a.iPij (i,j) i G }, ai' jeJ ''J where GK = (i,j) x = 0}. ij *K *K Then the solution (x K) is defined by x.. =1, and x. = 0 for j * ji and 'Ji ij i I FK. In the case of a tie, the algorithm selects the first minimum {aiPij}. A first estimate of the lower bound of the objective function is thus:

-15 - LBK = Z(xK) + Z(x*K) = Z(xK xK) a= a. + a.p,. ieFK Piji iFk 1 iji If (xK) completed by (x K) satisfies the constraints (2), (3), and (5), then it is an optimal solution of (P ). Otherwise, for each machine whose corresponding constraints are violated, we must modify the assignment with the least possible increase of the objective function in order to find a feasible solution to Problem (P6). In addition, the lower bound is improved. Let I be the set of operations assigned to machine j in the solution (x*K); IKn FK = 0 (see Figure 2); and j J1K be the set of machines for which either the capacity constraint or the workload constraint or both are violated. We define for all i e I^: c. = the minimal incremental cost that would result from a reassignment of operation i =min {a Pik a.Pi k * ji and (i,k) e GK}; 1k1Pk 1 b. = the overflow of the violated capacity constraint, i.e., the additional number of slots that are required in the magazine of machine tool j K *K K *K = d x. + i d.x.. + TCj(xK U K) - tj; ieFK i 1J i4FK i 1J a. = the workload overflow of machine j ap j a.*K - ieFK i 1mj ai iFK o m o ais t For each j c JK we must reassign one or more operations to other machines. Let yij be the reassignment variable to be used in the reassignment problem, (PR.)K, for each machine j c J,K at node K. The problem is: 3

-16 - Problem (PR.)K subject to subject to minimize Z. 3 I diYi + ij IK iYij -i~c lI ij 3 TCG (y) > b, 3 J TC!(y) = 3 VBC IK 3 |B2 31 B 1>2 (-1) IBI+1 w max iB {Yij}* > K aiP ij Yi > iI or Yi. = 0 or 1, J~ icIK ji where the decision variables, Yij, are: y 1, Yi = 0l, if operation ieIK another machine; otherwise. must be reassigned to FIGURE 2. Subsets of Assigned Operations at Node K. (*) The proof that the maximum operator is correct here derivation of the TC!(y) term in Appendix A. 3 is provided through the

-17 - The lower bound is improved by adding to Z(xK x K), the sum of the *K K objective function values Z.(y ) obtained by solving problems (PRj) for all jejK: LBK = Z(xK) + Z(x*K + (y*K). jeJtK J The reassignment problems, (PR.)K, for each machine jeJ'K are solved by a branch and backtrack procedure (Balas [1965]). This procedure is very quick because of the small size of the single-machine problems, (PR.) K 2.2.2 Selection of the Branching Variable *K The selection of which variable among the x.i to branch on is one such *K that y.. = 0, since these variables correspond to operations which will not i* * be reassigned. Intuitively, it is better to choose i and j. so that the objective function of (P ) would increase more if i were assigned to a * * * machine other than j.. Hence, the branching variable, x.i, can be found by using the following priority indices: i c Arg max {c. I y. = 01}. i iJi However, some preliminary computational experience has indicated that it is important to consider also both the remaining number of slots and the amount of work capacity available at each machine tool at node K to get a better choice of the branching variable. Tests with various sets of examples have shown that convergence towards the s-optimal solution is, in most cases, * * faster by using the following rule: select x.. such that: zJi i e Arg max {c / [d /(t. - I d ) + ap ( - a p )]} i ' Ji keFK k i Ji keFK k kji Ji ji *K K such that y.. =0 and where F. is the set of operations already assigned to Jh i Ji machine j i at node K.

-18 - This selection rule introduces an intelligent weighting of the reassignment penalties, ci. The c. 's are divided by a sum of: 1. a tool-storage-saving factor, which is the number of tool slots required by operation i per number of slots remaining in machine tool ji's tool magazine; 2. a utilization-saving factor, which is the workload required for operation i on machine tool ji per unit of work capacity remaining. This branching rule gives a lower reassignment priority to those machine tools that are already significantly loaded or tooled, among those machine tools that are candidates for reassignment of the operations. Once the branching variable is chosen, two nodes (two new candidate problems) are generated and the parameters associated with problem (P6 ) are updated to account for the new partial solutions at both nodes K + 1 and K + 2. Once problem (Ps ) is solved, the bounds of the maximum workload 6 are updated. Then a check is made to see if the interval size is less than e. If not, the next subproblem (P ) is solved. Otherwise, the e-optimal solution has been found (if a solution exists). 3. EXAMPLE To illustrate the branch and bound procedure, consider the following example consisting of three machine tools and eight operations. The data, including the weighted operation times, are provided in Table II below: TABLE II Three-Machine Tool, Eight-Operation Data 1 2 3 4 5 6 7 8 tj 3.0 4.0 2.5 6.0 4.0 2.0 2.4 5.0 20 3.4 3.5 3.0 5.5 4.1 3.0 2.0 4.7 20 2.8 4.2 2.7 6.0 5.0 2.5 2.6 5.2 20 6 7 6 10 8 5 4 9 *,,,,~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

-19 - An entry (i,j) in the table represents the term aipij. Moreover, assigning operations 1 and 2 together can save two slots in a tool magazine, assigning operations 1 and 4 to the same machine can save three slots, operations 3 and 5 can save two slots, operations 5 and 7 can save one slot, and operations 7 and 8 can save two slots. The Solution Algorithm STEP 1. INITIALIZATION: Set LV - 0, UV = o, 60 =, and ~ = 2/3 = 0.67. STEP 2. SOLUTION OF (P ): Node K = 1: 1 1 1 F =; G1 = x =. By inspection of Table II, the solution of (P6 R) is 60 *1 *1 *1 *1 *1 *1 *1 *1 13 = 22 31 =42 51 61 72 82 *1 and all other x.. = 0. 13 The lower bound is LB1 = Z(x1) = 27. However, this solution is not feasible for (P60 ) because the capacity constraint on machine 2 is violated (d2 + d4 + d7 + d8 - w78 > t2). To solve the problem, we solve a reassignment problem for machine 2: (PR2) minimize Z2 =.5Y22 +.5Y42 +.4Y72 + 3Y82 subject to 7Y22 + 10Y42 + 4Y72 + 9Y82 - 2 max {Y72,Y82} > 8 Yij = 0 or 1, for all i,j. UJ

-20 - Problem (PR2) is solved by a branch and backtrack procedure (see Figure 3). *1 * The optimal solution is y2 = 1 and all other yij are 0. Then Z2.5, and the tighter, improved lower bound is now 27.5. Y42- / Y42 =0 2 First Feasible Solution Y82 3 \ 82= With Z* =.5 Fathomed- No Feasible Fathomed Solution Can Be Better Than The First Found FIGURE 3. Branch and Backtrack Tree for Problem (PR2) The branching variable is x72 because: 7= Arg max {c./[di/t ] such that y = 0} i '. ' 2i ' i2 and the process is repeated (see Figure 4). ( ) LB1 =27.5 X72= 1// X72 LB2= 27.5 LB3 27. LB4=27.5 X61F X61 =0 LB4=27.5( i LB5=28 FIGURE 4. Branch and Bound Tree for Problem (P6 ). 0

-21 - Node K = 2: 2 2 JI~l 2 F = {7}; G = {(4,2)}, because Y4 2 == x. F y42 =72 The solution of (P6 R) is 60 *2 *2 *2 *2 *2 *2 *2 13 ~22 31 41 51 61 82 *2 and all other x.. = 0. 1I *2 *2 Note that setting x43 to 1 rather that x41 provides the same minimum *2 a.pij = 6. The algorithm arbitrarily selects the first minimum (x4 =1). The lower bound is LB2 = Z(x ) + Z(x ) = 27.5. This solution is not feasible for (P6 ) because the capacity constraint on machine 1 is violated (d3 + d4 + d5 + d6 - w36 > t1) We solve a reassignment problem for machine 1: (PR1)2 minimize Z1 =.2y31 + Oy41 +.1y51 +.5Y61 subject to 6Y31 + 10Y41 + 8y51 + 5y61 - 2 max {Y31,Y51} > 7 Yi. = 0 or 1, for all i,j. The optimal solution, found by branch and backtrack, is y41 = 1 and and all other Yil are zero. Then Z1 = 0. The branching variable is x61 —see Figure 4. Node K = 3: 3 3 3 F = 6; G = {(7,2)}; x = 2 = 01. The solution of (P R) is 60 *3 *3 *3 *3 *3 *3 *3 *3 x13 = 22 = 31 = x42 x51 = 61 71 = 82 1,

-22 - *3 and all other x.. = 0. ij The lower bound is 3 *3, LB3 = Z(x *3) = 27.4. This solution is not feasible for (P6 ) because the capacity constraint on machine 2 is violated (d2 + d4 + d8 > t2). We solve a reassignment problem for machine 2: (PR2)3 minimize.5Y22 + *5Y42 + 3Y82 subject to 7Y22 + 10Y42 + 9Y82 > 6 Yi2 = 0 or 1, for all i, j. *3 The optimal solution found by branch and backtrack is Y8 = 1 and *3 *3 * Y22 Y42 = 0. Then Z =.3 and the improved lower bound is now LB3 = 27.7. The branching variable (from node 3) would be x22. However, the selected dangling node to branch on is node 2 (because LB < LB3 —see Figure 4). Node K = 4: 4 4 4 F4 = {7,6; G = {(4,2), (4,1); x = {x = 1, x 1}. The solution of (P6 R)4 is 0 *4 *4 *4 *4 *4 *4 * = = =x =sx =S x 13 22 31 43 51 82 *4 and all other x.. O. The lower bound is 4 *4 4 LB = Z(x ) + Z(x ) 27.5. This solution is feasible for (P60). ~0

-23 - Node K = 5: 5 5 5= {(4,2),(6 F = {71; = {(4,2),(6,1)}; x = {x72 = 1, x61 = 01. The solution of (P R)5 is 0 *5 *5 *5 *5 *5 *5 *5 13 22 =31 =41 =51 =63 =82 1 *5 and all other x.. = 0. j1 The lower bound is LB5 = Z(x) + Z() 28. This solution is not feasible for (P 0) because the capacity con0 straint on machine 1 is violated (d3 + d4 + d5 - w35 > t1). We solve a reassignment problem for machine 1: (PR1)5 minimize.2y31 + OY41 + '1Y51 subject to 6Y31 + 10y41 + 8y51 - 2 max {Y31,Y51} > 2 Yij = 0 or 1, for all i,j. *5 *5 *5 * The optimal solution is Y41 = 1 and Y31 = 5 =0. Then Z =0. The branching variable from node 5 would be x31. However, the selected dangling node to branch on is node 4 (because LB < LB5 —see Figure 4). Since the solution (x4 Ux4) is feasible, we stop. STEP 3. UPDATE BOUNDS: m UV = max {r.} = 10.2; LV = ( j r.)/m = 9.16. j J j=1 (Notice the drastic improvement in the size of the interval [LV, UV].) STEP 4. CHECK STOPPING THRESHOLD: UV - LV = 1.04 > e =.67; then 61 = (UV + LV)/2 = 9.68 and go to STEP 2.

-24 - STEP 2. Apply the same procedures used for (Ps ) to obtain, again at the fifth node, the following feasible solution of (P 1): *5 *5 *5 *5 *5 *5 *5 *5 13 =22 31 43 x52 61 2 81 and all other x.. = 0. 13 STEP 3. UPDATE BOUNDS: UV = 9.6; LV = 9.3. STEP 4. CHECK STOPPING THRESHOLD: UV - LV =.3 < c =.67. STEP 5. STOP: 61 < a. The e-optimal solution is given in Table III. TABLE III The e-Optimal Solution Machine Operations Workloads Tools 1 3, 6, 8 9.50 2 2, 5, 7 9.60 3 1, 4 8.80 4. COMPUTATIONAL RESULTS The algorithm has been implemented in FORTRAN IV. The ten problems of Table IV were run on a PERKIN ELMER computer. The 45 problems of Table V were run on an AMDAHL 5860. The problems have been solved to optimality in very short CPU times. Our experimental plan is now described. The size of the problems of Table IV vary from 3 to 9 machine tools, which is the range of most FMSs. The number

-25 - of operations to be assigned range from 7 to 48. For the problems of Table V, the number of machines range from 4 to 15 and the number of operations range from 10 to 40. In most of the problems, the operation times are different on different machine tools, similar to the processing times described in Table II of ~3. However, two of the problems of Table IV contain machine tools for which the operation times on those machines are identical. In particular, Problem Number 10 of Table IV consists of 3 machine types: 4 machine tools of 1 type, 3 of another type, and 2 of the third type. Also, Problem Number 26 consists of 3 machine types: 4 of one type, 2 of another, and 1 of a third type. These problems, although not all real examples of FMSs (some are), provide a representative range of the sizes of the problems that would have to be run frequently to retool and reconfigure an FMS. TABLE IV Computational Results on a PERKIN ELMER Number Number Number Number CPU Problem of of of of Time Number Machines Operations Nodes Subproblems (seconds) 1 3 8 10 2 0.484 2* 3 8 79 3 3.839 3 3 12 19 3 0.548 4 4 7 65 3 1.109 5 4 12 23 5 3.095 6 4 24 47 5 3.592 7 5 20 182 6 10.103 8 6 24 157 5 10.306 9 6 48 237 6 38.531 10* 9 13 61 3 2.203 * In these problems, operation processing times are machine tools of a particular machine type. identical on all

-26 -TABLE V Computational Results on an AMDAHL 5860 Number Number Number Number CPU Problem of of of of Time Number Machines Operations Nodes Subproblems (seconds), I i 11(1)* 12(1)* 13(2)* 14(2)* 15 16(3)* 17(3)* 18(4)* 19(4)* 20(5)* 21(5)* 22(6)* 23(6)* 24(7)* 25(7)* 26 27(8)* 28(8)* 29(9)* 30(9)* 31(10)* 32(10)* 33(11)* 34(11)* 4 4 4 4 4 5 5 5 5 5 5 6 6 6 6 7 7 7 8 8 8 8 8 8 12 12 12 12 15 10 10 12 12 14 14 12 12 14 14 10 12 12 12 12 14 14 15 15 23 91 27 26 252 83 64 47 333 253 291 70 39 41 53 59 58 67 52 1,424 159 145 213 1,092 5 5 5 4 6 3 4 5 7 5 5 4 5 5 5 5 6 5 4 16 5 5 6 12 0.145 0.456 0.065 0.114 1.745 0.114 0.114 0.221 0.465 1.010 1.507 0.113 0.118 0.121 0.209 0.237 0.121 0.204 0.107 2.871 0.256 0.354 0.486 3.673

-27 -TABLE V (Continued) Number Number Number Number CPU Problem of of of of Time Number Machines Operations Nodes Subproblems (seconds) I1_ I _ I 35(12)* 9 15 28 6 0.116 36(12)* 9 15 26 6 0.127 37(13)* 9 20 53 5 0.232 38(13)* 9 20 47 5 0.251 39(14)* 10 20 338 7 1.046 40(14)* 10 20 338 7 1.188 41 10 25 904 12 5.278 42 11 20 369 6 1.250 43 11 20 369 6 1.371 44(15)* 11 24 542 8 3.154 45(15)* 11 30 443 9 6.370 46 11 30 223 7 5.529 47(16)* 12 20 754 12 2.269 48(16)* 12 20 854 12 2.376 49(17)* 12 35 88 6 1.476 50(17)* 12 35 618 9 12.922 51(18)* 13 36 771 10 13.674 52(18)* 13 36 771 10 15.111 53 14 35 656 10 7.655 54 15 30 732 10 5.309 55 15 40 849 11 16.163 *In these problems, operation processing times and the number of slots for holding the tools of each operation are identical on all machines of a particular machine type. The larger problem number of each pair (marked in parentheses) has a relatively smaller capacity of the tool magazine.

-28 - The computational results of these 55 problems are provided in Tables IV and V. In general, the algorithm performs better when the processing time of each operation is different on each machine tool or when the machine tools are of different types. This is because when there are many identical machine tools, there are many similar, equivalent solutions and the algorithm will not be able to prune the branch and bound trees as efficiently as otherwise. Such differences in performance can be seen by comparing Problem Numbers 1 and 2 of Table IV, both having 3 machines and 8 operations. For Problem Number 2, which has identical machines, the CPU time of 3.84 seconds compares unfavorably with.48 seconds. However, Problem Numbers 10 and 26 also consider identical machine tools and the CPU time is reasonable. A heuristic method to handle these particular types of systems having identical or pooled machines is currently being developed. Of the 45 problems that are reported in Table V, there are 18 pairs, which are noted in the parentheses. The larger problem number of each pair has a relatively smaller tool magazine capacity. These problems all take longer to solve because the smaller magazine capacity is harder to satisfy. In these cases, the run times appear to be somewhat dependent on the ratio of tool magazine capacity to the number of slots required. In addition, increasing problem size increases both the number of subproblems as well as the number of nodes considered, as might be expected. However, all of these 45 problems were solved in less than 16 seconds of CPU time. It appears that run time would not limit the solution of practical problems. These computational results are encouraging. The program is easy to apply, specialized, and self-contained. (This contrasts with the original solution procedure (Stecke (1983)), which is unwieldy and time consuming when performing the linearizations. Also it requires the availability of a mixed

-29 - integer code). The CPU times are low enough to allow the frequent (one to three weeks, say, on average) re-solving of the FMS loading problem. 5. SUMMARY AND FUTURE RESEARCH NEEDS This paper provides a self-contained and easy to use branch and bound approach for allocating operations and cutting tools to limited-capacity machine tools. This special purpose algorithm is tailored for FMS applications. Significant computational results demonstrate the efficiency of the algorithm. The focus here is on only one of several loading objectives, that of balancing the workload per machine while assigning each operation to only one machine. However, the procedures described in ~2 can be generalized to one of the pooling objectives of Stecke (1983). Prior to describing that extension, we recall some advantages of pooling. A group of pooled machine tools are similar and identically tooled. "Similar" means that all machines in a group can perform the same operations with identical processing times. Some advantages from the increased flexibility resulting from machine pooling include:. an improvement in the utilization of machine tools;. an increase in productivity; * a decrease in the mean flow time of parts in the system;. a decrease in waiting times;. a reduction in in-process inventory. Redundancy in the case of machine breakdowns is automatically provided with pooling. The processing sequence has several possible routes and the system can automatically cope with machine breakdowns and congestion. Machine pooling enhances the flexibility of real-time control and hence the production capacity of the FMS. The efficiency of grouping several single-servers into one multi-server queue is established (Kleinrock (1976)). However, because of tool magazine capacity constraints, maximum grouping (i.e., pooling all machines into a single group) is generally infeasible because no machine's tool magazine can

-30 - store all tools necessary to perform all required operations. In addition, machines of different types usually cannot belong to the same group. The algorithm presented in ~2 can be adapted to certain FMS situations with pooled machines. However, the tool magazine capacity constraint is harder to satisfy because each machine tool in a group must be able to perform any operation assigned to the group. The corresponding cutting tools are duplicated at each machine. Hence, the tool magazine capacity constraint for a group of machines is identical to the capacity constraint of any single machine in the group. To use the procedures described in ~2, the objective function of Problem (P ) is modified to fit a pooled machine situation. If the objective is to balance the workload per machine, this quantity is obtained by dividing the workload assigned to a group by the number of machines in the group. This version of the FMS loading problem is: Problem (PG) b a.pikik minimize [maximum ( I - l- )] k i=l Sk subject to: g xi = 1, idI k=l ik b I diik + TCk() < tk kl,..,g i=l Xik = 0 or 1, iEI and k=l,...,g, where g is the number of machine groups; Sk is the number of machine tools in group k; tk is the capacity of the tool magazine for any machine of group k; TCk(x) is given in equation (3). The algorithm presented in ~2 can solve problem (PG) provided that the number of machine tools in each group (Sk, k=l,...,g) is known. *This assumes that the tool magazine capacities of all machines in group k are identical. If not, tk is the smallest of these capacities.

-31 - The objective function of problem (PG) may not be appropriate when the s are not all equal. Stecke and Solberg (1985) show that when group sizes are unbalanced, workload per machine should also be unbalanced —in particular, each machine tool in a large group should be loaded more heavily than each machine in a small group, to maximize expected FMS production. This is shown using a closed network of multiserver queues (see Solberg (1977)). This model, although qualitatively robust (see Dukhovny and Koenigsberg (1981) and Suri (1983)), does not always provide reliable quantitative information. The optimal, unbalanced workload per machine of each group can be determined by using this model. There is not enough evidence to date that these workloads are also optimal for real FMSs having deterministic processing times. More research validating this point is needed before an unbalanced loading objective can be implemented on a shop floor. However, the unbalancing phenomenon is qualitatively and theoretically true. A similar efficient branch and bound algorithm, or perhaps another procedure, could be developed for this situation as well as for other loading objectives. APPENDIX A DERIVATION OF THE TCJ(y) TERM IN PROBLEM (PRK) Suppose that at node K, for a particular assignment of operations, x, the tool magazine capacity constraint is violated for machine j; then we have: b dixij + TC(x) - tj = bj > 0 where TCj(x-) = X (-1) I w m {x..} TC 00 = (-WB wB min {xij} V B CIeB -= -J

-32 - where IK = {i.i = 1}. J IK contains the indices of the operations assigned to machine j (see J Figure 1). To obtain a feasible solution that satisfies this tool magazine constraint, one or more operations in I. must be reassigned to other machines. If the set of reassignment variables is {Yij | is IK}, then the number of slots required by the operations remaining on machine j is: b (-1) IBI+l m {y (Al) } d x L d y.. + CK ' (1) i=l i ij ilI K i VB K 1)B iKl (A J J 3 3B 1 >2 The last term dictates that the amount of tool slot capacity previously taken (or returned), as measured by WB, is now returned (or taken), if there is at least one operation i in B that is reassigned (y.i = 1). The last term in equation (Al) can then be expressed as: TCj(x) - Ki (-1) IB wB maxK {Yj} TCj(x) - TC!(y), VBCI. i.i -- 3 J 3|BB 12 since min {1-yij} 1 - max {y..i} i i To insure a feasible solution that satisfies the tool magazine constraint of machine j, we have: b i d..i - i)K diYij + TC.(x) - TC!(y) < tj i=l 1 1 i which directly implies that: iK diYij + TCj(y) > b.. || ifl. ' J J

-33 -APPENDIX B EFFICIENT STORAGE OF DATA ASSOCIATED WITH COMMON TOOLING CONSIDERATIONS Computational time is decreased by providing a suitable means of storing the data pertaining to slots in a tool magazine that are saved when: 1. several cutting tools are common to two or more operations; and 2. the larger tools are positioned correctly in a tool magazine. Let p = number of subsets, B, of operations for which space can be saved in a tool magazine b = total number of operations A = p x 3 array containing the relevant cutting tool overlap information B = {il, i2,...,i l'BI Consider row L corresponding to some subset, B, of operations. Then A consists of the following entries: A(L,1) = IBI A(L,2) = index that characterizes subset B JB(IBI-k - 1 + I (ik - 1) * b k=l A(L,3) = wB. A(L,2) provides a unique ordered numeration of the elements of a multidimensional matrix in order to get a one-dimensional vector. This information, which is stored compactly in A, can be used efficiently during enumeration as follows: Suppose that a set, B., of operations has been assigned to machine tool j. Then TC.(B.) = (-I)11 1 wB. VBCB CB J 3|B|>2 If another operation k (g~B ) is now also assigned to machine tool j, then j

-34 - TC (B {k}) = TC.(Bj) + I (-1) I1 wBU{k, VBCB.BU 31B1>2 where wBU{k} is read from array A, if this entry exists. This approach to the calculation of the TC. 's can be somewhat burdensome computationally if many subsets of operations are listed in A. The maximum number of rows in A (which is p) could be up to 2 - b - 1. In practice, the number of rows of A is not very large because only tools common to two or three operations need be considered. APPENDIX C UPDATING LV WHEN (P6 ) IS FEASIBLE Problem (Pa6) is to find an optimal solution, x*(65), minimizing m m m Z = i I aiPijij = r (x) j=l i=l j=l under the condition: xe D(Sz), where D(6Q) is the set of feasible solutions satisfying constraints (1), (2), (3), (4), and (5'). Assume that (P ) has an optimal solution, x*(6 ). Updating LV, by setting Z*(6 ) m LV = = i rj(x*(6%)), is valid if we prove the following. m m j=l z*(zG) Proposition: Let K < St. If x*(6k) exists, then 6 > m. Proof: Note that 6, < 6 => D(6') < D(6 ), because of constraint (5). Hence, if x*(g') exists, then Z*(6) > Z*(6). But V j = 1,...,m, r(x*(6)) <. (from (55) i Y, P

-35 - This implies that (6') < m 6'. Z*(6 ) Z*(6 ) Hence, S6 > > - m - m Q.E.D ACKNOWLEDGEMENTS The authors would like to thank Dr. Didier Dubois of Paul Sabatier University in Toulouse for helpful discussions during the preparation of this manuscript as well as for useful suggestions concerning the derivation in Appendix A. We would also like to thank Mr. Ilyong Kim of The University of Michigan for providing many of the computational results and the Referees and the Associate Editor for unusually thorough reading and helpful suggestions on some details and organization. This research was supported in part by grants from Ford Motor Company and from the Graduate School of Business Administration of The University of Michigan.

-36 - REFERENCES BALAS, EGON, "Extension de l'algorithme additif a la programmation en nombres entiers et a la programmation non lineaire", C.R. Acad. Sc. Paris (May 1964). BALAS, EGON, "An Additive Algorithm for Solving Linear Programs with ZeroOne Variables", Operations Research, Vol. 13, No. 4, pp. 517-546 (1965). 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). CAIE, JAMES, LINDEN, JANET and MAXWELL, WILLIAM, L., "Solution of a Single Stage Machine Load Planning Problem", OMEGA, Vol. 8, No. 3, pp. 355-360 (1980). CAVAILLE, JEAN-BERNARD, FORESTIER, J. P. and BEL, GERARD, "A Simulation Program for Analysis and Design of a Flexible Manufacturing System", in Proceedings, IEEE Conference on Cybernetics and Society, Atlanta GA, pp. 257-259 (October 1981). DUKHOVNY, ISAAC M. and KOENIGSBERG, ERNEST, "Invariance Properties of Queueing Networks and Their Application to Computer/Communications Systems", Information Systems and Operations Research, Vol. 19, No. 3, pp. 185-204, (August 1981). GARFINKEL, ROBERT S. and NEMHAUSER, GEORGE L., Integer Programming, John Wiley & Sons, Inc., New York NY (1972). GLOVER, FRED, "Improved Linear Integer Programming Formulations of Non-Linear Integer Problems", Management Science, Vol. 22, pp. 455-460 (1975). GLOVER, FRED and WOOLSEY, EUGENE, "Further Reduction of Zero-One Polynomial Programming Problems to Zero-One Linear Programming Problems", Operations Research, Vol. 21, pp. 156-161 (1973). GLOVER, FRED and WOOLSEY, R. E., "Converting the 0-1 Polynomial Programming Problem to a 0-1 Linear Program", Operations Research, Vol. 22, pp. 180 -182 (1974). GRAVES, STEPHEN C. and LAMAR, BRUCE W., "An Integer Programming Procedure for Assembly System Design Problems", presented at the Joint National CORS/ ORSA/TIMS Meeting, Toronto, Ontario, Canada (May 1981). KARP, RICHARD M., "On the Computational Complexity of Combinatorial Problems", Networks, Vol. 5, pp. 45-68 (1975). KLEINROCK, LEONARD, Queueing Systems, Volume 2: Computer Applications, John Wiley & Sons, Inc., New York NY (1976). KUSIAK, ANDREW, "Loading Models in Flexible Manufacturing Systems", WP#05/83, Technical University of Nova Scotia, Department of Industrial Engineering, Nova Scotia, Canada (March 1983). ROSS, G. TERRY and SOLAND, RICHARD M., "A Branch and Bound Algorithm for the Generalized Assignment Problem", Mathematical Programming, Vol. 8, pp. 91-103 (1975).

-37 - SALKIN, HARVEY M., Integer Programming, Addison-Wesley, Reading MA (1975). SANDI, CLAUDIO, "Solution of the Machine Loading Problem with Binary Variables", in Combinatorial Programming: Methods and Applications, edited by B. Roy, D. Reidel, Dordrecht-Holland, pp. 371-378 (1975). SHANTHIKUMAR, J. GEORGE and STECKE, KATHRYN E., "Reducing Work-In-Process Inventory in Certain Types of Flexible Manufacturing Systems", European Journal of Operational Research, 1986, forthcoming. SOLBERG, JAMES J., "A Mathematical Model of Computerized Manufacturing Systems", in Proceedings, 4th International Conference on Production Research, Tokyo, Japan (August 1977). 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, Vol. 29, No. 3, pp. 273-288 (March 1983). STECKE, KATHRYN E., "Procedures to Determine Both Appropriate Production Ratios and Minimum Inventory Requirements to Maintain These Ratios in Flexible Manufacturing Systems", Working Paper No. 448, Division of Research, Graduate School of Business Administration, The University of Michigan, Ann Arbor MI (October 1985a). STECKE, KATHRYN E., "A Hierarchical Approach to Solving Machine Grouping and Loading Problems of Flexible Manufacturing Systems", European Journal of Operational Research (1985b), forthcoming. STECKE, KATHRYN E. and BROWNE, JIM, "Variations in Flexible Manufacturing Systems According to the Relevant Types of Automated Materials Handling", Material Flow, Vol. 2, No. 2, pp. 179-185 (July 1985). STECKE, KATHRYN E. and MORIN, THOMAS L., "The Optimality of Balancing Workloads in Certain Types of Flexible Manufacturing Systems", European Journal of Operational Research, Vol. 20, No. 1, pp. 68-82 (April 1985). STECKE, KATHRYN E. and SCHMEISER, BRUCE W., "Equivalent Representations of System Throughput in Closed Queueing Network Models of Multiserver Queues", Working Paper No. 324, Division of Research, Graduate School of Business Administration, The University of Michigan, Ann Arbor MI (December 1982). 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, Vol. 19, No. 5, pp. 481-490 (September-October 1981b). 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, Vol. 33, No. 4, pp. 882-910 (July-August 1985). SURI, RAJAN, "Robustness of Queueing Network Formulae", Journal of the Association for Computing Machinery, Vol. 30, No. 3, pp. 564-594 (July 1983).