Division of Research School of Business Administration Tile University of Michigan PERFORMANCE OF NONDELAY SCHEDULES: GENERALIZED OPEN SHOPS Working Paper #651 Ram Rachamadugu and Thomas J. Schriber The University of Michigan FOR DISCUSSION PURPOSES ONLY None of this material is to be quoted or reproduced without the expressed permission of the Division of Research Copyright 1990 The University of Michigan School of Business Administration Ann Arbor,'Michigan 48109-1234 December 1990

ABSTRACT This paper presents the results of a simulation-based study of the effects of sequencing flexibility on the performance of various scheduling rules in environments such as job shops and flexible manufacturing systems. A quantitative metric is proposed for sequencing flexibility. Relative differences in the performance of various scheduling rules diminish and the relative rankings also change as sequencing flexibility increases. It is found that the shortest processing time rule may not be the best scheduling rule for reducing inventories and flow times if sequencing flexibility is present in product structures and is used to advantage. Effects on due-date related criteria are also presented.

1. INTRODUCTION With the globalization of manufacturing, there has been renewed interest in the competitiveness of the manufacturing sector in the United States. A great amount of attention has been focused on the competitive advantages provided by technologies such as computer integrated manufacturing (CIM), robotics, and flexible manufacturing systems (FMSs). An important advantage enjoyed by manufacturers adopting these technologies results from the flexibilities inherent in these systems [Gustavsson 1984]. "Flexibility" is a term generally used to describe the ability of a system to respond in a cost effective manner to changes in volume requirements, mix requirements, machine status and processing capabilities. For a discussion of types of flexibilities, see Browne, Dubois, Rathmill, Sethi, and Stecke [1984], Chatterjee, Cohen, Maxwell and Miller [1984], and Sethi and Sethi [1990]. Flexibility can be classified into two broad categories-hardware and software flexibility [Blackburn and Millen 1986]. "Hardware" flexibility refers to the flexibility that is inherent in machines and material handling devices, for example, whereas "software" flexibility relates to the way information systems and decision making procedures are organized to support the use of such system resources as machines and material handling devices. The option of being able to choose among two or more machines to carry out a given operation is generally termed "routing flexibility." Routing flexibility is a type of hardware flexibility. In contrast with routing flexibility, consider the concept of sequencing flexibility. This type of flexibility exists when two or more operations can be performed in any order. This type of flexibility is product specific rather than process specific. For example, suppose that a pair of operations needs to be performed on a job, and that no precedence relationship exists between these two operations, so that they can be performed in either of two sequences. Such sequencing flexibility is a type of software flexibility. Since sequencing flexibility is product-specific, it exists in conventional machining systems as well as in flexible manufacturing systems. Even when it does exist, however, sequencing

