4 199S ON THE ROBUSTNESS OF USING BALANCED PART MIX RATIOS TO DETERMINE CYCLIC PART INPUT SEQUENCES INTO FLEXIBLE FLOW SYSTEMS Thomas M. Smith Hope College Department of Economics and Business Administration Holland, Michigan 49422-9000 and Kathryn E. Stecke The University of Michigan School of Business Administration Ann Arbor, Michigan 48109-1234 December 1994 Revised June 1995

ABSTRACT Most of the literature dealing with the determination of cyclic part input sequences in a flexible flow system is restricted in that it only searches for input sequences that are permutations of the minimal part set (MPS). This study is unique in that it investigates input sequences generated by integer programming (IP) formulations that balance or unbalance machine workloads to help maximize overall machine utilization (Stecke (1992)). Also, this study integrates the input sequence determination decision with the part mix ratio determination, within the overall framework of a flexible approach to FMS operation over time. A simulation model of a flexible flow system was designed to study the effects on overall machine utilizations caused by utilizing alternative part mix ratios to help determine input sequences. The procedures used to determine the part mix ratios include IP formulations and those that are generated randomly, including the MPS mix ratios. Three different experimental settings are used to test these effects as well as (1) the robustness of the part input sequences that can be derived from the IP generated mix ratios, and (2) the relative importance of the part mix ratio decision in relation to the part input sequence determination. A new FMS physical design that can also be easily modeled to capture look-ahead capability proved to be simple and effective. Several significant conclusions regarding part mix ratios, part input sequences, and lookahead capability are revealed. These include: (1) the determination of the part mix ratios proved to be more significant in improving FMS performance than the determination of part input sequences; (2) the robust nature of the IP formulations was demonstrated; and (3) look-ahead capability provides equally high overall machine utilizations at lower levels of work-in-process. Future research areas are presented that would help validate and extend the observations found in this study.

I. INTRODUCTION The overall FMS operation involves setting up the system before production begins and the subsequent operation by operation scheduling of parts through the system. A typical FMS operating environment specifies production requirements for parts of different types. Usually these part types can't all be produced during the same time period because there is not sufficient tool magazine capacity to hold all the tools required to produce these part types. Therefore, prior to production, certain system set-up issues must be addressed. Stecke (1983) defines five system set-up problems for an FMS that must be addressed before production can begin. These problems are as follows: (1) Part type selection problem: determine a subset of the required part types for immediate and simultaneous processing over the upcoming period of time. (2) Machine groupingproblem: partition the machines of similar types into identically tooled machine groups. (3) Production ratio problem: determine the relative part mix ratios at which the selected part types should be produced over time. (4) Resource allocation problem: allocate the (minimum numbers of) pallets and fixtures of different fixture types to the selected part types to maintain the particular production ratios. (5) Loadingproblem: allocate the cutting tools of all operations of the selected part types to some machine's limited capacity tool magazine. Once these static set-up problems have been addressed and implemented, the execution of the orders needs to be carried out over time. These decisions fall into the, category of scheduling and control problems, and include the following: (1) determining part input sequences, (2) determining the part processing sequence at each machine, (3) monitoring actual system performance.

The overall FMS operation is comprised of solving these static FMS set-up problems followed by the subsequent dynamic input sequencing and scheduling of parts over time. Both part types (orders) and parts come into and out of production according to the solutions to these problems. The focus of this paper is on integrating the production set-up problem of part mix ratio determination with the scheduling problem of part input sequence determination. Once determined, a part input sequence is then implemented cyclically over a production period. We focus on these two problems imbedded within an overall approach to FMS operation over time. Given that the "next" subset of part types to be produced has been selected, we've investigated the characteristics, selection, and relative importance of the best part mix ratios/input sequence over the next production period. Typically, this production period may last from two to seven days. These issues have not been previously examined in the literature. I. OVERALL OPERATING ENVIRONMENT The FMS operating environment under investigation produces part types having independent demands. Under these conditions, a key objective of production planning and operation is the maximization of system utilization. The part type selection problem has been addressed by Whitney and Gaul (1985), Hwang (1986), Rajagopalan (1986), Stecke and Kim (1986, 1989, 1991), and Amoako-Gyampah (1994), for example. The first three works utilize a batching approach, in which part types having production requirements are partitioned into distinct batches of part types to be machined one batch at a time. 2

Aflexible approach to part type selection, as opposed to a batching approach, enables the system to be more highly utilized. As described by Stecke and Kim (1988), the flexible approach begins in a manner similar to a batching approach. An initial batch of part types is selected to be produced subject to tool magazine capacity constraints. However, within the framework of a flexible approach, Stecke (1992) has developed mathematical programming formulations (integer programs) to select part types and/or determine the part mix ratios that balance or unbalance machine workloads to help maximize overall machine utilization. These part mix ratios define the relative numbers ofparts of the selected part types that should be in the system simultaneously in order to balance or unbalance the workload per machine. Parts are input and produced cyclically according to these ratios until the requirements for some part types are completed. The completed part types leave the system and new part types are merged with the in-process part types and new mix ratios are calculated to balance or unbalance the workload per machine. The flexible approach is useful whenever a disruption occurs within the current operating conditions. For example, a disruption may be when a production order needs expediting, when a part mix is changed, when a machine breaks down, or simply when the production requirements of some part types are completed., Since this approach more closely aligns with the objectives of the FMS operation under investigation, it will be-utilized to structure the objectives of our study. The integer programming (IP) formulations can incorporate the results from Stecke and Solberg (1985), which conclude that for a system comprised of groups of pooled machines of unequal size (which is the type of system under investigation for this study), the expected production rate is maximized by assigning a specific unbalanced workload per machine to each machine group. Other recent works on the assignment of this specific unbalanced workload per

