i Division of Research School of Business Administration The University of Michigan CLASSIFICATION AND REVIEW OF FMS SCHEDULING PROCEDURES Ram Rachamadugu University of Toledo and Kathryn E. Stecke University of Michigan July 1993 Working Paper No. 711

CLASSIFICATION AND REVIEW OF FMS SCHEDULING PROCEDURES Ram Rachamadugu The University of Toledo College of Business Toledo, Ohio Kathryn E. Stecke The University of Michigan School of Business Administration Ann Arbor, Michigan July 1993 ABSTRACT In this paper, existing flexible manufacturing system (FMS) scheduling procedures are classified and reviewed. First, a classification scheme is provided that is based on key factors such as the FMS type, the mode of system operation, the nature of the demands placed on the system, the scheduling environment, and the responsiveness of the system to disturbances. The choice of appropriate scheduling criteria is discussed. Differences between conventional job shops and FMSs, and the effects of these differences on potential scheduling procedures are provided. The classification, comparisons, and FMS scheduling reviews aim to be useful to vendors, users, and researchers. We point out specific areas which appear to have been overlooked. Future research directions are also indicated. Key words: flexible manufacturing, FMS scheduling

CLASSIFICATION AND REVIEW OF FMS SCHEDULING PROCEDURES 1. Introduction Recent trends in the U.S. economy have focused the attention of practitioners and academicians on the need to examine the productivity problems in the manufacturing sector. A considerable proportion of manufacturing output originates in the metal-working industry, particularly small batch manufacture. By some estimates this is perhaps one of the least productive sectors, with equipment being utilized only about 7% of the time on average (Opitz [1971]). Batch manufacturing has been characterized by low equipment utilization and high work-in-process inventories. Carter [1971] and Schaeffer [1981] also assert that for an average batch type production system, a part spends only about 5% of the time processed by the machine tool. In practice, manufacturing system designers can face a critical trade-off in their choices — flexibility versus efficiency. Flexibility to manufacture a wide range anof part types (i.e., with job shops) is generally derived at the expense of efficiency or unit cost of production. However, automatd ted systems provide nearly the flexibility of job shops with nearly the efficiency of large volume manufacture. Such systems effectively reduce the operating cost of small and mid-volume batch manufacturing. Flexible manufacturing systems (FMSs) achieve these goals by virtually eliminating operation set-up or changeover time between consecutive manufacturing operations. An FMS automatically operates with little human intervention. A metal-cutting FMS consists of a set of computer numerically controlled (CNC) machine tools, each capable of multiple tasks, interconnected by an automated materials handling system and sometimes a resource (i.e., cutting tools) delivery system. All of these are controlled by a computer system. Examples of existing FMSs are described in Groover [1980], Stecke and Solberg [1981], Ranky [1983], Stecke [1983, 1992a], and Miller [1985]. The design and subsequent operation of FMSs are complex and time-consuming tasks. The flexibility, complexity, and the need for system integration of FMSs increase the decision alternatives at both strategic and tactical stages. This makes the functions of FMS design and operation difficult. Strategic decisions involve FMS design, which are of a long-term nature, such as the choice of machines, material handling devices, part types likely to be manufactured using the system, the degree of flexibility to be built in, etc. Operational decisions involve tactical issues, such as part type selection, part input ratios, part input sequencing, and scheduling. See Stecke [1985a] for descriptions of these problems. They can be difficult because there may be alternative routes to consider, refixturing, and tool constraints. Hence most researchers have adopted hierarchical approaches to the design and operation of FMS. Suri [1985] and Stecke [1985b] review analytical models and approaches used by various researchers.

One aspect of FMS operational control is to schedule parts effectively, for example, to meet all requirements by their due dates. Scheduling is at the lowest level of detailed FMS decision-making and is part of the day-to-day operation of the system. Among the purposes of this paper are to review and classify the existing procedures that have been suggested for scheduling parts in FMSs. We are motivated to develop such a framework, since FMS operation can be complex because of the versatility and the integration required. Different scheduling procedures are appropriate for different situations. This study will help to identify issues that are critical to the development and use of scheduling procedures in various situations. Further, it is hoped that the review will be helpful in identifying areas for future research and development. It is also expected to be useful to vendors, users, and those developing FMS scheduling software and algorithms. The paper is organized as follows. In Section 2, a taxonomy of FMS scheduling issues is provided. The taxonomy is based on the FMS type as well as the nature of demands placed on the system. The differences between FMS and job shop scheduling are explored in Section 2.3. Factors relating to the choice of appropriate criteria are identified in Section 2.4. The influence of FMS planning, which can make FMS scheduling trivial for some systems, is discussed in Section 2.5. In Section 3, scheduling in flexible flow systems and in Section 4, the scheduling of dedicated FMSs are examined. As the various scheduling studies are examined, we try to note the sizes of the example systems, the assumptions made, and the significant conclusions and limitations of each study. Scheduling issues conceming nondedicated FMSs are discussed in Section 5. Potential effects of just-in-time manufacturing systems on FMSs are also explored. In Section 6, implications of FMS scheduling for higher levels in the hierarchy of decisions are identified. Finally, the paper concludes with future research directions. Prior to our discussions on scheduling procedures used in FMSs, it is necessary to define relevant FMS scheduling terminology. Although many of the terms are also used in conventional job shop scheduling, differences do exist in their usage in FMS scheduling. Our use of the terms is defined in Table 1. 2. Taxonomy of FMS Scheduling Issues FMS is a term collectively used to indicate different types of automated manufacturing systems. However, an appropriate classification of these systems is helpful in identifying relevant scheduling procedures. The classification scheme of Browne et al. [1984] is based on process characteristics. This categorization captures the major aspects of system design and operation such as the choice of equipment, layout, capacity decisions, and other tactical issues. -3 -

TABLE 1 TERMINOLOGY IN FMS SCHEDULING PART TYPE (TOOL) LOADING ROUTING MINIMAL* PART SET PART INPUT SEQUENCING SCHEDULING Each customer order is either one of the existing 'part types or a new part number and process plan is defined. FMS loading refers to the allocation of tooling and the physical loading of cutting tools into tool magazines of various machines. This determines which machine tool(s) can perform each operation. Tool magazines have limited capacity and hence the set of operations which can be performed on each machine are limited by the availability of tools. The term is dissimilar to its usage in conventional job shop scheduling. Routing refers to the specification of machine(s) on which a particular operation of a part type will be performed. The term is similar to its usage in conventional job shop scheduling. A difference is that in a job shop usually each part type is given only one route through the system. A minimal part set (MPS) consists of the minimum integer values that are proportional to periodic production requirements for all part types. Input sequencing refers to the order in which parts of various types are released into the system. The term 'input seuencing' in FMS scheduling is similar to the use of the term 'loading' in conventional job shop scheduling. FMS scheduing involves the process of determining when different operations of various part types are started and completed on various machine tools. The term is similar to its usage in conventional job shop scheduling. *Since the acronym MPS is widely used in the literature to denote Master Production Schedule, we use MPS to denote Minimal Part Set. -4 -

A dichotomy of FMSs which is useful from a scheduling point of view is Flexible Flow Systems (FFSs) and General Flexible Machining Systems (GFMSs). See Figure 1. FFSs can be further subcategorized into Flexible Assembly Systems (FASs) and Flexible Transfer Lines (FTLs). The conventionally termed Flexible Manufacturing System (primarily and initially used in the metal-cutting industry) is usually thought to be a nonserial machining system, which permits a random process routing of the part types (GFMSs). GFMSs are, in this respect, somewhat similar to conventional job shops. However, we outline many important differences in Section 2.3. Flexible Manufacturing System (FMS),,.,.,, ~General Flexible General ~Flow Flexible Physical < Flowo System Machining Flow rFFS System (FFS) Flexible F|lexible Dedicated Nondedicated Number Assembly Transfer ~System TineMachining Machining Part System Line (FAS) (FTL) System System Types VAA "7S T jL/NFM S) Decreasing Production Rate of Individual Part Types Increasing Simultaneous Part Type Variety Figure 1. Classification of FMSs Based on the Mode of Operation. An analysis of FMS scheduling procedures can be enhanced through the use of an appropriate classification scheme of the procedures. Although there are many dimensions in which to classify the scheduling procedures, it is useful to make the classification on those few dimensions which capture most of the differences. The few important dimensions on which the classification can be based are now discussed. -5 -

(i) Operational Mode: The nature of demands placed on the FMS is an important dimension for the classification of scheduling procedures. Based on the demands, an FMS can be operated in a dedicated or a nondedicated mode. In a dedicated mode, the FMS usually produces a specific set of part types and often for direct consumption by a downstream processor for inventory to meet user demands from a buffer. The ratios in which these parts are produced may vary from time to time depending on demand and/or operational efficiency factors. Such systems may be driven by an MRP-type system. The parts may be fed to a downstream process such as an assembly line. FMSs operated in this mode can be denoted as Dedicated Flexible Machining Systems or Flexible Transfer Lines for classification purposes. See Figure 1. How the system is operated forms the basis for this classification, as well as the hardware configuration. In a nondedicated mode of operation, the part types and production requirements change frequently. These systems are the most similar to job shops. Here, part routings can be different even for parts of the same type. We term systems operated in this mode as Nondedicated Flexible Machining Systems. (ii) Scheduling Environment: Another dimension that is important to the analysis of scheduling procedures is the type of environment. Prior studies in the context of lot-sizing decisions have shown that procedures which perform well in static environments need not necessarily perform well in dynamic environments. For example, MRP systems are very "nervous" to demand changes that affect the master production schedule. This raises a few scheduling issues that need to be considered. For example, how frequently should an FMS be scheduled or rescheduled? Should an FMS be scheduled on a periodic basis (such as shiftto-shift) or dynamically (whenever order status or machine status changes)? These considerations can influence the way procedures are developed and implemented as well as how they perform. (iii) Responsiveness: Yet another critical issue is the responsiveness of the scheduling system to changes in both the FMS status (i.e., which machines working, which part mix) as well as the external demands placed on the manufacturing system (new 'hot' orders). Since FMSs are centrally controlled, linked through automated material handling, and operate with minimal work-in-process and/or finished goods inventories, a change in the status of any one machine tool (such as a cutting tool breakdown or machine tool failure) can affect the operation of the other machine tools. Thus, scheduling procedures which generally tend to be computationally time consuming (such as many of the optimum-seeking procedures that have been suggested for job shops) may not be appropriate. A broad categorization on this basis could be real-time versus off-line scheduling. -6 -

