THE OPTIMAL CONFIGURATION AND WORKLOAD ALLOCATION PROBLEM IN FLEXIBLE MANUFACTURING SYSTEMS Heungsoon Felix Lee Department of Industrial Engineering Southern Illinois University Edwardsville, IL 62026-1802 Mandyam M. Srinivasan Candace Arai Yano Department of Industrial & Operations Engineering The University of Michigan Ann Arbor, MI 48109-2117 Abstract In this paper we consider the problem of determining the minimum cost configuration (number of machines and pallets) for a Flexible Manufacturing System with the constraint of meeting a prespecified throughput, while simultaneously allocating the total workload among the machines (or groups of machines). Our procedure allows consideration of upper and lower bounds on the workload at each machine group. These bounds arise as a consequence of precedence constraints among the various operations and/or limitations on the number or combinations of operations that can be assigned to a machine because of constraints on tools slots or the space required to store assembly components. Earlier work on problems of this nature assumes that the workload allocation is given. For the single machine-type problem we develop an efficient implicit enumeration procedure which uses fathoming rules to eliminate dominated configurations, and present computational results. We discuss how this procedure can be used as a building block in solving the problem with multiple machine types.

1. INTRODUCTION A Flexible Manufacturing System (FMS) is a computer-controlled system of numerically controlled machines and automated material handling equipment. Each machine is capable of performing a variety of operations with minimal changeover times between operations. When a system is being designed, one critical decision is the number of machines of each type to be purchased. Another important decision is the number of jobs (or pallets of jobs) circulating in the system since this has a significant impact on the number and type of material handling equipment required. These decision variables define a system configuration, and normally such a configuration is maintained for several years. The appropriate configuration choice, however, is influenced by the allocation of workload among the various machines (or machine groups). Of course, the total workload of each machine type may change over time as the product mix changes, and the "true" optimal configuration should consider these dynamics. We consider a static (steady-state) situation here, and generalize earlier work by taking advantage of the ability to allocate workload among machines of the same type while simultaneously considering other practical constraints on the workload allocation. Our procedure can be used in several different ways. First, it can be used to identify a set of viable, cost-effective system configurations by applying it to a variety of realistic workloads and related workload allocation constraints. The robustness of these configurations to product mix changes could then be evaluated. Second, if it is difficult to predict changes in product mix, the procedure can be applied to the new mix to determine how the system configuration and workload allocation should be modified. Third, even if the number of machines of each type and the number of jobs is fixed, our procedure can be used to regroup the machines of each type and reallocate the workload among them as the product mix changes. I

We investigate the problem of simultaneously determining the minimum cost configuration and the corresponding optimal workload allocation subject to a constraint on system throughput for a FMS which consists of a given number of stations. Each station may have one or more identical machines of a specified type. We assume that the total workload to be allocated among stations of the same type is given. The decisions to be made are the number of machines (servers) and the workload allocated to each station, and the number of pallets. If there were no constraints on the allocation of the workload among the machines, the optimal solution would have a single station for each machine type, with all of the workload for that machine type assigned to it. Our procedure allows consideration of upper and lower bounds on the workload at each station. These bounds arise as a consequence of precedence constraints among the various operations and/or limitations on the number or combinations of operations that can be assigned to a station. The latter may be a result of constraints on tools slots or the space to store assembly components nearby (e.g., within the reach of assembly robots). Earlier work on problems of this type assumes that the workload allocation is given. In order to solve this problem, we must evaluate several candidate configurations to ascertain whether the throughput constraint is satisfied. To accomplish this, we use the algorithm of Lee et al. 119881 to solve the subproblem of allocating the total workload among the stations to maximize system throughput within the constraints imposed by the upper and lower bounds on the workload at each station. In order to reduce the number of candidate configurations that must be evaluated, we develop fathoming rules to eliminate dominated configurations. We develop a procedure to obtain the optimal configuration and workload allocation for the case where all the machines are of the same type. We also discuss how this procedure can be used as a building block to solve the problem with multiple machine types. 2

