Division of Research School of Business Administration The University of Michigan December 1991 PART TYPE SELECTION AND BATCH SEQUENCING IN A FLEXIBLE FLOW SYSTEM Alessandro Agnetis Universita degli Studi di Roma "La Sapienza" Claudio Arbib II Universita degli Studi di Roma "Tor Vergata" Kathryn E. Stecke* The University of Michigan Working Paper # 670 *This research was begun while the third author was at the Fraunhofer Institute fiur Arbeitswirtschaft und Organisation, Stuttgart, Germany.

I

PART TYPE SELECTION AND BATCH SEQUENCING IN A FLEXIBLE FLOW SYSTEM Alessandro Agnetis Universita degli Studi di Roma "La Sapienza" Dipartimento di Informatica e Sistemistica Roma, Italy Claudio Arbib II Universita degli Studi di Roma "Tor Vergata" Dipartimento di Ingegneria Elettronica Roma, Italy Kathryn E. Stecke* The University of Michigan Graduate School of Business Administration Ann Arbor, Michigan December 1991 *This research was begun while the third author was at the Fraunhofer Institute fur Arbeitswirtschaft und Organisation, Stuttgart, Germany.

I

ABSTRACT A new approach to part type selection and the scheduling of batches over time in a flexible flow system is presented. The system consists of two machines, and all parts visit the two machines in the same order. The approach consists of first selecting a small number of part types for simultaneous production, in suitable ratios, in order to balance the workloads among the machines while not violating interstage buffer limitations. Production is organized in batches consisting of two part types each. Batches are then sequenced with the aim of minimizing the total number of tool changing operations. Detailed scheduling of each batch can be accomplished with no machine idle time and with minimum work-in-process requirements. Some advantages of the approach as presented here include management effectiveness and simplicity, in addition to other operational benefits inherent in a dynamic and flexible approach to part type selection (such as a higher utilization of the machines, a smoother tool changing activity, etcetera).

I

1. INTRODUCTION This research addresses some particular planning problems in flexible flow systems. In particular, the focus of the research is concerned with determining how to produce over time parts of many types, each with different production requirements, on two different machines. All parts are processed first on machine M1 and then on machine M2. The proposed approach accounts for optimal machine utilization, storage limitations, and tooling issues such as tool magazine capacity and change-over time minimization. In particular, approaches are specified to first partition all of the part types into overlapping batches, each batch to be produced consecutively over time. This is called part type selection (PTS). Each operation of each part type requires certain cutting tools that need to be placed in the corresponding machine's tool magazine. The PTS approach selects tool-compatible part types, i.e., part types that can be machined together subject to tool magazine capacity. Then, we also address the problem of batch sequencing (BS), i.e., finding the best sequence in which the overlapping batches should be processed. It usually takes some time to change tools in between finished and new batches of part types. We suggest a batch sequencing policy that minimizes the total change-over time, when different part types require different tool sets. More generally, our policy minimizes the total number of times parts types are reprocessed. Since changing more part types means in general changing more tools, a good bound to the overall change-over time is achieved in this way. The approach here can accommodate any tool-changing mechanism, either manual or automatic. Depending on each specific situation, different objectives for BS can however be considered. The problem of specifying how the parts of each type in each batch should be scheduled optimally is called input sequencing (IS). Two major objectives of IS are to maximize system utilization (minimize idle time) and to minimize the size of the buffer required to hold the waiting parts. The problem of minimizing the makespan without violating the buffer constraint is NP-hard in its general form (Papadimitriou and Kanellakis [1980]). However, we focus on the problem of finding, among the sequences minimizing the makespan, one that also minimizes the maximum

-2 - level of in-process inventory. This problem can be solved in polynomial time if the batch consists of two part types only (Agnetis et al. [1991]). Panwalkar [1991] provides an algorithm to determine an input sequence into a two-machine flow system that minimizes makespan. Travel time between the two machines by a single transporter is considered. We do not address IS further in this paper. There is a related literature on FMS part type selection. One general approach to select part types for concurrent production over time is called batching (Whitney and Gaul [1985], Hwang [1986], Rajagopalan [1986]). All part types are partitioned into disjoint batches and all parts in a particular batch are machined continuously until all requirements of all part types are finished. Another PTS approach is the flexible approach (Stecke and Kim [1988, 1989, 1991]). All part types in a particular batch are machined in certain relative ratios that balance machine workloads until the requirements of some part type are finished. Then the tools required for the finished part type may be taken out of the magazines and the tools required for the next part type(s) to be produced are loaded into the magazines, if new part types are selected to join the remaining part types. In general, following a flexible approach to system operation is better with respect to system operation performance than batching (Stecke and Kim [1988]). However, there are situations in which a batching approach is better (Stecke [1989]). The approach to optimal PTS and BS here is based on the flexible approach. Many compatible part types are selected subject to tool magazine capacity. Then, a subset of two of these part types are selected at a time for immediate processing. As previously mentioned, these two can be machined in suitable ratios that balance machine workloads, and sequenced so that both idle time and buffer requirements are minimized (see Agnetis et al. [1991]), until the requirements of one part type in the batch are finished. Then a new part type is selected to be processed with the remaining part type in new optimal ratios that balance machine workloads. Furthermore, by machining only two part types at a time, usually most or all pairs are feasible with respect to tool magazine capacity. This helps to simplify the PTS.

-3 - The advantages of our PTS algorithm include both optimal system operation as well as ease of operation. Our suggested approach is of course appropriate for some, but not all, FMS situations. In particular, either the processing time per operation (defined by several cutting tools) and/or the production requirements per part type need to be large enough to ensure that a system setup (changing the tools for a new part type) does not occur very often. This will usually not be a problem. Our global approach is especially useful in a dynamic environment, with orders arriving over time. Periodically, PTS and BS can be solved to optimally order the production of all part types. Near the end of a production period, there will be only a few part types remaining, all largely requiring the current bottleneck machine. At this point, the recently arrived orders can supplement the remaining orders and global PTS and BS are performed again. The plan of the paper is as follows. The global solution approach is described in Section 2. In Section 3, we detail the global approach, and provide efficient solution algorithms for both PTS and BS. In Section 4, we provide a detailed example. In Section 5, numerical evidence of the proposed approach is reported. Finally, we conclude in Section 6 with future research needs. 2. PROBLEM STATEMENT AND SOLUTION APPROACH Consider the following NP-hard scheduling problem (Papadimitriou and Kanellakis [1980]): Given a two-machine flow shop and a set J of part types to be processed, find a schedule of parts over time such that the completion time is minimum and the maximum level reached by the interstage buffer never exceeds a fixed capacity q >0. A solution to the above problem in real-world situations requires the consideration of some practical aspects. When s different part types are to be processed in the same mix, each machine must be equipped with a tool set which is the union of the tool sets needed by all selected part types: the larger the s, the higher the chance is that such tool set exceeds the capacity of the tool