2.1 Flexible Flow Systems The basic parameters of an FMS that is designed to produce a few part types in relatively large volumes would be different from those of one that manufactures a wide variety of part types. FFSs belong to the former category. They would generally: i. produce few part types; ii. be dedicated; iii. manufacture each part type in large volumes simultaneously. Because of these properties, it is likely that an FFS would not require the levels of flexibility that would be useful to an FMS designed and operating to produce a wide variety of parts (GFMSs). Material flow in FFSs tends to be unidirectional, except in the case of reentrant flow systems. Because of the volumes required, efficiency (unit cost of production) and throughput are important. Flexible flow systems can be classified as FASs or FTLs (see Figure 1). Examples of these include FFSs to fabricate and/or assemble electronic components such as IBM's Lexington, Kentucky facility (Modern Material Handling [1985]). Another example is an FAS designed by GMF Robotics to automatically assemble electric paint robots (see Hall and Stecke [1986]). Other types of FASs are described by Wittrock [1985] and Rohan [1985]. The SCAMP (Six Hundred Group Computer-Aided Manufacturing Project) FMS of the Colchester Lathe Company in the U.K. is similar to an FTL. The system largely consists of 2 -and 5-axis CNC lathes as well as hobbing and broaching machines. A unidirectional conveyor transports batches of cylindrical components from machine to machine in a fixed route. 2.2 General Flexible Machining Systems The hardware configuration of General Flexible Machining Systems (GFMSs) permits the manufacture of a wide variety of part types simultaneously. However, the system can be operated in several ways, in particular, in a dedicated mode (as a DFMS) to produce a few part types in particular required ratios. Alternatively, it may be operated to produce a wide variety of part types with the demands for part types varying over time (an NFMS). Then the goal is to maximize production subject to meeting daily or weekly production requirements. The traditional job shop problem of scheduling the operations on the machines over time is not the main problem in DFMSs. One scheduling problem is to determine an appropriate part input sequence into the system. Then the parts flow through the system to be either fabricated and/or assembled. Another operational problem that can impact the part input sequence problem is to determine appropriate ratios at which the part types selected to be produced next should be maintained. In some instances, the various part types are required in certain relative ratios (for example, equal) for subsequent assembly. These output ratios can be translated to operating -7 -

production ratios. Alternatively, if the part type demands are independent, then production ratios can be obtained that balance the workload. Nondedicated Flexible Machining Systems (NFMSs) are configured to handle a wide variety of part types with potentially different routings for each. Some operations can be performed by more than one machine tool. This allows routing flexibility. Since most aspects of FMS operation are computer controlled, there may be no need for an a priori specification of routing and sequencing. Then choices can be made dynamically, depending on the status of the FMS, including such factors as tool failures and machine breakdowns. Order sizes for a particular part type can vary considerably depending on the customer orders or internal requirements. Because of the potential alternate routing and sequencing alternatives that are available, an appropriate choice of scheduling procedures in a GFMS may be difficult. However, as some research shows, the existence of many alternative routes results in the system performance being less sensitive to the choice of scheduling rules. We explore these issues in detail in Section 4. Flexibilities inherent in the GFMSs can be used strategically. For example. General Electric reduced manufacturing lead time from 16 days to 16 hours in some machining processes, thus enhancing its ability to respond fast to changing market demands (Kinnucan [1983]). Similarly, one of the reasons for John Deere's use of a GFMS appears to be its ability to introduce new models at a low cost and reduced lead time (FMS Magaine [1982]). 2.3 How FMS Scheduling Differs from Job Shop Scheduling Conceptually, a GFMS may seem similar to a conventional job shop, particularly when it is configured to produce a wide variety of parts. However, there are substantial differences between the two which need to be considered when developing scheduling methods. Alternative routing: Because of the different types of flexibilities available from the FMS hardware and software capabilities, alternate routings are more widely available for use in real-time in a GFMS than in conventional job shops. Although conventional systems also have routing flexibility, the actual use is limited due to a lack of availability of timely information and issues related to organizational control. It is difficult to control operations if process sheets list all or many routing and sequencing alternatives and leave the choices to individual schedulers. Centralized computer control makes it relatively easy to use the routing flexibility in FMSs. In addition, although it is possible in a job shop to split a batch so that several machines are simultaneously performing a particular operation, this is usually not done because of the large set up times required for that operation. However, the ability to make use of alternate routings provides more flexibility. Using this flexibility can improve the system performance. However, this can make FMS loading, part input, and routing decisions more complex. -8 -

Buffer limitations: FMS material handling facilities are automated and most often limit the amount of work-in-process or finished parts that can be held in the system. In-process inventory can be held either: in centralized storage, or in buffers provided at the individual machine tools (if available), or in an automated storage and retrieval system, or on the material handling system. Job shop scheduling overlooks this aspect and assumes that all necessary storage space is available. However, this is often a critical constraint in FMS scheduling. Finite buffers can lead to blocking and starving. This has to be considered in the real-time FMS scheduling of parts. Transportation time: In a job shop, it is unlikely that a machine waits for a part while it is in transit. Part waiting time in a job shop is high because of the large queues and large batches. Hence even if travel times are substantial, it is unlikely that the subsequent operation is held up because of travel time. In an FMS, transportation time is important and partly depends on the material handling system utilization and speed. Although prior research has considered this at an aggregate level (see Buzacott and Shanthikumar [1980], Suri and Hildebrandt [1984], and Suri and Dillie [1985]) using techniques such as queueing network models, mean value analysis, and perturbation analysis, we are not aware of many scheduling procedures which explicitly consider travel and/or waiting times at a detailed level. Some FMS simulation studies take travel time into consideration. Transportation capacity: There can be capacity restrictions on the material handling system. There may be a finite number of AGVs or tow-line carts. Conveyors may be less restrictive with respect to capacity, but are less flexible. The material handling system is another resource that a part needs before it can be processed. Some coordination and integration need to be considered in scheduling the operations. Deterministic processing times: There is very little direct labor in the setup between consecutive operations and the running of the individual CNC machine tools in FMSs. Since the operations are computer controlled, processing times are highly predictable and nearly deterministic. This implies that not only are schedules predictable (except for failures which occur randomly), but also that resources might be better utilized. This could result in reduced waiting times and hence less in-process inventory. However, technological developments such as adaptive control of tools (Koren [1983]) may make the processing times less predictable in FMSs. Reduction of set-up time between consecutive operations: In automated facilities and their components which include, for example, robots, numerically controlled machines, CNC machine tools, direct numerically controlled machines, and FMSs, programmability of the instructions for operation drastically reduces set-up times between consecutive -9 -

operations. This in turn can reduce work-in-process inventories, which otherwise, in a job shop, would build up because of lot-sizing decisions. Pallet and fixture limitations: There are limited numbers of pallets and fixtures of different fixture types in an FMS. These limited resources affect both planning and scheduling problems and also need to be considered. These are the main differences between FMSs and job shops. All of these factors and others have to be considered when developing appropriate FMS scheduling procedures. In addition, downtime has to be considered. Although machines also break down in job shops, an FMS is even more sensitive to breakdowns because of the tighter synchronization, integration, and dependencies among the automated components. A study by Jaikumar [1986] comparing the FMSs in the U.S. and Japan underscores the importance of machine reliability and its impact on the availability of the system. 2.4 Criteria for Scheduling Another important consideration is the choice of appropriate criteria for scheduling. Although the ultimate objective of any enterprise is to maximize the net present value of the shareholder wealth, this criterion does not easily lend itself to operational decision-making in scheduling. Some researchers are developing methodologies which take revenue and cost effects of schedules into consideration (see Morton et al. [1986]). Researchers and practitioners have so far used operational surrogates that influence costs and revenues. These include: number of parts tardy, average tardiness, weighted tardiness, throughput (this is a revenue-influencing surrogate), as well as average number of parts in the system, machine utilization, and work-inprocess inventory, for example. Analyses of these surrogates indicate that a scheduling procedure which does well for one criterion is not necessarily the best for some other. For example, attempts to reduce mean tardiness can lead to an increase in mean flow time. Minimizing makespan can result in higher mean flow time. Further, a criterion which is appropriate at one level of decision-making may be unsuitable at another level. These raise further complications in the context of FMSs because of the additional decision variables involved in including, for example, routing and sequencing alternatives. Job shop research uses various types of criteria to measure the performance of scheduling algorithms. Performance measures used in FMS studies usually relate to throughput time, system output, and/or machine utilization. This is not surprising since many FMSs are operated as dedicated systems and the systems are very capital intensive. However, general purpose FMSs, such as Yamazaki Mazak (Jaikumar [1986], Miller [1985]), operate in some ways like job shops in that part types may have to be scheduled according to customer requirements. Part -10 -

production requirements at the Vought LTV system in Dallas, Texas are generated by an MRP system (Webster [1986]). In these systems due date related criteria are important. However, it is only recently that due date based procedures have been investigated by researchers for GFMSs. 2.5 The Influence of FMS Planning Although the focus of this paper is on FMS scheduling procedures, some words have to be said about the FMS planning function, that of setting up a system for production, but before production begins, as these problems are intimately related. FMS scheduling is concerned with controlling the flow of parts through the system, usually after the system has been set up during the planning stage. However, solutions to the planning problems provide constraints that the subsequent scheduling solutions have to satisfy. The FMS planning problems to be addressed before scheduling and production can begin include: 1. Selecting the part types that will be in simultaneous production over some upcoming period of time; 2. Possibly pooling two or more machines of the same type into identically tooled machine groups; 3. Determining ratios in which the selected set of part types should be produced; 4. Allocating the limited pallets and fixtures among the selected part types; and 5. Allocating each operation and its associated tools of the selected part types among the machines. Each of these planning problems can be solved in a variety of ways, each appropriate for different FMS types. Since solutions to these planning problems provide constraints for FMS scheduling, as potential scheduling procedures are presented in the subsequent sections, their capability to accommodate tooling, fixtures, and other FMS constraints will be noted. For some FMS types, if enough care is taken to solve the planning problems to help result in a subsequent flexible operation, FMS scheduling may be quite simple. For more complicated FMSs, scheduling can itself be an important function. For example, in some FMSs, each part may visit only one machine for all of its operations, sometimes requiring one or two refixturings in between such consecutive operations. These are then like single operation parts and all scheduling problems are trivial. A Comau system is like this, where the key operating problems involve tooling considerations (Stecke [1989]). Scheduling may likely be a more complicated function when each part needs to visit several machines and when several operations have a choice of machines. The availability of alternative routing can improve system performance as well as increase scheduling complexities. In general, queueing network models have been used to address FMS design problems quantitatively and FMS planning problems qualitatively. Queueing network models generally do not have sufficient modeling capability to address detailed scheduling problems. Some notable modeling research along these lines has been done by Shalev-Oren, Seidmann, and -11 -