-2 - flexibility is seldom exploited. The reader can easily visualize the chaotic conditions that are likely to result if the job process sheets, instead of specifying the exact sequence of operations, leave those decisions to be made by the shop personnel. Instead, for ease of operational control, most job process sheets simply list a prespecified sequence of operations to be carried out in completing a job. (Note that real time information and decision support systems are needed to exploit sequencing flexibility, and this fact may also further help explain why sequencing flexibility has been seldom exploited in the past.) Rachamadugu and Stecke [1986] discuss these issues in some detail, particularly in the context of FMSs. This work focuses on the impact of "perfect" sequencing flexibility on the performance of dispatching rules. (Perfect sequencing flexibility is defined in Section 3. The study explores how perfect sequencing flexibility affects the relative and absolute performance of various dispatching procedures in manufacturing systems. Surprisingly enough, despite the potential for sequencing flexibility even in conventional systems, few prior research studies have explored this issue from the scheduling point of view. The paper is organized as follows. Section 2 provides a review of related earlier studies. In section 3, a quantitative definition of sequencing flexibility is proposed. In section 4, a description of the sequencing rules and criteria studied in this paper is given, and the need for using evaluative studies to determine the effects of sequencing flexibility is discussed. Section 5 describes the simulation methodology used to support the research reported here. In section 6, results are discussed. Finally, future research directions are provided and references are given. 2. Literature Review There are very few analytical or evaluative studies that address the impact of sequencing flexibility on the performance of various scheduling procedures. Even recent surveys on job shop scheduling or text books do not mention the availability of prior literature on this topic, with the notable exception of Conway, Maxwell and Miller [1967]. Further, there appears to be no consensus regarding the impact of flexibility on the choice of scheduling procedures. Tsai [1985]

-3 - points out that in view of the multitude of decision alternatives open to the decision maker, scheduling decisions in flexible manufacturing systems are inherently complex. Stecke and Solberg [1981] conclude that effective scheduling procedures in such systems are likely to be system specific. Afentakis [1986] argues that under mildly restrictive conditions, scheduling procedures are almost irrelevant in some types of flexible manufacturing systems. Because of such widely varied views, the need exists to define flexibility precisely and measure its impact on the performance of scheduling rules. Wayson [1965] studied the effects of routing flexibility on the relative performance of dispatching rules. He found that even minimal routing flexibility had a profound effect on the relative performance of dispatching rules. Even with a small amount of routing flexibility, an arbitrary rule such as First Come First Served performed almost as well as the Shortest Processing Time rule implemented with no routing flexibility. Neimeier [1967] studied the impact of sequencing flexibility on the performance of several scheduling rules. However, his study did not fully exploit the sequencing flexibility inherent in product structures. His major conclusion was that the relative differences in the performance of scheduling rules decrease when sequencing flexibility is taken into account. Russo [1965] also studied similar situations. For a brief summary of these studies, see Conway, Maxwell and Miller [1967]. These studies did not control the amount of flexibility in their systems. Also, they used special product structures. Recently, Carrie and Petspoulos [1985] addressed the issue of operation sequencing in the context of a particular Flexible Manufacturing System in Scotland. They investigated this system to improve its performance, concluding that there were no discernible differences between various job sequencing rules. Lin and Solberg [1989] studied the simultaneous effects of process planning and sequencing decisions on the performance of scheduling rules. They report that deferring flexibility inherent in the process plan and exploiting it as late as possible in the execution of jobs significantly reduces the mean flow time. However, they did not study due-date related measures or explicitly control product structures. Also, their study did not segregate the effects of sequencing flexibility from routing (or process planning) flexibility. However, the study clearly

-4 - points to the benefits of exploiting flexibility inherent in the system. Our study here supplements the Lin and Solberg [1989] work by isolating the impact of sequencing flexibility on performance measures and also extends the research to due-date related criteria. Solberg [1989] also provides interesting related insights into various paradigms for scheduling. 3. A Quantitive Measure Of Sequencing Flexibility Some researchers addressed the issues relating to operational flexibility of manufacture. For a discussion on these studies, see the papers by Hutchinson and Sinha [1989], and Sethi and Sethi [1990]. The emphasis in these studies was on quantifying alternative manufacturing plans rather than to measure the numerous ways a set of operations can be performed. Sethi and Sethi [1990] refer to sequencing flexibility in their survey article in a different way. They term it as "Operation Flexibility". In their definition, operation flexibility is the result of both sequence flexibility and routing flexibility. Hence their definition subsumes both hardware and software flexibility. Their definition of operation flexibility is analogous to the definition of process flexibility used by Lin and Solberg [1989]. They state the the operation flexibility can be measured by the number of different process plans for completing a job. Though this is an initial step towards measuring sequencing flexibility, it could be improved upon by relating to the total number of process plans to the total number of operations needed to be performed for completing the job. Thus the need exists to precisely measure sequencing flexibility before its impact on scheduling methods can be evaluated. Consider the manufacture of a product whose operations have no specified precedence (call this product A) versus the manufacture of another product whose operations can only be performed in a strictly specified serial order (call this product B). Then we have complete flexibility in sequencing the operations of product A, and no flexibility at all in sequencing the operations of product B. Similarly, consider the manufacture of a product (call this product C) in which some of the tasks can be done in any arbitrary order, whereas the rest of the tasks must be done in a strictly specified order. We need to develop a quantitative measure of sequencing flexibility that ranks

-5 - product A as the most flexible (no other product can have a sequencing flexibility measure larger than product A), product B as the least flexible (no other product can have a sequencing flexibility measure smaller than product B), and product C at an appropriate intermediate level of sequencing flexibility. We proceed to define a measure of sequencing flexibility that ranges in value from 0 to 1, and such that product B above has a measure of 0, product A a measure of 1, and products like product C have a measure falling somewhere within the 0-1 interval (with the exact measure depending on the sequencing characteristics of the product). As motivation for the definition of such a measure, consider the operations graph of a job. An operations graph is a directed acyclic graph consisting of nodes that represent the operations and directed arcs that represent the precedence among the operations. Figure 1 shows the operations graph for a hypothetical product. Five operations are required to manufacture the product. Operation 1 must precede operation 2, and operation 2, in turn, must precede operation 3. Similarly, operation 4 must precede operation 5. But none of operations 1, 2, or 3 need to precede operation 4. Similarly, neither of operations 4 or 5 need to precede operation 1. Clearly, for the process to be feasible, the operations graph should be acyclic. In practice, however, there might be some cycling due to occasional need for rework. Note that an operations graph need not explicitly show transitive precedence among the nodes. Transitive precedence implies that if operation X precedes operation Y and operation Y precedes operation Z, then X precedes Z. In Figure 1, for example, there is no arc that directly connects node 1 to node 3, even though operation 1 must take place before operation 3 can take place.

-6 - Figure 1. Example of an Operations Graph To specify a quantitative measure for sequencing flexibility, we define the term Sequencing Flexibility Measure (SFM) for a job as follows: SFM = 1.0 - (2 * transitive precedence arcs )/n(n*(n-)) where n is the number of nodes in the operations graph. In Figure 1, for example, there are 5 nodes, 3 precedence arcs, and 1 transitive precedence arc, resulting in a Sequencing Flexibility Measure of 0.6. For product A above, the SFM is 1 (because there are no transitive precedence arcs when operations can be done in any order), and for product B it is 0 (because there are n*(n1)/2 transitive precedence arcs when operations must be done in a strictly determined order). To the best of our knowledge, there are no rigorous measures of sequencing flexibility defined in te existing literature. However, similar concepts are used in assembly line design and project networks. Our study here primarily addresses the perfect sequencing flexibility scenarioi.e., SFM = 1.0. In this scenario, there is no precedence among the operations of a job. They can be performed in any order. This is analogous to, but not same as, open shops, which have been used in the context of computer scheduling [Gonzalez and Sahni 1976]. In an open shop, a job has to be processed on all machines. In contrast, the situation studied in this paper permits a job to visit a subset or the whole set of machines. Thus the scenario studied here is generalization of the

-7 - open shop literature. Also, the open shop literature mostly addresses the issue of makespan, which has less relevance for systems in which jobs arrive continuously over time. 4. Need for Evaluative Models In this paper we study the situation where perfect sequencing flexibility exists and the job visits a subset of machines. Though the operations of a job can be performed in any order, there is a one-to-one correspondence between operations and machines. Each operation can be performed by only one machine. For the sake of keeping the model simple without loss of significance, it is assumed that a job visits a machine no more than once. Given this scenario, we wish to evaluate the effects of exploiting sequencing flexibility on the performance of various well known dispatching rules. We study the performance of dispatching rules such as the Shortest Processing Time rule (SPT), First Come First Served (FCFS), First in System (FIS), Least Work Remaining (LWR) and Fewest Remaining Operations (FRS) on important criteria such as the mean flow time and work-in-process inventory. SPT assigns highest priority for machine use to the task with the smallest processing time on the machine. FCFS assigns highest priority to the task that listed itself earliest at the machine. FIS assigns highest priority to the job that arrived earliest in the shop. LWR assigns highest priority to the job that has the least amount of work yet to be completed on it in the shop. FRS assigns highest priority to the job that has the fewest remaining tasks to be completed. Though these rules can be implemented in preempt-repeat, preempt-resume and nonpreemptive modes, we chose to implement them in nonpreemptive mode since it is the most widely studied case. Although these rules have been studied widely in the context of no sequencing flexibility, their absolute and relative performance are unknown when perfect or nearperfect sequencing flexibility exists in the system. From a practical point of view, due-date related measures are also quite important. In earlier industrial surveys, practitioners indicated due-date related criteria as the most important [Panwalkar et al. 1973 and Smith et al. 1986]. Hence we also study the performance of due-date

-8 - related rules such as Earliest Due Date (EDD), Critical Ratio Rule (CRR) and the Modified Due Date rule (MDD) on due-date related criteria such as mean tardiness of all jobs, proportion of tardy jobs and the mean tardiness of tardy jobs. EDD assigns highest priority to the job with the earliest due date. As for CRR, we implemented the rule as given below, where RPT stands for remaining processing time. CRR = (Due Date - Current Time - RPT) CRR -- RPT RPT MDD was developed by Baker and Bertrand [1982]. MDD is a dynamic version of the EDD rule. Whenever a job is under consideration for scheduling, its due date is modified as follows where, as before, RPT is remaining processing time: MDD = Max (Due Date, Current Time + RPT) In the MDD rule, modified due dates are used instead of the original due dates and then the job with the earliest due date is assigned the highest priority. MDD performed well in earlier evaluative studies [Baker and Kanet 1983]. It can also be shown analytically that MDD is a dominance condition for optimality in static environments [Rachamadugu 1987]. A wide class of dispatching rules based on operation due dates [Baker and Kanet 1983] can also be used to improve the performance of heuristic rules in conventional job shops. In these studies, a job's operations are performed without using sequencing flexibility. We have deliberately chosen to preclude this class of rules from consideration here because no precedence exists among the operations of a job under perfect sequencing flexibility and hence no conceptual equivalent of the operation due date exists in our scenario. We explored the alternative of analyzing the performance of the above-mentioned scheduling rules using prescriptive models. Even for conventional job shops, most prescriptive models are approximations. In cases where exact models are available, the assumptions made are so restrictive and/or unrealistic that their direct relevance to reality is questionable. However, we should point out that in the context of conventional job shops, it has been found that some

-9 - prescriptive models are quite robust [Buzacott and Shanthikumar 1985]. To the best of our knowledge, there are no known exact or approximate prescriptive models for analyzing the performance of scheduling rules under perfect or near perfect sequencing flexibility scenarios. This motivates us to use evaluative models to study the performance of sequencing rules for the case of perfect sequencing flexibility. 5. Design of the Simulation Experiment We developed a suite of simulation models to study the absolute and relative performance of the scheduling rules discussed in Section 4. The shop we modelled consists of 9 machines. Each job visits from 1 to 9 machines, with no machine visited more than one time per job. The number of machines visited by a job is determined by sampling from the uniform distribution of integers ranging from 1 to 9, inclusive. The particular machines visited by a job are determined at random. Operation times for all machines are assumed to be identically distributed. This assumption was made to reduce the dimensionality of the problem and to make it easier to isolate the impact of perfect sequencing flexibility on the performance of alternative dispatching rules. Operation times are 2-Erlang distributed [Law and Kelton 1990] with a mean of 30 minutes. They state that "experience has shown that if one collects data on the time to perform some task in the real world, the histogram of these data will often have a shape similar to that of the density function of a 2-Erlang distribution." Job interarrival times are exponentially distributed with a mean determined by the level at which the shop's overall expected machine utilization level is set. Simulations were performed with expected machine utilizations set at 60, 90, and 95 percent. These utilizations are typical of those used in studies of this type. In the simulation runs, realized utilizations varied only marginally from their expectations. Job due dates were set by using flow allowance factors based on the well known Total Work Content Rule [Conway, Maxwell and Miller 1967]. Values for the flow allowance factors were chosen so that approximately 1, 10, and 20 percent of the jobs were tardy for the FCFS rule

-10 - under conditions of no sequencing flexibility. We used this benchmark for establishing flow allowances to avoid any potential bias in setting the due dates in favor of one rule or another. The Method of Batch Means [Schmeiser 1982] was chosen as the statistical methodology used in the experimentation. For each dispatching rule and expected overall machine utilization, and for sequencing flexibility measures of 0.0 and 1.0, we performed a single simulation segmented into 16 consecutive, nonoverlapping batches. Each batch was sized so that exactly 1,000 jobs were completed per batch. The portion of the simulation corresponding to the first of the 16 batches moved the model through transient conditions and into conditions of operating equilibrium. Results from the first batch in each simulation were discarded, and results from the remaining 15 batches were retained for analysis. For each retained batch, observed performance measures included the mean job flowtime (hours), the mean job tardiness (hours) based on all jobs, the proportion of tardy jobs, and the mean job tardiness (hours) based only on tardy jobs. Both the mean of the batch means (that is, the grand batch mean) and the standard deviation of the batch means were computed for these measures. The resulting values are given in Tables 1 through 4 in Section 6, and are discussed there. Identical job sets were used for each simulation. In other words, any given job in a simulation had the same time of arrival, visited the same number of machines and the same specific machines, visited the machines in the same order (in the case of no sequencing flexibility), and had the same operating times at corresponding machines as did the equivalent job in each of the other simulations. This eliminated the need to take into account random differences among job sets when comparing and contrasting the performance of alternative dispatching rules. GPSS/H [Henriksen and Crain 1989, Schriber 1990] was chosen as the modeling language used in this study. Simulations were performed on an IBM 3090-600E. CPU times per simulation ranged from several CPU seconds up to a maximum of about 20 CPU seconds. GPSS/H User Chains [Schriber 1974] were employed consistently to keep CPU-time requirements at a minimum. In the models for perfect sequencing flexibility, each incoming job was split into a collection of sub-jobs, one sub-job per machine required by the overall job. The sub-jobs for a

-11 - given job then joined a GPSS/H Group [Henriksen and Cramn 1989] common to and restricted to that job. This facilitated the CPU-efficient updating of sub-job status, making it possible for example to flag the other sub-jobs in a Group as non-candidates for machining during time intervals when machining was already under way for any one of the Group's sub-jobs. In general, the models for perfect sequencing flexibility require more sophisticated logic and more CPU time than the models in which there is no sequencing flexibility. The constructs and supporting tools provided by GPSS/H were found to be more than adequate for the modeling requirements in this study. 6. Analysis Table 1 shows the mean flowtime results for different rules under both inflexible and flexible scenarios at various utilization levels. Note that the results for zero sequencing flexibility can be compared with results derived by researchers for conventional jobshops. Our observations in this context are consistent with the conclusions drawn by earlier researchers. As is to be expected, SPT performs better than any other rule for the flowtime criterion at a zero SFM level for all utilization levels. The results for an SFM value of 1.0 are very counterintuitive and differ from the conclusions drawn for an SFM value of 0. Firstly, at a low utilization level of 60% there is no reason to choose one rule over the other. All rules perform equally well. However, we note that all rules improve their performance when the SFM increases from 0 to 1. The improvement is very large for rules that perform poorly when the SFM value is 0. Thus, the differences between the rules decrease when sequencing flexibility is introduced. However, we wish to point out that SPT no longer minimizes the mean flowtime. Best results are achieved by the Least Work Remaining rule. This is significant in a number of ways. LWR is a global rule and it was known to perform not too well in prior studies. However, introduction of flexibility not only improves its perfonnance, but makes it the best choice.

-12 - Secondly, the low value of the batch mean variance leads us to speculate that the variance of the population flowtimes could also be low. (We are investigating this situation now by repeating the simulations with versions of the models modified slightly to include population flowtime variances as part of the postsimulation report.) Thus, with the introduction of flexibility, we might be gaining reductions both in mean flowtimes and in their variances. This aspect of the study merits further investigation. This study also points out that there is a change in the relative ranking of the rules when flexibility is introduced. This contradicts the earlier study by Russo [1965]. The differences in conclusions can be attributed partly to the fact that earlier researchers did not control product structures from the point of view of sequencing flexibility. Tables 2, 3, and 4 present the results for various due-date related criteria. For the sake of brevity, we report here only the results for flow allowances that result in approximately 10 percent of the jobs being tardy for the FCFS rule. The reader is directed to the paper by Rachamadugu and Schriber [1990] for full details regarding other flow allowances. Table 2 lists the results for the mean tardiness at three utilization levels for various dispatching rules. It can be observed that for all rules except SPT, mean tardiness and also the variance of the batch-mean tardiness decreases when sequencing flexibility is introduced. We would like to comment further on the aberrant behavior of the SPT rule. At the 95 percent utilization level, we note in Table 2 that the SPT performance deteriorates when flexibility is introduced. While all the other rules that we studied improve their performance, mean tardiness for the SPT actually increases with the introduction of flexibility at high utilization levels. This is also true for the other flow allowance factors which are not reported here. We conjecture that this decrease in performance is largely the result of SPT failing to improve its mean flowtime when flexibility is introduced. (See Table 1.) We also notice that the due-date related rules such as EDD, MDD and CRR perform better than other rules with respect to due-date measures. It is also interesting to note that FRS performs well despite the fact that it disregards due-date related information.

-13 - Table 1. Effects of Utilization Levels, Sequencing Flexibility, and Dispatching Rules on the Mean and (Standard Deviation) of Batch-Mean Flow Times (Hours) Overall Machine Utilization 60% I90% I 95% _____ Sequencing Flexibility Measure Rule 0.0 1.0 0.0 1.0 0.0 1.0 SPT 4.4 3.1 9.6 7.1 16.9 15.5 (0.2) (0.1) (1.6) (1.9) (3.6) (5.5) EDD 5.0a 3.2a 16.2b 7.0b 37.9c 26.O0 (0.3) (0.1) (3.0) (1.6) (8.4) (5.8) MDD 5.0a 3.2a 16.2b 7.0b 37.9c 26.Oc (0.3) (0.1) (3.0) (1.6) (8.4) (5.8) FIS 5.2 3.2 17.5 8.5 46.0 35.0 (0.3) (0.1) (4.0) (2.4) (9.5) (7.1) LWR 5.0 3.1 17.8 5.6 35.7 11.9 (0.3) (0.1) (3.2) (1.0) (10.2) (3.5) FCFS 5.2 3.2 18.7 8.5 51.2 35.0 (0.3) (0.1) (1.0) (2.4) (10.7) (7.1) CRR 5.2a 3.5a 19.3b 14.2b 54.8C 54.4C (0.3) (0.2) (4.3) (4.3) (9.8) (8.6) FRS 5.2 3.2 22.9 7.3 50.7 29.2 (0.3) (0.1) (4.8) (1.8) (15.6) (6.4) a: Flow Allowance Factor: 3.56 (set so that 10.2% of the jobs are tardy for FCFS). b: Flow Allowance Factor: 15.4 (set so that 10.1% of the jobs are tardy for FCFS) c: Flow Allowance Factor: 44.0 (set so that 10.0% of the jobs are tardy for FCFS)

-14 - Table 2. Effects of Utilization Levels, Sequencing Flexibility, and Dispatching Rules on the Mean and (Standard Deviation) of Batch-Mean Tardiness (Hours) Utilization Levels 90% 1 60% 95% Sequencing Flexibility Measure Rule 0.0 1.0 0.0 1.0 0.0 1.0 SPT 0.04 0.008 0.7 0.6 3.6 4.5 (0.02) (0.004) (0.06) (0.06) (3.8) (5.4) EDD 0.02 0.004 -0 -0 -0 -0 _ (0.01) (0.001) (-0) (-0) (- o)(- 0) MDD 0.02 0.004 -0 0.001 -0 -0 (0.01) (0.001) (-0) (0.002) (-0) (-0) FIS 0.20 0.05 1.0 0.2 2.6 1.5 (0.05) (0.01) (0.6) (0.2) (1.2) (0.7) LWR 0.12 0.005 3.3 0.2 9.8 2.7 (0.05) -0 (1.8) (0.2) (8.0) (3.2) FCFS 0.14 0.05 0.6 0.2 1.7 1.5 (0.04) (0.01) (0.05) (0.2) (1.1) (0.7) CRR 0.02 0.007 0.001 0.001 -0 -0 (0.007) (0.006) (0.001) (0.001) (-0) (-0) FRS 0.23 0.006 6.1 0.3 16.9 0.2 (0.07) (0.002) (3.3) (0.07) (10.5) (0.2) -0 implies the value is less than 0.001.

-15 - Table 3 reports on the performance of various dispatching rules for the "proportion of tardy jobs" criterion. This measure is useful when penalties are incurred based on whether a job is tardy or not. For example, in some industries the customer generally pays for product delivery if the product is delivered on time. However, if the delivery is tardy, the vendor pays the transportation expenses. Under such circumstances, the proportion of tardy jobs is a better measure than the mean tardiness. We note that all rules, with the exception of SPT and CRR at a 95% utilization level, improve their performance when flexibility in sequencing is introduced. The result relating to CRR at 95% is somewhat surprising. However, this can once again be explained by the fact that CRR does not significantly improve its mean flowtime at high utilization levels. As before, rules that make use of the due-date based information perform better than other rules when sequencing flexibility is available and is used in the scheduling process. Table 4 shows the results for various rules when conditional tardiness is used as the criterion. Conditional tardiness measures the average tardiness of tardy jobs. This measure is useful when the tardiness costs are superlinear, but the decision maker is unsure of the exact nature of these costs. With the exception of the SPT and LWR rules, all other rules improve their performance when sequencing flexibility is introduced. At high utilization levels, both SPT and LWR actually increase the conditional tardiness when sequencing flexibility is introduced. Due-date based rules,however, improve their performance. Yet another feature of SPT which is not obvious from the results here is that the conditional tardiness actually increases as the flow allowance increases when sequencing flexibility is present. This aspect of the study merits further investigation.

-16 - Table 3. Effects of Utilization Levels, Sequencing Flexibility, and Dispatching Rules on the Mean and (Standard Deviation) of the Batch-Mean Proportion of Tardy Jobs Utilization Levels 60% 90% I 95% ______ Sequencing Flexibility Measure Rule 0.0 1.0 0.0 1.0 0.0 1.0 SPT 3.3 1.6 1.6 1.4 1.1 1.2 (0.5) (0.4) (1.0) (1.3) (0.5) (0.6) EDD 2.4 1.2 0.2 0.03 0.02 0.007 (0.7) (0.3) (0.1) (0.05) (0.04) (0.03) MDD 2.3 1.2 0.2 0.03 0.02 0.007 (0.7) (0.3) (0.1) (0.05) (0.04) (0.03) FIS 12.8 4.4 14.3 5.4 13.3 8.4 (2.3) (0.7) (6.1) (2.7) (4.1) (2.7) LWR 4.9 1.4 5.7 0.5 3.7 0.8 (1.2) (0.3) (2.0) (0.4) (1.1) (0.4) FCFS 10.2 4.4 10.1 5.4 10.0 8.4 (1.8) (0.7) (6.8) (2.7) (4.2) (2.7) CRR 4.2 1.8 0.4 0.4 0.03 0.08 (1.2) (0.4) (0.2) (0.3) (0.05) (0.1) FRS 8.4 1.5 11.1 0.5 8.0 1.7 (1.4) (0.2) (3.1) (0.6) (3.3) (1.2)

-17 - Table 4. Effects of Utilization Levels, Sequencing Flexibility, and Dispatching Rules on the Mean and (Standard Deviation) of the Conditional Batch-Mean Tardiness (Hours) Utilization Levels 60% 90% 95% Sequencing Flexibility Measure Rule 0.0 1.0 0.0 1.0 0.0 1.0 SPT 1.2 0.5 37.1 36.8 356.1 414.3 _____ (0.5) (0.2) (30.3) (27.4) (347.5) (490.7) EDD 0.7 0.3 0.3 0.1 0.05 0.02 (0.3) (0.1) (0.2) (0.2) (0.1) (0.08) MDD 0.7 0.3 0.3 0.1 0.05 0.02 (0.4) (0.1) (0.2) (0.2) (0.1) ( 0) FIS 1.6 1.1 6.3 4.0 18.4 16.6 (0.2) (0.2) (1.5) (1.3) (4.6) (4.4) LWR 2.5 0.4 55.4 26.0 250.1 325.5 (0.7) (0.1) (17.5) (21.8) (199.6) (264.3) FCFS 1.3 1.1 4.7 4.0 15.7 16.7 (0.2) (0.2) (1.4) (1.3) (5.1) (4.4) CRR 0.4 0.4 0.4 0.3 0.1 0.1 (0.1) (0.3) (0.2) (0.2) (0.2) (0.2) FRS 2.7 0.4 52.4 2.7 194.6 9.8 (0.4) (0.1) (17.6) (4.2) (85.5) (4.8) -0 implies the value is less than 0.001.

-18 - 7. Conclusions In this paper, we analyzed the performance of widely studied dispatching procedures for the case when perfect sequencing flexibility is present. Our results indicate that when sequencing flexibility is present and exploited, dispatching procedures significantly improve their performance. However, the SPT rule displays aberrant behavior which is worthy of further analytical and evaluative studies. Also, we notice that the relative differences between various procedures diminish when sequencing flexibility is used. LWR performs better than the SPT rule for the mean flowtime measure under conditions of perfect flexibility. It needs to be determined at what level of sequencing flexibility this change takes place. As a rule, due-date based procedures perform better than others for due-date related criteria. We did not notice significant differences between MDD and EDD. This could be due to the low proportion of tardy jobs realized in this work. Our studies have both operational and strategic implications. At the operational level these studies imply that if sequencing flexibility is utilized, the role of scheduling is less important because the relative differences between the rules diminish. This also implies that the choice of dispatching rules needs to be dictated by other considerations such as the stability of schedules, ease of implementation and other criteria such as user acceptance. In the past, organizational control issues and the high cost of early generation information systems precluded the exploitation of sequencing flexibility even when it was available in the product structure. However, recent advances in information technology and the declining cost of information systems make it possible to use sequencing flexibility at the operational level. However, the organizational impediments can be a barrier to using sequencing flexibility. The methodologies used in this paper, if they are to be implemented, warrant that the short term resource allocation decisions are to be made by shopfloor personnel rather than centralized scheduling departments. This is an important issue which needs to be addressed before implementing scheduling procedures which dynamically use sequencing flexibility. At the strategic level, the issue needs to be addressed as to whether marginal investments should flow into hardware or information management systems. Sequencing flexibility inherent in

-19 - product structure can be exploited by appropriately using that information via real-time information systems. Also, we found that using flexibility significantly reduces mean flowtime and various due-date related measures. Thus, the introduction of information systems to exploit flexibility improves service levels. This provides a competitive advantage without necessarily replacing the existing investment in manufacturing hardware technology. Exploitation of sequencing flexibility is also a step toward justifying investments in manufacturing information technologies. Finally, we note that if the benefits of sequencing flexibility in terms of reduced flowtimes and inventories are sufficiently great, this has implications for designing products in such a way as to maximize the potential sequencing flexibility in manufacturing the products. Heretofore, product design has largely emphasized process and product compatibility with less emphasis, if any, on sequencing flexibility. This study adds an additional dimension to design for manufacturing.

-20 -ACKNOWLEDGEMENT This research was supported in part by the Faculty Summer Research Grant from the Graduate School of Business, University of Michigan, Ann Arbor, Michigan.

-21 - REFERENCES Afentakis, P. (1985), "An Optimal Scheduling Strategy for Flexible Manufacturing Systems," Working Paper No. 85-012, Department of Industrial Engineering and Operations Research, Syracuse University, Syracuse, NY. Baker, K.R. and J.M.W. Bertrand (1982), "A Dynamic Priority Rule for Sequencing Against Due Dates," Journal of Operations Management 4, 1, 11-22. Baker, K.R. and J.J. Kanet (1983), "Job Shop Scheduling with Modified Due Dates," Journal of Operations Management 3, 1, 37-42. Blackburn, J. and R. Millen (1986), "Perspectives on Flexibility in Manufacturing: Hardware versus Software," In Modeling and Design of Flexible Manufacturing Systems 2, 2, Andrew Kusiak, Ed. Elsevier Science Publishers, Amsterdam, The Netherlands, 116-117. Browne, J., D. Dubois, K. Rathmill, S. Sethi, and K. Stecke (1984), "Classification of Flexible Manufacturing Systems," The FMS Magazine 2, 2, 116-117. Buzacott, J.A. and J.G. Shanthikumar (1985), "On Approximate Queueing Models of Dynamic Job Shops," Management Science 31, 9, 870-887. Carrie, A.S. and A.C. Petsopoulos (1985), "Operation Sequencing in a FMS," Robotica 3, 259 -264. Chatterjee, A., M. Cohen, W. Maxwell, and L. Miller (1984), "Manufacturing Flexibility: Models and Measurements," In Proceedings of the First ORSA/TIMS Special Interest Conference on Flexible Manufacturing Systems, K.E. Stecke and R. Suri, Eds. The University of Michigan, Ann Arbor, MI, 49-64. Conway, R.W., W.L. Maxwell, and L.W. Miller (1967), Theory of Scheduling, Addison-Wesley Publishing Company, Reading, MA. Gonzalez, M.J. and S. Sahni (1976), "Open-Shop Scheduling to Minimize Finish Time," Journal of the Association for Computing Machinery 23, 655-679. Gustavsson, S.O. (1984), "Flexibility and Productivity in Complex Production Processes," International Journal of Production Research, 22, 801-808.

-22 - Henriksen, J.O. and R.C. Crain (1989), GPSSIH Reference Manual, Third Edition, Wolverine Software Corporation, Annandale, VA. Hutchinson, G.K. and D. Sinha (1989), "Quantification of the Value of Flexibility," Journal of Manufacturing Systems, 1, 47-56. Law and Kelton (1990), Simulation Modeling and Analysis, Second Edition, McGraw-Hill, New York, NY. Lin, Y.J. and J.J. Solberg (1989), "Flexible Routing Control and Scheduling," In Proceedings of the Third ORSAITIMS Conference on Flexible Manufacturing Systems, K.E. Stecke and R. Suri, Eds. Elsevier Science Publishers, Amsterdam, The Netherlands, 155-160. Neimeier, H. (1967), "An Investigation of Alternate Routing in a Job Shop," Master's Thesis, Cornell University, Ithaca, NY. Panwalkar, S.S., R.A. Dudek, and M.L. Smith (1973), "Sequencing Research and the Industrial Problem," In Symposium on the Theory of Scheduling and its Applications, S.E. Elmaghraby, Ed. Springer Verlag, New York, NY. Rachamnadugu, R. (1987), "A Note on the Weighted Tardiness Problem," Operations Research 35, 3, 450-452. Rachamadugu, R. and T.J. Schriber (1990), "Performance of Nondelay Schedules in Generalized Open Shops," Working Paper, Graduate School of Business, University of Michigan, Ann Arbor, MI. Rachamadugu,R. and K.E. Stecke (1989), "Classification and Review of FMS Scheduling Procedures," Working Paper, Graduate School of Business, University of Michigan, Ann Arbor, MI. Ramasesh, R. (1990), "Dynamic Job Shop Scheduling: A Survey of Simulation Research," OMEGA: International Journal of Management Science 18, 1, 43-57. Russo, F.T. (1965), "A Heuristic Approach to Alternate Routing in a Job Shop," Master's Thesis, Massachusetts Institute of Technology, Cambridge, MA.

-23 - Schmneiser, B. (1982). "Batch Size Effects in the Analysis of Simulation Output," Operations Research 30, 556-568. Schriber, T.J. (1974), Simulation Using GPSS, John Wiley & Sons, New York, NY. Schriber, T.J. (1990), An Introduction to Simulation Using GPSSIH, John Wiley & Sons, New York, NY. Sethi, A.K. and S.P. Sethi, "Flexibility in Manufacturing: A Survey," International Journal of Flexible Manufacturing Systems 2, 4, 289-328. Smith, M.L., R. Ramesh, R.A. Dudek, and E.L. Blair (1986), "Characteristics of U.S. Flexible Manufacturing Systems-A Survey," In Proceedings of the Second ORSAITIMS Conference on Flexible Manufacturing Systems, K.E. Stecke and R.J.Suri, Eds. Elsevier Science Publishers, Amsterdam, The Netherlands, 477-486. Solberg, J.J. (1989), "Production Planning and Scheduling in CIM," Information Processing, 919-925. Stecke, K. and J. Solberg (1981), "Loading and Control Policies for a Flexible Manufacturing System," International Journal of Production Research 19, 5, 481-490. Tsai, L. (1985), "The Application of Combinatorics to Flexible Manufacturing Systems," Working Paper, Graduate School of Business Administration, University of California, Berkeley, CA. Wayson, R.D. (1965), "The Effects of Alternate Machines on Two Priority Dispatching Disciplines in General Job Shops," Master's Thesis, Cornell University, Ithaca, NY.