-4 - magazine of some machine. It follows that it can be convenient to process only a few part types at a time, when this is sufficient to attain a good system performance. In the following, we say that two or more part types are tool-compatible if the tool set required for executing the corresponding operations can coexist in the appropriate tool magazines. We suggest a solution approach to the above problem that accounts also for these tooling issues. With this approach, production occurs as follows: a batch of only two part types with certain workload balancing mix ratios is in process at any time; when the requirements of one part type are finished, another part type is selected to be processed with the type remaining in new mix ratios, and together they form a new batch. Let the set P of all part types having production requirements be partitioned into two subsets, P1 and P2, so that if part type i E P1, (respectively, if k E P2) then a part of type i (of type k) requires a higher processing time on M1 than on M2 (on M2 than on M1). Since we look for a workload-balanced schedule of parts in each batch, one of the selected part types (say i) must belong to P1 and the other (say k) to P2. The detailed sequencing of the parts in the batch is performed according to the following rule: Rule 1. If a part of type i e P1 can be scheduled on M1 without creating idle time on M2, then schedule a part of type i. The following theorem holds: Theorem 1. If the part types in a particular batch are in workload-balancing mix ratios, then a schedule obtained by applying Rule 1 minimizes the maximum buffer level while keeping both machines always busy. Proof: See Agnetis et al. [1991]. In the following, let p (p ) denote the processing time of a type i (k) part on M., j=l or 2. The workload-balancing mix ratios can easily be computed a priori. Let 2. The workload-balancing mix ratios can easily be computed a priori. Let pik denote the number

-5 - of parts of type k that must be processed in the batch per one part of type i in order to balance the workloads of M and M2. In general, Pik is not integer, may attain any rational value greater than zero, and depends only on the processing times of a part of each type i and k on the two machines. These values are computed in Agnetis et al. (1991), where it is shown that Pik (Pk2 - Pkl) / (Pil - Pi2) (1) The value of the maximum buffer level, qik' reached by scheduling parts of type i and k according to Rule 1 is also a function of the processing times. A table providing formulas for the computation of qik is given in Agnetis et al. [1991]. Alternatively, qik can be obtained by a simple simulation of the application of Rule 1. The following example demonstrates the application of Rule 1. Example 1. Consider two parts types 1 and 2, with processing times of P 1 = 7, p12 = 4, p21 = 5, and 22 = 12 minutes. Therefore, part type 1 (part type 2) belongs to P1 (P2). The ratio p12 is given by (p22 -P21 /p 1 -P12) = 7/3 = 2.33. Figure 1 provides the schedule obtained by applying Rule 1 to a batch consisting of these two part types. Here we have sufficiently high requirements for both part types, and these are in the relative ratio p12. The first part of the schedule is a part of type 2; after that, two parts of type 1 can be scheduled without creating idle time on M2. Thereafter, the residual time on M2 is 6 minutes: there is no room for another part of type 1, since p 1 = 7 > 6. Therefore, a part of type 2 must be scheduled, followed by two parts of type 1. At this point, the residual time on M2 is 7. Initially, it seems that there is room for another part of type 1, but notice that if a part of type 1 is scheduled, then the residual time on M2 becomes 4, and this would create idle time on M2, whichever the following part is. For this reason, a part of type 2 is scheduled, followed by three parts of type 1. At this point (Y in Figure 1), notice that the situation is exactly the same as that at the beginning (point X). In fact the total workload of both machines to point Y is 64 = 3p21 + 7p 1 = 3P22 + 7P12. After point Y, the schedule obtained by following Rule 1 repeats identically over time. The cyclic input sequence of the two part types is: 211 211 2111.

-6 - By observing the schedule in Figure 1, we see that the buffer level never exceeds 1, i.e., in this example, q12 = 1. X Y x 6 7 y P21 Pll P22 P12 64 buffer level: 1 01 0 10 1 01 0 0 10 1 0 10 FIGURE 1. Schedule of Parts of Types 1 and 2 Following Rule 1. It is not necessary to consider part types having the same processing times on the two machines. In this case, these parts can be scheduled consecutively, indeed, in any manner (up to the fulfilling of the requirements), realizing a perfect workload balance with no occupation of the buffer. Clearly, the problem data may not always guarantee the existence of a solution such that M2 is always busy. Thus, we actually analyze the problem of maximizing the length of the interval during which both machines are busy and the buffer capacity is not exceeded. We say that two part types i and k are workload-compatible if and only if i E P1 and k E P2' A pair (i,k) of tool- and workload-compatible part types such that qik < q is called feasible. The general approach to the problems of PTS and BS may be summarized as follows. PTS AND BS ALGORITHM Step 1. Determine all of the tool- and workload-compatible pairs of part types (i,k), i PI andk e P2. Step 2. For each such pair, compute the mix ratio Pik and the buffer capacity required qik. Eliminate those pairs requiring a buffer that exceeds the actual system capacity q.

-7 - Step 3. Part Type Selection: Select a set of pairs of part types (batches), and for each pair, specify the number of parts to be produced (batch size), in order to maximize the interval in which both machines are busy. Step 4. Batch Sequencing: Determine the order in which batches have to be processed. Step 5. Input Sequencing: Sequence the parts of each batch according to the mix ratios computed at Step 2. The remainder of the paper is concerned with the problems addressed in Steps 3 and 4, namely, Part Type Selection and Batch Sequencing. For the solutions of the problems defined in Steps 2 and 5, see Agnetis et al. [1991]. 3. THE PART TYPE SELECTION APPROACH The Part Type Selection (PTS) Problem can be defined as follows: Given the requirements of each part type, determine which overlapping pairs of part types must be selected to form a batch, as well as how many parts, out of the requirements, must be produced for each part type in the batch, so as to maximize the interval in which both machines are busy without exceeding the buffer capacity. Let q denote the actual buffer capacity of the system. As before, qik denotes the minimum buffer capacity required to process parts of types i and k in the same batch with no idle time on either machine. Also, Pik denotes the number of parts of type k that must be processed in the batch per one part of type i in order to balance the workloads of M1 and M2. From Theorem 1, recall that as long as parts are processed in the relative ratio Pik, the buffer never exceeds qik and both machines are always busy. Let us now introduce a bipartite graph G = (U,V,E), where the vertex set U (V) is in a oneto-one correspondence with P1 (P2), and the edge set E is defined as follows:

-8 - E {(i,k) I pair (i,k) is feasible}. Clearly, only pairs of part types belonging to E may be processed in the same batch. In the remainder, we use the following notation: - Xik indicates the number ofparts of type i that will be produced with parts of type k in the same batch. According to the previous definitions, the corresponding number of parts of type k is given by Pik Xik. - ni (nk) denotes the requirements of part type i (part type k). A formulation of the PTS Problem is the following, Problem (P1): Problem (PI) max S (Pil + PikPkl)xik (i,k)e E s.t. n:= xi<n i E P k:(i,k)e E nk= Pik ik ni k P2 i:(i,k)e E The first (second) set of constraints ensures that the number of parts i (parts k) to be produced does not exceed the requirements for that part type. The objective is to maximize the length of the interval during which both M1 and M2 are busy, i.e., the total parallelized workload. Since workload balance is achieved by sequencing the parts in the given mix ratios, it is sufficient to maximize the workload of M1. Obviously, the batch size (xik, Pikxik) obtained from the solution of the linear Problem (P1) is generally not integer, even if xi is constrained to integrality, since in general pik is in turn noninteger. Therefore, a suitable rounding procedure is required. It turns out that a batch size obtained by rounding the solution of Problem (P1) is usually comparable, in terms of optimality, to a batch size obtained by rounding an integer solution of the same problem (see Section 5). This is especially true in the case of medium- or high-volume production, where, in our experience and for our purposes, rounding errors are usually negligible (see Arbib et al. [1991] and Stecke and Kim [1989]).

-9 - In general, a solution of Problem (P1) does not complete the production requirements ni and nk, for i E P1 and k E P2: only n.' < ni (n/ < nk) parts of type i E P1 (k E P2) are scheduled. Therefore, in general one has to decide how to process the remaining parts. However, this is not a problem in a dynamic environment, in which new orders arrive to join the remaining ones to provide new problem input. In a static environment, the solution of Problem (PI) does not cover the production of some parts, and hence we must specify how to schedule such parts. The problem consists of assigning the residual leftover parts to batches, where the cost of an assignment is related to the machine idle time introduced. An assignment of residual parts of class P1 (of class P2) may be realized by appending the residual parts at the end (at the beginning) of the batch. It can be proved that be doing so, irregardless of the assignment, the completion time of each batch is still optimal, and the buffer required is not greater than that required when parts i and k are processed in the ratio Pik (see Agnetis et al. [1991]). An intermediate approach may be useful when the arrival rate of new orders is not large enough to allow the dynamic generation of a meaningful sequence of PTS problems. In this case, we can extend the set of feasible pairs by considering pairs (i,k) of part types such that qik > q. Sequencing the parts of such batches without exceeding the buffer capacity clearly implies that there will be a certain amount of idle time on one machine. This idle time can however be easily taken into account by slightly modifying the problem formulation. In particular, we may require that the sum of the idle times accumulated inside each batch does not exceed a given percentage W of the total parallelized workload, i.e., of the value of the objective function. Thus, we can add the following constraint to Problem (P1): I Cikxik <W (Pil+PikPjl)Xik (2) (i,k) E (i,k)eE where cik denotes the amount of idle time introduced in a batch (i,k) of size (l,pik). In the following subsection, we analyze a structural property of basic feasible solutions of Problem (P1) and show how to exploit it for solving the Batch Sequencing problem.

-10 - 3.1 A Property of the Basic Solutions to Problem (P1) In this section, a structural property of the solutions to Problem (PI) that allows the minimization of the total number of tool changes is proved. This property results in more effective strategies for what concerns batch sequencing, as explained in Section 3.2. In a feasible solution to Problem (PI), the values xik specify the numbers of parts of type i that must be produced paired with Pik xik parts of type k. Given a feasible solution {x}, let G(x) = (U,V,E(x)) be an undirected graph, where the edge set E(x) is defined as follows: E = {(i,k) I i E P1, k E P2, and xik > 0}. Notice that Problem (PI) consists of n constraints, and therefore no more than n variables can be greater than zero in a basic feasible solution (bfs). Theorem 2. If {x} is a basic feasible solution to Problem (PI), then the graph G(x) is acyclic. Proof: Suppose that {x} is a bfs, and that in G(x) there is a cycle consisting of 2r edges. (Since G(x) is bipartite, this cycle must be even). Starting from a part type belonging to P1, let the part 1 0 0 0 0 0 0 0 0 p -p 2r,2 -2r,l Pll -p12 0 1 0 0 r+1,2 -Pr+1,1 P21 P22 0 0 0 0 TO TO TO TO 0 0 1 0 0 p P r+2,2 r+2,1 P31 -32 0 0 0 ooo 0 1... O... O 0 0 1 0 0 0 p P r+l,2 r+l,l 11 -12 0 0 0 1 0 0 0 r+2,2 r+2,1 P21 22 0 0 0 1 0 0 0 Pr+3,2Pr+3,1 P31 -P32 0 0... 0. 0 0 1.... O.. 0... 0 0 P2r-2 P2r-1 Prl Pr2 0... 2r-12 2r- 0 0 rl t2 0... 0 0 0 FIGURE 2. The Matrix AC.

-11 - types encountered on the cycle be: 1, r+1, 2, r+2,..., r, 2r, where part types 1, 2,..., r belong to P1 and types r+l, r+2,..., 2r belong to P2. Let C be the set of columns corresponding to the edges in the cycle, and let AC be the 2r x 2r submatrix obtained by selecting the rows and columns corresponding to the nodes in the cycle. Each column of AC has 1 in the i-th row and Pik in the k-th row, and the other elements are zero (see Figure 2). According to the definition of Pik' if we divide the i-th row by (Pil -Pi2), and the k-th row by (Pr+k,2 -Pr+k, 1) and add these two rows, we obtain a null row. This shows that AC is not of full rank, and since the only nonzero elements of C lie in AC, {x} is not a bfs. Q.E.D. 3.2 Part Type Selection Over Time (Batch Sequencing) In this section, we consider the problem of finding a good way to sequence the batches selected according to the method proposed using Problem (P1) for PTS. This problem is called the Batch Sequencing (BS) Problem. The objectives of BS may vary depending on the specific situation. In particular, different part types may require different tool sets, and hence one wants to minimize the total number of unnecessary re-tooling operations. We therefore require that, whenever possible, once a part type is input, it is processed until all the parts of that type that have been decided to be produced in the current planning period are finished. In the following, the notation (i,k) is employed to indicate the batch consisting of part types i E P1 and k E P2. Let {x*} indicate an optimal basic solution to Problem (P1). Theorem 2 indicates that G(x*) is a forest. From the viewpoint of minimizing the total number of re-tooling operations, a very favorable situation occurs when each connected component of G(x*) is a path. In this case, batches can be sequenced so that each part type and the corresponding tool set are loaded only once. Namely, if one of such paths is {1, 2, 3,..., m-1, m}, we can process the overlapping batches as follows: we start with the batch (1,2); after ni parts of type 1 are finished, we replace such part type by part type 3, and therefore process the batch (3,2), and so on, up to the last batch (m-1, m).