Schweitzer [1985] and Yao and Buzacott [1985]. Further research is required into using queueing models to address some scheduling problems. In the remainder of this paper, we focus on the use of more detailed models. 3. Scheduling In Flexible Flow Systems Since the intended purpose of FFSs is to manufacture a few part types, the roles of flexibility are primarily to dynamically reroute the parts in case of machine failures; to easily adapt to changes in relative volume requirements driven by changes in the market needs; and to easily changeover whenever modifications are made in part specifications. Flexible flow systems are suited for these purposes since they can be rebalanced to account for such changes. For systems such as FASs and FTLs, the main scheduling problem is to determine a good part input sequence (i.e., see O'Keefe and Rao [1991] and Smith and Stecke [1992]). This is because the flow of work is largely unidirectional. Also, because of small buffer space, routing, and other scheduling decisions usually do not need to be made. Machines may sometimes be bypassed. In addition, as noted in Section 2.3, finite buffers, capacity constraints, deterministic processing times, low set-up times between consecutive operations, and breakdowns all need to be considered in flexible flow systems. However, consideration of alternative routing in real time operation is less important, since parts usually flow from one machine to the next in a fixed sequence. When fewer part types are required in higher volumes, a periodic input sequence sometimes is appropriate because of the typically repetitive nature of the production requirements. Some relevant research into these types of problems has been done, which we now review. An early pair of studies of FTLs with finite buffers was performed by Hitz [1979, 1980]. The first study allows only a single buffer at each machine and only two consecutive parts are able to pass each other. The later study allows FIFO buffers of arbitrary capacity in the model (buffers of size 1 or 2 are considered in the study) and up to three consecutive parts are allowed to pass each other. The given production requirements were scaled down to provide the minimal part set (MPS) (see Table 1). An implicit enumeration algorithm is proposed to determine a periodic part input sequence from the MPS for one period that satisfies the buffer constraints and keeps the bottleneck machine busy. This tends to maximize the steady state production rate. It is assumed that the production ratios are prescribed in advance (they are an MPS that is proportional to the production requirements) and that for each part type, only one route is available. Eighteen problems of 6 and 8 machines, 5 part types, and 15-25 parts per period are investigated. The results indicate that finding an optimal input sequence is extremely time-consuming. However, a heuristic is proposed that uses the same algorithm. Suboptimal input sequences are found in 20-30 seconds of CPU time on a DEC 11/70. The heuristic provides a lower bound on -12 -

the steady state production rate. The most difficult problems solved were for FFSs having small buffer capacity, balanced workloads, and a wide range of processing times. A beneficial feature is that these periodic sequences, which maximize steady state performance, will rarely be unique. This should make it easy to find one of the good input sequences. A continuous flow control model for FASs is suggested by Akella, Choong, and Gershwin [1985] to determine a part input sequence for a system based on a four station IBM printed circuit card assembly line in Tucson, Arizona. The objective is to try to meet the production requirements while limiting WIP. To compensate for machine failures and to meet the production requirements, parts are input into the system to build up a buffer stock of each part type. System capacity is considered to keep WIP down. The ratio of cumulative production to cumulative demand and imbalances in production rates are used as surrogates for trying to maintain output rates close to desired demand rates. There is no scheduling as all parts flow through the large buffers in FCFS sequence. Simulation is used to compare the suggested approach to three simpler part input rules: i. Input the part whose type is furthest behind or least ahead of cumulative demand. N is the total number of parts allowed in the system. ii. The input rule is the same, except for an imposed limit of Ni parts for each type i. iii. The input rule is again the same, except that Ni equals zero, when a machine that type i visits, fails. Six part types are allowed in the system and each part type visits either 1, 2, or 3 of the four machines. Mean time between failures is 600 minutes and average repair time is 60 minutes. A goal is to maximize system utilization. Because of machine failure, production requirements of each type are generally not met. However, the suggested part input approach results in higher production percentages (percent of completed requirements), a better balance among the six part types, and lower WIP than the three simple input rules. The second and third rules also resulted in almost as good production percentages and good part type balances, but at a higher WIP. Further, they address problems involving the stability of sequences. Their earlier work would cause sequences to continuously change too drastically in response to breakdowns. In this version, the responses are smoothed. Wittrock [1985] develops heuristic algorithms for loading tools and input sequencing part types in an FAS. Bypassing is permitted and FCFS is used. He illustrates the suggested procedures on a model of an IBM production line, where components are inserted into printed circuit cards. The eight-machine FAS consists of three groups in series of two, three, and three machines each, respectively. On any day, the part type requirements (different card types and -13 -

components) are known. The first step determines the loading —i.e., which machines are tooled to perform various operations. The criterion is to balance the work among the machines in each group on the line. Each operation is assigned to only one machine. Thus, the production rate is limited by the bottleneck machine. The production requirements are scaled down to operating production ratios, from which a part input sequence is found (similar to Hitz [1979] and Erschler et al. [1982]). The part input sequence does not affect the production rate since there is no blocking or starving because of adequate buffers. Thus the objective in choosing the input sequence is to decrease the use of the limited buffers in front of each machine so that overflowing is avoided. This is similar to the objective of Akella et al. [1985] of minimizing WIP. Determining an optimal input sequence to minimize queueing is a hard problem. Hence Wittrock develops a heuristic input sequencing procedure. The heuristic is based on the idea that keeping the workloads balanced over time can generally reduce the buffer usage. An upper bound on the buffer requirements can be derived using procedures suggested by Afentakis [1986]. Wittrock reports on the performance of his procedure. Computational tests were done by Pasquier [1984], who simulates the 8-machine, 3 group IBM system. Wittrock's heuristic procedure performs better than some other rules in reducing the buffer usage. The rules tested are, for each MPS: i) Input each part into the system at a constant interval in the sequence suggested by Wittrock [1985]; ii) Input each part at a constant interval, but the sequence may be any random permutation of the parts in the MPS; and iii) Batch parts of the same type and input each batch sequentially. Wittrock also reroutes parts that had been scheduled on a machine that has gone down. He compares his suggested static rerouting policy with a dynamic rerouting policy suggested by Pasquier [1984]. The aim is to bring the system back to normalcy without blocking and/or starving. Wittrock's policy is as follows: when a machine breaks down, workloads of the other machines in the particular machine group are recomputed and reassigned. If necessary, part input is slowed down. When the machine is repaired, the original procedures are followed. Pasquier found the following dynamic routing policy to be the most effective: when a part arrives at a group of machines, it is assigned to the machine which has the least amount of work in its buffer. The dynamic rerouting policy performs better than the static policy, as might be expected. Further, he discusses how linear programming can be used to determine batches of -14 -

part types for each day's production when the planning horizon extends over a period of, say, a week or month. Part input sequencing into flexible flow systems has also been studied by O'Keefe and Rao [1991]. They use a fuzzy rule base in combination with a look-ahead simulation model to schedule the input of parts of various types. Pinedo, Wolf, and McCormick [1986] also investigate part input sequencing. Their study is motivated by a problem in sequencing the assemblies of different types of parts (copiers) in specified production ratios on an FAS with finite buffers. Although the blocking effects of finite buffers in stochastic transfer lines have been studied, the effect on FASs having deterministic processing times has not been investigated. The objective is to maximize the production rate. Although not explicitly stated in their study, machines seem to use FCFS. It appears that by-passing machines is not permitted. Production ratios are found as the smallest integer set proportional to the production requirements (an MPS similar to Hitz [1979], Erschler et al. [1982, 1986], and Wittrock [1985], for example). For any given input sequence, the production rate from the system can be determined by the longest path in an acyclic network. Hence the problem translates to specifying the input sequence (some permutation of the production ratios) so that the longest path is minimized. Pinedo et al. [1986] recognize that the problem is NP-complete even in its simplest form when the processing times are 0 or 1. They develop heuristics, although no computational results are reported. Das and Khumawala [1991] address the problem of scheduling batches of part types in flexible flow systems. The objective is to minimize makespan. A sequence dependent setup time is incurred when machines are configured to process a new batch of part types. They develop a two-stage heuristic procedure which provides near-optimal solutions in their computational studies. However, they limit their search to permutation schedules. Most of these early part input sequence studies of FFSs are constrained by requiring that the periodic (weekly, for example) production requirements need to be translated into operating production ratios, or production targets to aim for (see Afentakis [1986a, 1986b], Akella et al. [1985], Erschler et al. [1982, 1985], Hitz [1979, 1980], Pinedo et al. [1986], and Wittrock [1985]). This type of situation is similar to manufacturing in a dependent demand situation, such as MRP, where the requirements for some part types are proportional to the requirements of others. In these systems, the operating production ratios are defined externally. This may also be appropriate if the same mix is required each period. All part types may be required at the same time (perhaps for assembly). This is called a batching approach to scheduling part types over time (see Stecke and Kim [1988] and Amoako-Gyampah [1994]). More flexibility (and hence more operating options and resultant benefits) can be available in an independent demand situation, where the production requirements of each part type are unrelated to one another. Hence, the operating production ratios can be chosen by the FMS -15 -

operator. However, ratios do not have to be proportional to the requirements, but may be selected to help attain a good system utilization, for example. Due dates (daily or weekly, say) and requirements should still be considered. Some investigations of the implementation of such a more flexible approach to FMS operation and its benefits have been performed (see Agnetis et al. [1990, 1991], Stecke [1992b], Schriber and Stecke [1987, 1988], Amoako-Gyampah [1994], Stecke and Toczylowski [1991], and Stecke and Kim [1989, 1991, 1992]). Further studies of additional uses and benefits of the suggested flexible approach should be done. For example, these ratios can easily be used to determine a good part input sequence (Stecke [1992b]). This has been done in an FFS study, but needs further examination (see Stecke and Kim [1991] and Smith and Stecke [1992]). 4. Scheduling In Dedicated Flexible Machining Systems A survey by Jaikumar [1984] indicates that most early FMSs manufactured very few part types, ranging from four to twenty-two. These are essentially dedicated machining systems. DFMSs can be configured to produce a few part types in large volumes. The flow of materials need not be unidirectional. Erschler, Leveque, and Roubellat [1982] extend the work of Hitz. They develop a heuristic to find a periodic part input sequence from the MPS for a DFMS. The aim is to keep the bottleneck machine busy. They also assume that the production ratios (MPS), are specified in advance and that only one route is available for each part. They also assume that each machine has an unlimited buffer. An approach is provided that finds an upper bound on the duration of the transient period that occurs, before steady state production is attained. A heuristic is developed to determine input sequences into DFMSs, which are not periodic. For this heuristic, it is assumed that every part visits the bottleneck machine. Computational results are not provided. In a subsequent study, Erschler, Roubellat, and Thuriot [1985] provide a useful extension that considers the limited availability of pallets of each type. In addition to determining a periodic part input sequence (under steady state conditions), a schedule is determined for each machine. The scenario is a job shop. Each part type has only one route. As in previous studies, it is assumed that weekly production rate requirements are specified and that these translate into operating production ratios (MPS).- The pallet limitations are used to determine the maximum flow time for each part type. These part flow times and a fixed production period provide constraints. The production period is specified to consider either the bottleneck machine or the "bottleneck" pallet type, whichever is more critical. The solution method is based on resolving conflicts between operations on a single machine at a time, by modifying early start and late finish times. These modifications in turn affect other operation times, because of part type -16 -

routes, steady state periodicity, and part flow time constraints. The procedure is iterative. Steady state schedule feasibility conditions are provided. Further extensions to this work will allow alternative routes for each part type as well as machine grouping. Afentakis [1986a, 1986b] schedules part types in an FMS that feeds into an assembly system. These studies also assume that the part types are to be produced in specific ratios that are proportional to the production requirements. The objective is to maximize the production rate. The FMS is a DFMS with predetermined part routing. Each machine will perform the same operation on each part at periodic intervals. Then the maximum production rate is limited by the bottleneck machine. It can easily be seen that in the absence of buffer limitations, any repetitive sequence of the operations of the MPS assigned to a machine yields the maximum production rate. Thus the scheduling problem in this context is almost trivial. He suggests a heuristic algorithm to input parts in a sequence to balance workloads, which considers layout and material handling aspects. Tool magazine capacity is not considered. Afentakis also shows how the problem of minimizing in-process inventories can be reduced to makespan problems in a job shop. Further, he suggests how to use operation sequencing flexibility to reduce both material handling requirements and in-process inventories. Some practical limitations of this study are that the machines are assumed to have large buffers. Also, the material handling devices are assumed to be capable of choosing part types from the buffers in an arbitrary sequence. Further, pallets and fixtures are not treated as constraints. The cycle time in the downstream assembly process is implicitly assumed to be less than the cycle time of the bottleneck machine in the FMS. A common underlying theme in the above-mentioned studies of dedicated flexible machining systems is the focus on the bottleneck machine. Further, emphasis is on flexibility — i.e., achieving the desired output subject to considerations such as buffer limitations and material handling limitations. Scheduling is of less relevance here. We elaborate on this aspect in the conclusions. Some FMS scheduling studies address both input sequencing and scheduling problems. Nof et al. [1979] note two types of part input sequence problems: to determine an initial sequence (inputting parts into an empty FMS, such as after preventive maintenance or in between consecutive batches) and to determine a general input sequence (adding parts to an operating system). In this study, there are fifteen part types having periodic production requirements that are always produced. The machining system consists of three pairs of identical machining centers connected by a loop conveyer. Fixture availability limitations are not mentioned. The study captures many of the complexities involved in scheduling FMSs operating on a 'made-to-order' basis. Some priority rules that are tested for scheduling are FCFS, SPT, LPT, and PR/TR (assign the highest priority to the part whose proportion of required output is lagging -17 -

behind most). Machine utilization and production rate are used as the criteria for evaluating which combinations of part input and scheduling procedures perform best. Their significant conclusions are that: 1) having alternate processes for part types and dynamic process selection can increase productivity: 2) the performance of scheduling rules depends on which part input sequences are jointly used with them. Stecke [1977] and Stecke and Solberg [1981] consider similar FMS loading and scheduling issues. Their simulation study models an existing 9-machine plus inspection station Sundstrand/Caterpillar FMS in Peoria, Illinois. Pallet limitations (16 maximum) and fixture limitations for each of the six fixture types are considered. Loading tools and scheduling parts are performed. Tool magazine capacities and tool overlap are accounted for. Breakdowns are not considered. Five tool loading rules are developed. The authors suggest using material handling volume, workload balancing, and routing flexibility as possible criteria for loading tool magazines. Sixteen scheduling rules are proposed for comparison purposes. One of the criteria used for judging the performance of the loading and scheduling rules is the number of completed parts. They found that SPT/TOT (assign the highest priority to the part with the lowest ratio of processing time of the next operation to the total processing time for the part) performed best for the Sundstrand/Caterpillar system. However, they caution that, "which combination might be best is highly system dependent. Each system deserves an individual study of various loading and real-time control strategies, via a detailed simulation, say, in order to choose the best methods." It is evident from the above studies in this section that primarily two alternative approaches are used for scheduling parts in dedicated systems. One approach is to determine the best input sequence to either achieve the required output or to maximize output. The output is required in specified ratios. This is primarily the approach used by Hitz, Afentakis, and Erschler et al. This approach circumvents the complex scheduling problem by addressing a more manageable situation —input control. An alternative approach is one adopted by Nof et al. [1979] and Stecke and Solberg [1981] that views the system as dynamic and continuously changes the input and the sequences of parts at the machines. When the system is operating under steady state conditions, the former approach can be useful, since the methodology totally eliminates the need to address any complex sequencing (or scheduling) issues and meets the production requirements. However, when the system is in a transient state because of contingencies such as machine breakdowns or part type changes, the latter approach is useful. However, we caution that their conclusions have not been subjected to statistical significance tests. This may partly explain one of their conclusions, that the choice of appropriate rules is situation specific. -18 -