machine have utilized closed queueing network models (Dallery and Stecke (1990)) and simulation models (Stecke and Kim (1989)). Intuitively, inputting parts according to such ratios should help achieve system workload balance. However, for any set of part mix ratios, there are many -permutations of these mix ratios into part input sequences. For the remainder of this paper, the term balanced part mix ratios will be used to refer to the ratios generated by the IP formulations. Given the above scenario, that of a flexible approach to the overall FMS operation and the integration of the part mix ratios decision and the input sequence determination, the two primary objectives of this study are: (1) to examine the robustness of the part input sequences that can be derived from the balanced part mix ratios; and (2) to examine the relative importance of the part mix ratio decision in relation to the part input sequence determination upon overall machine utilization. A simulation model of a flexible flow system (FFS) was built in order to examine these two issues. In addition, as part of the simulation model, we provide a new system design specification that automatically allows a limited (i.e., next step) look-ahead capability without the necessity of additional complex software. This look-ahead capability is then used as one of the model parameters to investigate the stated objectives. Here, look-ahead capability means that a part will enter the machine input buffer of the corresponding machine that will become available at the earliest time. The motivation for this paper stems from several previous works. Schriber and Stecke (1988) state, "The influence of the part input sequences on system performance should be studied further. There is insufficient evidence presented here to even conjecture on the relative 4

importance of the choice of a part input sequence". Similar opinions regarding the study of alternative part input sequences are voiced by Agnetis et a. (1990) and Schriber and Stecke (1987). A review of the literature dealing with part input sequencing is presented in Section III. The details of the simulation model, similar to the one designed by Schriber and Stecke (1988), are described in Section IV. Section V details the design of the simulation experiments. A discussion of the results is given in Section VI. Section VII summarizes and presents the significant conclusions regarding this study. Finally, Section VIII comments on potential areas of future research. m. LITERATURE REVIEW Most of the early work done on part input sequencing assumed a batching approach to part type selection and studied cyclic sequencing approaches based on a minimal part set (MPS) proportional to the total requirements or desired ratios of finished parts. An MPS consists of the smallest integer values for a set of selected part types that are proportional to the production requirements. Hitz (1980) shows that cyclic input into a flexible flow shop without buffer limitations attains a periodic steady state in a finite time. This steady state is accomplished if parts periodically enter the system with a frequency that fills up the bottleneck machine. He also proposes a branch and bound procedure, which searches for the part input sequence that induces this steady state. Erschler et al. (1982) further examine the FFS proposed by Hitz and analyze the transient and steady state properties for the FFS at each stage in more detail. In addition, they propose a heuristic procedure to search for a sequence on the critical machine that allows for c

scheduling parts on other machines in order to minimize conflicts between these parts. The solution leads to an easy flow of parts by limiting the waiting time in the buffers. Wittrock (1985) studied sequencing an MPS in a flexible flow system in 'order to maximize throughput and minimize work-in-process (WIP). He states that since choosing a sequence for the MPS does not have a significant effect on the makespan, the goal of sequencing should be to minimize the amount of queueing. McCormick et al. (1988) examine a system similar to Wittrock's, but with finite capacity buffers between machines. They propose a heuristic method for sequencing within an MPS based on an equivalent maximum flow problem and using critical path techniques. In contrast to the static methods that have been developed for generating a permutation of the MPS, Akella et aL (1985) and OKeefe and Rao (1992) have proposed dynamic approaches to the part input problem. The two dynamic approaches considered by O'Keefe and Rao include look-ahead simulation and a rule-based model that incorporates the current state of the FFS to dynamically select the next part to input. OKeefe an and Rao also report that look-ahead simulation provides promising results, especially in an FFS environment that may suddenly change due to machine breakdowns, unplanned maintenance, or changes in production requirements. Agnetis et al (1990) present a new approach to part type selection and input sequencing in a two-machine FFS. Given the production requirements of each part type, they provide optimal rules to schedule parts of different types on the two machines. First, part types are partitioned into overlapping batches. Then the optimal cyclic input sequence and schedule for overlapping pairs of part types in each batch is specified in order to minimize completion time as well as to minimize WIP. The objective of minimizing completion time for a group of pooled machines is also used by Tang (1990). He assumes that a significant setup time is incurred when changing 6

from one part type to another. Tang develops a heuristic that provides two lower bounds on the optimal completion time. Miltenburg (1989) determines an input sequence for a mixed-model line, where the objective is to keep a constant rate of usage of every part produced by the line. Given the number of different part types to be produced and their demand schedules, he presents a number of algorithms that can be used to generate good feasible schedules. Departing from the FFS/MPS models, and assuming a flexible approach to part type selection, Escudero (1989) develops an algorithm for part input sequencing that attempts to minimize makespan in a more complex FMS setting. The algorithm initially obtains a part input sequence such that pooled machine groups' workloads are locally balanced over a time period. Once this sequence is established, improvement in the secondary objective of turnaround time is sought without degradation to the makespan. Stecke and Kim (1986, 1988) compare part type selection approaches using simulation to evaluate system performance. A cyclic part input sequence is utilized that is determined by using a combination of a modified Johnson's algorithm and the calculated part mix ratios. AmoakoGyampah (1994) compares three tool allocation and part type selection approaches. For the different part type mix situations examined, on average the flexible approach was the best for all of his performance measures. Most of the literature attempts to find the length of the transient period before steady state is reached and the optimal or "best" input sequence, or permutation of the MPS, in light of various system configurations and objectives. This study is different from the previous ones for several reasons. First, the use and investigation of input sequences generated by permutations of balanced mix ratios, as opposed to the MPS, has not been previously investigated. Intuitively,

