Division of Research Graduate School of Business Administration The University of Michigan LINEARIZED NONLINEAR MIP FORMULATIONS FOR LOADING A FLEXIBLE MANUFACTURING SYSTEM Working Paper No. 278 Kathryn E. Stecke The University of Michigan FOR DISCUSSION PURPOSES ONLY None of this material is to be quoted or reproduced without the express permission of the Division of Research. September 1981

ABSTRACT This paper addresses production planning problems for flexible manufacturing systems (FMS's). Specifically, the grouping and loading problems are formulated as nonlinear 0-1 mixed integer programs. Several linearization methods are examined and applied to data from an existing FMS. Several problems are solved using the linearization that results in the fewest additional constraints and/or variables. We also discuss when each linearization is best and the use of the linearized models in the solution of actual planning problems. Presented at the Joint ORSA/TIMS National meeting in Houston in October, 1981.

1. Introduction This paper addresses the grouping and loading problems, two of a series of five production planning problems that are defined here for flexible manufacturing systems (FMS's). An FMS is an automated batch manufacturing system consisting of numerically controlled machines, linked by automated material handling, that perform the operations required to manufacture parts. Each operation requires one or more cutting tools. The tools for all operations that can be performed by a machine are stored in its limited capacity tool magazine. Each machine has an automatic tool interchanging device that can interchange two cutting tools in seconds. This rapid interchange capability allows several consecutive operations to be machined with virtually no set-up time between operations. One or more computers control most activity such as machining operations, part movements, and tool interchanges. The computer cannot route a particular part to a machine unless all tools required for the next operation were previously placed in the magazine. This last requirement indicates the need for planning prior to production. For additional information concerning FMS's, see Stecke and Solberg [1981a]. Managing production for an FMS is more difficult than for production lines and job shops because: each machine is quite versatile and capable of performing many different operations, the system can machine several part types simultaneously, and each part may have alternative routes through the system. These additional capabilities and planning options increase both the number of decision variables and constraints associated with setting up an FMS. To best utilize an FMS's capabilities, a careful system set-up is required prior to production. Set-up decisions for batch manufacturing are made

- 2 - frequently to meet new or altered production requirements, for example, whenever production requirements for a part type are met. This contrasts with a mass production system where set-up is part of the design process and set-up changes are few. The decision variables of the set-up problem of an FMS are: part types to be produced next, relative numbers of parts of each type to be machined simultaneously, number of pallets and fixtures of each fixture type to be reserved for each part type, and allocation of operations (and tools) to machines. The objective of a set-up is system dependent, but commonly is to maximize expected production. Since the problem in its general form is intractable, the following approach is suggested. A set of five production planning problems are defined, the solutions to which are a system set-up. The problems can be solved sequentially, or alternatively, candidate solutions to the problems can be generated iteratively until a suitable final solution is found. In addition surrogate objectives are used for each problem rather than attempting to maximize production directly. The problems are: 1. Part type selection problem: From a set of part types that have production requirements, determine a subset for immediate and simultaneous processing. 2. Machine grouping problem: Partition the machines into machine groups in such a way that each machine in a particular group is able to perform the same set of operations. 3. Production ratio problem: Determine the relative ratios at which the part types selected in problem (1) will be produced.

-3 - 4. Resource allocation problem: Allocate the limited number of pallets and fixtures among the selected part types. 5. Loading problem: Allocate the operations and required tools of the selected part types among the machine groups subject to technological and capacity constraints of the FMS. For additional information concerning these problems, see Stecke [1981]. The plan of the paper is as follows. The machine grouping (2) and loading (5) problems are formulated in Section 2 as 0-1 nonlinear mixed integer programs (MIP's). In addition different methods of solving nonlinear MIP's are surveyed. Section 3 presents several linearization methods. In Section 4 these are applied to data from an existing FMS. Numerical solutions are obtained using the linearization resulting in the fewest additional constraints and/or variables. In addition conclusions are drawn concerning conditions under which each linearization is best. Computational experience, which shows advantages to considering the nonlinear terms, is discussed in Section 4. The paper concludes with a discussion in Section 5. 2. Mathematical Programming Formulations After defining required notation, this section begins by developing the constraint formulations necessary for the grouping and loading problems. The grouping problem is then defined and formulated. Finally, several loading objectives are developed. Parameters and Variables The subscripts, input parameters, and decision variables are given in Table 1. Several subscript conventions and parameters require further explanation.

- 4 - TABLE 1 Notation Subscripts: operation i=1,..., b machine j=1,..., m machine group 1=1,..., M machine type n=1,..., m set of operations k=1,..., K Parameters (Input): pi. = processing time of operation i on one of the machines in machine group 9; qi = maximum number of times that operation i can be assigned; d. = number of slots required in a tool magazine by operation i; 1 tt = capacity of the tool magazine for each machine in group 2; wik = number of slots saved due to common tools when operations i and k are assigned to the same machine; = 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; Bk = index set of sets of operations; w = number of slots saved when the operations in BK are assigned k to the same machine; P = index set of compatible part types that are to be produced simultaneously on the system of machines; a. = production ratio (relative to the remaining part types P-{i}) at which part type i will be produced; m = {jlmachine j is of machine type n}; Decision Variables (Output): MY = {jlmachine j is in machine group ~}; 1, if operation i is assigned to each machine in group 2; Xi = o 0O, otherwise.

-5 - In the formulations, several parameters of Table 1 might range over either machines (j) or machine groups (). In those formulations for which there is only one machine in each group, the machine subscript j is used. The differences between machine types and machine groups should be clarified. All machines of the same machine type are physically identical (i.e., same axes of motion, dimensions, horsepower, capabilities). Each set of machine types, mn, might be partitioned into several machine groups. Machines that are identically tooled comprise a group and are said to be pooled. Hence each machine in a particular group will be able to perform the same operations. Constraint Formulations The constraints of the grouping and loading problems are now given. First, each operation must be assigned to at least one machine of the machine type required by the operation. In addition there is a limited number of duplicate assignments allowed: M 1 < ~ x i < qi, i = 1,...,b. (1) =1l It is understood that x.ij(xi ) = 0 if operation i cannot be performed by the machine type corresponding to machine (group) j or Z. Second, the tool magazine capacity constraint which relates the number of tool slots required by the operations assigned to a machine (group) to the total number of slots contained in the machine (group)'s tool magazine, in its simplest form, is b ~ di XiQ < J t, x = 1,...,m. i=1 Since only one tool can be used at a time, however, it is unnecessary to assign

-6 - any tool more than once to the same machine. Also the actual number of slots used depends on the physical placement of the tools in the tool magazine. In the example shown in Figure 1, two three-slot tools placed side by side require only five slots rather than six. Another complicating consideration is that since larger tools are heavier, tool magazines must be weight balanced. In addition, several operations may require some of the same tools. Space in the tool magazine can be saved by eliminating tool duplication and considering overlap and weight balancing. These savings are measured by WB., Z7oJ 7 -TOOL SLOTS TOOL MAGAZINE TOOLS Figure 1. Tool Magazine. The tool magazine capacity constraint then becomes: b b-1 b Zd i it i w i X. ia Xi 9 Z wilw. x. xi2. + i=1 1=1 i=i 1+1 i 2 1 2 i1=1 i2-. 1 b-2 + E i -1 1 - b-1 b i Z i2=i1+1 i3=i2+1 2i1 3:i2 - xi i i + 1 2i 3 2 3 b-p+1 b-p+2 + (-1)p+1 Z z i 1=1 i2=i+1 b r w x. i xi2.exi < t, =ip_ +1 1i2...i p 1 2*p or, in more compact form,

-7 - b b d.xi + E (-1 + w_ n x. < t, Z=1,..., M. (2) p=2 lk' VB C Bk ik E B IBI=p Finally there is the integrality constraint: Xi. = 0 or 1, for all i,R. (3) Machine Grouping Formulation Pooling (see Kleinrock [1976], Stecke and Solberg [1981a]) increases system performance by decreasing the probability that a part is blocked by having no machine available for the next operation. Having more than one machine in a group is one way to allow alternate routes for some part types. Stecke [1981] considered the best partitions of m items (servers, machines) into M (machine) groups to maximize expected production using a closed queueing network model. In particular, the results include: i. Fewer groups are better, i.e., pool as much as possible; ii. The maximum expected production is obtained from systems with the most unequal sized groups. More generally, all possible partitions are ordered according to expected production. These results are used here. This paper considers a more detailed treatment of the grouping problem than that of Stecke [1981] by adding constraints on tool requirements and tool magazine capacity that use actual operation times. Maximum pooling of all machines of the same type into one group may not be possible because of some technological constraints such as tool magazine capacity. The approach we take to maximize pooling is as follows: 1. Set M equal to the minimum number of machines (or, machine groups)

-8 - required to perform all operations of the part types in P. 2. Use the optimal pooling for M groups from Stecke [1981]. Since all possible partitions of machines are ordered in Stecke [1981], the solution to the more detailed model is then the best feasible partition. Step 1, which determines M, is now described. The problem is to find {x..i=1,...,b, j=1,...,m} to m maximize Z YJs. j=1 subject to b b s. = t.-( Z d.xi + Z (-1)P' Z w_ x.), J J i=1 p=2 -V B B VBC BK ikE B1 IBI = p and equations (1), (3), and qi = 1, b where Y = Z di. Note that sk. is the slack in the tool magazine capacity i=1 J constraint of machine j. Let mon be the maximum number of machines of machine type n required to perform the operations of the part types in P, if common tooling is not taken into consideration, n = 1,..., m. The mon are obtained by adding the number of tool slots required of machine type n, dividing by the capacity of each machine's tool magazine, tn, and rounding to the next highest integer. Then an upper bound on the total number of required machines is mo machines, where m m = Z m O on=1 n=1

- 9 - The objective function formulation allows for the values of the slack (s.j) in the Imn machines to monotonically increase. For every machine type, the initial machines will be filled first; if there is insufficient tool slot capacity and another machine is required, machine i will tend to be filled before an operation is assigned to machine j, for i<j. The result is the minimum number of machines of each type that are needed to perform the required operations. An example will demonstrate the problem. Consider a 15-machine system of four machine types with m,=4, m =3, m 3=4, and m4 =3 Then 14 machines are ol' o2 '3 required if overlap is not considered. The machines, j, and their machine types, n, are as follows: n: 1 2 3 4 machine j: (1 2 3 4) (5 6 7) (8 9 10 11 12) (13 14 15) Suppose that the solution to Step 1 was that M=10, and that 3 machines were required of the first 3 types, and only one of the fourth type. Then the optimal pooling into machine groups according to Step 2 is: machine j: (1 2) (3) (4) (5) (6) (7) (8 9 10) (11) (12) (13 14 15) Notice that: all machines of the fourth type could be pooled, none of the second type could be, and there are 10 machine groups. Loading Formulations A usual loading procedure for both conventional systems and FMS's attempts to balance the assigned workload on each machine; the aim is to equalize the total weighted processing time, or workload, of the operations assigned to each machine. The processing time of each operation is weighted by the production ratio (ai) of the corresponding part type i as calculated in the fourth production planning problem. In addition each operation is often assigned to

- 10 - only one machine. The consequence is that each part type has a fixed route through the shop. However, the flexibility and capabilities of an FMS indicate that perhaps new planning and control procedures should be developed for FMS's, which could also perhaps be applicable to other types of manufacturing systems. In a previous study (Stecke [1977], Stecke and Solberg [1981b]), alternative loading objectives are defined. Application of any of several objectives can result in better system performance than that of a balanced assigned workload. Stecke [1981] has shown that the practice of balancing is too restrictive for most FMS's, since the inherent flexibility can often be utilized for better system performance. Several alternative loading objectives are listed in Table 2. The decision concerning which to apply is problem dependent. Each may be best under certain circumstances. Some are contradictory in some situations; for other systems, several objectives may apply. TABLE 2 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 sum of operation priorities.

- 11 - Consider the first objective function. Let r. be the relative workload assigned to machine j: b rJ = Z aiPij xij i=1 3 13 j=1,..,m. (5) Then r. is also a measure of the relative utilization of machine j. If all of J the r. are equal, the system is perfectly balanced. This is usually not possible because of the discrete values of processing times. The following formulations optimally balance the workloads assigned to machines as much as possible. Each objective function is a measure of system imbalance. The problem is to find {x. i i=1,...,b, j=1,...,m} to minimize h.(x), where hi (x) is one of the following four: 1. maximum Ir. - rh j=1,..., m-1 J h=1,..., m; m-1 m 2. z z Ir. - rhi Y>o j=1 h=j+1 m-1 m 3. ~ r (r - rh)2 j=1 h=j+1 4. S-ct subject to 0 a< < r. K B, The constraints are: (1), (2), (3), (5), and qi j=1,...,m. = 1. The second objective, minimize the number of movements, is quite different from the first. The second objective is relevant, for example, when transportation time or distance from machine to machine is large relative to average operation time. There are manufacturing systems for which minimizing movements from machine to machine is best even at the expense of balancing

- 12 - (Stecke and Solberg [1981b]). It can be more advantageous for a part type to remain on a machine for several consecutive operations rather than to move for the sake of balancing. Furthermore when several consecutive operations require the same machine type, time may be saved by processing all of them on the same machine, if this is technologically possible. Both travel time (from machine to machine) and waiting time (for a possibly busy next machine to become idle) may be saved. The first two objectives of Table 2 are often incompatible. When allocating operations in large sets, the potential for balance decreases: if the operation times to allocate are smaller, a better balance is likely. We now formulate the second loading objective. Notice that if i and i+1 represent consecutive operations, then 0O, if operations i and i+1 are on the same machine j; x..-x. = 1J i+lj +~1, if operations i and i+1 are assigned to different machines. If N is defined as twice the number of excess movements, then b-1 m b-1 m N = Z Ix. -x i+ = Z Z (Xij -x )2 i=1 ji=1 i=1 j=lij j+1,j Some of the differences (x. -xi+ j) need not be included in the calculation of N. For example for some machine j, operation i may require a machine type other than that of machine j; in this case, x.. = 0. In particular, if (xij - xi+l, ) = xij or -x i+1j, then this term may be excluded Lj i+i,j +,j from N. Inclusion is not incorrect, merely unnecessary and inefficient. The second objective, then, is to b-1 m minimize i z (x i i+i,) (or) i=1 j= 1J +lJ

- 13 - b-l m = Z Z }xij-x. I, i=l j=l subject to (1), (2), (3), and qi = 1. The advantages from utilizing flexibility by allowing pooling and hence alternative part routes provide motivation for the remaining loading objectives. The third (and fourth) objectives (un)balance the workload per machine for a system of groups of pooled machines. The applicability of either depends on the configuration of the manufacturing system, or how the machines are grouped (see Stecke [1981]). For the third objective, the problem is to minimize hi(x), where hi(x) is one of the following four: rz rk 1. maximum -- =1,..., M-1 s Sk k=:+1,..., M M-1 M rN rk 2. Z Z y — _ > 4=1 k=t+1 S k M-1 M r rk2 3. z z ( k) Z=1 k=l+1 sk 4. 6-a subject to 0 < a r /s. B, i=1,...,M, subject to (1), (2), (3), (5), and qi = 1. Notice that r//sz is the workload per machine in machine group ~. The fourth problem is to minimize gi(x), where g (x) is one of the following four: 1. maximum Ir4 - X 1 L=1,..., M 2. maximum Irz - X Y, Y > 0 =1,..., M

- 14 - M 3. Z (r - X ) Q=1 4. B -a subject to 0 < a < r - X, =1,..., M, subject to (1), (2), (3), (5), and qi = 1, and where XQ is the theoretical optimal workload that should be assigned to machine group ~ to maximize expected production (see Stecke and Solberg [1981b]). The rationale for the fifth objective of Table 2 is that when tool magazines are filled, perhaps several operation assignments are duplicated to result in alternative part routes, which should increase machine utilization and production, and decrease waiting time. No single tool should be assigned to any particular machine more then once. In addition the maximum number of times that an operation could be duplicated can be specified. One formulation of this objective minimizes slack in the capacity constraints for all machines. Then the problem is to m minimize Z st. j=1 J subject to (1), (3), qi > 1, and b b s. = t.- ( z dx..+ ( J hJ i=1 J p=2 The aim of the sixth objective in fifth: to duplicate assignments of should not be duplicated arbitrarily. other operations, such as bottleneck z w_ 1 x..). V- B ~ lkJ ~B Bk ikE B IBI=p Table 2 is similar to the aim of the some operations. Operation assignments Some operations are more critical than operations. In such cases, weights could

- 15 - be assigned to prejudice operation assignments. If w. is the weight assigned to 1 operation i, then the problem is to b m maximize ZS wix.. i=1 j=1 1 subject to (1), (2), (3), and q > 1. Almost all of the objective functions and some of the constraints are nonlinear. There is a variety of approaches to solve nonlinear MIP's. They can be solved directly (Cooper [1981], Ginsburgh and Van Peetersen [1969], Hammer [1969], Hansen [1971,1979], Marsten and Morin [1978], Morin [1978], Lawler and Bell [1967]). Alternatively, piecewise linear approximations (Dantzig [1962], Hu [1969], Watters [1967]), or heuristic algorithms (Stecke and Solberg [1981a]) can be used. Another approximate approach is to ignore some tooling considerations that result in the nonlinear terms in the capacity constraints. Ignoring these factors results in feasible, but worse solutions. An exact approach is to linearize the nonlinear terms (Balas [1964], Glover and Woolsey [1973, 1974], Glover [1975]). The resultant linearized 0-1 problems could either be solved directly, or relaxed. The applicability of a direct nonlinear approach versus a transformed linear approach is problem-dependent (Taha [1970]). The direct approach is more difficult while linearization results in much larger problems. In the following section, we present several methods to linearize the nonlinear terms, and apply combinations of these methods to data in Section 4. 3. Linearization of the Product Terms Fortunately the nonlinear terms in the formulations are products of 0-1 integer variables, for which there are several methods to linearize the terms.

- 16 - The standard procedure is to replace each cross product term with a new variable. Additional constraints are required to insure that the new variables take on the correct values. In this section we survey five linearization methods, which differ in both the numbers of additional variables (either integer or continuous) and constraints generated. The difficulty of integer problems depends primarily on the number of integer, rather than continuous, variables. Additional details concerning the linearizations of the formulations in Section 2, in particular, the generated variables and constraints, can be found in Stecke [1981]. The first method was developed by Balas [1964]. Each product term x. is replaced by a new variable x_ 3lkJ S ik CS x. - x_ < p-1, p = iSt (6) ikcS S Xi. + p x_ < 0, j=1,..., m (7) - SJ ik For each product term, there are two new constraints and one new integer variable. The second method, described in Glover [1975] for quadratic terms, can be used for higher order terms by recursive application (Stecke [1981]). For m x m quadratic terms, Balas's approach (method 1) introduces m(m-1)/2 new integer variables (one for each cross product term) and m(m-1) additional constraints. Glover's approach adds 4m constraints and m continuous variables, which are automatically 0-1 without requiring an integer restriction. The second method has the advantage that the transformed linear integer program has the same number of integer variables as the original nonlinear program.

- 17 The third method (Glover and Woolsey [1974]) allows the new variables x S (of equations (6) and (7)) to be continuous by replacing the second inequality of Balas' method (equation (7)) with ISI additional constraints. Despite the additional constraints method 3 can be better than the first method since the additional constraints are simpler and the new variables are continuous. The fourth method (Glover and Woolsey [1974]) also allows x_ to be S continuous by replacing several of the constraints (7) that contain terms with common variables, by a single constraint. If there are no variables in common, there is no reduction. The final method (Glover and Woolsey [1973]) consists of a series of three rules that reduces the number of required constraints of the first of the pair of constraints (equation (6)) generated by Balas's method. The new variables are continuous. 4. Application and Computational Results Combinations of the five linearizing methods are applied to data from. the Sundstrand DNC (Direct Numerical Control) line at the Caterpillar Tractor Company in Peoria, Illinois. The Caterpillar FMS consists of nine metal-cutting machines plus an inspection station. This set of machines includes four 5-axis Omnimills, three 4-axis Omnidrills, and two vertical turrent lathes (VTL's). In addition there are two automatically controlled transporters, which provide inprocess material handling and also deliver parts to the inspection station. The 16-station load/unload area is located midway along the line's length. These stations also provide some in-process inventory. A remotely located DEC PDP 11/20 computer and supporting equipment control the entire system on a real-time basis. The parts machined on this line are two sizes of housings for automatic transmissions. Each type of housing is composed of two parts, a transmission

- 18 - case and a cover. The parts arrive at the facility in rough casting form and leave as an assembled matched pair. There are three part types: transmission cases, covers, and assemblies. Caterpillar's loading objective was to balance the assigned workload per machine as much as possible; in addition each operation was assigned to only one machine. The machines have different capabilities. Some operations require a mill; others can be performed on either a mill or a drill (mills can do drilling operations, but not vice versa). The two VTL's could be pooled although they were not in management's original set-up strategies. After certain operations, a proportion of the parts will visit the inspection station. For additional information concerning the management and control of the DNC line, see Stecke [1977]. 4.1 Input Some operations are collected in advance into operation sets. For example, a large case requires 49 operations (Stecke [1977]), which Caterpillar had aggregated into nine operation sets. These operation sets, along with those of covers and assemblies, are allocated among machines according to various loading objectives. The input data includes for each operation set: the machine type required, the total number of tool slots required, the tool number and number of slots for any tool of that operation set which is required by at least one other operation set, and the processing time. Initial calculations include a table of the number of tool slots saved (WB ). This table, as well as the constraint formulations, are found in Stecke k and Solberg [1981a].

- 19 - 4.2 Constraints Linearized and Compared The tool magazine capacity constraint is formulated, and then linearized, according to the different methods. The basic nonlinear formulation consists of 48 integer variables and 25 constraints. See Table 3, which also contains the number of additional (continuous) integer variables and constraints that are generated by each of six combinations of the five linearizing methods. Application of each of the first two methods results in different constraint linearizations. Methods 3 and 4 replace the second of each pair of constraints generated by method 1, while the fifth method replaces the first constraint of each pair of method 1. The best combination of methods, with respect to fewest additional variables and/or additional constraints was to be chosen to run on a CDC 6600 in conjunction with each loading objective. TABLE 3 Number of Variables and Constraints Generated by Linearizing --— _ = Linearization Method s Nonlinear Formulations 1 2 3 4 5 4,5 Variables Integer 48 + 113 (76) (113) (113) 113 (113) (Continuous). ___ Constraints 25 +218 228 373 157 152 91;~~~~.I _ _ _,L L..-L - -,.- - I - -- The variables in parentheses are automatically 0-1 when the original variables are constrained to be so. Then the two sets of linearized constraints that are candidates for selection to use for solving the MIP's are method 2, and methods 4 and 5. Method 2 generates fewer variables, methods 4 and 5 fewer constraints. Since the difference in the number of constraints is large, the constraint set chosen to run the MIP's is that generated by the fourth and fifth

- 20 - methods. 4.3 Comparison of Linearizations Each linearization method is applicable to different types of nonlinear problems. If the product of nonlinear 0-1 variables is quadratic, then the second method (Glover [1975]) may be best. Since higher order product terms are present for our problem, the second linearizing procedure must be applied iteratively to result in an increasing number of generated constraints. In similar situations, methods 4 and 5 would usually be better than method 2. 4.4 Objective Functions Linearized The first objective function formulated is the grouping objective, which maximizes pooling. To accomplish this, the number of machines required is minimized. The remaining machines can then be pooled as indicated in Stecke and Solberg [1981a]. The two machine types, n, are mills and drills. Let moM(moD) be the upper bound on the number of mills (drills) required when overlap is not considered. The mn are obtained by rounding to the next highest integer, the ratio of the number of slots of all operations that require machine type n (M or D) divided by t. Then moM = r169/601 = r2.81 = 3 mills moD = r 68/601 = r1.1131 = 2 drills, where Fxl denotes the least integer greater than or equal to x. The grouping objective maximizes a linear combination of the slack variables to find the minimum number of required machines of each type. There are no additional constraints and variables that have not already been linearized for the capacity constraints in Section 4.2.

- 21 - The second objective formulated minimizes movements. The number of additional constraints required by an application of the second method is 48, and there are 16 new continuous variables. The first method introduces 16 integer variables and 32 constraints. However, several of the variables have previously been defined and linearized for the capacity constraints. Hence the first method introduces only 9 new integer variables and 16 new constraints. This information is summarized in Table 4. The constraint set cannot be reduced further by methods 4 or 5 because no two constraints contain any common variables. TABLE 4 Objective Function Linearizations Nonlinear Linearization Methods Formulations 1 2 Minimize Variables.. + 9. 1 (16) 1Constraint set cannot Movements Constraints _ + 16 48 be reduced further Balancing Variables+ (12) - Constraints 7.. 29 In general, the second method can require additional constraints using variables that previously have been linearized. The other methods do not require additional constraints for these variables. Finally, note that a composite objective can be defined that minimizes both movements and the number of required machines. This is achieved using a linear combination of the two objectives. The next loading objective that is linearized balances the assigned machine processing times. Some inequalities were used to reduce the number of new variables and constraints. Summarized in Table 4, the basic formulation introduces 7 continuous variables (the rj) and 7 constraints. Linearization by method 1 adds 12 continuous variables and 29 constraints. Formulations of the third (and fourth) loading objectives, (un)balancing, are similar to that of the first objective. In addition the resultant

- 22 - formulations are smaller than the first. Since machines are partitioned into groups and assignments are identical for each machine in a group, a capacity constraint is required only for each group rather than for each machine. The resultant smaller formulations are not linearized and solved here. 4.5 Problem Sizes A summary of the sizes of the linearized MIP formulations of the grouping problem, and the two representations of the loading problem, is given in Table 5. TABLE 5 Problem Sizes OBJECTIVES Maximize Minimize Pooling Movements Balancing Variables 48 + (113) 57 + (113) 48 + (132) ___._ = 161 = 170 = 180 Constraints 116 132 152 The computer code used to solve the three linearized mixed integer programming problems, MIPZ1, is described in McCarl, Barton and Schrage [1973]. Solution times ranged from about 1.5 to 2.5 minutes on a CDC 6600. The code is an adaptation of the code developed by Bravo, et al. [1970] and requires integer variables to be either zero or one. The algorithm is a modification of Balas's Additive Algorithm [1965] along the lines suggested by Glover [1968] and Salkin [1970]. Details are described in McCarl, et al. [1973]. 4.6 Solutions The nonlinear magazine capacity constraints result in larger linear MIP's, but also in better solutions. For the example, the solution to the grouping problem was that all three drills could be pooled. If overlap were ignored, the

- 23 - solution is that two drills are needed to hold all required tools. Consideration of tool duplication also allowed more pooling of mills than otherwise. The optimal solutions of the three MIP's are identical to those in Stecke and Solberg [1981b], which were obtained by heuristic means according to the same balancing/minimizing movements/pooling objectives. 5. Discussion The detailed nonlinear MIP formulations of the grouping and loading problems discussed in this paper provide optimal solutions that are feasible in actual applications. Linearizing methods have been suggested that are appropriate for different problems. For common problem sizes, the linearized MIP's can be solved. For larger systems, additional research needs to be done. Perhaps heuristic procedures, piecewise linear approximations, or linear relaxations of the MIP's could be used if optimal loadings are not required.1 The author would like to thank Bruce W. Schmeiser and James J. Solberg of Purdue University for their helpful comments during the preparation of this manuscript. The research was supported in part by the National Science Foundation Grant No. APR 74 15256.

- 24 - REFERENCES 1. 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). 2. BALAS, EGON, "An Additive Algorithm for Solving Linear Programs with Zero-One Variables," Operations Research, Vol. 13 (1965), pp. 517-545. 3. BRAVO, A., GOMEZ, J.G., LUSTOSA, L., SCHRAGE, L. and PIZZOLATO, N.D., A Mixed Integer Programming Code, Report 7043, University of Chicago, Chicago IL, September 1970. 4. COOPER, MARY W., "A Survey of Methods for Pure Nonlinear Integer Programming," Management Science, Vol. 27 (1981), pp. 353-361. 5. DANTZIG, GEORGE, B., Linear Programming and Extensions, Princeton University Press, Princeton NJ, 1962. 6. GINSBURGH, V. and VAN PEETERSEN, A., "Un algorithme de programmation quadratique en variables binares," Review Francoise d'Informaticue et de Recherche Operationnelle, Vol. 3 (1969), pp. 57-64. 7. GLOVER, FRED, "Surrogate Constraints," Operations Research, Vol. 16 (1968), pp. 741-749. 8. GLOVER, FRED, "Improved Linear Integer Programming Formulations of Non-Linear Integer Problems," Management Science, Vol. 22 (1975), pp. 455-460. 9. GLOVER, FRED, "Heuristics for Integer Programming Using Surrogate Constraints," Decision Sciences, Vol. 8 (1977), pp. 156-166.

- 25 - 10. GLOVER, FRED and WOOLSEY, EUGENE, "Further Reduction of Zero-One Polynomial Programming Problems to Zero-One Linear Programming Problems," Operations Research, Vol. 21 (1973), pp. 156-161. 11. GLOVER, FRED and WOOLSEY, R.E., "Converting the 0-1 Polynomial Programming Problem to a 0-1 Linear Program," Operations Research, Vol. 22 (1974), pp. 180-182. 12. HAMMER, PETER L., "A B-B-B Method for Linear and Nonlinear Bivalent Programming," Operations Research, Statistics and Economics Mimeograph Series No. 48, Technion, May 1969. 13. HANSEN, P., "Nonlinear 0-1 Programming by Implicit Enumeration," paper presented at the 7th Mathematical Programming Symposium, The Hague, September 1971. 14. HANSEN, P., "Methods of Nonlinear 0-1 Programming," Annals of Discrete Mathematics, Vol. 5 (1979), pp. 53-70. 15. HU, T.C., Integer Programming and Network Flows, Addison-Wesley, Reading, Massachusetts, 1969. 16. LAWLER, EUGENE L. and BELL, M.D., "A Method for Solving Discrete Optimization Problems," Operations Research, Vol. 15 (1967), pp. 1098-1112. 17. MARSTEN, ROY, E. and MORIN, THOMAS L., "A Hybrid Approach to Discrete Mathematical Programming," Mathematical Programming, Vol. 14 (1978), pp. 21-40. 18. McCARL, BRUCE, BARTON, DAVID and SCHRAGE, LINUS, MIPZ1 Documentation on a Zero-One Mixed Integer Programming Code, Dept. of Agricultural Economics, Purdue University, W. Lafayette IN, September 1973.

- 26 - 19. MORIN, THOMAS L., "Computational Advances in Dynamic Programming," Dynamic Programming and Its Applications, Martin L. Puterman, (ed.), Academic Press, New York, 1978. 20. SALKIN, HARVEY M., "On the Merit of Generalized Origin and Restarts in Implicit Enumeration," Operations Research, Vol. 18 (1970), pp. 549-555. 21. STECKE, KATHRYN E., "Experimental Investigation of a Computerized Manufacturing System," Master's Thesis, Purdue University, W. Lafayette, IN 47907, December 1977. 22. STECKE, KATHRYN E., "Production Planning Problems for Flexible Manufacturing Systems," Ph.D. Dissertation, Purdue University, W. Lafayette, IN 47907, August 1981. 23. STECKE, KATHRYN E. and SOLBERG, JAMES J., "The CMS Loading Problem," Report No. 20, NSF GRANT No. APR74 15256, School of Industrial Engineering, Purdue University, W. Lafayette, IN 47907, February 1981a. 24. STECKE, KATHRYN E. and SOLBERG, JAMES J., "Loading and Control Policies for a Flexible Manufacturing System," International Journal of Production Research, forthcoming in 1981b. 25. TAHA, HAMDY A., "A Balasian-Based Algorithm for 0-1 Polynomial Programming," Research Report No. 70-2, University of Arkansas, May 1970. 26. WATTERS, LAWRENCE J., "Reduction of Integer Polynomial Programming Problems to Zero-One Linear Programming Problems," Operations Research, Vol. 15 (1967), pp. 1171-1174.