5. Scheduling In Nondedicated FMSs It is well known that scheduling in job shops is complex. FMS scheduling can be even more so because of the additional options and lack of large batches. NFMSs are similar to job shops in the following sense: part types are produced as per customer specifications. The customer can be either an internal customer (such as an order released from the MRP system) or an external customer. Each part type or order may have a due date associated with it. Due dates can be specified either by the customer or negotiated between the customer and the vendor. A recent industry survey by Smith, Dudek, Ramesh, and Blair [1986] show that due date related criteria are very important in operating FMSs. In this section, we review various approaches to FMS scheduling when the system is driven by the customer orders. Many FMS planning and scheduling procedures are hierarchical. Ideally, it would be desirable to make all operational decisions simultaneously so that the best possible schedule can be found. Because of the computational intractability, hierarchical or sequential approaches are sometimes used to solve operational control problems. Hax and Meal [1975] cite additional benefits to hierarchical approaches, such as management involvement and ease of coordination. Dempster et al. [1981] provide analytical foundations for hierarchical planning. In a similar fashion, operational control problems in GFMSs can be structured and solved in a hierarchical framework (see Stecke [1983, 1985a, 1986, 1992a]). Mazzola, Neebe, and Dunn [1988] suggest a hierarchical framework for operating FMSs when demands placed on the system are generated by an MRP environment. Tool loading, part input sequencing, and routing decisions are made prior to the actual scheduling of individual parts. Such a sequential approach sacrifices some processing flexibility to make the decision-making tractable. Research has not yet addressed the magnitude of the deterioration in system performance resulting from the use of such sequential procedures. Dar-El and Sarin's [1984] approach to FMS scheduling partially considers alternate routings and part type due dates. Due date information is used only for releasing the parts into the system, but not for scheduling. Scheduling is done using the work in the next queue (WINQ) dispatching rule. WINQ is a rule which uses information about the status of other machines. Operation times are randomly generated. The simulation models three pairs of identical machines, just as the study by Nof et al. [1979]. Breakdowns are not considered, nor are pallet and fixture limitations. The objective used to evaluate performance in the simulation study is machine utilization. Routing flexibility is used only when selecting a set of part types for simultaneous processing. Only one particular fixed route is selected in advance of input into the system and used by all parts of a particular part type. Since each operation may have several different processing times in advance of input, it is not clear why machine utilization is used as the criterion. Further, the only scheduling rule -19 -

tested in the simulation of the hypothetical FMS is WINQ. No comparison with alternate procedures are made. A more interesting area for future research would be to extend the concepts here to allow alternative routes for different parts of the same part type in the system. This is where the routing flexibility is useful. The simulation studies of Stecke [1977], Nof et al. [1979], and Stecke and Solberg [1981] use this flexibility. Chang, Sullivan, Bagchi, and Wilson [1985] suggest a two-step procedure for scheduling parts. Tool loading decisions and tool magazine capacities are not specifically addressed, nor are breakdowns and due dates. In the first step of the proposed scheduling algorithm, several feasible schedules are generated for each part type subject to prior machine assignments. The aim is to generate enough feasible part type schedules so that "optimal" or near optimal schedules are hopefully included in the generated set. In the second step, a binary integer programming algorithm is used to choose complete detailed schedules to minimize mean completion time. In both steps, specialized algorithms are used to reduce the computational burden. They test their procedure on a model consisting of 4 machines (two are identical), 3 part types, and 20 pallets. Using simulation, they report that the two-step method performs better than the dispatching rules (SPT, LPT, FCFS, MWKR, and LWKR) for the mean flowtime criterion. It is observed that changing the batch sizes of part types does not change the relative performance of the various scheduling rules tested. This is obvious since there is no set-up time between consecutive mixes of part types. One limitation of the procedure is the likely high computational time required to use it in practice on a real time basis. The computational burden of the algorithm used in the second step increases exponentially with the number of parts. As system utilization increases, arrival rate increases. This has the effect of frequent runs of the algorithms and also increases computation time. A second aspect which needs further investigation is to validate the conclusions in a more general and realistic situation. However, Chang et al.'s [1985] approach differs from earlier studies in using an efficient (although problem-specific) optimization procedure for scheduling. Further, the computational experiment is well defined and statistically well examined. Ishii and Talavage [1994] extended earlier scheduling studies by allowing a choice among several dispatching rules at each machine. Simulation was used to evaluate FMS performance. Lin and Lu [1984] investigate the effect of various part input and scheduling rules on system performance. Tool magazine capacities appear to be considered. Tool overlap is not considered. They suggest two heuristic part input methods. One is workload balancing only and the other is workload balancing while considering the potential tardiness of the parts. In addition to the two heuristic rules, EDD and FIFO are also used to input parts in the simulation -20 -

study. Alternative routes for each part type are considered only in advance of input into the system. Highest priority is given to the longest route, presumably for workload balance considerations. They assume that a set of parts is released every eight hour shift. The hypothetical system consists of four machines. After the route is selected for each part type, each route is fixed during each simulation. Having input the parts, the performance of the WINQ, SPT, and FIFO rules are compared. Four criteria are used: mean flowtime, mean waiting time, ratio of maximum to minimum average queue length, and machine utilization variance. However, the first two criteria are equivalent here. The latter two are surrogates for workload balance. One scenario is examined. The unknown system utilization level does not change. Due date setting procedures are not indicated. No due date related criteria are used. For any of the four input rules, WINQ achieves a better mean flowtime than SPT and FIFO. However, for workload balance criteria, choosing a specific combination of a dispatching rule and an input rule yields better results. The results reported here are different from earlier results on the performance of WINQ in the conventional job shop literature. For example, Conway et al. [1967] report that despite the global nature of WINQ, SPT provides smaller queue lengths. In another study of FMSs operating in a made-to-order mode, Shanker and Tzen [1985] input and schedule parts according to due dates. They describe two heuristic input algorithms. The first balances the workload. The second considers due dates while using the first to balance workloads. Parts are classified into four classes depending on their due dates in comparison to the scheduling horizon. Then, inputting rules are similar to those described by Lin and Lu [1984] except for minor improvements through pairwise interchange among selected and unselected parts. A simulation of a hypothetical system is used to compare the input heuristic of balancing workloads with the sequential input rule, FCFS. The system consists of four machines. The study is carried out for one level of utilization. Four dispatching rules are tested: FIFO, SPT, LPT, and most operations remaining (MOPR). The performance criteria are workload unbalance and machine utilization. They conclude that their heuristic input method of workload balancing performs better than FCFS. However, they note that because of the limited simulation run length (80 hours), it is difficult to draw conclusions about the four dispatching rules. Due dates are set as a multiple of total processing time and used in an integer programming formulation. The authors comment that the formulation is impractical due to prohibitive computer time. However, it is not clear why due dates are set when this information is never used in the simulation, neither for inputting nor dispatching. Also, the criteria used in the simulation are not due date related. It is difficult to conclude anything about the two heuristic -21 -