this should be better in terms of system utilization as it aims to avoid the creation of bottlenecks. Second, the robustness of the input sequences generated by permutations of balanced mix ratios needs to be examined in light of the potential large number of input sequence alternatives. Finally, the relative importance of the decisions involving part type mix ratios in relation to those involving part input sequencing has not been examined. IV. THE SIMULATION MODEL A schematic of the flexible flow system utilized in this study is pictured in Figure 1. In defining this simulation study, we chose all parameters so as to model a typical and realistic FFS. For example, five machines each with an input and an output buffer is of typical size. Processing times, production requirements, and routings also mimic a typical FFS. Machines of the same type are pooled. Therefore, a part can visit either of the two drills or either of the two lathes. This allows flexible routing in real time. All part types visit each machine in a mill-drill-lathe unidirectional flow. A summary of the characteristics and assumptions of the model are now presented. (1) Secondary FMS Resources. Automated guided vehicles (AGVs) transport work-inprocess (WIP) for all possible transfers. In general, the number of AGVs in the system is a model parameter. Each machine in the system is provided with one input buffer (which can contain one part waiting for the machine) and one output buffer (which can also contain only one part when it is finished with that machine, and is waiting to be transferred to its next destination). 8

:Raw Material In * 'in. Input..: Bu rffr. Output i.'Buffer: 1 1. [ Input:I: iiffer l. I.Input... Buffer -:. Output.ut~ puI 'Buffer Buffer, Finished Goods:: _.| ',_ -Out Figure 1. Schematic of the Flexible Flow Shop. (2) Secondary Time Requirements. With local machine buffers, part transfer time from pickup point to destination is deterministic and independent of the points involved. This transfer time is a model parameter. (3) Operating Policies. The service order at the machines is first-come, first-served. Lookahead capability is a model parameter that is varied and will be explained in Section V. In 9

addition, the maximum number of parts (work-in-process) allowed in the system and the part input sequence are model parameters that will be manipulated to evaluate system performance. The measure of performance for the system will be overall machine utilization (the average of the individual machine utilizations). (4) Operating Data. Ten unique part types are produced by this FFS. The various arioust type machining times and production requirements are shown in Table 1.:Part Machining Times (Minutes) Production Type. Mill:Drill.:.:.: V: Requirements 1 10 60 50 60 2 15 20 ' 40 25 3 40 10 30 30 4 30 20 20 30 5 10 50 20 50 6 10 30 20 25 7 20 10 10 15 8 15 20 30 50 9 25 10 20 30 10 5 40 40 25 Table 1. Machining and Production Requirements for each of the Ten Part Types. The simulation model was built in GPSS/H, Version 2 (Henriksen and Crain (1988), Schriber (1991)). The model itself consists of 66 GPSS blocks, and the complete model file contains 271 statements. V. DESIGN OF THE SIMULATION EXPERIMENTS The simulation experiments are designed to perform the following: (1) measure overall machine utilizations achieved by the FFS described in Section IV; (2) determine the sensitivity of overall machine utilization to changes in the part input sequence; (3) compare overall machine 10

I II I I i utilizations for part mix ratios obtained using an IP approach versus part mix ratios obtained using either the MPS or a sometimes random approach (Non-IP); and (4) compare overall machine utilizations for part mix ratios obtained using an IP approach when look-ahead capability is present in the scheduling versus when no look-ahead capability is present. The particulars of the design of the experiments are now given. (1) Establishing Oerating Equilibrium. Since all arrival times, transfer times, and processing times are deterministic, only one replication is required for each alternative system design that is investigated. These variables are deterministic so that the variation in results may be attributed to the FMS planning and scheduling decisions and not confused with the characteristics of the FMS design or the parts to be produced or possible randomness in processing times. The run is composed of 25 eight-hour shifts (to move through transient conditions and into operating equilibrium), and then 275 eight-hour shifts (to gather statistical observations under operating equilibrium). The time required to move through the transient conditions and the time required to establish operating equilibrium was dependent upon the settings of the model parameters. We experimented with different parameter settings and found the extreme cases required about five 8-hour shifts to pass through transient conditions and about eight 8-hour shifts to establish operating equilibrium. Given the very low cost of the simulation runs and that we did not experiment using all possible parameter settings, the simulation times used for each replication are much longer to further ensure the accuracy of the results. (2) Experimental Settings. In light of the objectives of this paper, three different experimental settings are used to gather the relevant information. Since the purpose is to observe 11

changes in overall machine utilizations caused by changes in part input sequences, part mix ratios, and look-ahead capability, most of the model parameters were held constant over all three experimental settings. In developing such a simulation model, it is important to determine which parameters can be aggregated or ignored. Such decisions are dependent upon the purposes of the study. Certain parameters were clearly not a factor for the objectives of our study. For example, travel time is zero and the number of AGVs in the system is fixed at one for each experimental setting. It is understood that the number of AGVs is irrelevant when travel time is zero. Nevertheless, to aid in the future study of more complex systems, the model was built with these variables as parameters. Prior to the input of parts into the system, a "proper" part type selection decision (based on using the IP formulations in Stecke and Kim (1986) to select a subset of part types and balanced mix ratios) selected part types 2, 5, 6, 8, and 10 to be machined next in ratios of 2, 1, 2, 1, 1. (Table 2 summarizes this initial flexible batch. For the purposes of our study, the actual production requirements, in terms of the specific numbers of parts, are not significant. More generally, when actually operating the FMS over time, parts are input cyclically according to the sequence until the requirements of some part type(s) are finished. From Table 2, we see that part types 2 and 6 would finish first. At this time, the finished part types (i.e., part types 2 and 6) leave the system and new part types (selected by IP from the remaining set of part types 1, 3, 4, 7, and 9 from Table 1) can enter to join those not yet finished (i.e., part types 5, 8, and 10). New mix ratios are calculated to balance or unbalance the workload per machine and these part types are then input cyclically according to the new sequence. A more detailed explanation and examples of this part type selection procedure is found in Stecke and Kim (1991).) 12

-Part Tpe 'Part Type Mix Ratio Production Requirements 2 2 25 5 1 50 6 2 25 8 1 50 10 1 25 Table 2. Initial Batch Generated by the Flexible Approach. The first experimental setting (ES-1) utilizes the IP approach to determine the part mix ratios. The relative ratios that optimize machine workloads for the five selected part types are 2, 1, 2, 1, 1. In general, there are n!/nl!n2!...nr! different permutations of n objects, of which nl are alike, n2 are alike,.., nr are alike. Since there are seven parts in one cycle to be processed before the sequence repeats itself and there are two pairs of similar part types, the theoretical number of unique part input sequences (developed as permutations of these five mix ratios) is 7!/2!2!, or 1260. To examine each sequence would be quite prohibitive. Thus a combination of a random sample and intelligent selection of twenty permuted part input sequences from among the 1260 sequences are examined. The selection of these sequences will be discussed later in the paper. This setting has no look-ahead capability. In other words, the buffer choice is made simply because it is the first buffer available. This decision does not guarantee that the corresponding machine will be the next one to be available at the earliest time. Also, the levels of WIP that are allowed in the system are set at 5, 7, and 9. A WIP level of 5 was chosen on the low end because there are five machines in the system. A WIP level of 9 was chosen on the high end because we did not want the system to achieve high utilizations simply because there were more parts in the system than there were buffers I1

and machines. Therefore, a total of 60 simulation runs were made for ES-1. This corresponds to examining the overall machine utilizations for the twenty part input sequences obtained at the three different WIP levels. The second experimental setting (ES-2) is identical to ES-1 for all the parameters except for the limited look-ahead capability. This capability is not modeled in the traditional sense of running the simulation forward in time to provide look-ahead information. In this case, the look-ahead capability is modeled by delaying the decision of which input buffer to enter until a machine actually becomes available. In other words, the model is waiting for more information rather than generating it through the traditional sense of look-ahead. The characteristics of the FFS remain the same (one input buffer per machine, a capacity of one part per input buffer, and first-come, first-serve dispatching). However, the simulation model is altered by providing a single input buffer for the drills and another for the lathes with a capacity of two parts each. This new FMS software design proved simple, yet effective. Note that this can also be a new physical FMS design that automatically mimics limited (one-step) look-ahead capability with no additional software required. As was done for ES-1, 60 simulation runs covering the various parameter settings were made for ES-2. The third experimental setting (ES-3) is identical to ES-i for all parameters except that only two different WIP levels are examined (7 and 9), and an alternative approach is used to determine the part mix ratios. Given the five part types selected to be machined, the total number of unique part mix ratios that one can choose is extremely large (assuming one will not produce more than the requirements). It is therefore unrealistic to examine all the different sets of part mix ratios. Given that the IP approach yields a 14

sequence which includes seven parts per cycle, the Non-IP approach taken here is to investigate some of the different "unbalanced" part mix ratios for seven parts that could be obtained from the selected five part types. One of these unbalanced mix ratios (1, 2, 1, 2, 1) corresponds to the minimal part set. The specific mix ratios that are used, and the number of different sequences that are examined are shown in Table 3. Part Type:Mix:Ratio::Number of Sequences: Input Sequence PT2 PT5-'::.PT6.: PT8:.: PT10.. 'Examined.: — Number 2 2 1 1 1 2 21,22 2 1 1 2 1 2 23,24 2 1 1 1 2 2 25,26 1 2 2 1 1 2 27,28 1 2 1 2 1 2 (MPS) 29,30 1 2 1 1 2 2 31,32 1 1 2 2 1 2 33,34 1 1 2 1 2 2 35,36 1 1 1 2 2 2 37,38 3 1 1 1 1 1 39 1 1 3 1 1 1 40 Total 20 Table 3. The Non-IP Part Mix Ratios used for ES-3 and the Corresponding Input Sequence Number(s). (3) Selection of Part Input Sequences. The same twenty part input sequences from balanced mix ratios are used for ES-i and ES-2. -Eleven of these twenty sequences are chosen using some myopic sequencing logic. The sequencing logic for the modified Johnson's rule is based on one pass of the Campbell-Dudek algorithm (Campbell et al. (1970)). One sequence is chosen because it is used in the Schriber and Stecke (1988) paper. The remaining eight sequences are chosen randomly. A summary of the selection logic for these twenty sequences is found in Table 4. Because some machining times on a particular 15

machine are the same for some of the selected part types, more than one input sequence was examined for two of the sequencing rules. Since different unbalanced part mix ratios are used for ES-3, a different set of part input sequences had to be chosen. Some consistency with ES-i and ES-2 is utilized in that the Modified Johnson's Rule approach is used to generate one of the sequences for each set of mix ratios. All other sequences are generated randomly. A summary of the selection logic for this second set of twenty sequences is found in Table 5. Also, the specific input sequence number for each of the-different mix ratios is given in Table 3. ~ Input Sequence Number Sequencing Logic " 1 Used by Schriber and Stecke (1988) 2-5 Modified Johnson's Rule 6 Shortest overall processing time first 7 Longest overall processing time first 8-10 SPT for middle machine group first 11 Longest processing time for middle machine group first 12 Reverse order of Modified Johnson's Rule 13-20 Randomly generated input sequence Table 4. Sequencing Logic for the Selection of the Twenty Part Input Sequences for ES-1 and ES-2. Input Sequence Number Sequencing Logic ' 21, 23, 25, 27, 29, 31, 33, 35, 37, 39, 40 Modified Johnson's Rule 22, 24, 26, 28, 30, 32, 34, 36, 38 Randomly generated input sequence Table 5. Sequencing Logic for the Selection of the Twenty Non-IP Part Input Sequences for ES-3. VI. RESULTS Table 6 presents the overall machine utilizations achieved by each part input sequence under the conditions described for ES-1. The bold numbers signify that the theoretical maximum 16

utilization for the applicable mix ratios is achieved. An example of how the theoretical maximum utilization is derived for a specific set of mix ratios is given in Appendix A. Input Sequence. 'Input WIlP Level Number Sequence..- 7 9 1 2, 6, 5, 2, 8, 6, 10 78.4 92.9 95.2 2 10, 6, 6, 5, 8,2,2 85.1 92.6 95.2 3 10, 5,6, 6, 8, 2, 2 81.6 93.0 95.2 _ 4 _10, 6, 6, 5, 2, 2, 8 83.3 93.0 95.2 5 10, 5, 6,6, 2, 2, 8 84.0 93.6 95.2 6 6, 6, 8, 2 2, 5, 10 80.8 93.8 95.2 _ 7 _210, 5, 2, 2, 8, 6, 6 80.0 90.9 95.2 8 8, 2, 2, 6, 6, 10, 5 83.3 90.9 95.2 ____ 9 _2, 2, 8, 6, 6, 10, 5 80.0 90.9 95.2 10 2, 2, 8, 6, 6, 5, 10 80.0 92.6 95.2 11 5, 10,6,6,2,2,8 76.9 92.3 95.2 12 2, 8, 2, 6, 5, 6, 10 81.6 94.6 95.2 13 2, 10, 6, 8, 2, 5, 6 83.3 95.2 95.2 14 10, 58,2, 6, 2, 6 83.3 93.1 95.2 15 6, 2, 10, 2, 8, 6, 5 83.3 93.7 95.2 16 5, 6, 10, 6, 2 8, 2 79.6 90.9 95.2 17 5, 8, 6, 6, 2, 10, 2 81.6 93.0 95.2 18 2, 6, 8, 6, 10, 2, 5 76.9 90.9 95.2 19 6, 2, 8, 10, 5, 2, 6 83.3 93.7 95.2 20 l 2,5,2,6, 10,6, 8 81.6 93.0 95.2 i~~~~~~~ ~8. 95.2 Average - Logic Average - Random 81.5 81.3 92.6 92.9 95.2 95.2 Std. Dev. - Logic 2.2 1.2 0.0 Std. Dev. - Random 2.3 1.3 0.0 Min Value - Logic 76.9 90.9 95.2 Min Value - Random 76.9 90.9 95.2 Max Value - Logic 85.1 94.6 95.2 Max Value - Random 83.3 95.2 95.2 Table 6. Overall Machine Utilizations for Various Input Sequences: No Look-Ahead and Balanced IP Part Mix Ratios. As expected, due to the decrease in the amount of time that a machine is idle because it is waiting for a part, the average overall machine utilization increases as the amount of WIP that is I 7

allowed into the system increases. Two other results that are of greater interest are: (1) for all WIP levels, part input sequences that are generated using some kind of basic sequencing logic are not obviously better than those that are randomly generated; and (2) the theoretical maximum utilization of 95.2% was achieved by every sequence when the WIP level allowed in the system is nine, but achieved by only one sequence when the WIP level is seven. This observation is consistent with the results of Conway et al. (1988) in that the strategic use of a little WIP can produce substantial gains in certain operating objectives. The first result indicates the robustness of the IP part mix ratios in generating input sequences. The second result indicates that having enough WIP in the system can also let these balanced mix ratios achieve the maximum utilization. Note that in this case "enough WIP" is not a lot: this is just nine parts for five machines in the particular system under study. Table 7 presents the overall machine utilizations achieved by each part input sequence under the conditions described for ES-2. The limited look-ahead capability is incorporated into these simulation runs to gain a better understanding of the impact that both part input sequencing and look-ahead capability can have on overall machine utilization. The ability to choose the input buffer for the machine that will become available at an earlier time has a positive effect upon overall machine utilizations. The direction of this impact is not surprising, but the magnitude is greater than expected. For WIP levels of five, the relative improvement of ES-2 over ES-1 on the average overall machine utilizations is 3.9%, while the relative improvement is 2.8% for WIP levels of seven. The range of absolute improvement is -0.7% to 10. 1% for WIP levels of five and 0.0% to 4.3% for WIP levels of seven. A closer look at Table 7 reveals three interesting and significant results: (1) for a set of balanced mix ratios, part input sequences that are generated using some kind of basic sequencing 18

logic are not obviously better than those that are randomly generated; (2) the theoretical maximum utilization of 95.2% is achieved by every sequence when the WIP level allowed in the system is seven or nine, but is never achieved when the WIP level is five, and (3) those sequences that perform better/worse under ES do not necessarily perform better/worse under ES-2. Compare input sequence numbers 1, 5, 13, 15, 18 under both settings. Input Sequence. Input' WIP Level __ Number Sequence::. 5 7 9 1 2, 6, 5, 2, 8, 6, 10 87.0 95.2 95.2 2 10, 6, 6, 5, 8, 2, 2 87.0 95.2 95.2 3 10,5,6,6,8, 2, 2 85.1 95.2 95.2 4 10, 6 66, 5, 22, 8 87.0 95.2 95.2 5 10, 5, 6,-6,2,2, 8 83.3 95.2 95.2 6 6, 6, 8, 2, 2, 5, 10 85.1 95.2 95.2 7 10, 5, 2, 2, 8, 6, 6 83.3 95.2 95.2 8 8, 2, 2, 6, 6, 10, 5 83.3 95.2 95.2 9 2, 2, 8, 6, 6, 10, 5 80.0 95.2 95.2 10 2, 2, 8, 6, 6, 5, 10 81.6 95.2 95.2 11 5, 10, 6, 6, 2 2, 8 85.1 95.2 95.2 12 2, 8, 2, 6, 5, 6, 10 81.6 95.2 95.2 13 2, 10, 6, 8, 2, 5, 6 83.3 95.2 95.2 14 10, 5, 8, 2, 6, 2, 6 87.0 95.2 95.2 15 6, 2, 10, 2, 8, 6, 5 83.3 95.2 95.2 16 5, 6, 10, 6, 2, 8, 2 84.5 95.2 95.2 17 5, 8, 6, 6, 2, 10, 2 87.0 95.2 95.2 18 2, 6, 8, 6, 10, 2,:5 87.0 95.2 95.2 19 6, 2, 8, 10, 5, 2,6 83.3 95.2 95.2 20 22, 5, 2, 6, 10, 6,8 87.0 95.2 95.2 Average - Logic Average - Random 83.9 85.5 95.2 95.2 95.2 95.2 Std. Dev. - Logic 2.1 0.0 0.0 Std. Dev. - Random 1.7 0.0 0.0 Min Value - Logic 80.0 95.2 95.2 Min Value - Random 83.3 95.2 95.2 Max Value - Logic 87.0 95.2 95.2 Max Value - Random 87.0 95.2 95.2 1 Table 7. Overall Machine Utilizations for Various Input Sequences: Look-Ahead and Balanced IP Part Mix Ratios. 19

The implications of these results are similar to those of ES-. The first and third results indicate the robustness of the IP part mix ratios in generating input sequences. The second result underscores the improvement in system performance that can be achieved by incorporating even a limited look-ahead capability into the scheduling routine. Table 8 presents the overall machine utilizations achieved by each part input sequence under the conditions described for ES-3. Also, Table 8 provides the theoretical maximum overall machine utilization that can be achieved for the appropriate part mix ratios implicit in the part input sequence. These theoretical maximum utilizations are always lower than those achieved by the balanced IP ratios. Several observations can be made concerning the performance of the input sequences associated with the unbalanced Non-IP part mix ratios. Note that the MPS mix ratio is included in this group (sequence numbers 29 and 30). First, the relative change in average overall machine utilization from ES-i to ES-3 is a decrease of 3.6% for WIP levels of seven, and a decrease of 5.9% for WIP levels of nine. Second, for WIP levels of seven, 17 out of 20 sequences reach the theoretical maximum utilization, while every sequence reaches the theoretical maximum utilization for WIP levels of nine. Third, the theoretical maximum utilizations for all of the unbalanced mix ratios utilized in ES-3 are lower than the theoretical maximum utilization of ES-1. Fourth, of the three input sequences that do not produce the theoretical maximum utilization, all are generated using a random approach (as opposed to the Modified Johnson's Rule). Finally, when look-ahead capability is incorporated into ES-3 (for space reasons, this experimental setting and its accompanying table are not detailed in this paper), all twenty input sequences for WIP level of seven reach the theoretical maximum, but the relative average overall machine utilization is only 20

increased by 0.2%. The improvement is trivial because most of the sequences are able to produce the theoretical maximum utilization without the look-ahead capability. 'Input Sequence. Inputi...WIP Level 'Theoretical: Number:' e:Sequence 7. 9 Maximum 21 10, 5, 6, 5, 8, 2, 2 90.4 90.4 90.4 22 2, 5, 2, 5, 6, 10, 8 90.4 90.4 90.4 23 10, 5, 6, 8, 2, 8, 2 91.8 91.8 91.8 24 8, 2, 10, 2, 5, 6, 8 91.8 91.8 91.8 25 10, 10, 5, 6, 8, 2, 2 91.3 91.3 91.3 26 8, 2, 6, 10, 5, 10, 2 90.5 91.3 91.3 27 10, 5, 6, 5, 6, 8, 2 84.2 84.2 84.2 28 2, 8, 5, 6, 5, 10, 6 84.2 84.2 84.2 29 10, 5, 6, 5, 8, 2, 8 88.7 88.7 88.7 30 8, 6, 5, 8, 5, 2, 10 88.7 88.7 88.7 31 10, 10,5,6,5, 8,2 84.8 84.8 84.8 32 _ 5, 10, 2, 5, 8, 10, 6 84.8 84.8 84.8 33 10, 6, 5, 6, 8, 2, 8 93.3 93.3 93.3 34 6, 8, 10, 6, 5, 8, 2 92.7 93.3 93.3 35 10, 10, 6, 5, 6, 8, 2 88.7 88.7 88.7 36 2, 10, 6, 8, 10, 5, 6 88.7 88.7 88.7 37 10 010, 5, 6, 8, 2, 8 93.6 93.6 93.6 38 8, 10, 2, 10, 5, 8, 6 90.9 93.6 93.6 39 10, 5, 6, 2, 8, 2, 2 89.6 89.6 89.6 40 10, 6, 5, 6, 6, 8, 2 89.6 89.6 89.6 Average 89.4 89.6 89.6 Std. Dev. - Random 2.9 3.1 3.1 Min Value - Logic 84.2 84.2 84.2 Max Value - Random 93.6 93.6 93.6 Table 8. Overall Machine Utilizations for Various Input Sequences: No Look-Ahead and Unbalanced Non-IP Part Mix Ratios. VII. SUMMARY AND CONCLUSIONS The three experimental settings presented here allow for useful observations on the changes in overall machine utilizations caused by changes in part input sequences, part mix ratios, 21

and look-ahead capability. In the context of the operating conditions and assumptions specific to this study, the following conclusions may be drawn: * The theoretical maximum utilizations are actually attained for balanced part mix ratios and are greater (in all cases tested) than those for the unbalanced part mix ratios (including the MPS mix ratio). * The theoretical maximum utilizations are achieved under realistic levels of WIP for balanced part mix ratios. * On average, over all WIP levels, the simulation results for balanced part mix ratios are superior to those for the unbalanced part mix ratios, including those obtained from the MPS. * The theoretical maximum utilizations are achieved at lower levels of WIP for balanced part mix ratios when incorporating look-ahead capability. * The balanced part mix ratios are very robust in generating part input sequences, especially when incorporating limited look-ahead capability. * The part mix ratio decision has a more significant impact in determining overall machine utilizations than the input sequence determination. These results are representative of the many simulation experiments done while investigating these part mix ratio/part input sequence determination problems. The results are relevant and important for industries that require high utilizations from their FMSs. VII. FUTURE RESEARCH Experimentation using different model parameter settings is needed to further investigate and validate the conclusions listed above. In particular, similar experiments should be run using 22

data sets that have different, for example wider, ranges of machining times. This would allow for further observations on the robustness of the balanced mix ratios of the IP formulation to determine cyclic input sequences. Continuing the study as part types finish and new part types enter as in a flexible approach to system operation could provide further insights. For example, Table 1 may depict a week of production requirements. At the end of the week, when very few requirements remain, these part types would require the bottleneck machine. However, one could supplement these remaining part types with complementary part types from next week's requirements to achieve the balancing opportunities. In addition, further comparisons of system performance for input sequences generated by balanced mix ratios versus permutations of the MPS would be of benefit and interest. It may be possible to perform such future studies using the (max, +} algebra of Cohen et al. (1985). Because of the particular problems under investigation, a somewhat aggregate deterministic simulation model was sufficient for these purposes. Also, because of the cyclic input sequencing, each simulation could have been modeled as a decision-free, timed Petri net. Equations to model the cyclic behavior could have been developed and would be linear in a (max, +} algebra (see Cohen et al. (1985)). Examples are provided in Dubois and Stecke (1990). The {max, +} algebra could be used to provide similar system performance measures and could also likely confirm the system behavior that we have observed. We chose to use simulation for several reasons. First of all, simulation was easier. The few parameters were easy and fast to change. The (max, +} equations would have had to be developed for each input sequence and would take longer to develop. Also, the simulations were very fast and very cheap. The average CPU time was 0.85 seconds per run (there were 60 runs for ES-1) and the average cost per run was $0.33. 23

Finally, utilizing the same experimental design while simulating the characteristics of different flexible flow systems would provide fUrther insight into the significance of the part mix ratio decision as it relates to the part input sequence decision. This would also provide insight into the significance of look-ahead capability under these different flexible flow system environments. 24

ACKNOWLEDGMENTS We would like to thank Thomas Schriber of The University of Michigan for his insightful and thorough comments regarding an earlier draft of this paper. We would like to thank the referees and Associate Editor for their very careful reading, which helped improve the presentation and explanation. Kathy Stecke would like to acknowledge a summer research grant from the Michigan Business School. 25

REFERENCES Agnetis, A., C. Arbib and K.E. Stecke (1990) "Optimal Two-Machine Scheduling in a Flexible Flow System," in Proceedings of the Second International Conference on Computer IntegratedManufacturing, RPI, Troy, NY. Akella, R., Y. Choong and S.B. Gershwin (1985) "Real-time Production Scheduling of an Automated Cardline," Annals of Operations Research, Vol. 3, 403-425. Amoako-Gyampah, K. (1994) "A Comparative Study of FMS Tool Allocation and Part Type Selection Approaches for a Varying Part Type Mix," International Journal of Flexible Manufacturing Systems, Vol. 6, No. 3, 179-207. Campbell, H.G., R.A. Dudek and M.L. Smith (1970) "A Heuristic Algorithm for the n Job, m Machine Sequencing Problem," Management Science, Vol. 16, No. 10, June, 630-637. Cohen, G., D. Dubois, J.P. Quadrat and M. Voit (1985) "A Linear System Theoretic View of Discrete-Event Processes," IEEE Transactions on Automatic Control, Vol. AC-30, No. 3, 210-220. Conway, R., W. Maxwell, J.O. McClain and L.J. Thomas (1988) "The Role of Work-in-Process Inventory in Serial Production Lines," Operations Research, Vol. 36, No. 2, March-April, 229-241. Dallery, Y. and K.E. Stecke (1990) "On the Optimal Allocation of Servers and Workloads in Closed Queueing Networks," Operations Research, Vol. 38, No. 4, July-August, 694-703. Dubois, D. and K.E. Stecke (1990) "Dynamic Analysis of Repetitive Decision-Free DiscreteEvent Processes: Applications to Production Systems," Annals of Operations Research, Vol. 26, 323-347. Erschler, J., D. Leveque and F. Roubellat (1982) "Periodic Loading of Flexible Manufacturing Systems," in Proceedings of the IFIP Congress, APMS, Bordeaux, France, 327-339. Escudero, L.F (1989) "An Inexact Algorithm for Part Input Sequencing with Side Constraints in FMS," International Journal of Flexible Manufacturing Systems, Vol. 1, No. 2, April, 143 -174. Henriksen, J.O. and R.C. Crain (1988) GPSS/H User'sManual, 3rd edition, Wolverine Software Corporation, Annandale, VA. Hitz, K.L. (1980) "Scheduling of Flexible Flow Shops-II," Report No. LIDS-R-1049, Laboratory for Information and Decision Systems, MIT, Cambridge, MA. 26

Hwang, S. (1986) "Part Selection Problems in Flexible Manufacturing Systems Planning Stage," in Proceedings of the Second ORSA/TIMS Conference on Flexible Manufacturing Systems, (Ann Arbor, MI), K.E. Stecke and R. Suri (eds.), Elsevier, Amsterdam, 297-309. McCormick, S.T., M.L. Pinedo and B. Wolf (1988) "Sequencing in an Assembly Line with Blocking to Minimize Cycle Time," Operations Research, Vol. 36, No. 6, NovemberDecember, 925-935. Miltenburg, J. (1989) "Level Schedules for Mixed-Model Assembly Lines in Just-in-Time Production Systems," Management Science, Vol. 35, No. 2, February, 192-207. O'Keefe, R.M. and R. Rao (1992) "Part Input into a Flexible Flow System: An Evaluation of Look-ahead Simulation and a Fuzzy Rule Base," International Journal of Flexible Manufacturing Systems, Vol. 4, No. 2, January, 113-127. Rajagopalan, S. (1986) "Formulation and Heuristic Solution for Parts Grouping and Tool Loading in Flexible Manufacturing Systems," in Proceedings of the Second ORSA/TIMS Conference on Flexible Manufacturing Systems, (Ann Arbor, MI), K.E. Stecke and R. Suri (eds.), Elsevier, Amsterdam, 311-320. Schriber, T.J. (1991) An Introduction to Simulation Using GPSS/H, John Wiley & Sons, New York. Schriber, T.J. and K.E. Stecke (1987) "Using Mathematical Programming and Simulation to Study FMS Machine Utilizations," in Proceedings of the 1987 Winter Simulation Conference, A. Thesen, H. Grant and W.D. Kelton, (eds.), Society for Computer Simulation, San Diego, CA. Schriber, T.J. and K.E. Stecke (1988) "Machine Utilizations Achieved Using Balanced FMS Production Ratios in a Simulated Setting," Annals of Operations Research, Vol. 15, 229 -267. Stecke, K.E. (1983) "Formulation and Solution of Nonlinear Integer Production Planning Problems for Flexible Manufacturing Systems," Management Science, Vol. 29, No. 3, March, 273-288. Stecke, K.E. (1992) "Procedures to Determine Part Mix Ratios for Independent Demands in Flexible Manufacturing Systems," IEEE Transactions on Engineering Management, Vol. 39, No. 4, November, 359-369. Stecke, K.E. and I. Kim (1986) "Decision Aids for FMS Part Type Selection Using Aggregate Production Ratios to Study Pooled Machines of Unequal Sizes," Working Paper 478, Graduate School of Business Administration, University of Michigan, Ann Arbor, MI. 27

Stecke, K.E. and I. Kim (1988) "A Study of FMS Part Type Selection Approaches for ShortTerm Production Planning," International Journal of Flexible Manufacturing Systems, Vol. 1, No. 1, September, 7-29. Stecke, K.E. and I. Kim (1989) "Performance Evaluation for Systems of Pooled Machines of Unequal Sizes: Unbalancing Versus Balancing," European Journal of Operational Research, Vol. 42, 22-38. Stecke, K.E. and I. Kim (1991) "A Flexible Approach to Part Type Selection in Flexible Flow Systems Using Part Mix Ratios," International Journal of Production Research, Vol. 29, No. 1, 53-75.' Stecke, K.E. and J.J. Solberg (1985) "The Optimality of Unbalancing Both Workloads and Machine Group Sizes in Closed Queueing Networks of Multiserver Queues," Operations Research, Vol. 33, No. 4, July-August, 882-910. Tang, C.S. (1990) "Scheduling Batches on Parallel Machines with Major and Minor Set-Ups," European Journal of Operational Research, Vol. 46, No. 1, 28-37. Whitney, C.K. and T.S. Gaul (1985) "Sequential Decision Procedures for Batching and Balancing," Annals of Operations Research, Vol. 3, 301-316. Wittrock, R.J. (1985) "Scheduling Algorithms for Flexible Flow Lines," IBM Journal of Research and Development, Vol. 29, No. 4, 401-412. 28

Appendix A Calculation of the Theoretical Maximum Overall Machine Utilization for a Given Set of Part Mix Ratios The technique as well as the idealized operating assumptions used by Schriber and Stecke (1988) to calculate the theoretical maximum overall machine utilization are utilized in this paper. Only the highlights of their technique will be repeated here. Table Al shows the individual and total machining requirements, by machine type, for the part types making up one input cycle for the IP part mix ratios used in ES-1 and ES-2. The total workload per machine (80, 105, 105) is the optimal workload per machine provided by the closed queueing network model for a system comprised of(l, 2, 2) machines per group (Stecke and Solberg (1985)). Machining Time Per Part Number of Machining Time Per Input Cycle Part __ (Minutes) Parts Per.. ites Type Mill "Dll l VTL I.nput Cycle Mill Dil VTL 2 15 20 40 2 30 40 80 5 10 50 20 1 10 50 20 6 10 30 20 2 20 60 40 8 10 20 30 1 15 20 30 10 5 40 40 1 5 40 40 i~ i! -iiiii Total for all Machines of Each Type 80 210 210 iTotal per Machine of Each Type 80 105 105 Table Al. Machining Requirements per Part Input Cycle for ES-1 and ES-2. As shown in Table Al, -the seven parts making up one input cycle require no more than 105 minutes on any one machine. Therefore, the number of machining minutes available is 525 (105*5 machines). The two drills and the two lathes can be utilized 100% (105/105), and the mill can be utilized 76.1% (80/105). Of the potential 525 machining minutes, only 500 (80+210+210) can be achieved. Hence, the maximum overall machine utilization is 95.2% (500/525). m

Table A2 shows the individual and total machining requirements, by machine type, for the part types making up one input cycle for the unbalanced Non-IP part mix ratios used for input sequence numbers 27 and 28 for ES-3.. "Machining Time PerPart..'Nber."of.:.Machining.Time Per Input Cycle Pa(Min.' Part s:Per t ':,' ".. (Minutes)___ Type. Mill. Drill VTL.-Input. Cycle.il Dll VTL 2 15 20 40 1 15 20 40 5 10 50 20 2 20 100 40 6 10 30 20 2 20 60 40 8 10 20 30 1 15 20 30 10 5 40 40. 1 5 40 40 i n. i i i l l a Total for all Machines of Each Type 75 240 1 190 Total per Machine of Each Type 75 120 95 Table A2. Machining Requirements per Part Input Cycle for Part Input Sequence Numbers 27 and 28 for ES-3. The logic here is the same as in the previous calculation. The number of machining minutes available is 600 (120*5). The mill can be utilized 62.5% (75/120), the two drills can be utilized 100% (120/120), and the two lathes can be utilized 79.2% (95/120). Of the potential 600 machining minutes, only 505 (75+240+190) can be achieved. Hence, the maximum overall machine utilization is 84.2% (505/600). 30