Observe that this property holds for more general graphs than paths. The above discussion applies also if, for each connected component T of G(x*), there exists a path nt (called a dominating path) such that each node of T either belongs to I, or is a leaf of T. In De Simone et al. [1990], components with such a structure are called caterpillars. For example, if G(x*) is the graph of part types in Figure 3, a batch sequence with the desired characteristics is: (1,4), (2,4), (3,4), (5,4), (7,6), (8,6), (9,6), (9,10), (9,11). In general, some part types may have to be loaded more than once. However, the leaves of the forest G(x*) still correspond to part types (and tools) that need to be loaded only once. Let us therefore consider the forest F(x*) obtained from G(x*) by dropping all of its leaves. Let n denote 10 1 11 FIGURE 3. Graph G(x*) Having the Structure of a Caterpillar. a path of part types on F(x*). From the above discussion, the general BS problem can be defined as follows: Given an optimal solution x* to Problem (PI), find a partition 7 = [1,...., Im of the forest F(x*) into a minimum number of edge-disjoint paths. The number of paths in partition n minus the number of connected components of F(x*) is equal to the total number of times that some part types are loaded more than once. To find an optimal partition n, one can proceed as follows. ALGORITHM TO OPTIMALLY PARTITION n Step 0. Set n _ 0. Step 1. Find a path n linking two leaves of the forest F(x*).

-13 - Step 2. Add path n to partition n and remove from F(x*) all edges of n. Step 3. If F(x*) contains no edges, then stop; otherwise, go to Step 1. It is easy to see that if co denotes the number of odd-degree nodes of F(x*), then Inl = co/2. The following Example 2 illustrates the BS approach. Example 2. Consider the graph of part types, G(x*) of Figure 4a, obtained by solving Problem (P1). After removing its leaves, we obtain the graph F(x*) of Figure 4b. A partition nI {{1,2,3,4}, {5,3,6}, {7,8,9}} of F(x*) into a minimum number of edge-disjoint paths is also shown. An optimal batch sequence of part types is (1',l), (1",1), (1',1), (1,2), (3,2), (3,4), (4',4), (4",4), (5',5), (5",5), (3,5), (3,6), (6',6), (7,7), (7,8), (8,8'), (8,9), (9',9). In this sequence, only part type 3 needs to be processed at two different times. In fact, we have ini = 3, and F(x*) has two connected components. 4' 511 y 1"~61 2 6 l 8 7 7 161 91 7 a a 9 FIGURE 4b. The Forest F(x*) and a Partition of its Edges into a Minimum Number of Paths.

-14 - Finally, note that different objectives for the batch sequencing problem can be considered for different situations. Consider for example a situation in which, for any given batch, changing the tool set of one part type is as expensive or time-consuming as changing the tool sets of both. Clearly, a sequencing strategy such as the one described above may not be of interest. On the other hand, a possible objective is that of preventing buffer overflow during the transient period between any two consecutive batches, while also minimizing the total idle time. In this case, a feasible strategy is that of scheduling the first operation of the new batch on M1 so that it ends exactly when the last operation of the previous batch is completed. The problem of computing a batch sequence that does not violate this constraint and minimizes the total idle time is a 2-machine No-Wait Flow Shop problem and can be solved in time O(B log B), where B denotes the number of batches (Gilmore and Gomory, 1963). Observe that this strategy can also accommodate retooling times, even if these depend on the particular pair of batches considered, as demonstrated in Figure 5. re-tooling first operation of batch 1 of M first operation of batch 2 re-tooling ofM2 FIGURE 5. Transient Period Between Two Batches. 4. EXAMPLE Now a detailed example is provided to show the application of the methodology described in Sections 2 and 3. Consider the production of 671 parts of ten different types, for a total workload amounting to 678 hours (about 28 days). The production of each part type requires a two-stage process. Production requirements, together with operation times (in seconds), and tool codes for each stage are indicated in Table 1 for each part type. In particular, part types 1, 3, 4, 5,

-15 - 6, 7, 8, and 10 belong to P1 whereas part types 2, 6, and 9 belong to P2. Tools require either one slot in a tool magazine, or 3 slots if preceded by *. Table 2 summarizes total workload (hours) required per part type, as computed from the processing times of Table 1. TABLE 1. Input Data for the Example Problem. Part Type 1 2 3 4 5 Production Requirements 51 97 64 59 53 71 64 54 98 60 Operation Time 3013 1356 1502 2044 2111 1647 1370 1286 2524 1884 1456 1740 1817 1502 2147 1588 1781 1866 2391 1673 Class Tool Codes P1 017 043 046 067 *072 076 077 079 083 087 101 106 *120 021 026 047 063 094 125 131 P2 035 039 049 059 068 086 *096 113 *132 014 *036 037 050 051 *054 062 065 *078 *090 *108 124 P1 008 010 013 016 022 029 *030 031 068 *084 109 002 008 033 051 082 095 104 117 P *072 078 097 106 117 123 124 039 041 073 074 099 112 115 P 002 005 007 009 014 015 038 050 051 *054 *066 097 *132 *030 050 051 052 071 091 *120 *126 127 P2 005 017 035 *048 086 093 103 118 009 017 051 063 069 079 081 112 116 P1 011 047 057 074 076 082 *090 107 123 001 002 *006 040 *048 *054 055 056 081 098 112 P1 005 010 014 *042 050 055 089 097 117 118 127 007 032 *042 051 098 101 103 121 P2 001 013 *018 021 052 057 067 089 097 109 115 118 004 *006 011 033 045 069 070 116 121 129 131 P1 001 016 040 050 063 067 080 087 088 092 101 116 008 011 015 *060 094 100 110 6 7 8 9 10 * Tools that require 3 slots. The production system is a two-machine flexible flow line {M1, M2} with a very limited intermediate buffer that can hold only one part at a time. Each machine is equipped with its own tool magazine. There are 132 different types of tools. From Table 1, each tool takes either 1 or 3 slots in a tool magazine. The larger-sized tools are about 15% of the total. The tool magazine capacity is 30 slots per machine.

-16 - TABLE 2. Total Workload (Hours) per Part Type and Operations. Part Type 1 2 3 4 5 6 7 8 9 10 Total Operation 1 42.68 40.47 37.53 22.45 37.16 28.72 32.30 32.21 48.48 39.85 361.85 Operation 2 19.21 55.07 29.28 21.08 27.74 34.32 26.70 23.82 50.80 27.88 315.90 Operations 1 and 2 61.89 95.54 66.81 43.53 64.90 63.04 59.00 56.03 99.28 67.73 677.75 The concurrent production of a pair (i and k) of part types (i, k = 1,...,10, i X k) is feasible if: (i) Part types i and k are workload-compatible, i.e., i E P1 and k E P2; (ii) Part types i and k are tool-compatible, i.e., the tool sets required for both i and k on M1 and on M take no more than 30 slots in each tool magazine; (iii) It is possible to find a relative part mix ratio Pik between i and k such that there exists a production sequence which does not create idle time on M and never requires more than one part waiting in the intermediate buffer (q=l). For all compatible pairs, the mix ratios Pik can be obtained by equation (1) in Section 2 from the values of Table 1 and are listed in Table 3. TABLE 3. Relative Production Ratios for Compatible Pairs of Part Types. P1,2= 3.057 P,6 = 5.835 P1,9 = 19.494 P3,2 = 0.856 P36 = 1.634 P3,9 = 5.459 P4,2 = 0.155 P46 = 0.296 P49= 0.988 P5,6= 2.254 P7,6= 1.109 P7,9= 3.706 P8,6 = 1.968 P8,9 = 6.576 P106 = 2.528 P109 = 8.447

-17 - From the values of Tables 1 and 3, one can compute the maximum buffer requirement qik of each compatible pair, either from Table 1 in Agnetis et al. [1991], or by observation of the schedule, as done in Example 1 in Section 2. The values of Table 1 also provide the tool magazine requirements of each compatible pair. For example, the concurrent production of part types 5 and 6 would require 20 tools (3 of which are of the large size) on M1, for a global requirement of (3x3 + 17) = 26 slots, and 17 tools (3 of which are of the large size) on M2, for (3x3 + 14) = 23 slots. Notice that tools 005 and 051 are required by both part types 5 and 6, on M1 and M2, respectively. Therefore, the pair (5,6) is feasible. On the other hand, the pair (2,5) is not tool-compatible, as the tools needed for the second operation require (3x7 + 12) = 33 slots, which exceeds the tool magazine capacity of M2. To define the feasible pairs of part types in this example, we use the bipartite graph G = (U, V, E) of Figure 6. The white (black) nodes U (V) denote part types in Pl(in P2), respectively. The edges of E denote the feasible pairs. 3 2 4 7 9 8 10 FIGURE 6. The Graph G of Feasible Pairs of Part Types. The part type selection problem can be formulated as the integer linear program Problem (P1) of Section 3, as follows:

-18 - Example Problem (P1) maximize 2.112x1,2 + 3.197Xl,6 + 10.481xl,9 + 0.944x3,2 + 1.247x3,6 +3.287x3,9 + + 0.445x4,2 + 0.500x4,5 + 0.869x4 9 + 1.612x5,6 + 0.953x76 + + 2.388x7,9 + 1.392x8,6 + 3.850x8g9 + 1.687x10,6 + 4.843x109 subject to: x1,2 + X1,6 +X1,9 51 x3,2 + 3,6 + x3,9 64 X4,2 +x4,6 +x4,9 <59 5,6 < 53 X7,6 + x7,9 _< 64 X8,6 + X8,9 < 54 x10,6 + x10,9 < 64 3.057x1,2 + 0.856x3,2 + 0.155x4,2 < 97 5.835x 16 + 1.634x3 6 + 0.296x4,6 + 2.254x5,6 + 1.109x7,6 + 1.968x8,6 + 2.528x106 < 71 19.494xl 9 + 5.459x3,9 + 0.988x4,9 + 3.706x7,9 + 6.576x8,9 + 8.447x10,~9 98 x.. > 0 and integer, V(ij) E E. An optimum integer solution {xi} to this integer program is given in Table 4, together with solutions { cik} of the corresponding linear relaxation. The objective function values express the time interval (in hours) during which both Ml and M2 are busy. These values are very close, and can be compared to the bound given by the workload w of the least busy machine. (In this case, w = 315.9 hours. See Table 2.) This comparison clearly yields almost the same ratios for the two solutions, and allows us to conclude that more than 70% of the total workload can be assigned to the system with the described approach, for this example.

-19 - TABLE 4. Optimal Solutions to the Part Type Selection Problem. X1,2 11 X1,6 = X1,6 X3,2 64 r * - 0 x, 0 * =0 X3,6 = 0 X3,9 x * -55 * -0 X4,2 4,6 -4 4,9 = 4 X5,6 7 7,6* =48 x79* =16 X8,6* - 1 X * - 4 X8,6 1- x8,9 4 * =_n * - 1 x10,6 x10,9 Objective Function Value = 227.682 Objective Function Value/ Total Workload =.721 1,2 = 10.8 1,6 = 0.0 19 = 0.0 3,2 = 64.0 3,6 = 0.0 439 = 0.0 44,2 = 59.0 4,6 = 0.0 4,9 = 0.0 56 = 13.0 7,6 = 37.5 7,9 = 26.4 8,6 = 0.0 89 = 0.0 10,6 = 0.0 910.9 = 00 Objective Function Value = 228.135 Objective Function Value/ Total Workload =.722 The actual part type selection, of course, requires integer values not only for the number Xik of parts of type i that must be processed in the same cycle with parts of type k, but also for the number Pikxik of parts of type k that vice-versa must be processed in the same cycle with parts of type i. A rounding procedure has therefore to be defined, not only for the solution { ik} of the linear relaxation, but also for the integer optimum {xi.k}. Figure 7 shows two square matrices which we shall refer to as PTS matrices, the entries of which correspond to pairs of part types. Entry (i,k) is equal to the actual number of parts of type i that must be processed in the same cycle with parts of type k. Such a number is defined for compatible pairs only, and the matrix is generally not symmetric. A PTS matrix can be computed by applying a suitable rounding procedure to a feasible solution of Problem (P1). This rounding procedure should in general ensure that the result still represents a feasible solution of Problem (P1). Suppose that each component is rounded to the closest integer. Rounding down will never be a problem. On the other hand, among the candidate components, we may round up only those with the greatest fractional parts. If we apply such a rounding procedure to the relaxed solution {1ik1 of Example Problem (PI), we obtain the PTS matrix of Figure 7a. In particular, for each component 4ik > 0, entry (i,k) is obtained by rounding 4ik' and entry (k,i) is obtained by multiplying the rounded component by

-20 - the corresponding Pik, and again rounding the result. Therefore, for example, in order to apply the suggested approach, 13 parts of type 5 have to be processed in the same cycle with 29 parts of type 6. a. b. 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 1 1 110 0 11 1 11 ll_ _ 0 11 34 5597 2 34 55 834 8 9 97 3 64 0 0 64 3 64 00 64 4 59 0 0 59 4 55 0 4 59 5 _ 13 ___ 13 5 = 17. 1 7 6 0 0 0 29 42 0 0 71 6 0 0 0 1 6 53 2 0 71 7 = 38 = 26 64 7 48 16 64 8 = =0 0 _ 0 8 1 1 = 4 5 9 0 00 096 0 0 96 9 0 0 4 59 26 8 97 1000 10 0 _ 1 FIGURE 7. Actual Part Type Selections Obtained From: (a) The Linear Relaxation of Problem (P1), and (b) its Integer Optimum Solution. Figure 7b shows the PTS matrix derived by applying the same rounding procedure to the optimum solution {xik} of Example Problem (P1). In this case, seven parts of type 5 are to be processed in the same cycle with 16 parts of type 6. Each matrix is associated with a PTS vector indicating the total number of parts of each type to be processed with our approach. Notice that the integer solution obtained by rounding I{ikJ has a value of 227.284 hours, whereas the value of the solution corresponding to the integer optimum is 227.218. Hence the integer solution is still slightly worse than the rounded linear solution. Notice that in the case considered here, the optimum value of the objective function of Problem (PI) is 227.682, whereas the linear relaxation yields an optimum value of 228.135 (see Table 2). As observed in Section 3 (Theorem 2), the particular structure of the linear program (PI) is such that the selected feasible pairs (i,k), i.e., those corresponding to 7ik > 0, define a forest on the bipartite graph G. In our example, such a subgraph has the particular caterpillar topology shown in Figure 8.

-21 - 6 30- 2 7 4or 9 FIGURE 8. The Acyclic Subgraph of G Corresponding to the Feasible Pairs Selected Through the Linear Relaxation of the Example Problem (P1). As discussed in Section 3.2, this topology can be used to determine an effective way of sequencing the different but overlapping cycles of part types belonging to the same connected component. For example, from Figure 8 we can begin with the coupled production of part types 5 and 6, then pass to part types 6 and 7, and finally to types 7 and 9. Similarly, one can process the other connected component, beginning with the production of part types 1 and 2, proceeding with the production of 3 and 2, and then with production of 4 and 2. By doing so, every part type is processed only once and totally in the same planning period, and therefore it is not necessary to load the corresponding tool sets more than once. Observe that the described property does not hold in general for a nonbasic solution, and in particular for the integer optimum solution of Problem (P1). In the example presented here, the subgraph of G defined by those pairs (i,k) such that x* > 0 is given in Figure 9, and is exactly one cycle. 5 ~~~6 7 3o 2 8 I 10 FIGURE 9. The Subgraph of G Defined by the Optimum Integer Solution of the Example Program (P1).

-22 - It can be seen from Figure 9 that it can happen that sequencing the various cycles may require the processing of at least one part type more than once. 5. COMPUTATIONAL RESULTS In this section, we provide a vast collection of numerical results related to the part type selection and batch scheduling approaches described in Sections 2 and 3. The following analyses are the results of more than 600 sample problems of different sizes, generated with different distributions of operation times and tool requirements. All optimal solutions were found via the linear programming facility offered by the mixed-integer linear solver IBM MPSX-MIP/370, running on an IBM 3090 at the Universita di Roma "La Sapienza". In all cases, the computation required only a few milliseconds of CPU time. As it occurs in a mid-term planning situation, the problem instances generated are characterized typically by an average system workload not greater than 1 month. The required tools used are from 132 different cutter types. The capacity of the tool magazines of both machines of the system is 30 slots. 5.1 Quality of the Optimal Solutions of (PI) and Batch Sequencing Results The first set of 80 test problems has been generated to produce 5, 10, 15, and 20 different part types in a flexible flow system with two machines and an intermediate buffer capacity of 1 or 2. For each part type, the system has to produce from 50 to 100 parts. The production of each part requires from 7 to 13 different tools, and from 7 to 16 different elementary operations, some of which may require the same tool. An elementary operation may take from 60 to 240 seconds. All data have been randomly generated with uniform probability distributions in the respective ranges. The aim of this first test was on one hand to quantify the maximum system workload that can be totally processed in parallel with our approach, and on the other hand, to verify the possibility of sequencing all of the selected pairs without processing the same part type in more

-23 - than two different periods. Recall that this last possibility holds if all of the connected components of G(x*) have a caterpillar structure. The results reported in Table 5 allow a comparison between the average optimum values z* of the objective function of the linear relaxation of Problem (PI), and the average workload w of the least busy machine. Each value from each Test is obtained from 10 test problems of the same type. As observed, the value of w gives a trivial upper bound to the maximum period of parallel production. The last column of the table gives therefore an upper bound to the percentage of workload that is not parallelized with the proposed approach. TABLE 5. Test Set I. Average Values of the Optimized Parallel Workload Compared with the Theoretical Bounds. Number of Buffer w z* (w - z*)/w Test Part Types Capacity (Hours) (Hours) (%) 1 5 1 162.5 133.7 17.7 2 5 2 152.7 130.3 14.7 3 10 1 346.6 277.8 19.8 4 10 2 330.8 279.3 15.6 5 15 1 499.4 454.1 9.1 6 15 2 510.1 456.2 10.6 7 20 1 687.1 621.8 9.5 8 20 2 706.5 646.1 8.5 With only one exception (Tests 5 and 6), the percentage of non-parallelized workload decreases as the buffer capacity increases. In general, these percentages have been under 20% of the upper bound of the theoretical parallelizable workload. Table 6 gives, for the same Test Set, the average percentage of nodes that induce caterpillar components in the forest G(x*). From these values one can infer that should any two selected pairs require different tool sets on both machines (this property held for all of the problem instances generated in this test), then a high percentage of part types (from 87 to 100%) would require loading the corresponding tool sets only once. That is, all part types can be finished with

-24 - no re-tooling, therefore perfectly realizing the desirable operating mode corresponding to the flexible approach. TABLE 6. Test Set I. Average Number of Part Types that can be Finished with No Re-tooling. Number of Buffer Caterpillar Structure Test Part Types Capacity (% of Number of Part Types) 1 5 1 100 2 5 2 100 3 10 1 99 4 10 2 98 5 15 1 93 6 15 2 96 7 20 1 92 8 20 2 87 In practice, all generated cases required a very low total number of tool-changing operations. The number of such operations tends to increase with the number of part types: as more nodes (part types) of G are available, chances decrease that the resulting solution forest only consists of caterpillars. The worst case observed had 20 nodes and required 4 tool changing operations over the theoretical bound that corresponded to a caterpillar structure of the solution forest. 5.2 Behavior of the Model with Unbalanced Workloads A second Test Set of 458 problems was generated, corresponding to production of 15 or 20 different part types and buffer capacities of 1, 2, and 4. The objective of this test was to investigate the model behavior in cases of potentially unbalanced workloads or strong buffer requirements. Such situations may occur when the numbers of part types in the two different classes, as well as their operation times, differ significantly from each other.

-25 - There are three different sets of tests. The first set was intended to examine situations in which the processing times i2'Pil << Pk~lPk2 (or Pkl'Pk2 < Pi2,Pil), respectively, and has been organized as follows: * Each problem instance has a part types of class P1 and b part types of class P2 (a + b = 15 or 20). * The operation times of part types of class PI (class P1) are chosen randomly with uniform probability inside the interval [al, a2] (interval [b1, b2]). The times are in seconds. For problems with 15 part types, we chose a = 5, 7, 8, and 10 and, respectively, b = 10, 8, 7, and 5. For each pair (a, b) such that a + b = 15, two instances were generated with buffer capacities of 1, 2, and 4. Also, [a1, a2] = [300, 1800] and [b1, b2] = [1500, 3000], or viceversa, [a1, a2] = [1500, 3000] and [bl, b2] = [300, 1800]. The total number of instances generated has therefore been (4 x 2 x 3 x 2) = 48. For problems with 20 part types, we chose a = 5, 8, 10, 12, and 15 and, respectively, b = 15, 12, 10, 8, and 5. For each pair (a, b) such that a + b = 20, we generated ten instances with buffer capacities of 1, 2, and 4. Also, [a1, a2] = [300, 1800] and [b1, b2] = [1500, 3000], or vice-versa, [a1, a2] = [1500, 3000] and [b1, b2] = [300, 1800]. The total number of instances generated in this case has been (5 x 10 x 3 x 2) = 300. The experimental results obtained are provided in Figures 10 and 11. As a general feature (present in almost all generated cases), we observe a reasonable performance degradation for extreme (small and large) values of parameter a. This is expected in such unbalanced situations. As expected, the ratio between the optimized parallel workload and the theoretical bound generally improves for larger buffer capacities. The second Test Set was based on the consideration that a critical situation when Pik > 1 (respectively, when pik < 1) is one in which pk2 (respectively, pil) is much greater than the other operation times. In such cases, we have, respectively, (il - Pi2) << Pk2 and Pk2 - Pkl << Pil and the application of Rule 1 results in a large buffer requirement. Only a small number of feasible pairs can then be considered.

-26 - 100% - 90%80% 100% A el 0 buffer capacity = 1 O buffer capacity = 2 A buffer capacity = 4 8 a A 0 A 90% A a 0 a t ) 80%70% > 70% I 60% 5 6 7 8 9 10 a (a) [al, a2] = [300, 1800]; [b1, b2] = [1500,3000]. 5 6 7 8 9 10 a (b) [al, a2] = [1500, 3000]; [b1, b2] = [300, 1800]. FIGURE 10. Test Set II. Average Values of the Ratio Between the Optimized Parallel Workload and the Theoretical Bound, for Problem Instances with 15 Part Types. 100%90% - 100% 0 buffer capacity = 1 o buffer capacity = 2 A buffer capacity = 4 A t, 6 A Q o1 a A 90% J I s 80%) 80% 6 70% 70% o I I I I I I I I I I 60% 5 6 7 8 9 10 11 12 13 14 15 a (a) [al, a2] = [300, 1800]; [b 1, b2] = [1500,3000]. i I I I 5 6 7 8 9 10 11 12 13 14 15 a (b) [al, a2] = [1500, 3000]; [bi, b2] = [300,1800]. 7 FIGURE 11. Test Set II. Average Values of the Ratio Between the Optimized Parallel Workload and the Theoretical Bound, for Problem Instances with 20 Part Types.

-27 - For example, suppose that we have 20 part types and the same values of a and b of the previous test. Let Pil P2 Pkl (or, respectively, Pkl Pk2 P2) range between 300 and 900 seconds, and Pk2 (or pil) range between 2,400 and 3,000. One can see that when the buffer capacity is 1 or 2, the values of qik obtained result in no feasible pair. We therefore set up this Test Set by generating 10 problem instances with the above ranges for the operation times and a buffer capacity of 4, for a total number of (5 x 10 x 2) = 100 instances. See Figure 12. Furthermore, when a = 5, b = 15 (a = 15, b = 5), and the expected value of Pk2 (Pil) is much greater than the other operation time, we obtain very unbalanced situations in terms of workload. One can see this from the corresponding poor average values of z*/w (30.8% and 32.5% of total workload parallelization, respectively) reported in Figure 12. 90% — 70%- -o Pk2 >> than other operation times P* il >> than other operation times 50% 30% l i l:: I 5 8 10 12 15 a FIGURE 12. Test Set II. Average Values of the Ratio Between the Optimized Parallel Workload and the Theoretical Bound, for Problem Instances with 20 Part Types and Buffer Capacity = 4. The next Test Set (on 10 problem instances with buffer capacity of 4 and 20 part types each) is considered in order to confirm the trend observed in the extreme situations. In this case, we set a = 5 and b = 15. The operation times of each process range as follows: pil and Pi2 in [600, 900]; Pkl in [300, 600]; and Pk2 in [2400, 3000]. On average, of 220.3 total hours of workload, our approach could be applied for 87.3 hours (= 40%). Each of the 458 problem instances generated in this set featured very good performance w.r.t. batch sequencing. About 88% to 100% of the part types can be machined without reloading

-28 - the corresponding tools sets. The worst case observed required only 3 re-tooling operations over the theoretical bound. However, this particularly good behavior stems from the fact that in unbalanced situations, the solution forest usually contains very few edges. 5.3 Bimodal Distributions of Times and Requirements A third and last Test Set was set up in order to simulate a situation in which part types may be further partitioned according to short versus long operation times, and to small versus large production requirements. In particular, the total operation times of each part tiect ype range between 300 and 3,000 seconds, with a probability distribution having two maxima centered at 500-700 and 2,300-2,500 seconds. Similarly, the number of parts of each type required ranges between 30 and 120, with a probability distribution having maxima at 35-55 and 85-105 parts. (See Figure 13.) When generating each problem instance, we assume that operation times and production requirements are statistically independent variables. This means that to produce ten different part types, about two of them will on average have a total operation time less 12 minutes (= 700 seconds) and production requirements of at least 85 parts...... 30% 27%. -...... 20% 10% 10% 6% I I 300 3000 30 120 Operation Time Production Requirements FIGURE 13. Test Set III. Probability Distributions (Percentage of Part Types) of Operation Times and Production Requirements. With the above data, an appropriate range for the number of tools needed by each part type is 8 to 16. We generated 10 random problem instances with 5, 10, 15, and 20 part types each, with buffer capacities of 1 or 2, for a total number of 80 individual tests. The results are collected

-29 - in Tables 7 and 8. With respect to the results obtained with uniform probability distributions, the ratio (w - z*)/w shows a slight degradation. On the other hand, for each solution forest found, the average size of the caterpillar-structured subgraph appears slightly larger. However, as in the second Test Set, this behavior depends mainly on the low edge-density of the solution forests obtained. TABLE 7. Test Set III. Average Values of the Optimized Parallel Compared with the Theoretical Bounds. Workload Test 1 2 3 4 5 6 7 8 Number of Part Types 5 5 10 10 15 15 20 20 Buffer Capacity 1 2 1 2 1 2 1 2 w (Hours) 69.7 71.1 191.1 255.5 339.9 432.4 531.3 550.2 Ze* (Hours) 50.2 56.1 142.6 194.2 266.9 380.0 424.6 515.9 (w - z*)/w (%) 32.4 21.1 25.4 24.0 21.6 12.1 20.2 6.2 TABLE 8. Test Set III. Average Number with No Re-tooling. of Part Types That Can Be Finished Test 1 2 3 4 5 6 7 8 Number of Part Types 5 5 10 10 15 15 20 20 Buffer Capacity 1 2 1 2 1 2 1 2 Caterpillar Structure (% of Number of Part Types) 100 100 100 99 100 100 96 88

-30 - We conclude by noting that for a few problems of small size (no more than ten part types), the integer optimum was found by means of an IBM MPSX-MIP/370 spending a considerable amount of computational effort. However, as noted in Section 3, no remarkable improvement in the quality of the solutions with respect to the linear relaxation has ever been noticed. 6. FUTURE RESEARCH NEEDS This paper presents a new approach to part type selection in flexible flow lines, as well as to batch sequencing over time. To date, the analyses have concerned the two-machine with finite buffer situation. Among future problems that need to be addressed are the following: 1. Two-pools systems. Instead of two machines only, the system consists of two pools of m1 and m2 identical machines in each pool, respectively. The structure of the input sequencing problem is different. The solution will also depend on the number of buffer spaces and the location of the in-process inventories. 2. An m-machine flexible flow shop (with m> 2). For these larger types of systems, the number of part types to be selected for simultaneous production in order to guarantee workload balance will in general be greater than two. The input sequencing problem is likely to be much more complicated. The allowable numbers of buffers that can be between machines will also complicate the problem. ACKNOWLEDGEMENTS Kathy Stecke would like to acknowledge support from the Alexander von Humboldt Foundation in Bonn, the Universita di Roma, and a summer research grant from the Business School of The University of Michigan. We also thank Marco Tassitano for providing the computational results.

-31 - REFERENCES Agnetis, A., C. Arbib and K. E. Stecke, "Scheduling Two Part Types in a Two-machine Flexible Flow System", Working Paper, Universita di Roma "La Sapienza", Dipartimento di Informatica e Sistemistica, Rome, 1991. Arbib, C., M. Lucertini and F. Nicolo, "Optimal Workload Balance and Part Transfer in Flexible Manufacturing Systems", International Journal of Flexible Manufacturing Systems, Vol. 3, No. 1, pp. 5-25, February 1991. Hwang, S., "Part Selection Problems in Flexible Manufacturing Systems Planning Stage", in: K. E. Stecke and R. Suri (eds.) Proceedings of the Second ORSA/TIMS Conference on Flexible Manufacturing Systems: Operations Research Models and Applications, Elsevier Science Publishers, B. V., Amsterdam, pp. 297-309, August 1986. Panwalkar, S. S., "Scheduling for a Two-machine Flowshop with Travel Time Between Machines", Journal of the Operational Research Society, Vol. 42, No. 7, pp. 609-613, July 1991. Papadimitriou, C. H. and P. C. Kanellakis, "Flow-shop Scheduling with Limited Temporary Storage", Journal of the Association of Computing Machinery, Vol. 27, pp. 533-549, 1980. Rajagopalan, S., "Formulations and Heuristic Solutions for Parts Grouping and Tool Loading in Flexible Manufacturing Systems", in K. E. Stecke and R. Suri (eds.) Proceedings of the Second ORSA/TIMS Conference on Flexible Manufacturing Systems: Operations Research Models and Applications, Elsevier Science Publishers, B. V., Amsterdam, pp. 311-320, August 1986. Stecke, K. E., "Procedures to Determine Part Mix Ratios in Flexible Manufacturing Systems", Working paper No. 587, The University of Michigan, School of Business Administration, Ann Arbor MI, October 1989. Stecke, K. E. and I. Kim, "A Study of FMS Part Type Selection Approaches for Short-term Production Planning", International Journal of Flexible Manufacturing Systems, Vol. 1, No. 1, pp. 7-29, September 1988. Stecke, K. E. and I. Kim, "Performance Evaluation for Systems of Pooled Machines of Unequal Sizes: Unbalancing Versus Balancing", European Journal of Operational Research, Vol. 42, pp. 22-38, 1989. Stecke, K. E. and I. Kim, "A Flexible Approach to Part Type Selection in Flexible Flow Systems Using Part Mix Ratios", International Journal of Production Research, Vol. 29, No. 1, pp. 53-75, January-February, 1991. Whitney, C. K. and T. S. Gaul, "Sequencial Decision Procedures for Batching and Balancing in FMSs", Annals of Operations Research, Vol. 3, pp. 301-316, 1985.