input algorithms since one of them is never tested in the simulation and the other is compared only to a random input procedure (FCFS). The following study focuses on due date related criteria. Raman et al. [1989] model,threemachine and one cart FMS test bed at the National Bureau of Standards and develop procedures to schedule ten part types having due dates. The effects of batching on the system performance are also studied. Batching is required for this system because of the configuration of the cassettes in which part types are held for input to a certain machine. A myopic rule developed by Morton and Rachamadugu [1982] performs well. A dynamic implementation of a branch and bound procedure is developed that yields good results. Results of these procedures appear to be better than competing heuristics such as Montagne's rule, EDD, MDD, FCFS, and others. This study considers finite, although small, times required to set-up the machines between operations. The results and claims of better performance have been statistically validated. Slomp et al. [1988] provide a scheduling procedure that is better than some earlier studies because it explicitly addresses issues specific to FMSs —buffer handling and integrating transportation with machining. One scheduling rule considers alternative machines for operations. Each operation is assigned to the machine on which the operation finishes earliest (EFTA rule). This rule was proposed by Iwata et al. [1980]. Slomp et al. conduct simulation studies to compare this rule with the three other rules SPT, SPT*TOT, and SPT/TOT. They conclude that SPT/TOT performs best when compared to the other rules, supporting an earlier similar conclusion by Stecke [1977] and Stecke and Solberg [1981]. However, there are noteworthy differences between these two studies. The system of Stecke and Solberg is a dedicated system and the criterion is to maximize the production rate of the assembled units. The criterion of Slomp et al. is to maximize the makespan per part (although it is not clear what this criterion represents). It is also not clear that the superiority of the SPT/TOT rule can be sustained when subjected to classical hypothesis testing. Further, in the study by Slomp et al., EFTA performs well for both makespan per part and mean flowtime criteria. This supports conclusions of earlier investigators such as Wayson [1965], Neiemeier [1967], and Stecke [1988] that exploiting flexibility in routing and sequencing may make scheduling decisions relatively less critical to performance in job shop and FMS environments. Blazewicz et al. [1991] examine the scheduling problems in an FMS manufacturing helicopter parts. This is one of the few studies which addresses the simultaneous scheduling of machines and automated guided vehicles. They use dynamic programming to construct a pseudopolynomial time algorithm (in the number of machines, which are few in many FMSs) for finding an optimal schedule to minimize makespan. This study is illustrative of how mathematical programming techniques can be used to develop useful procedures for FMS scheduling. -22 -

Sabuncuoglu and Hommertzheim [1993] study the problem of scheduling machines and AGVs using dispatching rules. They use due date related criteria. The simulation studies show that the modified operation due date rule performs better than competing rules for tight due dates. Also, scheduling AGVs using the largest queue size as the priority for assignment yields better results than an FCFS policy. This study shows that the superior performance of the modified operation due date rule, which performs well in job shops, appears to carry over to FMSs as well. It is evident from the above studies that most procedures developed for Nondedicated Flexible Machining Systems mimic job shop scheduling methodologies. This is not necessarily inappropriate, if the system has to handle many part types in small volumes during some production period. The demands placed on the system may not be very different from the demands on a conventional job shop. However, the technological differences between the systems should be fully exploited in developing scheduling methodologies for NFMSs in order to obtain the advantages from the flexibility and the automation. For example, most of the research to date has not adequately addressed the benefits that can be obtained by using routing flexibility. Browne et al. [1984] distinguish between potential and actual routing flexibility. Potential routing flexibilit allows the ability to reroute, reload, and revise the system, in case of a machine breakdown, for example. This is usually a function of the system design. Under normal circumstances, the route for each part is fixed. Dar-El and Sarin [1984], Lin and Lu [1984], and Wittrock [1985] allow potential routing flexibility. These studies use routing flexibility to consider various potential routes at the tool loading stage. During operation, however, each part type has only one route through the system. Actual routing flexibility uses the flexibility during operation. This can be achieved by duplicating operation assignments or pooling machines. Then during real time, parts of the same part type can visit different machines. Advantages occur during down periods, because tools need not be moved around and reloaded. Advantages are also attained during system operation, as system performance increases. Stecke [1977, 1988], Nof et al. [1979], and Stecke and Solberg [1981, 1985], use actual routing flexibility to allow alternative routes for parts of the same type during real time. Lin and Solberg [1991] study the effects of flexibility on system performance. They conduct a simulation study which incorporates process, routing, and sequencing flexibilities. They note that flexibility permits workload balancing and that using the flexibility for routing and scheduling improves all regular measures of performance. Rachamadugu et al. [1993] isolate the effects of having sequencing flexibility and its impact on regular measures of performance. A measure for sequencing flexibility is defined. Their evaluative studies show that utilizing sequencing flexibility even to a small extent can -23 -

improve system performance. Since sequencing flexibility may be independent of hardware configuration, their conclusions are valid for both FMSs and job shops. Abdin [1986] conducts a simulation study, which highlights the benefits of the routing flexibility that can be available in FMSs. His study shows that when parts are allowed to choose between alternate machines, significant improvement occurs for all regular measures of performance. Also, work-in-process inventory reduces. 6. Conclusions and Future Research Recommendations Most FMSs do not handle very many part types. Scheduling in these flexible, but dedicated, systems has received less attention than they merit. There have been more studies of GFMSs that produce in small or unit batch sizes. However, flexibility also has many benefits in high-volume manufacturing, such as in the automotive industry, where there are changeovers, design changes, and model changes, for example. Flexibility to reduce these changeover times, as well as having the ability to changeover easily is useful, even for the high volume components. Circuit board fabrication and assembly are high volume, yet high variety operations. These applications merit further investigation (i.e., see Wittrock [1992]). For FMSs operating on a made-to-order basis, an operational control system usually has to consider due dates. However, most FMS scheduling research to date concentrates on criteria related to machine utilization and the avoidance of bottlenecks. At best, due date information has sometimes been used to determine which parts should be input next. Based on an FMS industrial survey, Smith et al. [1986] conclude that, "research should be directed towards developing scheduling procedures, with the primary objective of meeting due dates while considering criteria like maximizing machine and system utilization and minimizing in-process inventories as secondary objectives." Another development that will impact made-to-order types of FMSs is the increasing industrial implementation of just-in-time manufacturing systems. In some instances, this is a motivating factor for adopting FMS technology (Winter [1986]). In such an environment, minimization of weighted earliness is a relevant criterion for scheduling production. Weighted earliness is a surrogate for the inventory costs incurred by the manufacturer or vendor for fabricating a part type early. Even in single machine situations, this is an NP-hard problem (Chand and Schneeberger [1985]). In more complex situations, there are no easy procedures to verify the existence of a feasible solution, let alone finding an optimal solution. Recently, Kubiak and Sethi [1994] address the issue of how to find optimal just-in-time schedules for flexible transfer lines. Another FMS feature that requires consideration in scheduling is the limited buffer space. Although some simulation and queueing network studies have taken this aspect into con -24 -

sideration, it has been neglected in the development of scheduling procedures. For example, it is not clear how the relative ranking of various scheduling rules will change as the buffer storage space is tightened. Consideration of finite buffers is important because of the integration required of the systems and the consequences of the potential blocking and starving. There are many advantages arising from utilizing processing, routing, and other flexibilities (see Browne et al. [1984]). The same operation can be performed by several (types of) machine tools. Some researchers have exploited this flexibility at the tool loading stage. See Gray et al. [1993]. Although sequential decision-making, such as tool loading prior to scheduling, may be elegant and makes a complex problem more tractable, it is not clear how much has been sacrificed. Further, recent advances in technology such as automated tool delivery and tool loading may tend to reduce the tool magazine capacity limitations, and thus sometimes reduce the need for making loading decisions in advance of scheduling decisions. These loading decisions might now become part of the scheduling decisions, which in turn then become more complex. In view of these developments, it would be worthwhile to explore how system performance can be improved if loading and scheduling decisions are made simultaneously. Another type of flexibility, which is inherent in the part type rather than the processing system, is operation flexibility. For example, sometimes a hole may be drilled in a metal casting before one face is milled or vice versa. This flexibility can be advantageously used in manufacturing systems. Such flexibility in sequencing operations, if properly exploited, may have beneficial effects on various measures of system performance, by relieving bottlenecks or avoiding down machine tools, for example. See Lin and Solberg [1991] and Rachamadugu et al. [1993]. The organizational control issues and the early generation information technology used in job shops largely precluded exploiting routing and sequencing flexibilities. Consider a conventional shop without centralized computer control, which then has no real-time updating of machine and part/order status. If batches of part types are released into such a system with all routing and sequencing alternatives listed on the routing sheets, with these decisions to be made by each individual operator or machine center, chaos is likely to prevail. With the costs of information technology decreasing rapidly, real-time use of information in conventional job shops may perhaps lead to partial exploitation of routing and sequencing flexibilities. However, the large set up times for each operation would still necessitate following a fixed route for each part of a particular type. These flexibilities would tend not to be used. Early studies by Neimeier [1967] and Wayson [1965] point to the utility of exploiting sequencing and routing flexibility. For a summary of these studies, see Conway, Maxwell, and Miller [1967]. Their primary conclusions are that the relative superiority of sophisticated scheduling rules over naive -25 -