Previous research on related problems has typically used closed d queueing networks (CQNs) with the assumptions of exponential service, first-come-first-served service discipline, and arbitrary routings allowing multiple visits to a station to represent FMSs. Under these assumptions, the throughput function has the well-known product form (Gordon and Newell [1967]), and is therefore relatively easy to compute. The popularity of using queueing networks to model FMSs stems from its ability to capture the effects of congestion on throughput and queue lengths. Our model also assumes that the FMS is represented by a product form CQN (see Solberg [1977] and Sun and Hildebrant [1984J for CQN modeling of FMSs and support for its applicability). Vinod and Solberg 119851 and Dallery and Frein [19861 study the problem of finding the configuration that satisfies throughput requirements at minimum cost. Both capital equipment and operating costs are considered in their objectives. They assume that the number of stations and the workloads for each are given. (A station is represented by a multiple-server node in the queueing network.) The decisions are the number of machines to assign to each station, the number of pallets, and the number of automated guided vehicles (AGVs) where applicable. Yao and Shanthikumar [19861 and Shanthikumar and Yao [1987, 1988] study the problem of allocating servers to stations to maximize throughput. They assume that the number of stations and pallets, and the workload at each station are known. Their results suggest that a greedy allocation procedure is optimal. Various algorithms are available to solve the workload allocation in a product form CQN under the assumption that the number of stations, the number of machines at each station, the number of pallets, and the number of AGVs are given (see, for example, Yao [1985], Stecke and Solberg [19851, Stecke 11986], Lee et al. [19881). In our experiments, we will use the algorithm of Lee et al. They derive several properties of the optimal solution under the assumption that the throughput is a pseudo-concave function of the 3

workload allocation. Under this assumption, the first order conditions are both necessary and sufficient for optimality. These properties are then used as the basis for an efficient reduced gradient algorithm to find the optimal workload allocation when there are lower and upper bounds on the workload for each station. Previous research has thus considered obtaining either the minimum cost configuration assuming a given workload allocation, or the optimal (unconstrained) allocation of the total workload assuming a given system configuration. Our work differs in that we consider obtaining the optimal system configuration and the optimal workload allocation simultaneously. We assume that each operation can be done by only one type of machine, and that the machine types have been predetermined. Hence, for each machine type there is an aggregate workload which is the total processing time for all the operations that can be performed by that machine type. We assume that the total cost of machines of a given type depends only upon the total number of machines of that type, and is independent of where the machines are physically located or what operations each machine actually performs. The remainder of the paper is divided as follows. In section 2, we state a mathematical formulation of the minimum cost configuration problem for a system with a single machine type. In section 3, we present an optimal algorithm for this problem, including fathoming methods to eliminate dominated configurations. Related computational results appear in secion 4. In section 5, we present a solution procedure for the problem with multiple machine types. Section 5 also considers the system with batch transfer, where more than one part is transferred between stations at a time. We conclude with a brief summary and discussion in section 6. 4

2. PROBLEM FORMULATION As mentioned earlier, the optimal configuration and workload allocation problem is to simultaneously determine the optimal workload allocation, and the number of machines (servers) and pallets required to achieve a prespecified throughput at minimum cost. Here we assume that the number of stations, M, is given. However, if the number of stations is also a decision variable, one can simply solve this problem for several values of M. The total workload, TW, is the total expected machine processing time for one part. The workload allocation is specified by the vector W = (WO, WI,...,WM) where Wo is the total expected material handling time for one part, which is assumed to be a known constant, and Wi denotes the workload at station i, i = I,...,M. The number of servers at station i, Si, i = 1,...,M, and the number of pallets, N, define a configuration. For ease of presentation, we define S = (S,,...,SM). We initially assume each pallet carries only one part, which is common when parts are relatively large, but later relax this assumption. We first consider a simple FMS where there is only one type of machine. We assume that the material handling system (MHS) is a delay node. This means that there is a delay in transferring a part from one machine to another, but there is no contention for the MHS that results in any additional (queueing) delays. Typically, these systems are designed to prevent them from becoming bottlenecks, so this assumption is reasonable for many systems. Examples include loop conveyors and dedicated (stop-and-go) AGVs. Material handling systems for which considerable contention occurs may be modeled by representing them as other (processing) stations in the system. The cost function, z(N,K), is permitted to be any function which increases with N and M K = C Si. Thus, the annualized cost of the machines, material handling equipment, i=l pallets, and work-in-process inventory can be incorporated into the objective function. A mathematical formulation of the problem is to 5

P1: Minimize z(N,K) subject to: M K = X Si, (1) i=l TH(M,N,S,W) > d, (2) M Wi = TW, (3) i=l Li < Wi < Ui, i=..., M, (4) where TH(M,N,S,W) = throughput of the system, given M,N,S,W, d = throughput requirement, Li = lower bound on the workload at station i, and U = upper bound on the workload at station i. As mentioned earlier, the upper and lower bounds may be consequences of precedence relations among operations and/or constraints on the number or combinations of operations that can be assigned simultaneously to the station. In Appendix 1, we give an example to show how the upper and lower bounds are affected by precedence relations in a flow system. It should be intuitively clear how tool slot limitations, or constraints on the combination of assembly operations induced by consideration of the space required to store components nearby, will affect the upper bounds on workloads. Deriving tight bounds is not always easy, partly because the bounds at one station may influence the bounds at other stations. In many situations, however, they may be specified on the basis of experience. 3. AN OPTIMAL SOLUTION PROCEDURE We now consider a solution procedure for determining the optimal configuration and associated workload allocation for the FMS. We first present an overview of our procedure. This is followed by a detailed description of each step of the procedure, including fathoming methods which eliminate dominated configurations. 6

Procedure to Find the Optimal Configuration and Workload Allocation. 1. Find an initial feasible configuration and workload allocation, N1, S1, and WI, and set the incumbent equal to this solution. Let z represent the cost of the incumbent. 2. Find lower bounds on the number of pallets and the total number of servers, denoted as NLB and KLB" respectively, below which the prespecified throughput cannot be satisfied. 3. Implicitly enumerate over values of N and K satisfying N ~ NLB, K 2 KLB, and z(N,K) < z. The initial feasible solution in step I is obtained in the following manner. First, an initial feasible workload allocation is obtained by solving the workload allocation problem under the assumption that each station has an identical number of servers. Since balancing the workloads is optimal (for the unconstrained problem) when each station has the same number of servers, for reasonable upper and lower bounds on the workloads the resulting workload allocation is nearly balanced. Given this workload allocation, an initial feasible configuration is then obtained using the method of Dallery and Frein 119861. Since the initial feasible workload is nearly balanced, the initial feasible configuration generally has a similar number of servers at each station and, consequently, is easy to identify. This "balanced" solution serves as an initial solution for Problem PI. The lower bounds, NL' and K-.B, in step 2 can be derived using the asymptotic bound analysis of Muntz and Wong [ 1974]. Using this method, NLB is Fd.(TW+Wo0) where Fxl is the smallest integer greater than or equal to x. This simply says that the number of pallets in the system should be at least as large as the demand (arrival) rate multiplied by the minimum sojourn time in the system. KL-" is max (Fd-TW1, F S-LB ) where SiLB is 1=1 the lower bound on the number of servers at station i and is given as S LB =[dLiJ with [y] denoting the smallest integer greater than y. This essentially says that the total number of servers must be large enough so that the total system utilization and the utilization levels of 7

the individual stations are less than one. Dallery and Frein [19861 also use asymptotic bound analysis to obtain lower bounds on the number of pallets and machines. The implicit enumeration of step 3 is executed by considering all undominated combinations of N and K. For each (N,K) pair, we must determine whether there is a feasible S and W for P1. Related to this decision problem, we define another problem which is formulated as follows: P2: maximize TH(S,W) subject to constraints (1), (3), (4) of PI. _ * _ * Denote as S (N,K) and W (N,K) the optimum solution to P2. Clearly, when TH(S (N,K),W (N,K)) < d, there is no feasible solution to the problem for the given N and K. Later in this section we provide a procedure to solve P2. Before doing so, we present two lemmas that permit us to eliminate some dominated (N,K) pairs. Proofs of the lemmas appear in Appendix 2. Lemma 1. If TH(S (N,K),W (N,K)) < d, then TH(S (N,K- ),W (N,K- )) < d. Lemma 2. If TH(S (N,K),W (N,K)) < d, then TH(S (N-1,K),W (N-l,K)) < d. We solve P2 by generating all partitions of K machines among M stations and sequencing them from the most unbalanced to the most balanced. (This ranking turns out to be a lexicographic ordering.) Observe that for each partition, there are several different Ss, each of which corresponds to a different permutation of the station indices. For example, there is only one way to partition three machines into two groups: two machines in one group and one machine in the other. This partition gives two different Ss: (1,2) and (2,1). In order to distinguish between partitions and the various Ss, a partition is denoted by G=(GI,...,GM), where G1 2 G2...GM. x

Our rationale for sequencing the partitions from the most unbalanced to the most balanced is based upon the empirical observation by Stecke and Solberg [1985] that more unbalanced configurations achieve a higher throughput. Justification for this conjecture is based on the pooling effect (Kleinrock [1976]): a larger group of pooled machines can be loaded more heavily simply because pooled servers can achieve a higher utilization than an equal number of single servers given the same average customer waiting time. For each candidate S, we use the algorithm of Lee et al. [1988] to determine the workload allocation that maximizes throughput subject to constraints (3) and (4) of PI. In that paper, the throughput for a CQN is shown to be a pseudoconcave function of the workloads in special cases. Based on the conjecture that the function is pseudoconcave in general, two algorithms are developed: a reduced gradient procedure (Avriel 119761), and a fixed point procedure (Saigal 119771). The reduced gradient procedure is basically an ascent algorithm in which all of the variables can be changed simultaneously. A fixed point procedure is an iterative algorithm which converges to the solution, usually by changing one variable at each iteration. Both procedures take advantage of the fact that satisfaction of the Kuhn-Tucker (first order) conditions are both necessary and sufficient for optimality in a linearly constrained problem if the objective function is pseudoconcave. (Weaker forms of concavity require computation of the Hessian to find the optimal solution.) The fixed point procedure also uses the result that if the number of customers in the system is greater than the maximum number of servers at any station, the optimal solution is an interior Brouwer's fixed point. This fixed point can be found by the Eaves-Saigal (Saigal [19771) procedure, which converges quadratically for unconstrained problems. The workload allocation problem is complicated by the existence of upper and lower bounds on the workloads. Incorporating workload bounds into the fixed point procedure is easy, but quadratic convergence is no longer guaranteed because of the manner in which 9

constraints are handled by the procedure. In the case of the reduced gradient procedure, it is necessary to find an initial feasible solution, and a simple algorithm to find such a solution is presented in Appendix 3. We use the reduced gradient procedure in our compuational experiments. A computational comparison of the reduced gradient and the Eaves-Saigal algorithms appears in Lee et al. [1988]. Each candidate S is considered in turn until a configuration that satisfies the throughput constraint is identified or until all configurations have been considered and none satisfies the constraint. Some of the Ss can be eliminated from consideration using the lemmas below. Proofs of the lemmas appear in Appendix 2. Lemma 3. If U1 i Lk for any i and k, then we only need to consider S such that Si < Sk. Lemma 4. If Li < Lk < Ui S Uk for any i and k, then we only need to consider S such that Si < Sk. Qualitatively, Lemmas 3 and 4 state that a station with a greater workload should be assigned a larger number of servers. Lemmas 1 and 2 eliminate many (N,K) pairs. For each of the (N,K) pairs that still remain for consideration, we need to consider all possible partitions of K among the M stations, and each such partition will give rise to several possible permutations of the server vector. Lemmas 3 and 4 eliminate many of these permutations from consideration. In addition, other permutations can be eliminated from consideration using the following observation which is based upon the assumption of unimodality of the throughput function (Stecke and Solberg [1985], Stecke [19861, Lee et al. [1988]). Remark. Let WI be the optimal workload allocation for a given server vector S1. Also let I denote the set of stations for which Li < Wi' < Ui. Suppose we now permute the server vector and its corresponding workload vector for just those stations in the set I to get a new server vector S2 and a workload vector W2. If, for this configuration, we have Li 5 10

Wi2 I Uj for all i, then this workload allocation is also optimal, since the throughput of these two configurations is identical. The above remark enables us to eliminate the server vector S2 from consideration in the search process for such cases. It should also be noted that any S with Si < S1LB for any i can be eliminated from consideration, where SiLB is obtained from asymptotic bound analysis. We now elaborate on the implicit enumeration over N and K, which is step 3 of the procedure given earlier. In the implicit enumeration, we use the results in Lemmas 1 and 2 and the fact that z(N,K) is increasing in N and K to fathom solutions. We use NP and KP to refer to the values of N and K, respectively, in the present incumbent solution. The initial solution, NI and S1 provides the first incumbent solution. A description of the procedure follows. The Implicit Enumeration Procedure for Step 3. (Step 3a finds the next incumbent solution by decreasing K as much as possible from the initial solution K1 obtained from step 1 while maintaining feasibility.) (3a) For N = N1, find the smallest value of K 2 KLB for which TH(S*,W*) > d. This provides an incumbent solution which we denote as (Nf,Kf). Set (NP,KP) = (Nf,Kf). (Steps 3b and 3c search over N > Nf. For each value of N, the smallest feasible value of K is found. Whenever a feasible solution with lower cost is found, the incumbent solution is updated.) (3b) Increase N by one and find the largest K such that z(N,K) < z(NP,KP). (3c) If K < KB, then set K to Kf - 1, and go to step 3d. If K KLB and TH(S*,W*) < d, then go to step 3b. In all other cases, update the incumbent solution, reduce K by one, and repeat this step. 11

(Steps 3d and 3e search over K > K. For each value of K, the smallest feasible value of N is found. Whenever a feasible solution with lower cost is found, the incumbent solution is updated. (3d) Increase K by one and find the largest N such that z(N,K) < z(NP,KP). (3e) If N < NLB then go to step 3f. If N > NL-B and TH(S*,W*) < d, then go to step 3d. In all other cases, update the incumbent solution, reduce N by one, and repeat this step. (3f) The incumbent solution is optimal. Terminate. Example: We provide an example to clarify the solution procedure for problem P1. Let M=3 and Wo=8. Also let the processing capacity of a machine (i.e., total service time available from a machine during a period) be 960 time units. The number of units required during this period is 100 items, giving a throughput requirement of 100/960 items per unit time. The problem is to: minimize z(N,K) = 600 N + 5(XX) K subject to: 3 K = ~ Si i=1l TH(M,N,S,W) > 100/960, 3 Wi 30, i=l 5 W$110, 10I W2< 15, 5< W3<20. From Lemmas 3 and 4, we must have S < S2 and S1 < S3. We execute the three steps outlined in the procedure. 1. Initial solution: W1 = (110,0,10), S1 = (2,2,2), KI=6, N'=5, with cost z(5,6) = 33000. 2. Lower bounds: SLB=(1,2,1), KLB=4, and NLB=4. 12

3. The implicit enumeration procedure: (3a) With N = N = 5, we decrease K as much as possible, while maintaining feasibility. We obtain K = 5, and z(5,5)=28000. When K=5, there are two possible partitions: G1=(3,1,1) and G2=(2,2,1). The partition G1 provides two server vectors: S1=(1,1,3) and S2=(1,3,1). S1 is eliminated since S21 < S2LB. For S2, the workload allocation problem is solved and the resulting throughput is less than the required throughput. The partition G2 provides only one server vector: S1=(1,2,2). The solution to the workload allocation problem gives a throughput which is less than the throughput requirement. Thus, there is no feasible solution at N=5, K=5, and so (Nf,Kf) = (NI,KI) = (5,6). (3b,c) Search over N > N1. We first consider N = Nf + 1 = 6. To find the smallest feasible K, we start with K=5, giving z(6,5)=286()0. When K=5, the partitions G1=(3, 1,) and G2=(2,2,1) are examined. A better feasible solution is found when the the workload allocation problem is solved with S1=(1,2,2), and so the incumbent solution is updated as (NP,KP)=(6,5). We next decrease K by 1. This provides one partition G1=(2,1,1) and two resulting server vectors S =(1,1,2) and S2=(1,2,1). No feasible solution is found for both Ss: S1 is eliminated from further consideration since S21 < S2LB, and S2 is eliminated since TH(S2,W*) is less than the throughput requirement. We now increase N by one unit at a time and, for each value of N, find the largest K such that z(N,K) < z(NP,KP), and the solution is feasible. For N=7, in order to have z(N,K) < 28,600, we must have K54, but this gives a throughput less than the requirement. Similarly, for N=8, we must have K54, but this is infeasible too. A better feasible solution is found at N=9, K=4, with S2=(1,2,1). The incumbent solution is updated as (NP,KP)=(9,4). We now try to decrease K. This results in K < KLB. (3d,e) Search over K > Kf. For K=6, the largest N such that z(N,6) < z(NP,KP)=25400 is less than NLB. (3f) The current incumbent solution, namely, (NP,KP)=(9,4), with S*=(1,2,1) and W*=(7.5, 15, 7.5), is optimal. 13

The search process for the example is illustrated graphically in Figure 1. Figure 1. 4. EXPERIMENTAL RESULTS We use five sets of parameters to illustrate the optimal algorithm for a single machine type. We use the following linear cost function for z(N,K): z(N,K) = (Ch + Cp + Ca) * N + Ck * K where Ch, Cp, Ca and Ck are the annualized costs of a unit of work-in-process (WIP) inventory, a pallet, a stop-and-go AGV, and a machine respectively. When the MHS is a loop-conveyor instead of AGVs, Ca is assigned a value of zero. Note that only the ratios of these cost parameters are relevant since the cost function is linear. To investigate various scenarios, we use different ratios for the five sets of cost parameters. The workload bounds are chosen arbitrarily, but are consistent with the other problem data. The problem data are presented in Table 1. Table 1. The algorithm was coded in FORTRAN and run on an IBM 3090-600, using the VS-opt3 compiler. The following statistics were collected at termination of the algorithm for each problem: the optimum solution and its cost, the number of throughput computations, the number of workload allocation problems solved, and the CPU time. The number of throughput computations was recorded since this consumed most of the CPU time. The statistics are summarized in Table 2. Table 2. The results show that CPU time is sensitive to the throughput and the total workload. This follows since a larger aggregate workload (d.TW) necessitates more servers, which in 14

turn increases the number of partitions to be evaluated. The longest CPU time (17.28 sec.) was observed for problem D which had the largest d (200/960) and the largest TW (80). 5. EXTENSIONS We now consider more general versions of problem PI in which we relax some of the assumptions made in Section 2. We first relax the assumption that a pallet carries only one part. When the parts are small, a pallet can carry a batch of parts; thus, the batch size may be another decision variable. Under Q-part transfer (where Q is the batch size), the Q parts are processed consecutively at the same machine. Thus, the Q units can be viewed as one "part" of a new product type whose total workload is Q-TW. The workload and throughput parameters in PI must be scaled accordingly. The cost associated with pallets in the objective function should reflect the WIP inventory cost for Q parts instead of one part per pallet. We assume that the expected material handling time (Wo) remains the same regardless of the batch size. In other words, the speed of the handling equipment is unaffected by the weight of the pallets. Therefore, with Q-part transfer, the formulation of Problem P1 is restated as: PIQ: Minimize z(N,K,Q) M subject to: K = ~ Si i=1 TH(M,N,S,W) > d/Q, (5) M ~ Wi = Q.TW, (6) i=1 Q-Li 5 Wi < Q-Uij i=l,...,M. (7) We use the examples in Table 3 to study the effect of Q on the minimum cost. For Q = 1, 2, 3, 4, 5, 10, 15, 20, and 30, we solved Problem P1Q. The results are shown in Figure 2. We assume that WIP inventory costs are linear with respect to Q. The optimum batch size is determined by trading off three cost terms: material handling cost, machine cost and 15

WIP inventory cost. A large Q reduces the number of material moves, but increases WIP inventory cost. To compensate for this, the optimal value of N, the number of pallets (and stop-and-go AGVs) in the system usually declines. As a result, servers may be idle for a long time while waiting for a pallet to arrive. This, in turn, increases the number of machines required to achieve the desired throughput. We observed that the total cost function is unimodal in Q. Based on this observation, it appears that a search procedure could be adequate to solve the problem. Figure 2. We now consider the case of C machine types, and assume Q=l for ease of presentation. Let TWc be the total workload for machine type c, i.e., the mean service time demanded by a part from machine type c. Also let: Kc = number of machines of type c, Mc = number of stations of type c, Sci = number of machines at station i of type c, Wci = workload for station i of type c, Lci = lower bound on workload for station i of type c, Uci = upper bound on workload for station i of type c. The optimum configuration and workload allocation problem becomes: pIC: Minimize z(N,Ki,K2,..., KC) subject to: Mc Kc = Sci, c=l,...,C, (8) i=,I TH(M,N,S,W) 2 d,- (9) Mc Wci = TWc, c=l,...,C, (10) i=l Lci ~ Wci < Uci, i=l,...,Mc, c=l,...,C, (11) 16

where z(N,Ki,K2,..., Kc) is any cost function that increases with N and Kc for any c; C M = Y Mc; S = (Sc) with Sc = (Scl,...,ScMc); and W = (Wc) with We = (Wcl,...,WcMc). c=1 The solution procedure for Problem Plc is as follows. We consider each machine type, c, in isolation and use the solution procedure developed in section 3, to obtain the optimal values of K<*, Sc', Nc, and W,* with a throughput requirement of d. We next consider the overall system with the C machine types, with a server vector given by the Sc* values, and a workload allocation given by the Wc* values found above. This system is evaluated for each N until the throughput is greater than or equal to d. This gives us an initial feasible solution. Let CUB denote the cost of this solution. Clearly a lower bound on the cost, CLB, is given by Kc"', c= l,...,C, and N1", which are obtained in the same way as for the single machine type case. We now generate all possible combinations of (Ki,..., Kc, N) which have cost between CUB and CLB, rank these combinations in decreasing order of cost, and implicitly enumerate the candidates in this list using a bisection search. For each candidate examined, we obtain the optimal configuration and the corresponding workload allocation by solving problem P2C, which is a generalization of problem P2: P2C: Maximize TH(S,W) subject to constraints (8), (10), ( 1 ) of P IC. Lemmas 1 through 4 and the Remark can be generalized and applied to Problem P2C. It can easily be shown that the maximum throughput remains monotonic with respect to N and Kc for c=,...,C (cf. Lemmas I and 2). Also, Lemmas 3 and 4, and the Remark hold for stations of the same machine type. If the resulting throughput is feasible, then we can reduce the number of candidates which still need to be examined by half, and continue the bisection search. On the other 17

hand, if the candidate being examined does not provide a feasible solution, then we cannot reduce the number of remaining candidates by half. However, we can still eliminate the current configuration and other configurations which are infeasible because of the monotonicity of the throughput function with respect to N and Kc, c = 1,...,C. We then resume the bisection search on the remaining candidates. Since we use a bisection search, the workload allocation problem may need to be solved only for a relatively small number of candidates. 6. CONCLUSIONS In this paper, we considered the problem of finding the minimum cost configuration for an FMS subject to a constraint on throughput when there is some flexibility in allocating the workload among stations. The cost function includes the cost of machines, as well as the costs of material handling equipment and work-in-process inventory. We presented an implicit enumeration procedure for the problem with one machine type. We developed several fathoming methods to reduce the number of system configurations that must be evaluated. Computational experience with the algorithm suggests that problems of moderate size can be solved optimally within 20 seconds of CPU time on the IBM 3090-600 mainframe. We also outlined an optimal algorithm for the more general problem with multiple machine types. Further research is needed to develop efficient heuristics for this problem. ACKNOWLEGEMENT We thank Dr. Yeong-Dae Kim for providing the FORTRAN code which generates partitions for a given number of machines. The helpful comments and suggestions of the Editor, the Associate Editor, and the referees are greatly appreciated. 18

REFERENCES Avriel, M., 1976. Nonlinear Programming Analysis and Methods, Prentice-Hall, Inc., Englewood Cliffs, NJ. Dallery Y. and Y. Frein, 1986. An Efficient Method to Determine the Optimal Configuration of a Flexible Manufacturing System. Proc. of the 2nd ORSAITIMS Conf. on Flexible Manufacturing Systems, Elsevier Science Publishers, B.V., Amsterdam, pp. 269-282. Gordon, W.J. and G.F. Newell, 1967. Closed Queueing Networks with Exponential Servers. Operations Research, Vol. 15, pp. 252-267. Kleinrock, L., 1976. Oueueing Systems I and II, John Wiley and Sons, Inc., New York, NY. Lee, H.F., M.M. Srinivasan and C.A. Yano, 1988. Some Characteristics of Optimal Workload Allocation for Closed Queueing Networks. Technical Report 88-9, Dept. of Industrial and Operations Engineering, The University of Michigan, Ann Arbor, MI. Muntz, R.R. and J.W. Wong, 1974. Asymptotic Properties of Closed Queueing Network Models. Proceedings of the 8th Annual Princeton Conference on Information Sciences and Systems, Princeton University, Princeton, NJ. Saigal, R., 1977. On the Convergence Rate of Algorithms for Solving Equations That Are Based on Methods of Complementary Pivoting, Math. Oper. Res., Vol. 2, pp. 108-24. Shanthikumar, J.G. and D.D. Yao, 1987. Optimal Server Allocation in a System of MultiServer Stations. Management Science, Vol. 33, No. 9, pp. 1173-1180. Shanthikumar, J.G. and D.D. Yao, 1988. On Server Allocation in Multiple Center Manufacturing Systems. Operations Research, Vol. 36, No. 2, pp. 333-342. Solberg, J.J., 1977. A Mathematical Model of Computerized Manufacturing Systems. Proc. 4th Int. Conf. of Prod. Res., Tokyo, Japan. Stecke, K.E., 1986. A Hierarchical Approach to Solving Machine Grouping and Loading Problems of Flexible Manufacturing Systems. European J. of Operational Research, Vol. 24, pp. 369-378. Stecke, K.E. and J.J. Solberg, 1985. The Optimality of Unbalancing Both Workloads and Machine Group Sizes in Closed Queueing Networks of Multi-Server Queues. Operations Research, Vol. 33, No. 4, pp. 882-910. Suri, R., 1985. A Concept of Monotonicity and Its Characterization for Closed Queueing Networks. Operations Research, Vol. 33, No. 3, pp. 606-624. Suri, R., and R.R. Hildebrant, 1984. Modeling Flexible Manufacturing Systems Using Mean-Value Analysis. Journal of Manufacturing Systems, Vol. 3, No. 1, pp. 27-38. Vinod, B. and J.J. Solberg, 1985. The Optimal Design of Flexible Manufacturing Systems. Int. J. Prod. Res., Vol. 23, No. 6, pp. 1141-1151. Yao, D.D., 1985. Some Properties of the Throughput Function of Closed Networks of Queues. Operations Research Letters, Vol. 3, No. 6, pp. 313-317. Yao, D.D. and J.G. Shanthikumar, 1986. Some Resource Allocation Problems in MultiCell Systems. Proc. of the 2nd ORSAITIMS Conf. on Flexible Manufacturing Systems, Elsevier Science Publishers, B.V., Amsterdam, pp. 245-256. 19

APPENDIX 1 In this Appendix, we give a simple example to show how precedence constraints among operations influence the upper and lower bounds on workloads. Consider a flexible flow system with one machine type which is capable of processing all 30 operations for a given product. However, because of tool magazine constraints or limits on the number of components that can be located nearby, only 20 operations can be performed by a given machine at any point in time. Suppose the precedence relations specify that operation j must be performed before operation k ifj < k (i.e., serial precedence structure). It is clear that two stations are sufficient. For simplicity, we will assume that two stations are used. Assume that the processing time of operation i is i time units. The total workload per unit is 465 minutes. If we were to ignore the precedence constraints discussed above, the upper and lower bounds would be: 10 L1=L2= ~ti=55 i=30 and U = U2 = ti = 410. i= ll On the other hand, if precedence constraints are considered, a little logic will show that: 10 L = ti=55, i=1 20 U1= ~ti=210, i=1 30 L2= ti = 255, and i=21 30 U21= ti=410, inl I which are quite different from the bounds given above. It is important to note that a continuous workload allocation satisfying the latter set of constraints may not be achievable given the actual operation times. However, such an allocation is much more likely to be achievable (with respect to precedence constraints) than that obtained using the looser bounds. 20

APPENDIX 2 In this Appendix, we provide proofs of Lemmas 1 through 4. Lemmas 1 and 2 permit us to eliminate some dominated (N,K) pairs while Lemmas 3 and 4 permit us to reduce the number of Ss that must be considered for each undominated (N,K) pair.._* _, -* _. _ Lemma 1. If TH(S (N,K),W (N,K)) < d, then TH(S (N,K- 1),W (N,K-1)) < d. Proof: We will prove this by contradiction. Suppose TH(S (N,K),W (N,K)) < d and -* = * — * th TH(S (N,K- I),W (N,K- )) > d. Add to S (N,K- 1) one server in the it station to give a total of K servers. Then, it follows from the results on the monotonicity of throughput with increasing service rates (Suri 119841) that TH(S (N,K-l)+ei,W (N,K-1)) 2 * _- * TH(S (N,K-1),W (N,K-l)) > d where ei is a unit server vector with all elements zero except the ith element, which is set to 1. By definition of S (N,K) and W (N,K), TH(S (N,K), W (N,K)) > TH(S (N,K-l)+ei,W (N,K-l)) 2 d. This contradicts our original assumption. U Lemma 2. If TH(S (N,K),W (N,K)) < d, then TH(S (N-I,K),W (N-1,K)) < d. Proof: The proof is similar to that of the previous lemma. U Lemma 3. If Ui < Lk for any i and k, then we only need to consider S such that Si5 Sk. Proof: The product-form CQN under consideration consists of one delay node (the MHS station) and M multiple-server stations. The delay node also can be viewed equivalently as a multiple-server node with N servers, so there are no queueing delays. Thus, the CQN can be treated as a network where all stations have one or more servers. Shanthikumar and Yao [19881 show that the throughput function TH(S,W) of the multiple-server productform CQN is decreasing in transportation. That is, interchanging Si and Sk so that Si 5 Sk whenever Wi 5 Wk, may increase, and does not decrease, the throughput. This 21

rearrangement changes neither K nor z(N,K). Thus, if such a rearrangement is possible, it is preferable to do so. When Ui ~ Lk, W, ~ Wk for any feasible W. Therefore, any Ss not satsfying the relationship in the lemma are dominated. / Lemma 4. If Li ~ Lk < Ui 5 Uk, then we only need to consider S such that Si < Sk. Proof: For any feasible W, we have two cases. Case 1) Wi < Wk. From Lemma 3, we only need to consider S such that Si < Sk. Case 2) Wi > Wk. Consider W' = (W1',...,WM') which is obtained by interchanging Wi and Wk of W while keeping the other workloads fixed. This W' is feasible since Li 5 Lk < Wk < Wj, Ui ~ Uk implies that Li < Wk S U, and Lk 5 Wi ~ Uk, or equivalently, Li 5 Wi' 5 Ui and Lk < Wk' S Uk by the definition of W'. Hence, by applying the result of Case 1 to W, we prove this lemma. This argument is valid since the throughput function is permutation invariant, i.e., TH(S,W) = TH(7T(S),rc(W)) for any permutation it. 22

APPENDIX 3 The following algorithm can be used to find a good initial feasible solution to the constrained workload allocation problem. We assume that the indices of the stations are arranged so that Si 2 S2 >... > SM. We also assume that there is a feasible workload allocation (i.e., TW < Zi Ui). 1) Find a balanced workload allocation, W. If it is feasible, then terminate. Otherwise go to step 2. 2) Let A = ( i I Wi > Ui }, B = { i I Wi < L }, SA = ~ (Wi - Ui), SB = ~ (L. - Wi). lEA i~B Reset Wi to Ui for all i e A and to Li for all i e B. If SA - SB > 0 (less than the total workload is allocated), go to step 3. If SA - SB < 0 (more than the total workload, TW is allocated), go to step 4. Otherwise, terminate. 3) Reallocate SA - SB by assigning as much additional workload as possible to stations 1,...,M in sequence while maintaining feasibility. Terminate whenever a feasible reallocation has been found. 4) Reduce the workloads at stations M,..., I in sequence while maintaining feasibility, until a total reduction of SB - SA has been achieved. The rationale for steps 3 and 4 is a result of Shanthikumar and Yao [19881 that for the multiple-server product-form CQN, throughput is increased by assigning more workload to a station with a larger number of servers. 23

Figure 1. An Example for the Implicit Enumeration Procedure Legend: X an initial feasible solution O a better feasible solution * an infeasible solution a a solution fathomed by lemmas 1 and 2 K z(N,K)=6(X)N + 5000KK 6 5 z(N' )"" 00'N"+- 5000 z(5,6) = 33,000 at the initial solution IV9 ^'-^' _~ ----- z(6,5) = 28,600 at the first improved solution 3 34 ~z(9,4) = 25,400 at the second improved solution, which is optimal bNP=4 5 6 7 8 9 N The numbers near the circles indicate the sequence in which the solutions are evaluated. The optimum solution is indicated by "6". 24

Table 1. Five Data Sets Problem M d*960 TW W0 Ch Cp Ca Ck A 3 100 30 8 100 500 0 5000 B 4 100 60 25 100 500 600 2000 C 5 150 8 48 1 500 1000 D 6 200 80 35 1 500 500 1500 E 8 1() 80 18 100 500 500 2500 Problem L (workload lower bound) U (workload upper bound) A (5,10,5) (10,15,20) B (5,10,15,15) (10,40,30,40) C (5,10,15,15,5) (30,40,30,40,50) D (5,5,5,5,5,5) (40,40,40,40,40,40) E (5,10,15,15,1,10,5,1) (10,40,30,40,50,20,10,40) 25

Table 2. Results of Experiments with the Optimal Algorithm Problem Optimum solution Optimum cost Number of Number of CPU time ~(N, -s- ~throughput workload (sec.) (N, S,, W) l|computations allocation problems A 9, (1,2,1) 25,400 24 8.05 (7.5,15,7.5) B 12, (1,2,2,4) 32,400 74 18.11 (5,11.7,15,28.3) C 25, (2,3,3,6,3) 29,525 940 448 4.20 (7.4,13.2,15,30.5, 13.9) D 28, (10,5,2,2,2,2) 62,528 2285 343 17.28 (40,17.84,5.54,5.54, 5.54,5.54) E 17, (1,2,2,2,2,2,1,1) 51,200 25 13.11 (5,12.3,15,15,12.3, 12.3,5,3.1) ) ___ 26

80000 70000 o8 60000 - D 50000 40000 30000 C 20000-, 0 10 20 30 Q Figure 2. Effect of Transfer Batch Size Q on Optimum Cost 27