rules such as FCFS decreases substantially even with a little use.of routing and/or sequencing flexibility. Also, a simulation study by Wilhelm and Shin [1985] demonstrates that dynamically exploiting operation flexibility improves the system utilization. Yet another FMS characteristic is the transportation resources and time involved in moving parts from one machine to another. In conventional job shops, material handling is generally nonautomated, and the amount of time spent waiting is considerably larger than the processing and transportation times. In such cases, transportation times do not significantly affect scheduling decisions. There are queues at the bottleneck machines, which are usually not waiting for work to arrive. However, in FMSs where material handling is automated, transportation resources are limited, and transportation times can be comparable to the processing times (particularly in flexible assembly systems). Scheduling of material handling devices can influence the overall system performance. From the literature, it is not clear that these aspects have been sufficiently considered in developing FMS scheduling procedures. Afentakis [1986b] provides procedures for special dedicated flow systems. Sometimes travel time is considered in simulation-based investigations, but not as a scheduling parameter. In spite of the development of tools such as closed queueing networks, mean value analysis, and mathematical programming techniques, which can help in designing the system, at the operational level, the best operational control policies need to be chosen and validated by well designed simulation experiments. Schriber and Stecke [1987, 1988] show that the system output and utilization may be less by as much as 29% from the predictions made by very aggregate assumptions. As the level of aggregation decreases and additional system detail is included, performance results become more accurate. However, qualitative comparisons using such aggregate models are quite accurate. Also, the performance predicted by the aggregate models can be obtained by suitably setting buffer and transportation levels. Appropriate scheduling procedures should be evaluated by simulation experiments and validated by statistical significance tests. Some researchers are investigating procedures for FMS scheduling and operational control using artificial intelligence and expert systems (see Ben-Arich [1986], Meszaros and Szelke [1990], Shaw [1986], Shaw and Whinston [1988, 1989], Shen and Chang [1986, 1988], Young and Rossi [1988], and Thesen and Lei [1986], for example). Many FMSs operating in U.S., Europe, and Japan use a human supervisor for planning and control decisions (FMS/IMS, 1983). Young and Rossi [1988] note that most control decisions are still 'man-in-the-loop' activities. They suggest that this is largely due to the difficulty in predicting the short term behavior of the system. Although some of these approaches may prove to be useful, there is no conclusive evidence to date that indicates whether they might be suited for FMS operation, particularly in real-time applications. Young and Rossi [1988] appropriately point out that before AI -26 -

techniques can be successfully used, the question to be answered for FMS control is "whether or not the control system would be sufficiently fast to execute in near real time. The answer awaits empirical results." Most recent prototypes appear to be too slow to meet the demands of realtime operational requirements. However, new performance results appear to be becoming more competitive. For example, Ow and Smith [1987] compare their expert system for scheduling with a conventional dispatching approach, the COVERT rule. Although the prototype runs too slow, it performs better than COVERT. However, the study needs to be validated by a statistical verification of the results. Also, the expert system needs to be compared with other currently available scheduling procedures in addition to other dispatching rules. In general with these approaches, the number of rules to scan in the knowledge base might become very large. One potential use is in the development of knowledge bases to appropriately represent research done in FMS planning or operational control. This would be useful to practitioners in choosing appropriate planning and scheduling procedures. Other potential uses could be in developing rules to help determine how to react under machine breakdown situations. These uses of artificial intelligence techniques to aid FMS scheduling and control are currently being researched. Matsuo et al. [1988] have used simulated annealing techniques for scheduling parts in job shops. Their experiments show that better results than existing heuristic procedures can be obtained although computational times are higher. These methods should be further investigated for FMS applications. We have outlined many FMS features that need to be taken into consideration in developing effective scheduling procedures. Current technological capabilities can be utilized more productively with the development of appropriate scheduling procedures. 7. Acknowledgments We wish to thank Professors Tom Morton and Lee Schwartz for their detailed and constructive comments on an earlier version of this paper. We also acknowledge a grant from the Graduate School of Business Administration of The University of Michigan which helped to support this research. -27 -

REFERENCES ABDIN, M.F. 1986, Solution of Scheduling Problems of Job-Shop Type FMS With Alternative Machine Tools. Computers and Industrial Engineering, 11, 241-245. AFENTAKIS, P. 1986a, Maximum Throughput in Flexible Manufacturing Systems. Proceedings of the Second ORSAITIMS Conference on Flexible Manufacturing Systems: Operations Research Models and Applications, eds. K. E. Stecke and R. Suri (Elsevier Science Publishers B.V., Amsterdam), 509-52. AFENTAKIS. P. 1986b, Operational Control Problems in Flexible Manufacturing Systems. WP #85-012, Department of Industrial Engineering and Operations Research, Syracuse University (Syracuse, New York). AGNETIS, A., ARBIB, C. and STECKE, K.E. 1990, Optimal Two-Machine Scheduling in a Flexible Flow System. Proceedings of the Second International Conference on Computer Integrated Manufacturing, Rensselaer Polytechnic Institute (Troy, NY). AGNETIS, A., ARBIB, C. and STECKE, K.E. 1991, Part Type Selection and Batch Sequencing in a Flexible Flow System. Working Paper #670, The University of Michigan (Ann Arbor, Michigan). AKELLA, R., MAIMON, 0. and GERSHWIN, S.B. 1990, Value Function Approximation Via Linear Programming for Flexible Manufacturing System Scheduling. International Journal of Production Research, 28(8), 1459-1470. AKELLA, R., CHOONG, Y. and GERSHWIN, S. B. 1985, Real-Time Production Scheduling of an Automated Cardline. Annals of Operations Research, 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, 6(3), forthcoming. ANONYMOUS 1982, Big System at John Deere Solves New Product Problems. FMS Magazine, 16-19. ANONYMOUS 1985, IBM's Automated Factory —A Giant Step Forward. Modern Material Handling, 274-281. BEN-ARICH, D. 1986, Knowledge Based Control System for Automated Production and Assembly. In Modeling and Design of Flexible Manufacturing Systems (Elsevier Science Publishers B.V., Amsterdam), 347-365. BERRADA, M. and STECKE, K. E. 1986, A Branch and Bound Approach for Machine Load Balancing in Flexible Manufacturing Systems. Management Science, 32(10), 1316-1335. -28 -

BLAZEWICZ, J., EISELT, H.A., FINKE, G., LAPORTE, G. and WEGLARZ, J. 1991, Scheduling Tasks and Vehicles in a Flexible Manufacturing System. International Journal of Flexible Manufacturing Systems, 4(1), 5-16. BLAZEWICZ, J., DROR, M., PAWLAK, G. and STECKE, K. E. 1992, Scheduling Parts Through a Two-stage Tandem Flexible Flow Shop. Working Paper No. 699, The University of Michigan (Ann Arbor, Michigan). BROWNE, J., DUBOIS, D., RATHMILL, K., SETHI, S. P. and STECKE, K. E. 1984, Classification of Flexible Manufacturing Systems. FMS Magazine, 2(2), 114-117. BRUNO, G., ELIA, A. and LAFACE, P. 1986, A Rule-based System to Schedule Production. Computer, 19, 32-40. BUZACOTr, J. A. and SHANTHIKUMAR, J. G. 1980, Models for Understanding Flexible Manufacturing Systems. AIIE Transactions, 12, 339-350. CARTER, C. F. JR. 1971, Trends in Machine Tool Development and Application. Proceedings of the Second International Conference on Product Development and Manufacturing Technology, University of Strathclyde (United Kingdom), 125-141. CHAN, D.-Y. and BEDWORTH, D.D. 1990, Design of a Scheduling System for Manufacturing Cells. International Journal of Production Research, 28(11), 2037-2050. CHANG, Y.-L., MATSUO, H. and SULLIVAN, R.S. 1989, A Bottleneck Based Beam Search for Job Scheduling in a Flexible Manufacturing System. International Journal of Production Research. 27(11), 1949- 1962. CHANG, Y.-L., SULLIVAN, R. S., BAGCHm, U. and WILSON, J. R. 1985, Experimental Investigation of Real-Time Scheduling in Flexible Manufacturing Systems. Annals of Operations Research, 3, 355-378. CHRYSSOLOURIS, G., DICKE, K. and LEE, M. 1994, An Approach to Real-Time Flexible Scheduling. International Journal of Flexible Manufacturing Systems, 6(3), forthcoming. CONWAY, R. W., MAXWELL, W. L. and MILLER, L. W. 1967, Theory of Scheduling (AddisonWesley, Reading, Massachusetts). CRUZ, J. B. JR., SOERHEIM, E. A. and MULLIGAN, J. H. JR. 1991, An Extension of the Tardiness Heuristic Feedback Algorithm for Scheduling. Journal of Manufacturing Systems, 10(2), 158-165. DAR-EL, E. M. and SARIN, S. C. 1984, Scheduling Parts in FMS to Achieve Maximum Machine Utilization. Proceedings of the First ORSAITIMS Conference on Flexible Manufacturing Systems, eds. K. E. Stecke and R. Suri, The University of Michigan (Ann Arbor, Michigan), 300-306. -29 -

DAS. S.D. and KHUMAWALA, B.M. 1991, An Efficient Heuristic for Scheduling Batches of Parts in a Flexible Flow System. International Journal of Flexible Manufacturing Systems, 3(2), 121-148. DEANE, R. H. and MOON, S. H. 1992, Work Flow Control in the Flexible Flow Line. International Journal of Flexible Manufacturing Systems, 4(3/4), 217-236. DEMPSTER, M. A. H., FISHER, M. L., JANSEN, L., LAGEWEG, B. J., LENSTRA, J. K. and RINNOOY KAN, A. H. G. 1981, Analytic Evaluation of Hierarchical Planning Systems. Operations Research, 29(4), 707-716. DONATH, M. and GROVES, R.J. 1989, Flexible Assembly Systems: Test Results for an Approach for Near Real Time Scheduling and Routing of Multiple Products. International Journal of Production Research, 2, 215-228. DUGGAN, J. and BROWNE, J. 1991, Production Activity Control: A Practical Approach to Scheduling. International Journal of Flexible Manufacturing Systems, 4(1), 79-104. DUTTA, A. 1990, Reacting to Scheduling Exceptions in FMS Environments. IIE Transactions, 22(4), 300-314. EAVES, B.C. and ROTHBLUM, U.G. 1988, A Discrete Time Average Cost Flexible Manufacturing and Operator Scheduling Model Solved by Deconvexification Over Time. Operations Research, 36(2), 242-257. EMMONS, H. 1975, One Machine Sequencing to Minimize Mean Flow Time with Minimum Number Tardy. Naval Research Logistics Quarterly, 22(3), 585-592. ERSCHLER, J., LEVEQUE, D. and ROUBELLAT, F. 1982, Periodic Loading of Flexible Manufacturing Systems. Proceedings of the IFIP Congress, APMS (Bordeaux, France), 327 -339. ERSCHLER, J., ROUBELLAT, F. and THURIOT, C. 1985, Steady State Scheduling of a Flexible Manufacturing System with Periodic Releasing and Flow Time Constraints. Annals of Operations Research, 3, 333-353. "FMS/IMS State-of-the-Art Review" 1983, Appendix E, Manufacturing Technology for Advanced Machining Systems, AFWAL-TR-83-4116, USAF Materials Laboratory, WrightPatterson Air Force Base (Ohio). FRENZEL, B. and SCHMIDT, G. 1987, IFPS: an Approach to Intelligent Production Scheduling and Control of Flexible Manufacturing Systems. Angewandte Informatik, 29(11), 458-464. GERSHWIN, S.B. and MAIMON, O.Z. 1988, Expert System Facilitates Scheduling of General Dynamics' Fort Worth FMS. American Machinist and Automated Manufacturing, 132, 25. GHOSH, S. and GAIMON, C. 1992, Routing Flexibility and Production Scheduling in a Flexible Manufacturing System. European Journal of Operational Research, 60(3), 344-364. -30 -

GRAY, A. N., SEIDMANN, A. and STECKE, K.E. 1993, A Synthesis of Decision Models for Tool Management in Automated Manufacturing. Management Science, 39(5), 549-567. GROOVER, M. P. 1980, Automation, Production Systems and Computer-Aided Manufacturing (Prentice-Hall Inc., Englewood Cliffs, New Jersey). GUPTA, Y.P., EVANS, G.W. and GUPTA, M.C. 1991, A Review of Multi-criterion Approaches to FMS Scheduling Problems. International Journal of Production Economics, 22, 13-31. HALL, D. N. and STECKE, K. E. 1986, Design Problems of Flexible Assembly Systems. Proceedings of the Second ORSAITIMS Conference on Flexible Manufacturing Systems: Operations Research Models and Applications, eds. K. E. Stecke and R. Suri (Elsevier Science Publishers B.V., Amsterdam), 145-156. HAX, A. and MEAL, H. 1975, Hierarchical Integration of Production Planning and Scheduling. in TIMS Studies in Management Sciences, Vol. 1: Logistics, ed. M. Giesler (NorthHolland/Elsevier, New York). HITOMI, K., YOSHIMURA, M. and ONASHI, K. 1989, Design and Scheduling for Flexible Manufacturing Cells with Automatic Setup Equipment. International Journal of Production Research, 27(7), 1137-1148. Hrrz. K. L. 1979, Scheduling of Flexible Flow Shops I. LIDS Report No. 879, Massachusetts Institute of Technology (Cambridge, Massachusetts). Hrrz, K. L. 1980, Scheduling of Flexible Flowshops II. LIDS Report No. 1049, Massachusetts Institute of Technology (Cambridge, Massachusetts). HOPPE, V. and KOVALEV, M.M. 1990, On Some Problems in the Optimization of Sequencing of the Operative Control of FMS (Flexible Manufacturing Systems). Optimization: A Journal of Mathematical Programming and Operations Research, 21(1), 109-121. HUTCHISON, J. and KHUMAWALA, B. 1990, Scheduling Random Flexible Manufacturing Systems with Dynamic Environments. Journal of Operations Management, 9(3), 335-351. HUTCHISON, J., LEONG, K., SNYDER, D. and WARD, P. 1991, Scheduling Approaches for Random Job Shop Flexible Manufacturing Systems. International Journal of Production Research, 29(5), 1053-1068. ISHI, N. and TALAVAGE, J.J. 1991, A Transient Based Real Time Scheduling Algorithm in Flexible Manufacturing Systems. International Journal of Production Research. IsHu, N. and TALAVAGE, J.J. 1994, A Mixed Dispatching Rule Approach in FMS Scheduling. International Journal of Flexible Manufacturing Systems, 6(1), forthcoming. IWATA, K., MUROTSU, Y. and OBA, F. 1980, Solution of Large-scale Scheduling Problems for Job Shop Type Machining Systems with Alternative Machining Tools. Annals of the CIRP, 29, 335-338. -31 -

JAIKUMAR. R. 1984, Flexible Manufacturing Systems: a Managerial Perspective. Working Paper #1-784-078, Harvard Business School (Cambridge, Massachusetts). JAIKUMAR, R. 1986, Postindustrial Manufacturing. Harvard Business Review, 64(6), 69-76. JONES, C. H. 1973, An Economic Evaluation of Job Shop Dispatching Rules. Management Science, 20(3), 293-307. KINNUCAN, P. 1983, Flexible Systems Invade the Factory. High Technology, 33-42. KOREN, Y. 1983, Computer Control ofManufacturing Systems (McGraw-Hill, New York). KUBIAK, W. and SETHI, S.P. 1994, Optimal Just-in-time Schedules for Flexible Transfer Lines. International Journal of Flexible Manufacturing Systems, 6(2), forthcoming. LEE, H.F., SRINIVASAN, M.M. and YANO, C.A. 1991, Design and Scheduling of Flexible Assembly Systems for Large Products: A Simulation Study. Journal of Manufacturing Systems, 10(1), 54-66. LIN, L. S. and Lu, C. Y. J. 1984, The Scheduling Problem in Random Flexible Manufacturing System. Proceedings of the First ORSAITIMS Conference on Flexible Manufacturing Systems, eds. K. E. Stecke and R. Surfn, The University of Michigan (Ann Arbor, Michigan), 278-283. LIN, Y.-J. and SOLBERG, J. J. 1991, Effectiveness of Flexible Routing Control. International Journal of Flexible Manufacturing Systems, 3(3/4), 189-212. LUCERTINI, M., NICOLO, F. and AGNETIS, A. 1993, Flow Management in Flexible Manufacturing Cells with Pipeline Operations. Management Science, 37, 491-496. MAIMON, O.Z. and GERSHWIN, S.B. 1988, Dynamic Scheduling and Routing for Flexible Manufacturing Systems that Have Unreliable Machines. Operations Research, 36(2), 279 -292. MATSUO. H., SUH, C. J. and SULLIVAN, R. S. 1988, A Controlled Search Simulated Annealing Method for the General Job Shop Scheduling Problem, Working Paper #03-04-88, Graduate School of Business, The University of Texas at Austin (Austin, Texas). MAZZOLA, J. B., NEEBE, A. W. and DUNN, C. V. R. 1988, Production Planning of a Flexible Manufacturing System in a Materials Requirement Planning Environment. International Journal of Flexible Manufacturing Systems, 1(2). MERCHANT, M. E. 1982, World Trends in Flexible Manufacturing Systems. The FMS Magazine, 1(1), 4-5. MESZAROS, I. and SZELE, E. 1990, Knowledge-based Adaptive Control of FMS Contributing to CIM. Computers in Industry, 14, 89-98. -32 -

MILLER, S. M. 1985, Industrial Robotics and Flexible Manufacturing Systems,' in The Management of Productivity and Technology in Manufacturing, ed. P. R. Kleindorfer (Plenun Press, New York), 17-40. MONTAZERI, M. and VAN WASSENHOVE, L.N. 1990, Analysis of Scheduling Rules for a Flexible Manufacturing System. International Journal of Production Research, 28(4), 785-802. MORTON, T. E. and RACHAMADUGU, R. V. 1982, Myopic Heuristics for the Single Machine Weighted Tardiness Problem. Technical Report CMU-RI-TR-83-9, Robotics Institute, Carnegie Mellon University (Pittsburgh, Pennsylvania). MORTON, T. E., LAWRENCE, S. R., RAJAGOPALAN, S. and KEKRE, S. 1986, MRPSTAR: PATRIARCH's Planning Module. Graduate School of Industrial Administration, Carnegie Mellon University (Pittsburgh, Pennsylvania). MUKHOPADHYAY, S.K., MAITI, B. and GARG, S. 1991, Heuristic Solution to the Scheduling Problems in Flexible Manufacturing Systems. International Journal of Production Research, 29(10), 2003-2024. NAKAMURA, N. and SALVENDY, G. 1988, An Experimental Study of Human Decision Making in Computer Based Scheduling of Flexible Manufacturing Systems. International Journal of Production Research, 26(4), 567-584. NEIMEIER. H. A. 1967, An Investigation of Alternate Routing in a Job Shop. Master's Thesis, Cornell University (Ithica, New York). NOF, S. Y., BARASH, M. M. and SOLBERG, J. J. 1979, Operational Control of Item Flow in Versatile Manufacturing Systems. International Journal of Production Research, 17(5), 479-489. O'KEEFE, R. M. and RAO, R. 1991, Part Input into a Flexible Flow System: An Evaluation of Look-Ahead Simulation and a Fuzzy Rule Base. International Journal of Flexible Manufacturing Systems, 4(2), 113-128. OPrrz. H. 1971, Planning Manufacturing Systems. Manufacturing Seminar, The University of Michigan (Ann Arbor, Michigan). Ow, P. and SMITH, S. F. 1987, Two Design Principles for Knowledge Based Systems. Decision Sciences, 18(3), 430-447. PANISHEV, A.V. and VARAKIN, A.S. 1992, Optimal Sequencing of Two-stage Jobs in Flexible Manufacturing Systems. Akademiya Nauk Ukrainy. Institut Kibemetiki. Kibernetika i Sistemnyi Analiz, 2, 85-93. PASQUIER, J. 1984, High-Level Simulation of Flexible Card Assembly Lines. Research Report RC-10881. IBM Thomas J. Watson Research Center (Yorktown Heights, New York). -33 -

PINEDO, M. L., B. WOLF and S. T. McCORMICK 1986, Sequencing in a Flexible Assembly Line with Blocking to Minimize Cycle Time. Proceedings of the Second ORSAITIMS Conference on Flexible Manufacturing Systems: Operations Research Models and Applications, eds. K. E. Stecke and R. Suri (Elsevier Science Publishers B.V., Amsterdam), 499-508. RACHAMADUGU, R., NANDKEOLYAR, U. and SCHRIBER, T. 1993, Scheduling with Sequencing Flexibility. Decision Sciences, 24(2), 315-342. RAMADGE, P.J. and CHASE, C. 1992, On Real-time Scheduling Policies for Flexible Manufacturing Systems. IEEE Transactions on Automatic Control, 37, 491-496. RAMAN, N., RACHAMADUGU, R. V. and TALBOT, F. B. 1989, Real-Time Scheduling of an Automated Manufacturing Center. European Journal of Operational Research, 40(2), 222 -242. RAMAN, N., TALBOT, F.B. and RACHAMADUGU, R.V. 1989, Due Date Based Scheduling in a General Flexible Manufacturing System. Journal of Operations Management, 8(2), 115 -132. RANKY, P. G. 1983, The Design and Operation of FMS - Flexible Manufacturing Systems, IFS (Publications) Ltd. (Bedford, United Kingdom). ROHAN, T. R. 1985, Getting It Together Flexibly —Assembly's Role in the Factory of the Future. Industry Week, 39-49. SABUNCUOGLU, I. and HOMMERTZHEIM, D.L. 1992a, Experimental Investigation of FMS Machine and AGV Scheduling Rules Against the Mean Flow Time Criterion. International Journal of Production Research, 30(7), 1617-1636. SABUNCUOGLU, I. and HOMMERTZHEIM, D.L. 1992b, Dynamic Dispatching Algorithm for Scheduling Machines and Automated Guided Vehicles in a Flexible Manufacturing System. International Journal of Production Research, 30(5), 1059-1080. SABUNCUOGLU, I. and HOMMERTZHENI, D.L. 1993, Experimental Investigation of an FMS DueDate Scheduling Problem: Evaluation of Machine and AGV Scheduling Rules. International Journal of Flexible Manufacturing Systems, 5(4), forthcoming. SAWIK, T. 1990, Modeling and Scheduling of a Flexible Manufacturing System. European Journal of Operational Research, 45(2-3), 177-190. SCHAFFER. G. H. 1981, Implementing CIM. American Machinist Special Report, 736. SCHRIBER, T. J. and STECKE, K. E. 1987, Using Mathematical Programming and Simulation to Study FMS Machine Utilizations. Proceedings of the 1987 Winter Simulation Conference, eds. A. Thesen, H. Grant, and W. D. Kelton, The Society for Computer Simulation (San Diego, California). -34 -

SCHRIBER, T. J. and STECKE, K. E. 1988, Machine Utilization Achieved Using Balanced FMS Production Ratios in a Simulated Setting. Annals of Operations Research, 15,229-267. SHALEV-OREN, S., SEIDMANN, A. and SCHWEITZER, P. J. 1985, Analysis of Flexible Manufacturing Systems with Priority Scheduling: PMVA. Annals of Operations Research, 3, 115-139. SHAW, M. J. 1988a, A Pattern-Directed Approach to FMS Scheduling. Annals of Operations Research, 15, 85-104. SHAW, M.J. 1988b, Knowledge Based Scheduling in Flexible Manufacturing Systems: an Integration of Pattern Directed Inference and Heuristic Search. International Journal of Production Research, 26(5), 821-844. SHAW, M.J. and WHINSTON, A.E. 1989, An Artificial Intelligence Approach to the Scheduling of Flexible Manufacturing Systems. lIE Transactions, 21(2),170-183. SHAW, M. J. and WHlNSTON, A. B. 1988, A Distributed Knowledge-based Approach to Flexible Automation: the Contract Net Framework. International Journal of Flexible Manufacturing Systems, 1(1), 85-104. SHEN, S. and CHANG, Y.-L. 1986, An Al Approach to Schedule Generation in a Flexible Manufacturing System. Proceedings of the Second ORSAITIMS Conference on Flexible Manufacturing Systems: Operations Research Models and Applications, eds. K. E. Stecke and R. Suri (Elsevier Science Publishers B.V., Amsterdam), 581-592. SHEN, S. and CHANG, Y.-L. 1988, Schedule Generation in a Flexible Manufacturing System: a Knowledge Based Approach. Decision Support Systems, 4(2),157-166. SLOMP, J., GAALMAN, G. J. C. and NAWIJN, W. M. 1988, Quasi On-line Scheduling Procedures for Flexible Manufacturing Systems. International Journal of Production Research, 26(4), 585-598. SMITH. M. L., RAMESH, R., DUDEK, R. A. and Blair, E. L. 1986, Characteristics of U.S. Flexible Manufacturing Systems - A Survey. Proceedings of the Second ORSAITIMS Conference on Flexible Manufacturing Systems: Operations Research Models and Applications, eds. K. E. Stecke and R. Suri (Elsevier Science Publishers B.V., Amsterdam), 477-486. SMITH, T. M. and STECKE, K.E. 1992, On the Robustness of Using Optimal Part Mix Ratios to Determine Cyclic Part Input Sequences into Flexible Flow Systems. Working Paper #658-b. The University of Michigan (Ann Arbor, Michigan). SOLOT, P. 1990, A Concept for Planning and Scheduling in a Flexible Manufacturing System. European Journal of Operational Research, 45(1), 85-95. SRISKANDARAJAH, C. and SETHI, S.P. 1989, Scheduling Algorithms for Flexible Flow Shops: Worst and Average Case Performance. European Journal of Operational Research, 43(2), 143-160. -35 -

SRISKANDARAJAH, C., SETI, S.P. and LADET, P. 1989, Scheduling Methods for a Class of Flexible Manufacturing Systems. Annals of Operations Research, 17, 139-161. STECKE, K. E. 1977, Experimental Investigation of a Computerized Manufacturing System. Master's Thesis, Purdue University, West Lafayette, Indiana. STECKE, K. E. 1983, Formulation and Solution of Nonlinear Integer Production Planning Problems for Flexible Manufacturing Systems. Management Science, 29(3), 273-287. STECKE, K. E. 1985a, Design, Planning, Scheduling, and Control Problems of Flexible Manufacturing Systems. Annals of Operations Research, 3, 3-12. STECKE, K. E. 1985b, Useful Models to Address FMS Operating Problems. Proceedings of the Advances in Production Management Systems Conference, Budapest, Hungary. STECKE. K. E. 1986, A Hierarchical Approach to Solving Machine Grouping and Loading Problems of Flexible Manufacturing Systems. European Journal of Operational Research, 24(3), 369-78. STECKE, K. E. 1989, Algorithms to Efficiently Plan and Operate a Particular FMS. International Journal of Flexible Manufacturing Systems, 1(4), 287-324. STECKE, K.E. 1992a, Planning and Scheduling Approaches to Operate a Particular Flexible Manufacturing System. European Journal of Operational Research, 61(3), 273-291. STECKE, K. E. 1992b, Procedures to Determine Part Mix Ratios for Independent Demands in Flexible Manufacturing Systems. IEEE Transactions on Engineering Management, 39(4), 359-369. STECKE, K. E. and KIM, I. 1988, A Study of FMS Part Type Selection Approaches for ShortTerm Production Planning. International Journal of Flexible Manufacturing Systems, 1(1), 7-29. STECKE, K. E. and KIM, I. 1989, Performance Evaluation for Systems of Pooled Machines of Unequal Sizes: Unbalancing versus Balancing. European Journal of Operational Research, 42(1), 22-38. STECKE, K. E. and KIM, I. 1991, A Flexible Approach to Part Type Selection using Part Mix Ratios in Flexible Flow Systems. International Journal of Production Research, 29(1), 53 -75. STECKE, K. E. and SOLBERG, J. J. 1981, Loading and Control Policies for a Flexible Manufacturing System. International Journal of Production Research, 19(5), 481-490. STEKE, K.. and To ws, E. 1992, Profit-based FMS Dynamic Part Type Selection over Time for Mid-term Production Planning. European Journal of Operational Research, 63,54-65. -36 -

STOEVA, S.P. 1990, A Due Date Based Dispatching Rule for Flexible Manufacturing Systems. International Journal of Production Research, 28(11), 1991-2000. SURI, R. 1985, An Overview of Evaluative Models for Flexible Manufacturing Systems. Annals of Operations Research, 3, 13-22. SURI. R. and DLiwE, J. W. 1985, A Technique for On-line Sensitivity Analysis of Flexible Manufacturing Systems. Annals of Operations Research, 3, 381-382. SURI, R. and HILDEBRANDT, R. R. 1984, Modeling Flexible Manufacturing Systems Using Mean Value Analysis. Journal of Manufacturing Systems, 3, 61-69. TABE, T., YAMAMURO, S. and SALVENDY, G. 1989, An Approach to Knowledge Elicitation in Scheduling FMS: towards a Hybrid Intelligent System. Ergonomics of Hybrid Automated Systems I (Elsevier Science Publishers B.V., Amsterdam), 259-266. THESEN, A. and LE, L. 1986, An Expert System for Scheduling Robots in a Flexible Electroplating System with Dynamically Changing Workloads. Proceedings of the Second ORSAITIMS Conference on Flexible Manufacturing, Systems: Operations Research Models and Applications, eds. K. E. Stecke and R. Suri (Elsevier Science Publishers B.V., Amsterdam), 555-566. ToczYLowsKI, E. and HINDI, K.S. 1991, Aggregate Capacitated Lot Size Scheduling for a Class of Flexible Machining and Assembly Systems. HIE Transactions, 23(3), 239-266. TSUKIYAMA, M., MoRI, K. and FUKUDA, T. 1991, Dynamic Scheduling with Petri-net Modeling and Constraint-based Schedule Editing for Flexible Manufacturing Systems. System Modelling and Optimization (Springer, Berlin), 913-922. Tu, Y. and SORGEN, A. 1991, Real-time Scheduling and Control of Transportation in Flexible Manufacturing Cells. Computers in Industry, 16, 315-320. TzuBONE, H., ANZAI, M. and SUGAWARA, M. 1991, An Interactive Production Planning and Scheduling System for a Flow-type Manufacturing Process. International Journal of Production Economics, 22, 43-51. VAN WASSENHOVE, L. N. and BAKER, K. R. 1982, A Bicriterion Approach to Time/Cost Tradeoffs in Sequencing. European Journal of Operational Research, 11(1), 48-54. VAN DYKE PARUNAK, H. 1991, Characterizing the Manufacturing Scheduling Problem. Journal of Manufacturing Systems, 10(3), 241-259. WAYSON, R. D. 1965, The Effects of Alternate Machines on Two Priority Dispatching Disciplines in the General Job Shop. Master's Thesis, Cornell University, Department of Industrial Engineering and Operations Research (Ithaca, New York). -37 -

WEBSTER, W. B. 1984, Production and Order Planning in the FMS Environment. Proceedings of the Fall Industrial Engineering Conference, Institute of Industrial Engineers; reprinted in Production Planning, Scheduling, and Inventory Control, Third Edition, eds. F. R. Jacobs and V. A. Mabert (Industrial Engineering and Management Press, Atlanta, Georgia). WIDMER, M. 1991, Job Shop Scheduling with Tooling Constraints: a Tabu Search Approach. Journal of the Operations Research Society, 42(1), 75-82. WILHELM, W. E. and SHN, H. M. 1985, Effectiveness of Alternate Operations in a Flexible Manufacturing System. International Journal of Production Research, 23(1), 65-79. WINTER, R. E. 1986, Computer-guided Tools are Catching On. Wall Street Journal, February 28. WITTROCK, R. J. 1985, Scheduling Algorithms for Flexible Flow Lines. IBM Journal of Research and Development, 29(4), 401-412. WITrROCK, R.J. 1990, Scheduling Parallel Machines with Major and Minor Setup Times. International Journal of Flexible Manufacturing Systems, 2(4), 329-342. WITTROCK, R.J. 1992, The "Orchard" Scheduler for Manufacturing Systems. International Journal of Production Economics, 28(1), 47-70. Wu, S.-Y. and WYSK, R.A. 1989, An Application of Discrete Event Simulation to On-line Control and Scheduling in Flexible Manufacturing. International Journal of Production Research, 27(9), 1603-1624. XIE, X. 1989, Real Time Scheduling and Routing for Flexible Manufacturing Systems with Unreliable Machines. RAIRO Recherche Operationnelle, 23(4), 355-374. YAMAGATA, K., TAMURA, H. and HATONO, I. 1991, Modeling and On-line Scheduling of Flexible Manufacturing Systems using Stochastic Petri Nets. IEEE Transactions on Software Engineering, 17, 126-132. YAO, D. D. and BuzAcoTrr, J. A. 1985, Modeling a Class of State-dependent Routing in Flexible Manufacturing Systems. Annals of Operations Research, 3, 153-167. YOUNG. R. E. and ROSSI, M. A. 1988, Toward Knowledge Based Control of Flexible Manufacturing Systems. III Transactions, 20(1), 36-43. -38 -