

small (250x250 max)
medium (500x500 max)
Large
Extra Large
large ( > 500x500)
Full Resolution


JOB SHOP SCHEDULING: A QUANlli'lED SEQUENCING RULE FOR IMPROVING SYSTEM PERFORMANCE UNDER DIVERSIFIED OPERATIONAL PARAMETERS By AMR ABUSULEIMAN Bachelor of Science Jordan University of Science and Technology Irbid, Jordan 1995 Submitted to the Faculty of the Graduate College of Oklahoma State University in partial fulfillment of the requirements for the degree of MASTER OF SCIENCE July, 1998 JOB SHOP SCHEDULING: A QUANTIFIED SEQUENCING RULE FOR IM:PROVING SYSTEM PERFORMANCE UNDER DIVERSIFIED OPERATIONAL PARAMETERS Thesis Approved Thesis Advisor l"1~~ ~tNrIi$ De . . of the Graduate College 11 ACKNOWLEDGMENTS In the name of Allah, Most Gracious, Most Merciful Tbis thesis has been a major milestone in my academic career. I feel obligated to acknowledge the help of some people without whom this work would not have been completed in this timely manner. First and foremost, I wish to express my greatest thanks, deepest appreciation, and sincere gratitude to my family, especially my father Suleiman K. AbuSuleiman and my mother Fairouz Shehabi. I thank them for supporting me and giving me the opportunity to pursue my graduate studies. Moreover, I will never forget their love, encouragement, warm emotions, and sacrifice to make me a better person in all aspect of life. My thanks are also extended to the rest of my family members, my beloved sisters Nismen, Abeer, and Reem, and my brother Ghaith. Despite the very long distance, their warm emotions have always made me feel between them and inspired me to do my best always .. I also thank my advisor, Dr. David B. Pratt for his continuous guidance, his encouragement during the frustrating periods, and his compliments during the productive periods. His continuous support kept my motivation at the highest level during the course of this research. My great appreciation is also extended to my committee members Dr. Manjunath Kamath and Dr. Sanjay Melkote. Their valuable comments and suggestions had a significant impact on the quality of this research. I also want to thank: Dr. Mike Branson for his help in the statistical aspects of this research. 1Il I would like to mention again my advisor Dr. David Pratt and Dr .. Manjunath Kamath for fmancial assistanoe by giving me the opportunity of working at the Center for Computer Integrated Manufacturing at Oklahoma State University. I would also like to thank them for helping me improve in my academic and professional career. I also acknowledge the fmancial support of the National Science Foundation. I would also like to mention my best lifetime friends, Omar Na'd, Sa'ed Salhieh, and lmad Hindi. I have always remembered the great times we have, and I am not sure that I would have been able to concentrate on my research without their true and sincere friendship. Thank you buddies! Last but never least, I would like to thank my aunt, Fida Shehabi for her great care and friendship during my stay in the states. iv TABLE OF CONTENTS CHAPfER PAGE I THE PROBLEM AND ITS SETIING .............. ' ............................................ , ...................................... 1 INTRODUcnON ..... ...... ................................. ...................... ................................ " .... .... " .......................... 1 DISPATCIDNG RuLEs .................................................. .... " .......................................... " ....... ... .... ............. 2 PERFORMANCE MEASURES ............... " ............................. " ......... . ........ . ...................................... ............. 2 PROBLEM STATEMENT ................................... ... ........ ..................................................... . ... .. ........... .. .... 3 DEFINITION OF 'TERMINOLOGy .... .............. .............. " ....... .................................. ....... ........ " ........ , ... .. ......... 4 n LITERATURE REVIEW " ............... ' ................................................................................................... 5 INTRODUCTION ..................................................... . ........ , ......... . .......... ....... . ................... ... .. , .... " .............. 5 LITERATURE REVIEW ON CONSTRUCTING COST MODELS ......... , ........................................... , ................... 5 LITERATURE REVIEW ON SEQUENCING RULES ..... .. . , .......................................................................... . .... ,,9 LITERATURE REVIEW ON EXPERIMENTAL DESIGN ....................................................................... ......... 13 CONCLUSION .... .............. . ... ' ............................ " ................................................... " ................. ...... ....... . 16 m RESEARCH G'OALS AND OBJECTIVES .......... , ................................................ "'., ....................... 17 REsEARCH OBJECTIVE ..... , .......................... .. ........ .. ............... . ...... .. ........ " ......................................... , .... 18 TASKS ............................................................................................. . ... ... ................. ... ........................ 18 IV RESEARCH MEmODOLOGY .................................................................................................... 1" AsSUMPTIONS .................... .............. .......... .. ............................. ............ ......................... ... .... .. ... ... ..... . 20 lOB SHOP DESCRIPTION ..... " ......... .... ....... ... .................... . ..................................................................... 21 COST STRUCTURE ............................................................................................................................... 23 Example .......... .............................................. .......................... ... .......... .... ............................. .. ...... 25 RESEARCH FACTORS ............................ .... ............... " .................................... ..................... .................. 27 v SIMULATION MODEL ..•... , .....•...••..•..........•..•. •..•.......... ,. ..•....•.............•.......••.....•......•....•....•.......•••.... ..••• 28 SIMULATION CHARACIERlSTICS ..•..•..•....•..••............•.......................... .., .................................... " .......... 28 SIMULATION VERIFICATION AND VALIDATION ... ................................. ............... . ................................. 29 V RESUL TS ............................................................................................ " ........ " ..................................... 31 RESULTS CONSIDERING RC PERFORMANCE MEASURE ......... ....................... ......... . .... ............... .. . ........... 32 RESULTS CONSIDERING TIME BASED SUPPLEMENTARY PERFORMANCE MEASURES ...... , ......................... 36 THE EffECT OF THE POWER FACfOR (Z) ON PERFORMANCE MEASURES .............................................. .40 DETERMIN1NG THE V AWE Of Z BASED ON THE SYSTEM PARAMETERS ......... ...... .. ................ . ................ 51 VI CONCLUSION .................................................................................... " ..................... , ...... , ........ " ....... 53 SEQUENONG USING THE MODIFIED CRITICAL RATIO .............................. ....................... ...... ............. ... 53 SEQUENCING USING A QUANTIFIED DECISION DOMAIN ..... .................................................................. 55 REsEARCH COr...'TRlBUTION .................................................................................................................... 56 FuTURE DIRECTIONS ... ............................... ........................... ........................... .................. .. .......... .. .... 56 Future directions related to the modified critical ratio rule ........................................................... 57 Future directions related to generalizing the sequencing paradigm introduced in this research ... 58 REFEREN CES ......................... '."" ....... , ........ , ..................................................................... " ................... ,. 59 ,ApPENDIX I lNTlERARRlVAL TIME CALCULATIONS .. ................................................ ....... " ........... . ...... . 62 ,ApPENDIX 2 _ DESCRIPTION OF THE SIMULATION MODEL ....................... ............................. .................. 65 ApPENDIX 3  FORTRAN PROGRAM ...................................................................................................... 71 VI LIST OF TABLES Table Page TABLE I  SUMMARY OF RELEVANT TIME BASED SEQUENCING RULES .......................................................... 10 TABLE II  EXAMPLE DESCRlPl10N ................................................................................. .......................... 26 TABLE III  EVENTS DESCRIPTION .............................................................................................................. 26 TABLE IV  VALUES OF COST VARIABLES .................................................................................................. 27 TABLE V DESCR.WI10N OF EXPERIMENTAL CONFIGURATIONS ......................................... .......................... 31 TABLE VI  REsUlTS CONSIDERING RC MEASURE ................................................................................... 33 TABLE VII  REsm.. TS OF SAMPLE EXPERIMENT (6) ..................................................................................... 34 TABLE VIII  TARDINESS RESULTS .. .......................................................................................................... 37 TABLE IX  EARLlNESS RESULTS ........................... ........... ............... ........................ .................... ................ 37 TABLE X  ABSOLUTE DEVIATION FROM DUE DATE REsULTS ...................................... . .............................. 37 TABLE XI  DESCRIPTION OF A ITRIBUTES AND GLOBAL VARIABLES ........................... ............................... 68 vii LIST OF FIGURES Figure Page FIGURE 1  MODELING TARDINESS PENALTY COST ...................... . ...................................................... ...... 20 FIGURE 2  WARM UP ANALySIS ........................... ... ., ...... .................... ..................................................... 29 FIGURE 3 Ra.ATlVECOST RESULTS AT LOW UTILIZATION .............. . ........................................................... 35 FIGURE 4  RELATIVE COST REsULTS AT HlGH UTILIZATION ................. ...... .................. ............................. 36 FIGURE 5TARDINESS REsULTS ............................................................................... .............. " .................. 38 FIGURE 6  ABSOLUTE DEVIA TJON FROM DUE DATE REsULTS ............................................................. ...... 38 FIGURE 7 EARLINESS REsULTS .......................................................................................... ...................... 39 FIGURE 8  RELATIVE COST VERSUSZ FOR EXPERIMENT 1.. ......................................................................... 41 FIGURE 9 RELATIVE COST VERSUS Z FOR EXPERIMENT 2 .................................................... ...................... 41 FIGURE 10 RELATIVE COST VERSUS Z FOR EXPERIMENT 3 ....................................................................... .41 FIGURE 11 RELATIVE COST VERSUS Z FOR EXPERIMENT 41 .............................. .................. ......... .............. .42 FIGURE 12 RELATIVE COST VERSUS Z FOR EXPERIMENT 5 ........................ .................................................. 42 FIGURE 13  RELATIVE COST VERSUS Z FOR EXPERIMENT 6 ...................................................................... .42 FIGURE 14  RELATIVE COST VERSUS Z FOR EXPERIMENT 7 .......................................................................... 413 FIGURE 15  RELATIVE COST VERSUS Z FOR EXPERIMENT 8 ...................................................................... .43 FIGURE 16  RELATIVE COST VERSUS Z FOR EXPERIMENT 9 ...................................................................... ,43 FIGURE 17  RELATIVE COST VERSUS Z FOR EXPERIMENT 10 ..................................................................... 44 FIGURE 18  RELATIVE COST VERSUS Z FOR EXPERIMENT 11 ..................................................................... 44 FIGURE 19  RELATIVE COST VERSUS Z FOR EXPERIMENT 12 ..................................................................... 44 FIGURE 20  TARDINESS VERSUS Z FOR EXPERIMENTS 1 AND 2 ................................................................... 45 FIGURE 21  TARDINESS VERSUS ZfOR EXPERJMENTS 3 AND4 ................................................ . ........ ......... 45 FrGURE 22  TARDINESS VERSUS Z FOR EXPERIMENTS 5 AND 6 ................................................................. ,45 viii FIGURE 23  TARDINESS VERSUS Z FOR EXPERIMENTS 7 AND 8 ................................................................. .46 FIGURE 24  TARDINESS VERSUS Z FOR EXPERIMENTS 9 AND 10 ................................................................. .46 FIGURE 25  TARDINESS VERSUS Z FOR EXPERIMENTS 11 AND 12 ............................................................... 46 FIGURE 26  EARLINESS VERSUS Z FOR EXPERIMENTS 1 AND 2 ................................................................. .47 FIGURE 27  EARLINESS VERSUS Z FOR EXPERIMENTS 3 AND 4 ............. ..................................................... 47 FIGURE 28  EARLINESS VERSUS ZFOR EXPERlMENTS 5 AND 6 .................................................................. 47 FIGURE 29  EARLINESS VERSUS Z FOR EXPERlMENTS 7 AND 8 ............................. ...................................... 48 FIGURE 30  EARLINESS VERSUS Z FOR EXPERIMENTS 9 AND 10 ....................... ........................................... .48 FIGURE 31  EARLINESS VERSUS Z FOR EXPERIMENTS 11 AND 12 ............................................................. ..48 FIGURE 32  ABSOLUTE DEVIATION FROM DUE DATE VERSUS Z FOR Exp. 1 AND 2 .......... ................ .......... 49 FIGURE 33  ABSOLUTE DEVIATION FROM DUE DATE VERSUS Z FOR Exp. 3 AND 4 .................................... 49 FIGURE 34  ABSOLUTE DEVIATION FROM DUE DATE VERSUS Z FOR Exp. 5 AND 6 .. .................................. 49 FIGURE 35  ABSOLUTE DEVIATION FROM DUE DATE VERSUS Z FOR Exp. 7 AND 8 .................................... 50 FIGURE 36  ABSOLUTE DEVIATION FROM DUE DATE VERSUS Z FOR Exp. 9 AND 10 .............. .................... 50 FIGURE 37  ABSOLUTE DEVIATION FROM DUE DATE VERSUSZ FOR Exp. 11 AND 12 ................................ 50 FIGURE 38  SYSTEM REPRESENTATION .......................... ........................ . ......... . ........... .. .......................... 62 FIGURE 39  SLAM NETWORK MODEL ............... ...... ........................... .............................................. ......... 69 ix I The Problem and its Setting Introduction Organizing shop floor activities is an important task that affects the overall performance of a manufacturing enterprise. One of these activities is scheduling the jobs that are to be processed on the machines on the shop floor. In this research, we consider the scbeduling problem in a job shop environment. A maketoorder system is studied. Each job has its own due date, and if a job is fmished before its due date, it waits until its due date before being shipped to the customer. This characteristic is commonly referred to as forbidden early shipment. Job shops are one of the most popular shop floor structures in industry. Therefore, exploring the potential of improving the cost performance of job shop manufacturing is of high importance for both researchers and practitioners. Considering that the industrial community is giving considerable attention to speed and agility in the decade of the 90' s, it is justifiable that scheduling deserves significant study and research from the industrial engineering research community. In the decade of the 70's, technology was the key for a successful manufacturing business. The factors that affect the investment in technology (such as automated manufacturing systems or robots) were easily quantified in tenns of fmancial measures. Therefore, the process of justifying such investments was relatively easy. On the other hand, quality was the key word of a successful manufacturing business in the decade oftbe 80's. It was more difficult to measure the performance of a manufacturing system in terms of fmancial measures if quality was the aspect of concern. However, the existence of functions such as the Taguchi loss function helped to bridge the gap between technical ] and financial performance measures. For example. a technical performance measure such as variation from targiet can be related to financial performance measures such as cost. However, in tenns of the decade of the 90's, where the primary concern is time to market, the gap between technical and fmancial performance measures is not fully bridged. Considering that leadtime is a technical measure of speed or agility, the effect of reducing the leadtime is not easiJy quantified in tenns of cost or profit. Hence, an investment that leads to reducing the leadtime may not be fmancially justified. Also, there are other performance measures that are considered in a scheduling problem in addition to the leadtime such as inventory level, lateness and tardiness. Improving one of these performance measures may, and in many cases does, affect other performance measures. However, the trade off between these measures is not clearly understood. Dispatching Rules Dispatching rules are a popular technique in scheduling. Dispatching rules are simple heuristics that enable the decisionmaker to choose which job to load on a machine (if more than one is available) once it becomes idle. Dispatching rules are also known as sequencing rules. In this research, the terms dispatching rules and sequencing rules are used as synonyms. Dispatching rules provide good results and they are widely used because of their simplicity. Previous research fmdings in this area show that the dispatching rule that provides the best performance depends on system variables such as due date tightness, tardiness cost and inventory cost. 2 Performance Measures Different performance measures are being used in this research area. These performance measures can be divided into two basic categories.. The frrst category is time based performance measures, such as tardiness, earliness, absolute deviation from due date, throughput, time in system, average number of jobs in queue, and several other measures. The second category of measures is monetary based measures such as total cost per period and net present value. In this research, the primary performance measure of concern is a monetary based performance measure, which is relative cost per job (tms term is briefly de·f1ned later in this chapter and tborougbly discussed in Chapter IV). However, the cost perfonnance of a system is highly sensitive to the cost structure. Therefore, time based performance measures are monitored as supplementary performance measures to avoid any bias in results caused by the cost structure. Problem Statement The sequencing problem in previous research efforts is modeled as a problem that has a continuous action range (the setting of system parameters), and a discrete reaction domain (available sequencing rules). This inconsistency represents a potential problem and an area of research opportunity. This research attempts to model this problem as a problem that has both continuous range and continuous domain. Therefore, the objective ofthls research can be stated as to "investigate the potentia] of improving the performance of manufacturing systems through introducing a sequencing rule that has a continuous decision domain". 3 Definition of Terminology We defme here some of the key terminology used in this research. Leadtime: Lead time for a job j is defined as the difference between the due date of job j and the order arrival date of job j. Relative ,cost: relative cost fDr a job j is defmed as the total incurred co.st by a job (due to. inventory holding cost and tardiness penalty cost) divided by its selling price. Forbidden early shipment: If a job is co.mpleted before its due date, the job is stored in a storage area until its due date. In this research,. the cost associated with completing a job before its due date is the cost of holding this job as inventory. No. other penalties are realized as a consequence of completing the job early. However, the holding cost of fmished goods is higher than the holding cost of workinpro.cess. 4 II Literature Review Introduction In this chapter, a review of re]ated literature is present.ed. This review focuses on the research that studies job shop scheduling in a forbidden early shipment environment considering economic performance measures, since this is the area of concern in this research. The scheduling problem has several aspects including order review and release rules, due date setting and sequencing. The sequencing aspect of the scheduling problem is reviewed in this chapter. Other aspects of the scheduling problem are not reviewed since they are not relevant to this research. The literature review is divided mto three sections. First, different methodologies for modeling the fmancial aspects of the scheduling problem are reviewed. Next, the sequencing problem is considered. Finally, different experimental designs are reviewed in order to help designing the experiment of this resesrch. Literature Review aD Constructing Cost Models Most studies in this field consider tardiness cost and inventory carrying cost as the two basic cost segments that are affected by scheduling policies. However, the implications of these two factors have been modeled differently. Ragatz and Mabert (1988), Ahmed (1990),. Ahmed and Fisher (1992), and Philipoom et al. (1993) use the same cost structure. The performance measure used in these studies is total cost per period. Holding cost is calculated as a proportion of the work completed on ajoh (constant per week per hour processing time completed). This assumption means that no cost:i:s associated with holding raw materials, which might not be a realistic assumption. Tardiness penalty cost is considered as a proportion of the 5 holding cost (constant per week per hour processing time completed). The ratio between holding cost and tardiness penalty cost in these studies is 1 :20. Other ratios are used for sensitivity analysis. In addition, tardiness penalty in this cost structure is proportional to the work content. Considering that due date allowance is proportional to the work content, the oost structure that is used in the above mentioned studies results in a proportional relationship between due date allowance and tardiness penalty. In the: current study, we explore a more realistic tardiness penalty; one that is proportional to some measure of relative tardiness, such as tardiness divided by leadtime. Rohleder and Scudder (1992) use net present value as the perforIDalnce measure. They evaluated the inventory holding cost as a proportion of the job cost. Also in their study, there is no inventory cost associated with bolding raw materials in stock. The job cost is calculated as the cost of operating the machines (induding setup cost) that ajob has visited. They use a holding cost ratio of 20% ofthe inventory value per year (i.e., 20% of the job value will be incurred as inventory cost if a job waits for one year). The tardiness cost in their study is calculated as 10% of the selling price per year. Scudder et a1 (1993) use the same cost structure but modify the holding cost ratio to be 30% and the tardiness penalty ratio to be 20%. Scudder et al. (1990) also use net present value as the performance measure. In their study, the inventory holding cost is proportional to the job value. They also defme the job value as the cost of machine set up and the cost of machine operation. The researchers assume a justintime environment where raw materials arrive at the time of the flrst operation. Hence, there is no holding cost for raw materials. Two levels of tardiness penalty cost are explored. The flrst level is zero, i.e., there is no penalty 6 associated with late delivery. The second level is at 25% of job cost per day. This ratio may represent a highly perishable product considering that the average work content is 36 working hours. The same cost structure is used by Yang and Sum (1994). In a study by Amar and Xio (1997), the authors present an analytical model to minimize total cost in a static job shop (no order arrivals). The authors in this study consider inventory cost only. The authors show that a linear approximation of the time value of money effect is reasonable. The resulting cost structure, after neglectitng the compounding effect of interest, is a linear relationship between holding cost and the inventory value multiplied by the waiting time. Kawtununachai et al. (1997) study static scheduling in an automated flow shop. In their study, tardiness is handled by working overtime. Therefore, the actual tardiness penalty is the extra cost of overtime. Inventory holding cost is divided into two segments. First, workinprocess (WIP) inventory cost and second, [mal product inventory cost. WIP cost is proportional to the number of jobs in system multiplied by average holding time. The [mal product inventory cost is proportional to the number of fmished goods multiplied by the time finished goods wait for their due date. The difference between the two types of inventory cost is the holding cost factor. The average ratio of bolding cost factor for fmished goods to holding cost factor for WIP is approximately 15, which is high relative to other research efforts. Different cost structures have been introduced in the literature, several of which have been reviewed above. Most of these cost structures are based on quantifying inventory holding cost and tardiness penalty cost. Some researchers introduce time value of money into the cost structure. However, the effect of compounding discounting rates 7 has not been shown significant (Amar and Xio, 1997). The inventory and penalty cost that have been used in literature can be expressed in the following generic form: I j = !(Vj,t) where; Ij: the inventory cost for job j Vj: the value of job j t/ the time job j spent in the system and where; Pj: is the tardiness penalty of job j dj: The time job j departed the system DD/ Due date of job j The following points describe the basic differences between different cost structures: 1. differences in the methodology used to estimate the job value through the cycle time, 2. differences in the relationship between tardiness penalty cost and inventory holding cost, and 3. differences in the cost difference between holding finished goods and WlP. In the reviewed liteIatu~e, tardiness penalty depends only on the job value and absolute tardiness. This research explores a more realistic cost structure by expressing the tardiness penalty as a function of job value and relative tardiness. The details of this approach are discussed in Chapter IV. 8 Literature Review on Sequencing Rules Sequencing jobs on available machines has received considerable attention in the literature. Many sequencing rules have been proposed. However, few studies are found in the area of this research, which is job shop scheduling in a forbidden early shipment environment considering economic performance measures. In this section, sequencing rules that have been used in forbidden early shipment environments considering fmancial performance measures are reviewed. Sequencing rules in this area can be divided into two major types. The fIrst type is time based sequencing rules, and the second is monetary based sequencing rules. In general, time based rules perform better than monetary based rules (Hoffmann and Scudder 1983, Scudder and SmithDaniels 1989, Scudder et aI. 1990). Time based sequencing rules are the rules that use the time attributes of jobs to decide job priorities. Table I illustrates the sequencing rules that have been used in this research area A survey of sequencing rules can be found in Panwalkar and Iskander (1977). The rules listed in Table I are jobdependent rules. In some research, the authors use the operationdependent versions of these rules. For example, the operationbased version of SPT is to give the priority for the job that has the shortest operation processing time rather than shortest remaining processing time. In general, critical ratio (CR) has been found to be the dominant rule that performs best in forbidden early shipment in most shop structures (Ragatz and Mabert 1988, Scudder et. al 1990, Rohleder and Scudder 1992, Ahmed, 1990 and Ahmed and Fisher, 1992). 9 Sequencing Rule Description FCFS (First Come First Served) Process the job that arrived first to the queue SPT (Short'est Processing Time) I Prooess.the ~ob that has the least total remaining I . processmg tJDle CR (Critical Ratio) I Process the jOb that has the least critical ratio CR= (Time remaining until due date)! (Total rernainiI!Kprocessing time.) EDD (Earliest Due Date) Process the job with earliest due date N1DD (Modified Due Date) Process fIrst the job that has the earliest modified due dat.e. Modified due date is defmed as the maximum of job due date and its ear[y fmish time. Early [wish time is defmed as current time plus total remaining processing time. Table I  Summary ()f Relevant Time Based Sequencing Rules In the study by Ragatz and Mabert (1988), CR perfonns the best regardless of due date tightness and utilization level. In some cases, EDD and CR perform the same statistically (the authors did not specify these cases). In the case of 1; 1 cost ratio between inventory cost and lateness cost, EDD dominates other sequencing rules in providing the lowest cost. In the study of Ahmed and Fisher (1992), EDD and CR are found to be the best rules in most cases depending on the release mechanism and due date setting rule. Their study concentrates on the interaction between sequencing rules, due date assignment rules and release mechanism. Philipoom ,et al (1993) reach interesting results that are not oonsistent with other literature. They compare the perfonnance of SPT ta CR under different conditians .of due date tightness, machine utilization and release rules. Their results show that SPT out performs CR in most cases. CR is better only in the case of loose due date setting. The authors conclude that this inconsistency with the literature might be attributed to the high 10 tightness level used. In addition, as the ratio between penalty cost and inventory cost is reduced (1: 1), CR outperforms SPT in both loose and medium due date tightness. Scudderet al. (1990) also find CR to be the best rule, yielding the highest net present value in most of the cases they studied. CR ratio is compared with monetary basedmles. Scudder et al. (1993) fmd that operation based rules performs better under tight due date conditions, but as due dates are relaxed, job based rules perfonn better. They fmd that CR based rules and modified due date (MDD) perform the best considering NPV criterion. The results of this research are consistent with a previous work of Rohleder and Scudder (1992). Monetary based rules are the rules that use the financial information of jobs. Several researchers have examined monetary based rules. The general findings in this area show that time based rules perform better than monetary based rules (Scudder et al. 1990). Yang and Sum (1994) introduce two new rules that performed better than CR. The rules they introduce combine CR and tardiness penalty of the job. Their rules consist of a threshold based on the critical ratio. The jobs that have critical ratio above the specified threshold are scheduled based on weighted critilcal ratio (WCR) defined as follows: WCR= CRJHourly tardiness cost In their study, job value and processing time for a job are sampled from independent distributions, which might give an advantage to the rule they introduced since it considers both processing time and job value (by considering tardiness cost). 11 However, if job value is considered to be proportional to the processing time,. then the hourly tardiness cost will be proportional to the processing time and their rule becomes: WCR= CRffotal. processing time = Time remaining until due date/ (remaining processing time*total processing time) The above rule is a modification of the critical ratio rule by modifying the weight of the processing time in the critical ratio rule. However, the improvement achieved by Yang and Sum ( 1994) is not definitely attributed to modifying the critical ratio rule. The problem scenario in their research, which samples the job vaIue and work content from independent distributions, may have affected the results. In general, many researchers categorize dispatching rules according to their information content. For example, Chang et aI. (1996), divide dispatching rules into, shortest processing time based rules, longest processing time based rules, due date based rules, slack based rules and queue status based rules. The results of choosing the best sequencing rule are usually attributed to the information content of the sequencing rules. Chang et aI. conclude that if tardiness is the performance measure of concern, a due date based rule work the best. They also conclude that a shortest processing time based rule is the best rule to choose if completion time or flow time is the major perfonnance measure of concern. Using the same concept, Montazeri and Wassenhove (1990) conclude that shortest processing time based rules minimize waiting times. The review of research in this area shows critical ratio (CR) perfonns the best in most configurations. Other rules that performed well in the literature are EDD and to a lesser extent SPT. The literature suggests that the most important factors that affect the 12 performance of sequencing rules are due date tightness level, system utilization, and cost structme of the system. The best sequencing rule can be changed as the operating conditions change. Pierreval and Mebarki (1997) introduce a strategy that selects the sequencing rule based on the system conditions andlor based on the performance measure considered. Also, Wu and Wysk (1989) introduce an algorithm that allows selecting the sequencing rule for each short period. In both of these research efforts, the selection of the best sequencing rule is limited to the available sequencing rules. Also, at each change oppurtunity, the decision is either to change the current rule or stay with the current rule. Therefore the decision has discrete a domain in these cases. Literature Review on Experimental Design The objective of this section is to belp in designing the job shop structure that will be studied in this research. A Job Shop is defined by APICS (1970) as follows: "A flllnctional organization whose departments or work centers are organized around particular types of equipment or operations, such as drilling, forging, spinning, or assembly. Products flow through departments in batches conesponding to individual orders, which may be either stock orders or individual customer orders." Tbe factors that affect the job shop structure are the following: 1. tbe number of machines in the job shop, 2. the number of operations and the routing of each job, 3. the utilization level, order arrival process and prooessing time, and 4. the due date setting procedure. 13 Number of machines: Most researchers use environments with the number of machines between five and nine. Ragatz and Mabert (1988), Vig and Dooley (1991) and Ahmed and Fisher (1991) study a fivemachine job shop. Christy and Kanet (1990), Kanet and Christy (1989) study an eightmachine job shop environment. A model that is introduced by Hoffmann and Scudder (1983) consists of nine machines. This model has been used in several reseatrch efforts thereafter, e .. g., Rohleder and Scudder (1992) and Yang and Sum (1994). Philipoom et al. (1993) use a ISmachine job shop as an experimental environment for their reseatrch. Routing and number of operations: In most of the related literature, the average number of operations per job is either four or five operations in most cases. For example, in the study by Philipoom et al. (1993), the number of operations is sampled from a uniform distribution ranging from three to seven operations.. Also, in the often used model introduced by Hoffmann and Scudder (1983) the number of operations varies from two to seven with an average of four (no more information about the probability distribution is given). In the above studies, reseatrchers use random routing. Each machine bas the same probability of being visited next once a job compietes one of its operations. Revisiting is aUowed but not consecutively. This purely random routing represents a more difficult control problem and any bias introduced by this purely random flow should be considered in the conservative direction (Ragatz and Mabert, 1988). Order arrival processing time and utilization: Consistently, the arrival process follows a Poisson process in the reviewed literature. However, different distributions were used to model the processing time. Philipoom et al. (1993), Ahmed and Fisher 14 (1991), and Ragatz and Mabert (1984) use an exponential distribution to model the processing time. Vig and Dooley (1991) use a 2Erlang distribution. Hoffmann and Scudder (1983) use a truncated DOnnal distribution with a standard deviation equal to one ninth of the mean. The variance is increased by other researchers who studied the same system, e.g., Rohleder and Scudder (1992) who use a standard deviation equal to one third of the mean. The mean interarrival time and the mean process time are set to achieve a desired level of utilization. The above researchers use utilization levels between 85% and 93%. In most of the above research, preemption, breakdown, and splitting of jobs are not considered. Also,. setup time is usually included in processing time. Only Hoffman and Scudder (1983) explicitly consider setup time in their model Due Date Setting: Many procedures are used in literature to set due dates. Excellent reviews of due date setting mechanisms can be found in Ahmed (1990), Cheng and Gupta (l989), and Ragatz and Mabert (1984). The rule that shows the best performance in different settings is total work content (Kanet and Christy 1989, Baker 1984). Therefore,. most of the research in this area use a TWK rule (e.g., Ragatz and Mabert, 1988, and Philipoom et al. 1993). TWK is defmed as follows: DD. =a.+k~n p .. 1 } ""'';=1 l) where; DDj : is the due date of job j aj: Arrival time of job j Pij: is the processing time of operation i for job j k: allowance factor 15 n: number of operations Different procedures are adopted in the literature to select the value of k. In general. researchers study three values of k that result in three due date tightness le¥els, loose, medium and tight. Ragatz and Mabert (1988) choose the values ofk such that the ....... resulting number of tardy jobs is 5%, 10%, and 20% for loose, medium and tight due dates respectively when FCFS is used. Yang and Sum (1994) use the same procedure but they use CR instead of FeFS. Philipoom et aI. (1993) use a k value ranging from 4.3 to 10.9. Baker and Kanet (1983) use allowance factor values between 2.5 and 20. Conclusion The literature review shows that the selection of best sequencing rule depends on the systems parameters. Although the change in system parameters has continuous range. the response (selecting tbe best sequencing rule) has a discrete domain. The research gap that this research attempts to fill is providing a mechanism that quantifies the response domain (selecting the best sequencing rule) over a continuous range. 16 ill Research Goals and Objectives The main goal of this research is to introduce a sequencing rule that has more flexibility than existing sequencing rules. One important characteristic that is need,ed in such a rule is that it should have a continuous decision domain. In this research, we propose a modified critical ratio rule CRz• We defme the modified critical ratio rule as follow where; CRz: is the modified critical ratio DD/ is the due date for job j rpj: is the remaining processing time for job j t: is the current time z: a power factor The value of the power factor z is to be determined as a function of system parameters. Consider the following two values of the power factor (z); zero and one. These values of z will result in the following. 1. If z is set to zero, CRz yields DD.t CR = J =DD. _to z 0 J' (rpj) Which is the EDD rule 2. If z is set to one, CRz yields 17 CR z DDjt _ DDit.  , 1 (rpj) (rpj) Which is the CR rule. The above cases show that using an appropriate value of z, the modified critical ratio rule yields decisions consistent with EDD or CR. Using other values of the power factor z, over its continuous range,. yields other (hopefully superior) sequencing decisions. Research Objective The primary objective of this research is to mvestigalte the potential of improving the cost performance for a given job shop using the modified critical ratio rule. The effect of three factors on z value will be studied in this research. These three factors are due date tightness., cost structure and machine utilization. Tasks The tasks required to accomplish the research goal are the following. 1. develop the job shop model and the cost structure, 2. develop the simulation model, 3. perform pilot runs to fmalize experimental factors, 4. execute the simulation experimental design, 5. analyze the simulation results, 6. develop the empirical formula of the power factor z, 7. develop conclusions and reconunendations, 8. document the research, and 9. identify areas of future research. 18 IV Research Methodology Simulation is the evaluation tool in this research. Simulation is widely used in this research area since developing analytical solutions for job shops with dynamic arrivals is difficult and requires many assumptions. In order to use simulation as an analysis tool, we developed a job shop model to be used in this research. The SLAM II simulation language (Pritsker, 1995) is used to simulate the job shop. The job shop was developed to be consistent with other literature based model. In addition, the literature has been considered in developing the cost structure. However, we propose a ma:jor modification in modeling the tardiness penalty. Traditionally, tardiness penalty has been calculated as a function of job value and absolute tardiness. In this research, we consider the tardiness penalty as a function of job value and relative tardiness. Relative tardiness will be modeled with respect to leadtime. As discussed in the literature review, tardiness penalty cost and inventory holding cost have been modeled in the following generic forms: In this research, the inventory carrying cost will follow the same generic form. However, the tardiness penalty cost will be modeled as P=f[V {d'J DDJ. }] } J' DD·a. } } where; /j: the inventory cost for job j; Vj: the value of job j.; 19 Pj: is the tardiness penalty of job j; dj: The time job j; departed the system; DDj: Due date of job j; and aj: the order arrival time of job j. Figure 1 illustrates how the tardiness penalty cost is modeled. Ajob will accumulate tardiness penalty cost equal to its selling price if it is late for a period proportional to its lead time. The constant pt shown in Figure ~ is defined as the penalty tightness factor. Two levels of penalty tightness factor (pt) are studied in this research; I and 2. If the penalty tightness factor is set to 1, it means that ajob wiu mcur tardiness penalty cost equal to its selling price if it is late for the period of its lead time. Similarly, a job will incur tardiness penalty cost equal to its selling price if its lateness is twice its lead time, when pt is set to 2. Revenue Selling Price Delivery Date I Lead Time '" pt I Figure 1  Modeling Tardiness Penalty Cost Assumptions The following assumptions are made in this research. • Machine breakdown is not considered. 20 • No scrap or rework is taken into account. • Queue capacities are infmite. • Preemption is not allowed. • Setup time is included in the work content of each job. • Time value of money is included in the holding cost and penalty cost factors. • Jobs are released to the shop floor immediately after receiving the order. • The cost structure is valid in environments where relative tardiness is valid as a performance measure. Job Shop Description In this research. we study a job shop that consists of seven machines. Orders arrive for one unit of each product. Each product is unique therefore, setup time is included in processing time. The number of operations required to complete a job is sampled from a discrete uniform distribution from three to seven operations.. The duration of each operation for a job is sampled independently from a uniform distribution of [3.5, 6.5] time units. Routing of jobs is set randomly such that ajob has the same chance of visiting any machine except the machine that is visited at the current operation. Therefore, revisiting is allowed but not consecutively. InterarrivaI time of orders is exponentially distributed. The mean of the exponential distribution is set so that the desired utilization level (an experimental factor) is achieved. The mean oftbe interarrival time is set according to the following equation A = lAp Q J1 where; Ao: is the order interarrival time 21   J.l:: is the average processing time p: is the desired machine utilization. A complete derivation of the above equation can be found in Appendix 1. After all operations are completed for a job, the job will wait if it is completed before its due date. Otherwise, the job will leave the system. Due dates are set on one of three levels; loose, medium and tight. The Total Work Content method (TWK) is used to set the dates. The value of the constant k is chosen to be 3,6 and 9 to generate loose, medium and tight due dates. Some researchers set the due dates tightness based on the number of tardy jobs. For example, Ragatz and Mahert (1988) set the levels of the allowance factor k so as 5%, 10%, and 20% tardy jobs are achieved when FCFS sequencing rule is applied. In this research, we refrained from following this procedure since the percentage of tardy jobs does reflect the actua1 performance of tbe manufacturing system of concern in this research. The percentage of tardy jobs depends on the sequencing rule appJlied at the queues. Also, average tardiness is not correlated with the number oftardy jobs. A given sequencing rule might produce low percentage of tardy of jobs which indicates that the due dates are loose, however, the average tardiness produced by this rule may he high which contradlicts the conclusion that the due date are loose. The selling price (Sj) of each job is linearly proportional to its processing time. The raw material cost of a job j (Rj ) is 30% of its selling price (Sj) and the value added to each job is 20% of its selling price. The value added at each operation is proportional to the proportion of work content completed at this operation. This cost structure assumes that 50% of the seUing price is aUocated for profit and overhead expenses. Also, it is 22 assumed that 25% of the selling price is allocated for overhead expenses and 25% is allocated for profit. After a job is completed, its value is 75% of its selling price (Sj), which includes raw .material cost, value added, and overhead expenses .. The job value is increased instantaneously after an operation is completed. The job value is used to calculate the inventory value. The various percentages in this approach were set arbitrarily but are believed to be representative of realistic scenarios. Cost Stmcture The performance measure in this research is average relative cost per job as defmed below. where: RCj: average relative cost per job Tej : total incurred cost for a job j. The total incurred cost is the sum of inventory holding cost and penalty cost. ~.: the selling price for job j Two types of costs are considered in this research. First, the inventory holding cost and second the penalty cost. As discussed in the literature review, these two segments are the two major segments that have been introduced in the literature .. The inventory holding cost per job is defined as follows: where; dj I j = f HVjdt rj 1/ is the inventory holding cost for job j 23 H: is the ho ldim:g cost factor "}: is the value of job j Tj: is the release time for job j (the time at which job j is released to the shop floor) dj: is the time job j departed the system. Since the system of concern is a discrete system, the above integration can be expressed as follows: ,,+1 1 j = I. Ifti;,itj,i  t i_I ,}) i=l where; lj: is the inventory holding cost for job j; H: is the holding cost factor; V;,/ is the value of job j before being processed on machine I;. and t;,j: is the time at which job j leaves machine i, !oj = rj. Note that Vi,} is the cost of raw material for job j (Rj). The storage area where jobs wait until their due date is modded as the machine number (n+ 1). The value of a job in the storage area will considered 75% of the selling price for the purpose of estimating the holding cost in the storage area. The value of H will be set so the raw material of an average job (5 operations, 5 days each) will incur 5% of its selling price, iftbe raw material is stored for the period of the job's lead time. The holding cost ratio will vary between 2.7% (for a job that needs 3 operations, 3.5 days each) and 9.1 % (for a job that needs 7 operations, 6.5 days each) according to this configuration. The second segment of cost that is considered is the penalty cost caused by missing a due date. The penalty cost is defmed as follows: 24 Where; Pj: is the penalty cost for job j; Pj: is the penalty cost factor for job j; , '1 DDj: is the due date for job j; and I , 'I dj : is the time job j departed the system. The value of the factor pj is set so that the tardiness penalty cost is proportional to the job's leadtime. The factor pjis calculated as follows: where; Sj: is the selling price of job j pt: is the level of penalty, when pt =1, the penalty cost is equal to the selling price if a job tardiness is equal to its lead time. Pj: is the penalty cost factor for job j DD/ is the due date for job j aj: is the arrival t.ime for job j Example Consider a simplified system that consists of two machines. The initial conditions are idle and empty. The value ofH is 0.01. Two jobs are considered and their attributes are shown in Table II. 25 I Ii Job 1 Job 2 Arriving time 0 2 Routing 12 21 Processing Time on maclhine 1 10 1 Processing Time on machine 2 5 I J 1 Due Date 45 8 Selling price ($) 75 10 Table II  Example Description Table ill describes the events each job goes through: Time · Event 0 Job 1 starts its frrst operation on machine 1 2 Job 2 starts its fIrst operation on machine 2 3 Job 2 finishes its fast operation and waits tor machine 1 10 Job 1 fmishes its first operation and starts its second operation on machine 2 10 Job 2 starts its second operation on machine 1 11 • Job 2 finishes its second operation and leaves the system 15 Job 1 fmishes its second operation and waits until its due date 45 Job 1 leaves the system Table In  Description of Events Note that Job 1 finishes 30 time units early and Job 2 fmishes 3 time units late. Table IV shows the cost variables that willlbe used to calculate the cost of each job. The variables shown in Table IV are calculated using the approach described in the previous section. After identifying all tbe cost variables, the relative cost ratio for each job is calculated as follows. For Job1: ,,+1 II = L.~.l (ti ,1  ti_I .I ) i=1 = 0.01(22.5)(10) + 0.01(30)(5) + 0.01(56.25)(30) = $20.63 ~ = PI[dl  DDI r = 0.08333(0) = $0.00 Tel = $20.63 26  ReI = 26.63n5 = 27.5% The interpretation of this number is that the sum of inventory cost ($20.63) and tardiness penalty cost ($.00) is 27.5% ofthe selling price ($75.00) For job 2: n+1 /2 = LHV;,2(ti,2 ti  1,2) ;=1 = 0.01(3)(1) + 0.01(4)(10) + 0.01(7.5)(0) = $0.70 TC2 = 0.70 + 2.50 = $3.20 RC2 = 3.2/10 = 32% Variable Description Value RI Raw Material Cost of Job 1 $22.50 R2 Raw Material Cost of Job 2 $3.00 jJI Penalty cost factor for job 1 $0.8333/ time unit P2 Penalty cost factor for job 1 $0.8333/ time unit Vl,l Value of Job 1 before being processed on machine 1 $22.50 , V21 Value of Job 1 before being 'Qfocessed on machine 2 $30.00 V3.1 VaIue of Job 1 after completing all operations $56.25 V2.1 Value of Job 2 before being processed on machine 1 $3.00 V2~ Value of Job 2 before being processed on machine 2 $4.00 V3,2 Value of Job 2 after completing all operations $7.50 Table IV  Values of Cost Variables Research Factors The effect of the following factors on cost performance will be considered: 1. due date allowance factor (k), 2. penalty tightness Cpt), 3. power factor z, and 4. system utilization. 27 L < Due date allowance factor levels are 3,6, and 9. Two levels of penalty tightness are considered, pt = 1 and pt = 2. The effect of utilization is studied on two levels of 85% and 92%. At each of these combinations, the value ofz that yields the best performance measure ofconcem is determined experimentally. Simulation Model The SLAM II simulation language is used to simulate the job shop described above. All the job's attributes are assigned at the time the job arrives to the system. This ensures that jobs in different simulation scenarios have the same attributes. Therefore, the simulation runs are dependent due to common random numbers and a paired ttest can be used to establish desired conclusions. A paired ttest is stronger since it eliminates the variation between simulation runs due to using different random number streams in djfferent runs. A complete description of the simulation model can be found in Appendix 2. Simulation Characteristics Three characteristics are important to ensure good simulation results. These are run length, warm up period and number of replications. Warm up period is specified by observing variation of the performance measure (average relative cost) with run time. The procedure described in Law and Kelton (1991) was foUowed to determine the length of the warm up period. The number of replications we used to apply this procedure is seven replications. Also, we ased a window length w of 800. The time after which the relative cost values are stable (plus a safety factor) is set to be the warp up time. Figure 2 shows the moving average of the performance measure. As shown in Figure 2,. the average relative cost is observed to stabilize after 3,000 to 28 c 4,000 jobs leave the system However, since execution time was not a major limitation in this study, a conservative warm up period of approximately double this number of jobs is used. The warm up time is set at 30,000 time units which corresponds to approximately 7,500 jobs. Warm up Analysis 1400 1200 1000 CJ 800 a: 600 ~ r.... r~ ...............  I '" 'v'"" ......./ "' I 400 200 0 o 5000 10000 15000 20000 25000 Job Number Figure 2  Wann up Analysis The run length is determined to be 400,000 time units. This run length is longer than the recommended rule of thumb that suggests a run length equal to ten times the warm up period. The number of replication used in each run is 10 replications. The above values were acceptable after analyzing the simulation results. The results based on the above characteristics were found accurat,e enough to establish conclusions based on a paired ttest. The above parameters (run length and number of replications) were chosen so that the performance of different sequencing rules will be statistically different using a paired t test. Simulation Verification and Vatidation Verification is the process of ensuring that the simulation program is executed properly. Tracing is a very effective tool to perform the verification process. Extensive tracing reports were generated. Entities (jobs) were traced to ensure that the entities went 29 « through the proper sequence of events and the proper assignment of attribute values. Also,. tracing reports showed that priority was given to a job in the queue according to the intended dispatching discipline. Validation is the process of ,ensuring that the model is representing the real system. Since there is no existing real system that can be used to compare the simulation results, the validation process can not be conducted in this manner. Validation has been conducted by comparing the simulation results with similar published research results. Consistence with the literature, the critical ratio rule was found to perfonn the best in most cases, also the shortest processing time was found to be the best rule under very tight due date conditions. Also, the simulation output indicated that the utilization level of the machines, average processing time, and average number of operations corresponded with the expected values. 30 I L c V Results As discussed previously, 12 different system configurations were studied. Table V describes the value of each experimental factor for each of these configurations. Experiment K (due date allowance factor) U (Utilization) pt (penalty tightness factor) ] 3 85% i 1 2 3 85% 2 3 3 92% 1 4 3 92% 2 5 6 85% 1 6 6 85% 2 7 6 92% 1 8 6 92% 2 9 9 85% 1 10 9 85% 2 I 11 9 92% 1 , 12 9 92% 2 Table V Description of Experimental Configurations For each experiment, multiple values of the power factor z were evaluated. These values included zero and one, to generate results equivalent to the EDD and CR rules. In addition, the SPT rule was evaluated (not using the CRz formulation). A search for the best value of z based on relative cost performance was conducted.. A statistical comparison of the perfonnance of modified critical ratio rule at the best identified z value and the SPT, EDD, and CR was conducted using a paired ttest. The primary performance measure of this research is relative cost. Other time based perfonnance measures are monitored to assure that the superior performance of the modified critical ratio is not influenced by the cost structure introduced in this research. The time based performance measure monitored are tardiness, earliness, and absolute deviation from due date. The following results were collected from the simulation model: I l 31 s ~, . 1. average tardiness oftardy jobs, 2. average earliness of early jobs, 3. average relative cost per job, 4. number of early jobs, and 5. number oftardy jobs, In addition to the above measures, average inventory holding cost per job and. average tardiness penalty cost of tardy jobs is collected. However, these statistics were not considered as performance measures; but they are used to help explain and draw conclusions about certain behaviors of the system. The rest of this chapter is organized as follows. First, the performance of the modified critical ratio rule is compared with other benchmarking rules considering relative cost as the performance measure. Second, the results showing performance of different sequencing rules considering supplementary time based peribrrnance measures ale presented. The performance of modified critical ratio rule using different values of the power factor z is discussed next. Finally, the setting of the best value ofz as a function oftbe system parameters is discussed. Results Consid'ering RC P,erformance Measure This section compares the performance of the modified critical ratio rule with EDD, CR, and SPT rules. The results presented in this section regarding the performance of the modified critical ratio rule ale the results achieved by using a z value that yields the best relative cost value at each configuration. Table VI shows the average relative cost achieved by using the SPT, EDD,. CR, and CRz rules ~espectively, in each of the experiment configurations listed in Table V. The improv,ement achieved by using the 32  5 modified critical ratio rule over the best sequencing rule in each experiment configuration is also presented in Table VI. The best performance among SPT, EDD and CR is marked by an asterisk. Experim.ent I Average Average Average Average % Improvement I . RCwben RCwben RCwhen RCwhen compared with I using SPT . using using CR using CRz best rule I EDD I I 1 38.0% , 36.17% *32.24% ~1.95% 0.89% 2 I I i 2].4% 20.29% *18.12% 17.97% 0.79% I 3 *101.8% I 130.46% 119.33% 103.70% 1.85% : 4 *54.4% I 68.42% 62.73% 54.84% 0.79% I 5 i 16.3% 9.36% *8.78% 8.76% 0.26% I 6 I 12.7% 8.74% *8.51% 8.50% 0.19% 7 42.1% I 30.66% *24.81% 23.59% 4.9 1% i 8 I 16.7% 0.66% *0.80% 13.64% 0.17% I 9 26.2% 19.24% *16.20% 15.56% 3.9.5% I 10 15.5% 0.65% *0.79% 13.61% 0.25% I I 11 ! , 15.6% 30.31% *13.74% 13.40% 2.47% 12 14.0% 22.56% *12.77% 12.59% 1.46% Table VI  Results Considering RC Measure A paired ttest was llsed to test whether the results are significantly different at 95% confidence level. For each experiment, the performance of each rule was found significantly different from the performance of other rules. Table VII shows the results obtained by applying the modified critical ratio rule and the critical ratio rul.e for experiment 6 (K=6, U=85%, pt=2). The procedure followed to test the significance of the difference is demonstraied using the values shown in Table VII. Ho: The difference between CR and CR12 is zero H1: The difference between CR and CR1.2 is not zero I I 1 33 L 9 Rejection criterion: Construct a 95% confidence intell'Val for the difference. If the confidence interval contains zero, do not reject the null hypothesis, else reject the null hypothesis. The width of the confidence interval (CIW) is obtained using the following equation: The value of ta12 for a= 95% is 2.228, and the standard deviation for the difference coluIIlll in Table VII is 0.145. Hence, the width of confidence interval CIW will be 0.102. The average of the Difference coluIIlll in Table VII is  0.153. Therefore, the upper bound of the confidence interval is  0.509. Hence, the null hypothesis is rejected and we conclude that the perfonnance of CRI.2 is statistically better than the performanoe of CR. Replication CR Results CR1.2 Results Difference 1 I 84.85 85.03 0.18 2 84.69 85.04 0.35 3 84.31 84.23 0.08 4 85.58 85.86 0.28 5 85.25 85.45 0.2 6 84.36 84.61 0.25 7 85.19 85. 11 0.08 8 85.14 85.36 0.22 9 86.04 86. 19 0.15 10 84.09 84.15 0 . .06 Table VII Results of sample experiment (6) The modified critical ratio rule provides better performance than other tested sequencing rules in all cases except for experiments 3 and 4 at which the utilization level is 92% (high) and the due date allowance factor is 3 (tight). In these cases, the maximum 34  value of z that was tested is 22 due to computer execution limitationsl . Figure 3 shows the performance of 'each sequencing rule at the high utilization level and Figure 4 shows their performance at the low utilization level. It is noteworthy that the penalty tightness factor does not appear to affect the conclusion of this researcb.. The performance of different sequencing rules is consistent at the two levels of the penalty tightness factor pt. Also, the next sections will show that the value of best z does not change when the penalty tightness factor pt is changed from I to 2. RC Relative cost at low utilization 0.4 0.35 0.3 0.25 0.2 0.15 0.1 0.05 o ~ ~ Figure 3 Relative cost results at low utilization ~Edd I:mI S PT IIGR .CIRz I FORTRAN Language gives an execution error if a number is larger than 9.9XloJ8• At z value greater that 22, some of the numbers become greater than 9.9Xl~8 35  Relative cost at: high utilization 1.4 1.2 1 RC 0.8 1m! Edd mSPT i 0.6 III C.R 0.4 .CRz 0.2 0 Figure 4  Relative Cost Results at high utilization Results Considering Time Based Supplementary Performance Measures Tables vrn through X present the perfonnance of the modified critical ratio role compared with other sequencing roles considering tardiness, earliness and absolute deviation from due date measures, respectively. The same set of main experiments shown in table V was used. However, more values of the power factor z were evaluated in some cases to fmd the z value that yields the best performance for each particular performance measure. Since the cost structure is not a factor when time based performance measures are considered, there are six, rather than 12, experimental configurations when timebased performance measures are considered. The same statistical test discussed showed that the performance of each rule is significantly different than the performance of other rules at each experiment. The SPT rule is known to perfonn the best when average flow time performance measure is considered. However,. since we are concerned with a forbidden early shipment environment, a 36  comparison between the SPT rule and the modified critical ratio rule is not conducted. The comparison between the modified critical ratio rule and the SPT rule is conducted to test whether SPT will still outperform the modified critical ratio rule when due date related measures are considered. Experiment Average Tardiness EDD CR CRt; % Improvement When Using SPT 1,2 32.22 , 24.23 21.48 21.28 1.09% 3,4 94.33 I 89.14 86.09 82 . 83 3.79% 5,6 14.59 1.96 1.17 0.82 31.73% 7,8 65.07 33.52 26.43 24.88 5.88% 9,10 7.74 0.09 0.03 0.02 39.64% 11,12 48.41 8.96 4.45 3.75 15.58% , Table VIII  Avernge Tardiness results Experiment SPT EDD CR CRz % Improvement 1,2 14.91 6.69 4.67 3.83 17.96% 3,4 10.88 1.24 0.59 0.48 17.67% 5,6 62.85 60.13 52.88 50.55 4.42% 7,8 56.63 21.67 16.77 13.69 18.39% 9,10 141.07 133.87 122.31 119.45 2.34% 11 ,12 114.95 73.28 63.77 55.39 13.14% Table IX  Average Earliness Results Experiment SPT EDD CR CR~ % ImprovemeDt 1,2 47.13 30.92 26.15 25.50 2.47% 3,4 105.21 90.39 86.68 83.49 3.68% 5,6 77.44 62.10 54.08 52.35 3.20% 7,8 121.70 55.19 43.20 38.77 10.26% 9,10 148.81 133.96 122.34 119.47 2.35% 11,12 163.37 82.23 68.22 60.11 11.88% Table X  Average Absolute Deviation from Due Date Results Figures 5, 6 and 7 show the performance of the modified critical ratio rule compared with other experimented rules. In Figure 5, average tardiness results for experiments 5 and 9, are not included. The average tardiness in these experiments is very small, and it can not be compared with other experimental results on the same scale. 37   Also, in Figure 7, average earliness results for experiment 4 are not shown for the same reason. Perfiorman,ce of Sequencing Rules 100 90 80 70 (I) 60 II) G) c =0 50 ~ ~ l 40 30 20 10 0 K=3,U=85% K=3,U=92% K=6,lI=92% K=9,U=92% Figure 5· Average Tardiness Results Performance o,f Sequencing R'ules II) 180 ,, :Iii c G) 1601 5 140+~~~ III Edd' Ii!SPT IIICR .CRz iE 120 + ,, m~ c 100+o ;:l' CIJ ·t c S ::J "0 CD .Q '" 80 +== 60 + 40 +~I 20 o IiliISPT mCR .CRz Figure 6  Average Absolute Deviation from Due Date Results 38  I t I ! L 160 140 120 GO .G.O .E 100 m 80 t .. 60 <" 40 20 a [/5\0 ,;:f'fi ¥~' IPerforman,~e of Sequen~ing IRules [/5\0 1>\0 !t\o ,;:f'fi ,;:f .;)~' .1" ~' t?' Figure 7 Average Earliness Results IIEdd ~SPT filCR .CRz These results show that the modified critical ratio rule outperforms other tested rules in all configuration settings in each time based performance criteria considered. This assures that the superiority of critical ratio rule is not influenced by the cost structure introduced in this research. On the ,contrary, the cost structure has a negative impact on the performance of the modified critical ratio rule. SPT was the only rule to beat the modified critical ratio in the case of tight due dates and high utilization (experiments 3 and 4). This can be explained by understanding that the SPT rule results in very high variation in the flow time of its jobs. The SPT rule tends to make the jobs of small work content fmish early and the jobs of large work content finish late. The jobs that are late have a high work content and consequently high due date allowance (since TWK is used to set due dates). Therefore, although SPT generates higher tardiness than the modified critical ratio, the relative tardiness of the late jobs are not high. Since the cost structure is concerned with relative tardiness rather than absolute tardiness, the SPT rule performs better than the modified critical ratio even though the modified critical ratio produce lower tardiness, and preferred time based performance. 39 r It is also noteworthy that the improvement achieved by the modified critical ratio rule is higher when time based performance measures are consider,ed. When time based performance measures are considered, the performance of the sequencing rules is compared to an ideal value of zero (the ideal tardiness, earliness, and absolute deviation from due date is zero). On the other hand, the ideal performance when relative cost performance measure is not zero. If a job is completed on its due date, it will still incur some inventory holding cost. Therefore, the difference between the performance of sequencing rullies will be influenced by the minimum cost incurred by a job, and the percentage of improvement will be less than the improvement realized when time based performance measures are considered. Another issue to be considered is the practical significance of the improvement realized by the modified critical ratio rule. Previously, we have shown that this improvement is statistically significant. When relative cost performance measure is concerned, we can see that the improvement realized by the critical ratio rule varies between 0.26% to 4.91 %. This improvement corresponds to an increase in the profitability of the product, which might be practically significant. The simplicity of applying the modified critical ratio rule does indeed add to its practical significance. The Effect Of The P'ower Factor (Z) On Performance Measures The simulation results presented in previous sections demonstrate the superiority of the modified critical ratio rule. In this section, the values of the power factor (z) tbat yield this superiority are discussed. Figur'es 8 through 37 show the values of different I performance measures as a function of the power factor z. I I l 40 rC I i L 37% 36% 35% RC 34% 33% 32% 31% o ~ ~ 0.5 K=3.U=850/0~ pt =1 ~ ~ ~ V' 1 1.5 2 Power Factor (z) Figure 8  Relative Cost versus z for Experiment 1 20.50% 20.00% 19.50% RC 19.00% 18.50% 18.00% 17.50% ~ o ~ ~ 0.5 K=3, U=85%, pt=2 "" ~ ~~ "" 11.5 Puwer Factor (z) 2 Figure 9 Relative Cost versus z for Experiment 2 K=3,U=92%, pt=1 135% 125% K \ RC 115% 105% '¥"~ 95% 0 5 10 15 20 Power Factor (z) Figure 10 Relative Cost versus z for Experiment 3 41 2.5 2.5 25 K=3,U=95%. pt=2 70% ~______________ ~I 1'. 65% +~T~« RC 60% +~~=~ 55% +~~==~~==~~~ 50% +~~~~~ o 5 10 15 20 25 RC RC Power Factor (z) Figure 11 Relative Cost versus z for Experiment 4 K=6,U=85%,pt=1 9.40% 9.30% 9.20% 9.10% 9.00% 8.90% 8.80% "" ~ "'" / "'" /' I , /' 8.70% '" o 0.5 1 1.5 2 Power Factor (z} Figure 12 Relative Cost versus z for Experiment 5 8.75% 8.70% 8.65% 8.60% ~ ~ '" 8.55% 8.50% 8.45% o 0.5 '" ~ / ~ / v 1.5 Power Fadm" (z) 1> 2 Figure 13  Relative Cost versus z for Experiment 6 42 2.5 2.5 K=6,U=92%,pt=1 35%., 30%~~~~ 25%r~~~_ ~_~_~ ====~==~~==~.~ RC 20%+~~~_r~~~ o 0.5 1.5 2 2.5 3 3.5 Power Factor (z) Figure 14  Relati¥e Cost versus z for Experiment 7 K=6,U=92%,pt=2 20.00% +i RC 17.50% +""..,':;;;OO(Ii 15.00% +....,r~~;! o 0.5 1 1.5 2 2.5 3 Power Factor (z) Figure 15 • Relative Cost versus z for Experiment 8 K=~,U=85%.,pt=1 13.85% 13.80% ~ .~ ...() RC 13.75% / / '13.70% I 13.65% 13.60% 1.5 ~ "'0"" , 1 0.5 A o 0.5 1.5 2 Power Factor (z) Figure 16 • Relative Cost versus z for Experiment 9 43 2.5 .... K=9,U=85 %,pt=2 13.85% 13.80% '" ! 1 ~ / "V RC 113.75% RC RC 13.70% 13.65% 13.60% 1.5 6 1 / ~ "V' 0.5 o 0.5 1.5 2 Power Factor (z) Figure 17  Relative Cost versus z for Experiment 10 K=9,U=92 %,pt=l 2.5 17.50% r, 15.00% 1"""'0;;::1 12.50% +1 1 0.00% +...,...rrr.~'T"""I 1 0.5 0 0.5 1.5 2 2.5 3 3.5 Power Factor (z) Figure 18  Relative Cost versus z for Experiment 11 K="U=92%,pt=2 14.50"10 ,.., 14.00% +'~........,.~I 13.50% +~~..:j 13.00% +=....:_j 12.50% l~::::::'Q:::==~=4 12.00% +,.,r'T""".,_j 1 0.5 o 0.5 1 1.5 2 2.5 3 Power Factor (z) Figure 19  Relative Cost versus z for Experiment 12 44 1 .. r K=3,U=85% 25 i III 24 III CD :cc 23 ... II:! I 22 ..... I ~ I I ~ i ~ <> .21 v 20 o 0.5 1 1.5 2 2.5 P01r'Ier !Factor (z) Figure 20  Tardiness versus z for Experiments 1 and 2 K=6,U=85% 2.3 '~" I: 1.9 :s ''""' 1.5 ~ 1.1 p / ~ I ~ / "' ./ 0.7 ... o 0.5 1.5 2 2.5 Power Factor (z) Figure 21 Tardiness versus z for Experiments 3 and 4 K=9,U=85% 0.5 r, 0 .375 +l 0.25 +l 0.125 +,~. 'Qo..,,=___; ·1.5 1 0.5 o 0.5 1 1.5 2 2.5 Power Factor (z) Figure 22  Tardiness versus z for Experiments 5 and 6 45 K=3,U=92% 100 ! ~ 95 c \ :a s.. 90 '" ~ Eo 85 ~ 80 5 0 5 10 15 20 25 Power Fa.ctor (z) Figure 23  Tardiness versus z for Experiments 7 and 8 K=6,U=92% 34 ~ til :!l :ca 30 ~ s.. E'o"< 26  22+._..~~ o 0.5 1.5 2 2.5 Power Factor (z) Figure 24  Tardiness versus z for Experiments 9 and 10 ~ J: =s s.. K=9,U=92% 11 +~ ~ 7+~~~ 3+~._._r~ 1 o 2 3 4 Power !Factor (z) Figure 25  Tardiness versus z for Experiments 11 and 12 46 r f ~ =.=. ~ 7 ~ ~ ~~ 0 6 5 ~ 4 3 o 0.5 1 1.5 2 2.5 Power Factor (z) Figure 26  Earliness versos z for Experiments 1 and 2 K=6,U=85% 62~~ 59+~~ 56+~~~ 53 +~==~~ 50 +O~~T_~ o 0.5 1.5 2 2.5 Power Factor (z) Figure 27  Earliness versus z for Experiments 3 and 4 150 140 130 120 110 , 100 1.5 A K=9,U=85% ~ 0.5 0.5 1.5 Power Factor (z) Figure 28  Earliness versus z for Experiments 5 and 6 47 ! 2.5 ...  K=3,U=92% 1.9 '~" .5 11.4 'i: ~) = ~ ~ 0.9 'l 0.4 " 0 5 10 15 20 25 Power Fador (z) Figure 29  Earliness versus z for Experiments 7 andS K=6,U=92% 21 '" '~" ~ .5 18 'i: ~ ('II ~ 15 ~ 12+r,.r~ o 0.5 1.5 2 2.5 Power Factor (z) Figure 30  Earliness versus z for Experiments 9 and 10 K=9,U=92% 75 ~ '" , ~ .If> v 70 65 60 55 50 1 0.5 o 0.5 1.5 2 2.5 3 3.5 Power lFactor Iz) Figure 31  Earliness versus z for Experiments 11 and 12 48  K=3,U=8S% ~ ~ J'> ~ 0.5 1.5 2 2.5 Power Factor (z) Figure 32  Absolute Deviation From Due Date versus z for Exp. 1 and 2 K=6,U=8.5% .g 62 ~I .:~: =o ".::I a. .~ ~ 56 +'>.,;,___; ~ C 'C ~ :I 1 J: 50 +....,..,.1 < o 0.5 1 1.5 2 2.5 Power Factor (z) Figure 33 . Absolute Deviation From Due Date versus z for Exp. 3 and 4 K=9,U=8.5% .., 1$~=~~~~, 1 "C>I SC~IS 130 +"~ ____l G)'C ~ 'C ~1~+,,~r____; ~'C "..... ! a 120+~~~==~I 00 v III 104 ~~115+~~..,....,.r~ 1.5 1 0.5 o 0.5 1 1.5 2 2.5 Power Factor (z) Figure 34  Absolute Deviation From Due Date versus z for Exp. 5 and 6 49 T ! K=3,U=92% 92~, e Q 90~; ~~ 2 88 +\ 1\; CIS CIS .~ "CI 86 +"'ri "~CIo a=I ~ ; "CI84t~~~~==;:;==~~==~~~ Q v ~ 82 +r~r_,_~ < 0 5 10 15 20 25 Power Fadel" (z) Figure 3S • Absolute Deviation From Due Date versus z for Exp. 7 and 8 K=6,U=92 % 59 ; ~ 55 E ~ eo 51 .!:: ::: ~ eo '.c '" 47 ~ til ... 1:\1 .~ >g 43 '"  ".l:.I 39 "=0 III ..c 35 < 0 0.5 1.5 2 2.5 Power Factor (z) Figure 36  Absolute Deviation From Due Date versus z for Exp. 9 and 10 e 82 Q ..: § 76 ~ .!! 1:\1 1:\1 .;;: "CI 70 ~ ~ 2 "CI 64 Q= ~ 58 < 1 ~ o K=9,U=92% ~ '" '" ~ I 2 3 4 Power Factor (z) Figure 37  Absolute Deviation From Due Date versus z for Exp. 11 and 12 50 Figures 8 through 37 show that a unique optimum exists over the range considered for each of the system configuration when time based performance measures are considered. Tbis is very important because it makes the search for the best value of the power factor z easier. A search for the best value of z will be easier if it is known that there is a unique optimum for the objective perfonnance measure. This property of the modified critical ratio rule is very important, since it makes the search for the best z more structured and facilitates the implementation of the modified critical ratio rule. In the case of loose due dates and low utilization level, Figures 16 and 17 show that two local optima exist when relative cost performance measme is concerned. Results show also that the performance measure is sensitive to the value of the power factor z. This can be observed most markedly at z values near zero where the slopes of the performance curves are steep. Determining the Value of z Based on the System Parameters The above results show that using the appropriate value of z, the modified critical ratio rule yields better performance than other traditional sequenc.ing rules.. The question that arises next is how to choose the best value of z. However, this should not be a limitation for implementing the modified critical ratio rule. If any of the traditional sequencing rules were to be implemented, a search for the best rule is needed to detennine the best rule. Therefore, implementing the modified critical ratio rule should not be eliminated because of the search involved in this implementation. The improvement achieved by using the modified critical ratio should justify the extra experiments needed (if any). Nevertheless, we attempted to fmd a nonsearch based methodology to specify the best value of Z without conducting an extensive search. 51 T I , The methodology considered in this research to determine the best z value is regression modeling. We attempted to model the best value of the power factor (z) as a function of the system parameters. The power factor (z) was modeled as a function of due date tightness, system utilization and penalty tightness factor. However, the adjusted r square parameter that represents the appropriateness of the regression model was 0.448 (maximum value indicating perfect fit is 1.00). One ofthe reasons that perhaps lead to this low value of Adjusted R2 is the lack of data points. This research generated only twelve data points to be used in a regression model. This might explain wby the regression approach did not generate a higher adjusted R2. Future research efforts might provide a more suitable regression model for determining the best value z by investigating more data points andlor other parameters. This research does not provide a nonsearch methodology for determining the best value of the power factor z. A search is still needed to determine the best value of z as a fmding of this research effort. 52 VI Conclusio.n This chapter presents the conclusions, insights, and future directions of this research. The conclusions and insights regarding the use of the modified critical ratio rule are presented fIrst. Then, we attempt to generalize the fmdings of this research and their impact on the sequencing research area. Finally, we conclude this chapter by presenting potential research directions to follow this l'esearch. Sequencing Using the Modifi,ed Critical Ratio. In the previous chapter, we justified that the modified critical ratio does improve the performance of a manufacturing system The modified critical ratio is an extension of the critical ratio rule that has shown good performance in the literature. The advantage of the critical ratio rule is tbat it considers both the remaining slack of the job and its processing time. The critical ratio rule gives priority to the job that has the least ratio of slack time to the processing time. However, there is an underlying assumption when the critical ratio rule is used.. The sequence of the jobs generated by the critical ratio rule assumes that the required time needed for ajob to flow through the manufacturing system is proportional to its processing time processing time only. Therefore,. the job that has the least slack to processing time ratio is given the highest priority. Consider two jobs, the fIrst, job A, has a remaining slack of d days and a remaining processing time of p days, willIe the second, job B, has a remaining slack of 2d days and a remaining processing time of 2p days. Both jobs will have the same priority if the critical ratio rule is used, since their slack to processing time ratio is dip. However, depending on the system confIguration,. a dip slack to processing time ratio may be sufficient for one job and small for another job. For example, if the operation time for each job is the same, job B will 53  bave more remaining operations and consequently it will visit more queues. Therefore, job B is expected to spend more waiting time than job A. Hence,even though job A and job B have the same dip ratio, it will likely be more desirable to give the priority to job B rather than job A. The modified critical ratio avoids the above conflict by modifying the importance of the processing time in assigning the priority to each job. The importance of the processing time is raised to the power z. Therefore, according to the configuration of the system, the importance of the processing time in deciding which job should have the highest priority is varied. The critical ratio rule depends heavily on whetber the due date of a job has passed or not. If the job's due date has not passed yet, the numerator of the critical ratio rule is positive. Therefore, if two jobs have the same remaining slack time, the priority will be given to the job that has the highest remaining processing time. On the other hand, if the job's due date has already passed, the numerator of the ,critical ratio rule win be of a negative value. Therefore, if two jobs have the same remaining slack time, the priority will be given to the job that has the lowest remaining processing time. The same conflict is observed when the modified critical ratio rule is used. Consider a hypothetical case where a z value of a is found to be the best value that yields the best performance for such a configuration. It is not clear whether modifying the weight of the remaining processing time by raising it to the power Ct gives the priority to the jobs that have small remaining processing time, or whether it gives the priority to the jobs that have large remaining processing time. This numerical sensitivity makes it more 54  difficult to understand and explain at which value of the power factor z. the modified critical ratio will yield the best performance. Sequencing Using A Quantified Decision Domain The modified critical ratio bas shown improvement over other tested benchmarking rules in this research. Thits improvement can be explained based on two main factors. 1. The critical ratio rule considers two important characteristics of a job, the remaining slack and the remaining processing time. However. the weight or the importance of each of these characteristics when assigning the priority of each job is fIxed. On the other hand. using the modified critical ratio. rule, the weight or the importance of each of these characteristics is varied according to system parameters. In traditional sequencing rules, choosing the best sequencing rule involves choosing the information considered in the selected sequencing rule. Therefore, the decision domain will be discrete. On the other hand, chQosing the best value of the power fac~or z involves choosing the weight of information considered in the modified critical ratio rule. Therefore the decision domain is continuous. 2. The modified critical ratio rule can react sensil1:ively to the changes in the system parameters. Traditionally, the sequencing problem is a problem that has a continuous range of system parameters and a discrete domain of available sequencing rules. Consider a system configuration A where EDD is the best sequencing rule. If one or more ofthe system parameters (utilization, due date tightness, etc.) is changed, the decisionmaker will have a decision domain ofcbanging the sequencing rule or sticking with EDD Wu and Wysk (1989), Pierreval and Mebark (1997). On the other hand, using 55 ! I I I I the modified critical ratio rule, the sequencing problem is a problem that has continuous range and a continuous domain. Therefore, if any change in the system parameters is introduced, the reaction will be changing the power factor z, which is a continuous reaction domain. This is the second reason tbat contributed into the superiority of the modified critical ratio rule. Researcb Contribution This research has introduced a new sequencing rule, that has been shown to perform statistically better than published sequencing rules in most of the settings experimented in this research. This fmding is important for practitioners as it provides a methodology to improve the performance of a manufacturing syst'em. On a conceptual level, the sequencing rule introduced in this research introduces a new sequencing paradigm. Traditional sequencing is concerned with choosing the best rule that yields the best performance. Sequencing rules differs based on the information content of these rules. Therefore, choosing the best sequencing rule involves choosing the information considered when jobs are prioritized. On the other hand, the sequencing paradigm followed in this research .is not concerned with the information that should be considered when jobs are prioritized, rather, it is concerned with the weight or the effect of the information considered when jobs are prioritized. Future Directions This research has introduced a new sequencing rule that has introduced an extension of the critical ratio rule, that bas shown to perform better than tested sequencing rules. Future clirections to follow this research can be divided into two areas. First, the modified critical ratio rule needs to be studied more thoroughly. The second 56 future direction is in generalizing the sequencing paradigm that has been introduced in this research. Future directions related to the modified critical ratio rule 1. In a. previous chapter, we presented one approach that might be followed to determine the best value of z, regression analysis. However, regression did not generate promising results in this research. We have explained the inappropriateness of the regression model by the lack of sufficient data. One of the future directions that can be pursued is conducting more experiments with diffemnt settings of system parameters in order to achieve an improved regression model. 2. In this research, the factors that have been studied are due date tightness, utilization le¥el, and penalty tightness factor cost. Future research may consider other factors such as number of machines, alternate routing, due date setting procedure, release mechanism, manufacturing system structure, permitted early shipment environment, and many other job shop factors and their interactions. 3. In this msearch, the search for the best value of z was restricted by a computational limitation (numeric overflow), therefore, the maximum experimental value of z was 22. Future research may investigate higber values of the power factor z, especially in the case of high system utilization and tight due dates. At this configuration, a value of z higher than 22 may lead to improved performance. It is noticed in Figure 11 that as the value of z is increased, the average r:elative cost is improved. 57  4. As discussed previously in this chapter, both critical ratio and modified critical ratio rules give higher priority for jobs of high processing time if there is a late job in the queue, and higher priority for jobs of low processing time if all the jobs ill the queue are ,early. This inconsist,ency may have a negative impact on the system's performance. A future dir:ection might be to investigate a modification of the modified critical ratio rule to overcome this inconsistency. F'uture directions related to generalizing tbe seqoencing p'arndigm introduced in this research This research introduced a shift in the sequencing paradigm The traditional sequencing paradigm is concerned with the selection of the best rule that will yield best performance. Sequencing is no longer concerned with choosing the information content of a sequencing rule, rather it is concerned with choosing the importance or the weight of a job information when prioritizing job is considered. This shift in the objective can be used to explore a more generalized rule that considers more information in a job. Such a rule might consider the number of operations for a job, arrivaJi time of a job, and the fmancial aspects of a job such as inventory value, job value and accumulated tardiness penalty cost. This might be a promising approach. Previous research fmdings have found that monetary based sequencing rules do outperform time based sequencing rules. However, by rethinking the importance or the weight of the fmandal information of a job, monetary based or combined timemonetary based rules might show improved performance. 58 References Ahmed, I. (1990), ''The interaction of due date assignment, job order release, and sequencing techniques in job shop scheduling," Unpublished doctoral dissertation, The University of Mississippi. Ahmed, 1. and W. Fisher (1992), "Due date assignment, job order release, and sequencing interaction in job shop scheduling," Decision Sciences, 23(3), 663647. Amar, A. and B. Xiao (1997), "Scheduling on a bottleneck station: a comprehensiJve ,cost model and heuristic algorithms," International Journal of Production Research, 35(4), 10111030. . Baker, K. (1984), "Sequencing rules and duedate assignments in ajob shop," Management Science, 30(9),10931105. Baker, K. and J. Kanet (1983), "Job shop scheduling with modified due dates," Journal of Operations Management, 4(1), 1123. Chang Y., S. Sueyoushi, and R. Sullivan (1996), "Ranking dispatching rules by data envelopment analysis in a job shop environment," IlE Transactions, 28, 631642. Cheng, T. and M. Gupta (1989),"Survey of scheduling research involving due date detemtination decisions," European Journal of Operational Research, 38, 156 166. Christy, D. and J. Kanet (1990), ''Manufacturing systems with forbidden early shipment: implications for choice of scheduling rules," International Journal of Production Research, 28(1), 91100. Hoffmann, T. and G. Scudder (1983), "Priority scheduling with cost considerations," International Journal of Production Research, 21(6),881889. Law, M. and W. Kelton (1991), Simulation Modeling and Anaiysis, Second Edition, McGraw Hill, Inc., New York. Kanet,1. and D. Christy (1989), "Manufacturing systems with forbidden early shipment: implications for setting manufacturing lead times," International Journal of Production Research, 27(5), 783792. Kawtummachai, R., Y. Yanagawa, K. Ohashi and S. Miyazaki (1997), "Scheduling in an automated flow shop to minimize cost: backwordmeta scheduling method," International Journal oj Production Economics, 49, 225235. 59 Montazeri. I. and L. Wassenhove (1990), "Analysis of scheduling rules for anFMS," International Journal of Production Research, 28(4), 785802. Panwalkar, S. and W. Iskander (1977), "A survey of scheduling rules," Operations Research, 25(1 J, 4561. Philipoom. P., M. Malhotra and J. Jensen (]993), "An evaluation of capacity sensitive order review and l'elease procedures in job shop," Decision Sciences, 24(6}, 1109 1133. Pierreval, H. and N. Mebarki (1997), ''Dynamic selection of dispatching rules for manufacturing system scheduling," International Journal of Production Research, 35(6), 15751591. Pritsker, A. A. B. (1995), Introduction to Simulation and SLAM II, Fourth Edition, John WHey & Sons, Inc., New York. Ragatz, G. and V. Mahert (1984), "A simulation analysis of due date assignment rules," Journal of Operations Management, 5(1), 2739. Ragatz, G. and V. Mabert (1988), "An evaluation of order release mechanisms in a jobshop environment," Decision Sciences, 19(1), 167189. Rohleder, T. and G. Scudder (1992), "Scheduling rule selection for forbidden early shipment environment: a comparison of economic objectives," International Journal of Production Research, 30(1), 129140. Scudder, G. and T. Hoffmann (1987), "The use of costbased priorities in random and flow shops,." Journal of Operations Management, 7(1&2), 217232. Scudder, G., T. Hoffmann, and T. Rohleder (1993), "Scheduling with forbidden early shipments: alternative performance criteria and conditions," International Journal of Production Research, 31(10), 22872305. Scudder, G. and D. SmithDaniels (1989), "Application of the net present value in random and flow shop scheduling," Decision Sciences, 20(3), 6'02622. Scudder, G., D. SmithDaniels and T. Rohleder (1990), "Use ofthe net present value criterion in a random job shop where early shipments are forbidden," Journal of Operations Management, 9(4), 527547. Sherrill, R., ED (1970), "APICS dictionary of inventory control terms and production terms'" Third Edition, American Production and Inventory Control Society, Washington, D.C. Vig, M. and K Dooley (1991), "Dynamic rules for duedate assignment," International 60 Journal of Production Research, 29(7), 13611377. Wu, S. and R. Wysk (1989), "An application of discreteevent simulation to online control and scheduling in flexible manufacturing," International Journal of Production Research, 27(9), 16031623. Yang, K and C. Sum (1994), "A comparison of job shop dispatching rules u:sing a total cost criterion," International Journal of Production R,esearch, 32(4),807820. 61 Appendix 1  Interarrival Time Calculations The system studied in this research is presented in Figure I. Orders arrive to tile system at the rate of Ao, which is the parameter we need to determine. The arrival rate at machine i is 14, i.e., Al is the arrival rate to machine 1. The value of ~ can be determined by using equation 1: ~o Al Ml ~ 0 M2 I I I ? I .I. 0 M7 Figure 38  System Representation (Equation 1) Where; ~: the arrival rate for machine i. p: the desired utilization level. /li: the average processing time at machine i. The average departure rate from any machine is same as the average arrival rate to the same machine assuming the utilization is less than or equal !, However, the jobs 62 departing from any machines may either leave the system or stay in the system to be processed by another machine. The rate of jobs staying in the system is denoted as 'Yi. The jobs arriving to machine i consist of two components. The fIrst is the jobs arriving to machine i as the frrst machine, i.e., the first operation for these jobs is to be performed on machine i. Since each machine has the same probability of being the machine for the fIrst operation for a job, the arrival rate of this component is A.o divided by seven (number of machines). The second component is the jobs arriving to machine i after being processed by any machine other than machine i. Therefore, 1..0, can be determined by the following formula: (Equation 2) The frrst term of the above equation represents the rate of jobs arriving to machine i as their fIrst operation. The second term represents the portion of jobs leaving other machines and arriving to machine i. The value of 'Y .... is calculated as follows: r k (Equation 3) Where; j: operation number a: the probability of a job leaving machine k has j operations b: the probability that a job leaving machine k has not completed all its operations The constant a is determined as follows: j a =7 (Equation 4) Ln j"J 63 The factor a in equation 3 and 4 is the probability that a job leaving machine i has j number of operation. Note that a job that has a bigher number of operations circulates more in the system than a job that has, a smaller number of operations. The factor b is determined by the following formula: jl b= j (Equation 5) The above equation calculates the probability that a job did not fmish all its operations. The numerator in equation five consists of the number of visits a job will make to any machine before finishing an its operations. The denominator in equation 5 consists of the number of visits that a job will make to any machine in order to finish its operations. Combining equations 2 through 5, AI( is detennined as follows: A = ,1,0 +.!.. ~ A ~ j 1 t 7 6L k 7 • j =l,j"k In } (Equation 6) n=l Substituting in the above equation, equation 6 reduces to: A A =_0 +O.8JL t 7 k (Equation 7) Combining equations 7 and 1, A.o can be determined by the following formula: A = 1.4,11 o P 64 (Equation 8) Appendix 2  Description of the simulation model The simulation model was coded in the SLAM II simulation language with FORTRAN subroutines inserts (Pritsker, 1995). Figures 39a and b shows Ithe SLAM II network of the sllnulated syste~ and the FORTRAN program is shown in Appendix 3, while the attributes and global variables used in this simulation model are shown in Table XI. Jobs arrive to the system at a calculated interarrival rate. The arrival process is modeled in the CREATE node shown in the network graph. After arrival, the following attributes of each job are assigned in the AWAIT node labeled EVl: 1. the number of operation for the job, 2. the sequence of the operation for the job, 3. the processing time of each operation, 4. the value of the job, and 5. the selling price of the job. After the attributes containing the above information are assigned, the attributes that are specific to next operation are assigned in the AWAIT node labeilied EV2. These attributes are the number of the next operation for the job, the machine number of the next operation, and the processing time of the next operation. Then, the job leaves the AWAIT node labeled EV2 to one of the branches that start with one of the ASSIGN nodes labeled MC1 to MC7. These seven branches (starting with ASSIGN nodes MC1 to MC7) represent the queues in front of machines 1 to 7. In each of these branches, there is one ASSIGN node and one AWAIT node. At the ASSIGN node (labeled MCl, MC2 to MC7), the attribute that stores the current time is updated. This attribute (ATRlB (24) is used to calculate the inventory cost associated with each job. Jobs leave the ASSIGN 65 node in each of these branches and arrive to an AWAIT node that follows each ASSIGN node. At the A WAIT node, a job waits for the machine required for its next operation. The FORTRAN subroutine that starts with the line number 100 is used at each of these AWAIT nodes. The FORTRAN subroutine is called when 1) a job arrives to the Await node or 2) when the resource is freed. In the FORTRAN subroutine, a check is made to detennine if a machine is idle and if there are jobs in the queue. Then, there are two possibilities to execute the subroutine depending on the sequencing rule applied. If the modified critical ratio is applied, the modified critical ratio is calculated for each job. The job that has the least ratio is remoVied from the queue, and is assigned to the idle machine. On the other hand, if the SPT rule is used, the job that has the highest priority in the queue is removed from the queue, and is assigned to the idle machine. The priorities in this case are assigned based on ATRIB (29), which stores the remaining processing time of a job. Jobs leave the AWAIT node and stay in the activity that follows the AWAIT node for the period its operation processing time. After the operation is completed, the resource that represents the machine used by a job is freed in the AWAIT node labeled FREE. Then the attributes that store information about the job value, remaining processing time of the job, and the inventory cost of the job are updated in the AWAIT node labeled EV3. After the jobs attributes are updated, a job is routed again to the AWAIT node labeled EV2 if the job's operations are not completed. Otherwise, if the job's operations are completed, the job is routed to the ASSIGN node labeled LEA VE. At the ASSIGN node labeled LEA VE, the attribute that stores the current time is updated. This attribute (ATRIB (24» is used to calculate the tardiness penalty cost for tardy jobs, and the inventory holding cost of finished goods. Also, at the 66 ASSIGN node labeled LEAVE, the value of A 'fRIB (22), that stores the job's deviation from its due date, is calculated. A job leaves the AWAIT node labeled LEA VB to the branch starting with the AWAIT node labeled EVES if it is completed after its due date, and to the branch starting with the AWAIT node labeled EVE4 if it is completed befm:e its due date. H a job is completed after its due date, its tardiness penalty cost is caliculated in the AWAIT node labeled. Then the average tardiness of tardy jobs, and average penalty cost of tardy jobs are collected in the COLLECT nodes ]abeled LAT and PENC respectively. If a job is fmished early, it is routed to the A WIAT node EVE4 through an activity that last for the time of its earliness. The inventory cost of storing an early finished jobs is calculated in the AWAIT node labeled EVE4, and is added to the total inventory cost incurred by the job. Then the earliness of early jobs is calculated in the COLLECT node labeled EAR. Both early and tardy jobs are joined at the AWAIT node labeled EVE6 at which the relative cost of each job is calculated. After a job leaves the AWAIT node labeled EVE6, the average inventory cost and the average relative cost statistics for all jobs are collected in the COLLECT nodes labeled INVC and RC respectively. The entity that represents ajob is terminated. 67 Attribute Description Attribute( 1) Job's arriving time Attribute(2) Number of operations Attribute(3) Machine of first operation Attnbute( 4) Machine of second operation Attnbute( 5) Machine of third operation Attribute( 6) Machine of fowth operation Attribute(7) Machine of fifth operation Attribute(8) Machine of sixth operation Attribute(9) Machine of seventh o£eration Attnoute( 10) Duration of first oiPeration Attribute( 11 ) Duration of second operation Attribute(l2) Duration ofthird operation i Attribute(l3) Duration of fourth operation Attribute( 14) Duration of fifth o~ation Attribute(15) Duration of sixth operation Attribute( 16) Duration of seventh operation Attribute ( 17) Number of completed operations Attribute ( 18) Machine of next operation Attribute( 19) Duration of next operation Attribute (20) Due Date Attribute(21 ) Selling Price Attribute(22) Waiting time in storage area Attribute(23) I Job's Value 1 Attribute(24 ) Waiting time reference I Attribute(25) Completed processing time Attribute(26) Accumulated holding cost per job Attribute(27) Penalty cost per job Attribute(28) Relative cost Attribute(29) Attribute(30) Total Processing Time DD(1) Due date tightness DD(2) Selling price factor DD(3) Factor of inventory cost (H) DD(4) The value of power factor (z) DD(5) Penalty tightness (pt) DD(6) Scale ofRC 1 DD(7) Scale of processing time I' Table XI  Description of attributes and global variables 68 0\ 'D ItiMetll111 [iJWEfl IllMellllll H0 0WEFl l'IMCSlll sl ~rn Fig 39. a  SLAMll Network Model (part 1) ,.Q t: c: Q., ~ "0 Ii Q .... ~ i ~ ..:.:: 100 Q ~ ~ z =~= j r.J'1 ,.Q e\ :is fI') ~ § 100 ~ = ..b.( ) ~ !:II: .,.. l=!!l § ~ 70 Appendix 3  lFortran Program SUBROUTINE AL,LOC (I, IFLAG) COMMON/SCOM1/ATRIB(100) ,DD(100) ,DDL(100" ,DTNOW, II,MFA,MSTOP,NCLNR 1 , NCRDR, NPRNT,.NNRUN,NNSET ,NTAPE, SS (100) , SSL (100) , TNEXT, TNOW,XX (100) NA=I GOTO ( 100, 100, 100 I 100, 100, 100, 100, 1, 2, 3 ,. 4 , 5 , 6) , I 100 I FLAG = 0 IF (NNRSC (NA) .EQ. 0) RETURN IF (NNQ (NA} . EQ . 0) RETURN IF(DD(8) .EQ. l. ) GOTO 122 DO 110 K=l,NNQ(NA) CALL COPY(K,NA,ATRIB) RNUM=ATRIB(20)TNOW DEN1=ATRIB(30)ATRIB(25) Z=DD(4) DEN=DEN1**Z CRITL=RNUM/DEN IF(K.EQ.1) THEN CRITT=CRITL MCRIT=l ELSE IF (CRITL.LT.CRITT) THEN CRITT=CRITL NCRIT=K ENDIF ENDIF 110 CONTINUE CALL SEIZE(NA,l) CALL COPY {NCRIT, NA,ATRIB) IFLAG=NCRIT IF (IFLAG. EQ. 0) CALL ERROR (NCe1) RETURN 122 IFLAG=1 CALL SEIZE{NA,l) RETURN 1 IF(NNQ(8).NE.1) CALL ERROR (3) CALL COPY(1,8,ATRIB) NOP1=UNFRM(3.,8.,B) ATRIB(2)=NOP1 DO 10 LS1=1,ATRIB(2) 13 NF1=liNFRM(1.,8.,9) IF (LSl. EQ. 1 ) GOTO 15 MAll=LS1+1 IF (NFl.EQ.ATRIB(MAll}) GOTO 13 15 MA12=LS1+2 ATRIB(MA12)=NFl 10 CONTINUE DO 12 LD1=1,ATRIB(2) MA19=LD1+9 ATRIB(MA19)=UNFRM(3.5,6.5,LDl)*DD{7) ATRIB (30) =ATRIB(30) +ATRIB (MA19) 12 CONTINUE ATRIB(21)=ATRIB(30)*DD(2) ATRIB (20) =TNOW+ATRIB (30) *DD (1) ATRIB(23)=ATRIB(21} *0.3 I FLAG= 1 RETURN 2 IF (NNQ (8) .NE .1) CALL ERROR (3) CALL eoPY (1,8, ATRIB) NX01=ATRIB(17) +1 ATRIB( 17)=NX01 NA12=NX01+2 NA19=NX01+9 71 ATRIB (18) =ATRIB (NA12 ) ATRIB (19) =ATRIB (NA19) IFLAG=l RETURN 3 IF(NNQ(8).NE.1) CALL ERROR (3) CALL COPY(1,8,ATRIB} ATRIB(25) =ATRIB(25) +ATRIB(19) ATRIB(23)=(ATRIB(25)/ATRIB(30)*O.2+0.3)*ATRIB(21) ATRIB (26) =ATRIB (26) +DD(3) *ATRIB (23) * (TNOWATRIB (24) ) ATRIB (29) =ATRIB (30) ATRIB (25) I FLAG = 1 RETURN 4 IF(NNQ(8).NE.l) CALL ERROR(3) CALL COPY ( 1, 8 ,.ATRIB) ATRIB(26)=ATRIB(26)+O.75*ATRIB(21)*DD(3)*{TNOWATRIB(24» IFLAG=l RETURN 5 IF(NNQ(8).NE.l) CALL ERROR(3) CALL COPY(1;8,ATRIB) ATRIB(22}=ATRIB(22) ATRIB(27}=ATRIB(21)*ATRIB{22}/(DD{5)*(ATRIB(20)ATRIB(1») IFLAG=l RETURN 6 IF(NNQ{8).NE.l) CALL ERROR(3) CALL COPY(l,8,ATRIB) ATRIB(28)=(DD(6) * (ATRIB(27)+ATRIB(26) ) )/ATRIB(21) IF(DD(9) .EQ.l.} THEN WRITE{NPRNT,61) ATRIB(28) 61 FORMAT {FlO. 2, FlO .. 3) END IF IFLAG=l RETURN END 72 VITA Amr AbuSuleiman Candidate for the degree of Master of Science Thesis: JOB SHOP SCHEDULING: A QUANTIFIED SEQUENCING RULE FOR IMPROVING SYSTEM PERFORMANCE UNDER DIVERSIFIED OPERATIONAL PARAMETERS Major field: Industrial Engineering and Management Biographical: Persona] Data: Born in Amman, Jordan, On March 20, 1973, the son ofSuleaman AbuSuleirnan and Fariouz Shehabi Education: Received Bachelor of Science degree in Mechanical Engineering from Jordan University of Science and Technology, Irbid, Jordan; completed the requirement for a Master of Science degree in Industrial Engineering and Management at Oklahoma State University in May 1998, Experience: Trainee Engineer at Arab Solar Industries, Sahab, Jordan, from Honors: June 1994 to September 1994; Marketing Engineer, AI·Ghanem Trading and Contracting Company, Amman Jordan, from September 1995 to July 1996; Graduate Research Assistant, Center for Computer Integrated Manufacturing, Oklahoma State University, from January 1997 to May 1998; Graduate Teaching Assistant, Oklahoma State University, from August] 997 to May 1998 Alpha Pi Mu Industrial Engineering Honor Society Affiliations: Institute ofIndustrial Engineers (HE), Institute For Operations Research and Management Science (INFORMS)
Click tabs to swap between content that is broken into logical sections.
Rating  
Title  Job Shop Scheduling: a Quantified Sequencing Rule for Improving System Performance Under Diversified Operational Parameters 
Date  19980701 
Author  AbuSuleiman, Amr 
Document Type  
Full Text Type  Open Access 
Note  Thesis 
Rights  © Oklahoma Agricultural and Mechanical Board of Regents 
Transcript  JOB SHOP SCHEDULING: A QUANlli'lED SEQUENCING RULE FOR IMPROVING SYSTEM PERFORMANCE UNDER DIVERSIFIED OPERATIONAL PARAMETERS By AMR ABUSULEIMAN Bachelor of Science Jordan University of Science and Technology Irbid, Jordan 1995 Submitted to the Faculty of the Graduate College of Oklahoma State University in partial fulfillment of the requirements for the degree of MASTER OF SCIENCE July, 1998 JOB SHOP SCHEDULING: A QUANTIFIED SEQUENCING RULE FOR IM:PROVING SYSTEM PERFORMANCE UNDER DIVERSIFIED OPERATIONAL PARAMETERS Thesis Approved Thesis Advisor l"1~~ ~tNrIi$ De . . of the Graduate College 11 ACKNOWLEDGMENTS In the name of Allah, Most Gracious, Most Merciful Tbis thesis has been a major milestone in my academic career. I feel obligated to acknowledge the help of some people without whom this work would not have been completed in this timely manner. First and foremost, I wish to express my greatest thanks, deepest appreciation, and sincere gratitude to my family, especially my father Suleiman K. AbuSuleiman and my mother Fairouz Shehabi. I thank them for supporting me and giving me the opportunity to pursue my graduate studies. Moreover, I will never forget their love, encouragement, warm emotions, and sacrifice to make me a better person in all aspect of life. My thanks are also extended to the rest of my family members, my beloved sisters Nismen, Abeer, and Reem, and my brother Ghaith. Despite the very long distance, their warm emotions have always made me feel between them and inspired me to do my best always .. I also thank my advisor, Dr. David B. Pratt for his continuous guidance, his encouragement during the frustrating periods, and his compliments during the productive periods. His continuous support kept my motivation at the highest level during the course of this research. My great appreciation is also extended to my committee members Dr. Manjunath Kamath and Dr. Sanjay Melkote. Their valuable comments and suggestions had a significant impact on the quality of this research. I also want to thank: Dr. Mike Branson for his help in the statistical aspects of this research. 1Il I would like to mention again my advisor Dr. David Pratt and Dr .. Manjunath Kamath for fmancial assistanoe by giving me the opportunity of working at the Center for Computer Integrated Manufacturing at Oklahoma State University. I would also like to thank them for helping me improve in my academic and professional career. I also acknowledge the fmancial support of the National Science Foundation. I would also like to mention my best lifetime friends, Omar Na'd, Sa'ed Salhieh, and lmad Hindi. I have always remembered the great times we have, and I am not sure that I would have been able to concentrate on my research without their true and sincere friendship. Thank you buddies! Last but never least, I would like to thank my aunt, Fida Shehabi for her great care and friendship during my stay in the states. iv TABLE OF CONTENTS CHAPfER PAGE I THE PROBLEM AND ITS SETIING .............. ' ............................................ , ...................................... 1 INTRODUcnON ..... ...... ................................. ...................... ................................ " .... .... " .......................... 1 DISPATCIDNG RuLEs .................................................. .... " .......................................... " ....... ... .... ............. 2 PERFORMANCE MEASURES ............... " ............................. " ......... . ........ . ...................................... ............. 2 PROBLEM STATEMENT ................................... ... ........ ..................................................... . ... .. ........... .. .... 3 DEFINITION OF 'TERMINOLOGy .... .............. .............. " ....... .................................. ....... ........ " ........ , ... .. ......... 4 n LITERATURE REVIEW " ............... ' ................................................................................................... 5 INTRODUCTION ..................................................... . ........ , ......... . .......... ....... . ................... ... .. , .... " .............. 5 LITERATURE REVIEW ON CONSTRUCTING COST MODELS ......... , ........................................... , ................... 5 LITERATURE REVIEW ON SEQUENCING RULES ..... .. . , .......................................................................... . .... ,,9 LITERATURE REVIEW ON EXPERIMENTAL DESIGN ....................................................................... ......... 13 CONCLUSION .... .............. . ... ' ............................ " ................................................... " ................. ...... ....... . 16 m RESEARCH G'OALS AND OBJECTIVES .......... , ................................................ "'., ....................... 17 REsEARCH OBJECTIVE ..... , .......................... .. ........ .. ............... . ...... .. ........ " ......................................... , .... 18 TASKS ............................................................................................. . ... ... ................. ... ........................ 18 IV RESEARCH MEmODOLOGY .................................................................................................... 1" AsSUMPTIONS .................... .............. .......... .. ............................. ............ ......................... ... .... .. ... ... ..... . 20 lOB SHOP DESCRIPTION ..... " ......... .... ....... ... .................... . ..................................................................... 21 COST STRUCTURE ............................................................................................................................... 23 Example .......... .............................................. .......................... ... .......... .... ............................. .. ...... 25 RESEARCH FACTORS ............................ .... ............... " .................................... ..................... .................. 27 v SIMULATION MODEL ..•... , .....•...••..•..........•..•. •..•.......... ,. ..•....•.............•.......••.....•......•....•....•.......•••.... ..••• 28 SIMULATION CHARACIERlSTICS ..•..•..•....•..••............•.......................... .., .................................... " .......... 28 SIMULATION VERIFICATION AND VALIDATION ... ................................. ............... . ................................. 29 V RESUL TS ............................................................................................ " ........ " ..................................... 31 RESULTS CONSIDERING RC PERFORMANCE MEASURE ......... ....................... ......... . .... ............... .. . ........... 32 RESULTS CONSIDERING TIME BASED SUPPLEMENTARY PERFORMANCE MEASURES ...... , ......................... 36 THE EffECT OF THE POWER FACfOR (Z) ON PERFORMANCE MEASURES .............................................. .40 DETERMIN1NG THE V AWE Of Z BASED ON THE SYSTEM PARAMETERS ......... ...... .. ................ . ................ 51 VI CONCLUSION .................................................................................... " ..................... , ...... , ........ " ....... 53 SEQUENONG USING THE MODIFIED CRITICAL RATIO .............................. ....................... ...... ............. ... 53 SEQUENCING USING A QUANTIFIED DECISION DOMAIN ..... .................................................................. 55 REsEARCH COr...'TRlBUTION .................................................................................................................... 56 FuTURE DIRECTIONS ... ............................... ........................... ........................... .................. .. .......... .. .... 56 Future directions related to the modified critical ratio rule ........................................................... 57 Future directions related to generalizing the sequencing paradigm introduced in this research ... 58 REFEREN CES ......................... '."" ....... , ........ , ..................................................................... " ................... ,. 59 ,ApPENDIX I lNTlERARRlVAL TIME CALCULATIONS .. ................................................ ....... " ........... . ...... . 62 ,ApPENDIX 2 _ DESCRIPTION OF THE SIMULATION MODEL ....................... ............................. .................. 65 ApPENDIX 3  FORTRAN PROGRAM ...................................................................................................... 71 VI LIST OF TABLES Table Page TABLE I  SUMMARY OF RELEVANT TIME BASED SEQUENCING RULES .......................................................... 10 TABLE II  EXAMPLE DESCRlPl10N ................................................................................. .......................... 26 TABLE III  EVENTS DESCRIPTION .............................................................................................................. 26 TABLE IV  VALUES OF COST VARIABLES .................................................................................................. 27 TABLE V DESCR.WI10N OF EXPERIMENTAL CONFIGURATIONS ......................................... .......................... 31 TABLE VI  REsUlTS CONSIDERING RC MEASURE ................................................................................... 33 TABLE VII  REsm.. TS OF SAMPLE EXPERIMENT (6) ..................................................................................... 34 TABLE VIII  TARDINESS RESULTS .. .......................................................................................................... 37 TABLE IX  EARLlNESS RESULTS ........................... ........... ............... ........................ .................... ................ 37 TABLE X  ABSOLUTE DEVIATION FROM DUE DATE REsULTS ...................................... . .............................. 37 TABLE XI  DESCRIPTION OF A ITRIBUTES AND GLOBAL VARIABLES ........................... ............................... 68 vii LIST OF FIGURES Figure Page FIGURE 1  MODELING TARDINESS PENALTY COST ...................... . ...................................................... ...... 20 FIGURE 2  WARM UP ANALySIS ........................... ... ., ...... .................... ..................................................... 29 FIGURE 3 Ra.ATlVECOST RESULTS AT LOW UTILIZATION .............. . ........................................................... 35 FIGURE 4  RELATIVE COST REsULTS AT HlGH UTILIZATION ................. ...... .................. ............................. 36 FIGURE 5TARDINESS REsULTS ............................................................................... .............. " .................. 38 FIGURE 6  ABSOLUTE DEVIA TJON FROM DUE DATE REsULTS ............................................................. ...... 38 FIGURE 7 EARLINESS REsULTS .......................................................................................... ...................... 39 FIGURE 8  RELATIVE COST VERSUSZ FOR EXPERIMENT 1.. ......................................................................... 41 FIGURE 9 RELATIVE COST VERSUS Z FOR EXPERIMENT 2 .................................................... ...................... 41 FIGURE 10 RELATIVE COST VERSUS Z FOR EXPERIMENT 3 ....................................................................... .41 FIGURE 11 RELATIVE COST VERSUS Z FOR EXPERIMENT 41 .............................. .................. ......... .............. .42 FIGURE 12 RELATIVE COST VERSUS Z FOR EXPERIMENT 5 ........................ .................................................. 42 FIGURE 13  RELATIVE COST VERSUS Z FOR EXPERIMENT 6 ...................................................................... .42 FIGURE 14  RELATIVE COST VERSUS Z FOR EXPERIMENT 7 .......................................................................... 413 FIGURE 15  RELATIVE COST VERSUS Z FOR EXPERIMENT 8 ...................................................................... .43 FIGURE 16  RELATIVE COST VERSUS Z FOR EXPERIMENT 9 ...................................................................... ,43 FIGURE 17  RELATIVE COST VERSUS Z FOR EXPERIMENT 10 ..................................................................... 44 FIGURE 18  RELATIVE COST VERSUS Z FOR EXPERIMENT 11 ..................................................................... 44 FIGURE 19  RELATIVE COST VERSUS Z FOR EXPERIMENT 12 ..................................................................... 44 FIGURE 20  TARDINESS VERSUS Z FOR EXPERIMENTS 1 AND 2 ................................................................... 45 FIGURE 21  TARDINESS VERSUS ZfOR EXPERJMENTS 3 AND4 ................................................ . ........ ......... 45 FrGURE 22  TARDINESS VERSUS Z FOR EXPERIMENTS 5 AND 6 ................................................................. ,45 viii FIGURE 23  TARDINESS VERSUS Z FOR EXPERIMENTS 7 AND 8 ................................................................. .46 FIGURE 24  TARDINESS VERSUS Z FOR EXPERIMENTS 9 AND 10 ................................................................. .46 FIGURE 25  TARDINESS VERSUS Z FOR EXPERIMENTS 11 AND 12 ............................................................... 46 FIGURE 26  EARLINESS VERSUS Z FOR EXPERIMENTS 1 AND 2 ................................................................. .47 FIGURE 27  EARLINESS VERSUS Z FOR EXPERIMENTS 3 AND 4 ............. ..................................................... 47 FIGURE 28  EARLINESS VERSUS ZFOR EXPERlMENTS 5 AND 6 .................................................................. 47 FIGURE 29  EARLINESS VERSUS Z FOR EXPERlMENTS 7 AND 8 ............................. ...................................... 48 FIGURE 30  EARLINESS VERSUS Z FOR EXPERIMENTS 9 AND 10 ....................... ........................................... .48 FIGURE 31  EARLINESS VERSUS Z FOR EXPERIMENTS 11 AND 12 ............................................................. ..48 FIGURE 32  ABSOLUTE DEVIATION FROM DUE DATE VERSUS Z FOR Exp. 1 AND 2 .......... ................ .......... 49 FIGURE 33  ABSOLUTE DEVIATION FROM DUE DATE VERSUS Z FOR Exp. 3 AND 4 .................................... 49 FIGURE 34  ABSOLUTE DEVIATION FROM DUE DATE VERSUS Z FOR Exp. 5 AND 6 .. .................................. 49 FIGURE 35  ABSOLUTE DEVIATION FROM DUE DATE VERSUS Z FOR Exp. 7 AND 8 .................................... 50 FIGURE 36  ABSOLUTE DEVIATION FROM DUE DATE VERSUS Z FOR Exp. 9 AND 10 .............. .................... 50 FIGURE 37  ABSOLUTE DEVIATION FROM DUE DATE VERSUSZ FOR Exp. 11 AND 12 ................................ 50 FIGURE 38  SYSTEM REPRESENTATION .......................... ........................ . ......... . ........... .. .......................... 62 FIGURE 39  SLAM NETWORK MODEL ............... ...... ........................... .............................................. ......... 69 ix I The Problem and its Setting Introduction Organizing shop floor activities is an important task that affects the overall performance of a manufacturing enterprise. One of these activities is scheduling the jobs that are to be processed on the machines on the shop floor. In this research, we consider the scbeduling problem in a job shop environment. A maketoorder system is studied. Each job has its own due date, and if a job is fmished before its due date, it waits until its due date before being shipped to the customer. This characteristic is commonly referred to as forbidden early shipment. Job shops are one of the most popular shop floor structures in industry. Therefore, exploring the potential of improving the cost performance of job shop manufacturing is of high importance for both researchers and practitioners. Considering that the industrial community is giving considerable attention to speed and agility in the decade of the 90' s, it is justifiable that scheduling deserves significant study and research from the industrial engineering research community. In the decade of the 70's, technology was the key for a successful manufacturing business. The factors that affect the investment in technology (such as automated manufacturing systems or robots) were easily quantified in tenns of fmancial measures. Therefore, the process of justifying such investments was relatively easy. On the other hand, quality was the key word of a successful manufacturing business in the decade oftbe 80's. It was more difficult to measure the performance of a manufacturing system in terms of fmancial measures if quality was the aspect of concern. However, the existence of functions such as the Taguchi loss function helped to bridge the gap between technical ] and financial performance measures. For example. a technical performance measure such as variation from targiet can be related to financial performance measures such as cost. However, in tenns of the decade of the 90's, where the primary concern is time to market, the gap between technical and fmancial performance measures is not fully bridged. Considering that leadtime is a technical measure of speed or agility, the effect of reducing the leadtime is not easiJy quantified in tenns of cost or profit. Hence, an investment that leads to reducing the leadtime may not be fmancially justified. Also, there are other performance measures that are considered in a scheduling problem in addition to the leadtime such as inventory level, lateness and tardiness. Improving one of these performance measures may, and in many cases does, affect other performance measures. However, the trade off between these measures is not clearly understood. Dispatching Rules Dispatching rules are a popular technique in scheduling. Dispatching rules are simple heuristics that enable the decisionmaker to choose which job to load on a machine (if more than one is available) once it becomes idle. Dispatching rules are also known as sequencing rules. In this research, the terms dispatching rules and sequencing rules are used as synonyms. Dispatching rules provide good results and they are widely used because of their simplicity. Previous research fmdings in this area show that the dispatching rule that provides the best performance depends on system variables such as due date tightness, tardiness cost and inventory cost. 2 Performance Measures Different performance measures are being used in this research area. These performance measures can be divided into two basic categories.. The frrst category is time based performance measures, such as tardiness, earliness, absolute deviation from due date, throughput, time in system, average number of jobs in queue, and several other measures. The second category of measures is monetary based measures such as total cost per period and net present value. In this research, the primary performance measure of concern is a monetary based performance measure, which is relative cost per job (tms term is briefly de·f1ned later in this chapter and tborougbly discussed in Chapter IV). However, the cost perfonnance of a system is highly sensitive to the cost structure. Therefore, time based performance measures are monitored as supplementary performance measures to avoid any bias in results caused by the cost structure. Problem Statement The sequencing problem in previous research efforts is modeled as a problem that has a continuous action range (the setting of system parameters), and a discrete reaction domain (available sequencing rules). This inconsistency represents a potential problem and an area of research opportunity. This research attempts to model this problem as a problem that has both continuous range and continuous domain. Therefore, the objective ofthls research can be stated as to "investigate the potentia] of improving the performance of manufacturing systems through introducing a sequencing rule that has a continuous decision domain". 3 Definition of Terminology We defme here some of the key terminology used in this research. Leadtime: Lead time for a job j is defined as the difference between the due date of job j and the order arrival date of job j. Relative ,cost: relative cost fDr a job j is defmed as the total incurred co.st by a job (due to. inventory holding cost and tardiness penalty cost) divided by its selling price. Forbidden early shipment: If a job is co.mpleted before its due date, the job is stored in a storage area until its due date. In this research,. the cost associated with completing a job before its due date is the cost of holding this job as inventory. No. other penalties are realized as a consequence of completing the job early. However, the holding cost of fmished goods is higher than the holding cost of workinpro.cess. 4 II Literature Review Introduction In this chapter, a review of re]ated literature is present.ed. This review focuses on the research that studies job shop scheduling in a forbidden early shipment environment considering economic performance measures, since this is the area of concern in this research. The scheduling problem has several aspects including order review and release rules, due date setting and sequencing. The sequencing aspect of the scheduling problem is reviewed in this chapter. Other aspects of the scheduling problem are not reviewed since they are not relevant to this research. The literature review is divided mto three sections. First, different methodologies for modeling the fmancial aspects of the scheduling problem are reviewed. Next, the sequencing problem is considered. Finally, different experimental designs are reviewed in order to help designing the experiment of this resesrch. Literature Review aD Constructing Cost Models Most studies in this field consider tardiness cost and inventory carrying cost as the two basic cost segments that are affected by scheduling policies. However, the implications of these two factors have been modeled differently. Ragatz and Mabert (1988), Ahmed (1990),. Ahmed and Fisher (1992), and Philipoom et al. (1993) use the same cost structure. The performance measure used in these studies is total cost per period. Holding cost is calculated as a proportion of the work completed on ajoh (constant per week per hour processing time completed). This assumption means that no cost:i:s associated with holding raw materials, which might not be a realistic assumption. Tardiness penalty cost is considered as a proportion of the 5 holding cost (constant per week per hour processing time completed). The ratio between holding cost and tardiness penalty cost in these studies is 1 :20. Other ratios are used for sensitivity analysis. In addition, tardiness penalty in this cost structure is proportional to the work content. Considering that due date allowance is proportional to the work content, the oost structure that is used in the above mentioned studies results in a proportional relationship between due date allowance and tardiness penalty. In the: current study, we explore a more realistic tardiness penalty; one that is proportional to some measure of relative tardiness, such as tardiness divided by leadtime. Rohleder and Scudder (1992) use net present value as the perforIDalnce measure. They evaluated the inventory holding cost as a proportion of the job cost. Also in their study, there is no inventory cost associated with bolding raw materials in stock. The job cost is calculated as the cost of operating the machines (induding setup cost) that ajob has visited. They use a holding cost ratio of 20% ofthe inventory value per year (i.e., 20% of the job value will be incurred as inventory cost if a job waits for one year). The tardiness cost in their study is calculated as 10% of the selling price per year. Scudder et a1 (1993) use the same cost structure but modify the holding cost ratio to be 30% and the tardiness penalty ratio to be 20%. Scudder et al. (1990) also use net present value as the performance measure. In their study, the inventory holding cost is proportional to the job value. They also defme the job value as the cost of machine set up and the cost of machine operation. The researchers assume a justintime environment where raw materials arrive at the time of the flrst operation. Hence, there is no holding cost for raw materials. Two levels of tardiness penalty cost are explored. The flrst level is zero, i.e., there is no penalty 6 associated with late delivery. The second level is at 25% of job cost per day. This ratio may represent a highly perishable product considering that the average work content is 36 working hours. The same cost structure is used by Yang and Sum (1994). In a study by Amar and Xio (1997), the authors present an analytical model to minimize total cost in a static job shop (no order arrivals). The authors in this study consider inventory cost only. The authors show that a linear approximation of the time value of money effect is reasonable. The resulting cost structure, after neglectitng the compounding effect of interest, is a linear relationship between holding cost and the inventory value multiplied by the waiting time. Kawtununachai et al. (1997) study static scheduling in an automated flow shop. In their study, tardiness is handled by working overtime. Therefore, the actual tardiness penalty is the extra cost of overtime. Inventory holding cost is divided into two segments. First, workinprocess (WIP) inventory cost and second, [mal product inventory cost. WIP cost is proportional to the number of jobs in system multiplied by average holding time. The [mal product inventory cost is proportional to the number of fmished goods multiplied by the time finished goods wait for their due date. The difference between the two types of inventory cost is the holding cost factor. The average ratio of bolding cost factor for fmished goods to holding cost factor for WIP is approximately 15, which is high relative to other research efforts. Different cost structures have been introduced in the literature, several of which have been reviewed above. Most of these cost structures are based on quantifying inventory holding cost and tardiness penalty cost. Some researchers introduce time value of money into the cost structure. However, the effect of compounding discounting rates 7 has not been shown significant (Amar and Xio, 1997). The inventory and penalty cost that have been used in literature can be expressed in the following generic form: I j = !(Vj,t) where; Ij: the inventory cost for job j Vj: the value of job j t/ the time job j spent in the system and where; Pj: is the tardiness penalty of job j dj: The time job j departed the system DD/ Due date of job j The following points describe the basic differences between different cost structures: 1. differences in the methodology used to estimate the job value through the cycle time, 2. differences in the relationship between tardiness penalty cost and inventory holding cost, and 3. differences in the cost difference between holding finished goods and WlP. In the reviewed liteIatu~e, tardiness penalty depends only on the job value and absolute tardiness. This research explores a more realistic cost structure by expressing the tardiness penalty as a function of job value and relative tardiness. The details of this approach are discussed in Chapter IV. 8 Literature Review on Sequencing Rules Sequencing jobs on available machines has received considerable attention in the literature. Many sequencing rules have been proposed. However, few studies are found in the area of this research, which is job shop scheduling in a forbidden early shipment environment considering economic performance measures. In this section, sequencing rules that have been used in forbidden early shipment environments considering fmancial performance measures are reviewed. Sequencing rules in this area can be divided into two major types. The fIrst type is time based sequencing rules, and the second is monetary based sequencing rules. In general, time based rules perform better than monetary based rules (Hoffmann and Scudder 1983, Scudder and SmithDaniels 1989, Scudder et aI. 1990). Time based sequencing rules are the rules that use the time attributes of jobs to decide job priorities. Table I illustrates the sequencing rules that have been used in this research area A survey of sequencing rules can be found in Panwalkar and Iskander (1977). The rules listed in Table I are jobdependent rules. In some research, the authors use the operationdependent versions of these rules. For example, the operationbased version of SPT is to give the priority for the job that has the shortest operation processing time rather than shortest remaining processing time. In general, critical ratio (CR) has been found to be the dominant rule that performs best in forbidden early shipment in most shop structures (Ragatz and Mabert 1988, Scudder et. al 1990, Rohleder and Scudder 1992, Ahmed, 1990 and Ahmed and Fisher, 1992). 9 Sequencing Rule Description FCFS (First Come First Served) Process the job that arrived first to the queue SPT (Short'est Processing Time) I Prooess.the ~ob that has the least total remaining I . processmg tJDle CR (Critical Ratio) I Process the jOb that has the least critical ratio CR= (Time remaining until due date)! (Total rernainiI!Kprocessing time.) EDD (Earliest Due Date) Process the job with earliest due date N1DD (Modified Due Date) Process fIrst the job that has the earliest modified due dat.e. Modified due date is defmed as the maximum of job due date and its ear[y fmish time. Early [wish time is defmed as current time plus total remaining processing time. Table I  Summary ()f Relevant Time Based Sequencing Rules In the study by Ragatz and Mabert (1988), CR perfonns the best regardless of due date tightness and utilization level. In some cases, EDD and CR perform the same statistically (the authors did not specify these cases). In the case of 1; 1 cost ratio between inventory cost and lateness cost, EDD dominates other sequencing rules in providing the lowest cost. In the study of Ahmed and Fisher (1992), EDD and CR are found to be the best rules in most cases depending on the release mechanism and due date setting rule. Their study concentrates on the interaction between sequencing rules, due date assignment rules and release mechanism. Philipoom ,et al (1993) reach interesting results that are not oonsistent with other literature. They compare the perfonnance of SPT ta CR under different conditians .of due date tightness, machine utilization and release rules. Their results show that SPT out performs CR in most cases. CR is better only in the case of loose due date setting. The authors conclude that this inconsistency with the literature might be attributed to the high 10 tightness level used. In addition, as the ratio between penalty cost and inventory cost is reduced (1: 1), CR outperforms SPT in both loose and medium due date tightness. Scudderet al. (1990) also find CR to be the best rule, yielding the highest net present value in most of the cases they studied. CR ratio is compared with monetary basedmles. Scudder et al. (1993) fmd that operation based rules performs better under tight due date conditions, but as due dates are relaxed, job based rules perfonn better. They fmd that CR based rules and modified due date (MDD) perform the best considering NPV criterion. The results of this research are consistent with a previous work of Rohleder and Scudder (1992). Monetary based rules are the rules that use the financial information of jobs. Several researchers have examined monetary based rules. The general findings in this area show that time based rules perform better than monetary based rules (Scudder et al. 1990). Yang and Sum (1994) introduce two new rules that performed better than CR. The rules they introduce combine CR and tardiness penalty of the job. Their rules consist of a threshold based on the critical ratio. The jobs that have critical ratio above the specified threshold are scheduled based on weighted critilcal ratio (WCR) defined as follows: WCR= CRJHourly tardiness cost In their study, job value and processing time for a job are sampled from independent distributions, which might give an advantage to the rule they introduced since it considers both processing time and job value (by considering tardiness cost). 11 However, if job value is considered to be proportional to the processing time,. then the hourly tardiness cost will be proportional to the processing time and their rule becomes: WCR= CRffotal. processing time = Time remaining until due date/ (remaining processing time*total processing time) The above rule is a modification of the critical ratio rule by modifying the weight of the processing time in the critical ratio rule. However, the improvement achieved by Yang and Sum ( 1994) is not definitely attributed to modifying the critical ratio rule. The problem scenario in their research, which samples the job vaIue and work content from independent distributions, may have affected the results. In general, many researchers categorize dispatching rules according to their information content. For example, Chang et aI. (1996), divide dispatching rules into, shortest processing time based rules, longest processing time based rules, due date based rules, slack based rules and queue status based rules. The results of choosing the best sequencing rule are usually attributed to the information content of the sequencing rules. Chang et aI. conclude that if tardiness is the performance measure of concern, a due date based rule work the best. They also conclude that a shortest processing time based rule is the best rule to choose if completion time or flow time is the major perfonnance measure of concern. Using the same concept, Montazeri and Wassenhove (1990) conclude that shortest processing time based rules minimize waiting times. The review of research in this area shows critical ratio (CR) perfonns the best in most configurations. Other rules that performed well in the literature are EDD and to a lesser extent SPT. The literature suggests that the most important factors that affect the 12 performance of sequencing rules are due date tightness level, system utilization, and cost structme of the system. The best sequencing rule can be changed as the operating conditions change. Pierreval and Mebarki (1997) introduce a strategy that selects the sequencing rule based on the system conditions andlor based on the performance measure considered. Also, Wu and Wysk (1989) introduce an algorithm that allows selecting the sequencing rule for each short period. In both of these research efforts, the selection of the best sequencing rule is limited to the available sequencing rules. Also, at each change oppurtunity, the decision is either to change the current rule or stay with the current rule. Therefore the decision has discrete a domain in these cases. Literature Review on Experimental Design The objective of this section is to belp in designing the job shop structure that will be studied in this research. A Job Shop is defined by APICS (1970) as follows: "A flllnctional organization whose departments or work centers are organized around particular types of equipment or operations, such as drilling, forging, spinning, or assembly. Products flow through departments in batches conesponding to individual orders, which may be either stock orders or individual customer orders." Tbe factors that affect the job shop structure are the following: 1. tbe number of machines in the job shop, 2. the number of operations and the routing of each job, 3. the utilization level, order arrival process and prooessing time, and 4. the due date setting procedure. 13 Number of machines: Most researchers use environments with the number of machines between five and nine. Ragatz and Mabert (1988), Vig and Dooley (1991) and Ahmed and Fisher (1991) study a fivemachine job shop. Christy and Kanet (1990), Kanet and Christy (1989) study an eightmachine job shop environment. A model that is introduced by Hoffmann and Scudder (1983) consists of nine machines. This model has been used in several reseatrch efforts thereafter, e .. g., Rohleder and Scudder (1992) and Yang and Sum (1994). Philipoom et al. (1993) use a ISmachine job shop as an experimental environment for their reseatrch. Routing and number of operations: In most of the related literature, the average number of operations per job is either four or five operations in most cases. For example, in the study by Philipoom et al. (1993), the number of operations is sampled from a uniform distribution ranging from three to seven operations.. Also, in the often used model introduced by Hoffmann and Scudder (1983) the number of operations varies from two to seven with an average of four (no more information about the probability distribution is given). In the above studies, reseatrchers use random routing. Each machine bas the same probability of being visited next once a job compietes one of its operations. Revisiting is aUowed but not consecutively. This purely random routing represents a more difficult control problem and any bias introduced by this purely random flow should be considered in the conservative direction (Ragatz and Mabert, 1988). Order arrival processing time and utilization: Consistently, the arrival process follows a Poisson process in the reviewed literature. However, different distributions were used to model the processing time. Philipoom et al. (1993), Ahmed and Fisher 14 (1991), and Ragatz and Mabert (1984) use an exponential distribution to model the processing time. Vig and Dooley (1991) use a 2Erlang distribution. Hoffmann and Scudder (1983) use a truncated DOnnal distribution with a standard deviation equal to one ninth of the mean. The variance is increased by other researchers who studied the same system, e.g., Rohleder and Scudder (1992) who use a standard deviation equal to one third of the mean. The mean interarrival time and the mean process time are set to achieve a desired level of utilization. The above researchers use utilization levels between 85% and 93%. In most of the above research, preemption, breakdown, and splitting of jobs are not considered. Also,. setup time is usually included in processing time. Only Hoffman and Scudder (1983) explicitly consider setup time in their model Due Date Setting: Many procedures are used in literature to set due dates. Excellent reviews of due date setting mechanisms can be found in Ahmed (1990), Cheng and Gupta (l989), and Ragatz and Mabert (1984). The rule that shows the best performance in different settings is total work content (Kanet and Christy 1989, Baker 1984). Therefore,. most of the research in this area use a TWK rule (e.g., Ragatz and Mabert, 1988, and Philipoom et al. 1993). TWK is defmed as follows: DD. =a.+k~n p .. 1 } ""'';=1 l) where; DDj : is the due date of job j aj: Arrival time of job j Pij: is the processing time of operation i for job j k: allowance factor 15 n: number of operations Different procedures are adopted in the literature to select the value of k. In general. researchers study three values of k that result in three due date tightness le¥els, loose, medium and tight. Ragatz and Mabert (1988) choose the values ofk such that the ....... resulting number of tardy jobs is 5%, 10%, and 20% for loose, medium and tight due dates respectively when FCFS is used. Yang and Sum (1994) use the same procedure but they use CR instead of FeFS. Philipoom et aI. (1993) use a k value ranging from 4.3 to 10.9. Baker and Kanet (1983) use allowance factor values between 2.5 and 20. Conclusion The literature review shows that the selection of best sequencing rule depends on the systems parameters. Although the change in system parameters has continuous range. the response (selecting tbe best sequencing rule) has a discrete domain. The research gap that this research attempts to fill is providing a mechanism that quantifies the response domain (selecting the best sequencing rule) over a continuous range. 16 ill Research Goals and Objectives The main goal of this research is to introduce a sequencing rule that has more flexibility than existing sequencing rules. One important characteristic that is need,ed in such a rule is that it should have a continuous decision domain. In this research, we propose a modified critical ratio rule CRz• We defme the modified critical ratio rule as follow where; CRz: is the modified critical ratio DD/ is the due date for job j rpj: is the remaining processing time for job j t: is the current time z: a power factor The value of the power factor z is to be determined as a function of system parameters. Consider the following two values of the power factor (z); zero and one. These values of z will result in the following. 1. If z is set to zero, CRz yields DD.t CR = J =DD. _to z 0 J' (rpj) Which is the EDD rule 2. If z is set to one, CRz yields 17 CR z DDjt _ DDit.  , 1 (rpj) (rpj) Which is the CR rule. The above cases show that using an appropriate value of z, the modified critical ratio rule yields decisions consistent with EDD or CR. Using other values of the power factor z, over its continuous range,. yields other (hopefully superior) sequencing decisions. Research Objective The primary objective of this research is to mvestigalte the potential of improving the cost performance for a given job shop using the modified critical ratio rule. The effect of three factors on z value will be studied in this research. These three factors are due date tightness., cost structure and machine utilization. Tasks The tasks required to accomplish the research goal are the following. 1. develop the job shop model and the cost structure, 2. develop the simulation model, 3. perform pilot runs to fmalize experimental factors, 4. execute the simulation experimental design, 5. analyze the simulation results, 6. develop the empirical formula of the power factor z, 7. develop conclusions and reconunendations, 8. document the research, and 9. identify areas of future research. 18 IV Research Methodology Simulation is the evaluation tool in this research. Simulation is widely used in this research area since developing analytical solutions for job shops with dynamic arrivals is difficult and requires many assumptions. In order to use simulation as an analysis tool, we developed a job shop model to be used in this research. The SLAM II simulation language (Pritsker, 1995) is used to simulate the job shop. The job shop was developed to be consistent with other literature based model. In addition, the literature has been considered in developing the cost structure. However, we propose a ma:jor modification in modeling the tardiness penalty. Traditionally, tardiness penalty has been calculated as a function of job value and absolute tardiness. In this research, we consider the tardiness penalty as a function of job value and relative tardiness. Relative tardiness will be modeled with respect to leadtime. As discussed in the literature review, tardiness penalty cost and inventory holding cost have been modeled in the following generic forms: In this research, the inventory carrying cost will follow the same generic form. However, the tardiness penalty cost will be modeled as P=f[V {d'J DDJ. }] } J' DD·a. } } where; /j: the inventory cost for job j; Vj: the value of job j.; 19 Pj: is the tardiness penalty of job j; dj: The time job j; departed the system; DDj: Due date of job j; and aj: the order arrival time of job j. Figure 1 illustrates how the tardiness penalty cost is modeled. Ajob will accumulate tardiness penalty cost equal to its selling price if it is late for a period proportional to its lead time. The constant pt shown in Figure ~ is defined as the penalty tightness factor. Two levels of penalty tightness factor (pt) are studied in this research; I and 2. If the penalty tightness factor is set to 1, it means that ajob wiu mcur tardiness penalty cost equal to its selling price if it is late for the period of its lead time. Similarly, a job will incur tardiness penalty cost equal to its selling price if its lateness is twice its lead time, when pt is set to 2. Revenue Selling Price Delivery Date I Lead Time '" pt I Figure 1  Modeling Tardiness Penalty Cost Assumptions The following assumptions are made in this research. • Machine breakdown is not considered. 20 • No scrap or rework is taken into account. • Queue capacities are infmite. • Preemption is not allowed. • Setup time is included in the work content of each job. • Time value of money is included in the holding cost and penalty cost factors. • Jobs are released to the shop floor immediately after receiving the order. • The cost structure is valid in environments where relative tardiness is valid as a performance measure. Job Shop Description In this research. we study a job shop that consists of seven machines. Orders arrive for one unit of each product. Each product is unique therefore, setup time is included in processing time. The number of operations required to complete a job is sampled from a discrete uniform distribution from three to seven operations.. The duration of each operation for a job is sampled independently from a uniform distribution of [3.5, 6.5] time units. Routing of jobs is set randomly such that ajob has the same chance of visiting any machine except the machine that is visited at the current operation. Therefore, revisiting is allowed but not consecutively. InterarrivaI time of orders is exponentially distributed. The mean of the exponential distribution is set so that the desired utilization level (an experimental factor) is achieved. The mean oftbe interarrival time is set according to the following equation A = lAp Q J1 where; Ao: is the order interarrival time 21   J.l:: is the average processing time p: is the desired machine utilization. A complete derivation of the above equation can be found in Appendix 1. After all operations are completed for a job, the job will wait if it is completed before its due date. Otherwise, the job will leave the system. Due dates are set on one of three levels; loose, medium and tight. The Total Work Content method (TWK) is used to set the dates. The value of the constant k is chosen to be 3,6 and 9 to generate loose, medium and tight due dates. Some researchers set the due dates tightness based on the number of tardy jobs. For example, Ragatz and Mahert (1988) set the levels of the allowance factor k so as 5%, 10%, and 20% tardy jobs are achieved when FCFS sequencing rule is applied. In this research, we refrained from following this procedure since the percentage of tardy jobs does reflect the actua1 performance of tbe manufacturing system of concern in this research. The percentage of tardy jobs depends on the sequencing rule appJlied at the queues. Also, average tardiness is not correlated with the number oftardy jobs. A given sequencing rule might produce low percentage of tardy of jobs which indicates that the due dates are loose, however, the average tardiness produced by this rule may he high which contradlicts the conclusion that the due date are loose. The selling price (Sj) of each job is linearly proportional to its processing time. The raw material cost of a job j (Rj ) is 30% of its selling price (Sj) and the value added to each job is 20% of its selling price. The value added at each operation is proportional to the proportion of work content completed at this operation. This cost structure assumes that 50% of the seUing price is aUocated for profit and overhead expenses. Also, it is 22 assumed that 25% of the selling price is allocated for overhead expenses and 25% is allocated for profit. After a job is completed, its value is 75% of its selling price (Sj), which includes raw .material cost, value added, and overhead expenses .. The job value is increased instantaneously after an operation is completed. The job value is used to calculate the inventory value. The various percentages in this approach were set arbitrarily but are believed to be representative of realistic scenarios. Cost Stmcture The performance measure in this research is average relative cost per job as defmed below. where: RCj: average relative cost per job Tej : total incurred cost for a job j. The total incurred cost is the sum of inventory holding cost and penalty cost. ~.: the selling price for job j Two types of costs are considered in this research. First, the inventory holding cost and second the penalty cost. As discussed in the literature review, these two segments are the two major segments that have been introduced in the literature .. The inventory holding cost per job is defined as follows: where; dj I j = f HVjdt rj 1/ is the inventory holding cost for job j 23 H: is the ho ldim:g cost factor "}: is the value of job j Tj: is the release time for job j (the time at which job j is released to the shop floor) dj: is the time job j departed the system. Since the system of concern is a discrete system, the above integration can be expressed as follows: ,,+1 1 j = I. Ifti;,itj,i  t i_I ,}) i=l where; lj: is the inventory holding cost for job j; H: is the holding cost factor; V;,/ is the value of job j before being processed on machine I;. and t;,j: is the time at which job j leaves machine i, !oj = rj. Note that Vi,} is the cost of raw material for job j (Rj). The storage area where jobs wait until their due date is modded as the machine number (n+ 1). The value of a job in the storage area will considered 75% of the selling price for the purpose of estimating the holding cost in the storage area. The value of H will be set so the raw material of an average job (5 operations, 5 days each) will incur 5% of its selling price, iftbe raw material is stored for the period of the job's lead time. The holding cost ratio will vary between 2.7% (for a job that needs 3 operations, 3.5 days each) and 9.1 % (for a job that needs 7 operations, 6.5 days each) according to this configuration. The second segment of cost that is considered is the penalty cost caused by missing a due date. The penalty cost is defmed as follows: 24 Where; Pj: is the penalty cost for job j; Pj: is the penalty cost factor for job j; , '1 DDj: is the due date for job j; and I , 'I dj : is the time job j departed the system. The value of the factor pj is set so that the tardiness penalty cost is proportional to the job's leadtime. The factor pjis calculated as follows: where; Sj: is the selling price of job j pt: is the level of penalty, when pt =1, the penalty cost is equal to the selling price if a job tardiness is equal to its lead time. Pj: is the penalty cost factor for job j DD/ is the due date for job j aj: is the arrival t.ime for job j Example Consider a simplified system that consists of two machines. The initial conditions are idle and empty. The value ofH is 0.01. Two jobs are considered and their attributes are shown in Table II. 25 I Ii Job 1 Job 2 Arriving time 0 2 Routing 12 21 Processing Time on maclhine 1 10 1 Processing Time on machine 2 5 I J 1 Due Date 45 8 Selling price ($) 75 10 Table II  Example Description Table ill describes the events each job goes through: Time · Event 0 Job 1 starts its frrst operation on machine 1 2 Job 2 starts its fIrst operation on machine 2 3 Job 2 finishes its fast operation and waits tor machine 1 10 Job 1 fmishes its first operation and starts its second operation on machine 2 10 Job 2 starts its second operation on machine 1 11 • Job 2 finishes its second operation and leaves the system 15 Job 1 fmishes its second operation and waits until its due date 45 Job 1 leaves the system Table In  Description of Events Note that Job 1 finishes 30 time units early and Job 2 fmishes 3 time units late. Table IV shows the cost variables that willlbe used to calculate the cost of each job. The variables shown in Table IV are calculated using the approach described in the previous section. After identifying all tbe cost variables, the relative cost ratio for each job is calculated as follows. For Job1: ,,+1 II = L.~.l (ti ,1  ti_I .I ) i=1 = 0.01(22.5)(10) + 0.01(30)(5) + 0.01(56.25)(30) = $20.63 ~ = PI[dl  DDI r = 0.08333(0) = $0.00 Tel = $20.63 26  ReI = 26.63n5 = 27.5% The interpretation of this number is that the sum of inventory cost ($20.63) and tardiness penalty cost ($.00) is 27.5% ofthe selling price ($75.00) For job 2: n+1 /2 = LHV;,2(ti,2 ti  1,2) ;=1 = 0.01(3)(1) + 0.01(4)(10) + 0.01(7.5)(0) = $0.70 TC2 = 0.70 + 2.50 = $3.20 RC2 = 3.2/10 = 32% Variable Description Value RI Raw Material Cost of Job 1 $22.50 R2 Raw Material Cost of Job 2 $3.00 jJI Penalty cost factor for job 1 $0.8333/ time unit P2 Penalty cost factor for job 1 $0.8333/ time unit Vl,l Value of Job 1 before being processed on machine 1 $22.50 , V21 Value of Job 1 before being 'Qfocessed on machine 2 $30.00 V3.1 VaIue of Job 1 after completing all operations $56.25 V2.1 Value of Job 2 before being processed on machine 1 $3.00 V2~ Value of Job 2 before being processed on machine 2 $4.00 V3,2 Value of Job 2 after completing all operations $7.50 Table IV  Values of Cost Variables Research Factors The effect of the following factors on cost performance will be considered: 1. due date allowance factor (k), 2. penalty tightness Cpt), 3. power factor z, and 4. system utilization. 27 L < Due date allowance factor levels are 3,6, and 9. Two levels of penalty tightness are considered, pt = 1 and pt = 2. The effect of utilization is studied on two levels of 85% and 92%. At each of these combinations, the value ofz that yields the best performance measure ofconcem is determined experimentally. Simulation Model The SLAM II simulation language is used to simulate the job shop described above. All the job's attributes are assigned at the time the job arrives to the system. This ensures that jobs in different simulation scenarios have the same attributes. Therefore, the simulation runs are dependent due to common random numbers and a paired ttest can be used to establish desired conclusions. A paired ttest is stronger since it eliminates the variation between simulation runs due to using different random number streams in djfferent runs. A complete description of the simulation model can be found in Appendix 2. Simulation Characteristics Three characteristics are important to ensure good simulation results. These are run length, warm up period and number of replications. Warm up period is specified by observing variation of the performance measure (average relative cost) with run time. The procedure described in Law and Kelton (1991) was foUowed to determine the length of the warm up period. The number of replications we used to apply this procedure is seven replications. Also, we ased a window length w of 800. The time after which the relative cost values are stable (plus a safety factor) is set to be the warp up time. Figure 2 shows the moving average of the performance measure. As shown in Figure 2,. the average relative cost is observed to stabilize after 3,000 to 28 c 4,000 jobs leave the system However, since execution time was not a major limitation in this study, a conservative warm up period of approximately double this number of jobs is used. The warm up time is set at 30,000 time units which corresponds to approximately 7,500 jobs. Warm up Analysis 1400 1200 1000 CJ 800 a: 600 ~ r.... r~ ...............  I '" 'v'"" ......./ "' I 400 200 0 o 5000 10000 15000 20000 25000 Job Number Figure 2  Wann up Analysis The run length is determined to be 400,000 time units. This run length is longer than the recommended rule of thumb that suggests a run length equal to ten times the warm up period. The number of replication used in each run is 10 replications. The above values were acceptable after analyzing the simulation results. The results based on the above characteristics were found accurat,e enough to establish conclusions based on a paired ttest. The above parameters (run length and number of replications) were chosen so that the performance of different sequencing rules will be statistically different using a paired t test. Simulation Verification and Vatidation Verification is the process of ensuring that the simulation program is executed properly. Tracing is a very effective tool to perform the verification process. Extensive tracing reports were generated. Entities (jobs) were traced to ensure that the entities went 29 « through the proper sequence of events and the proper assignment of attribute values. Also,. tracing reports showed that priority was given to a job in the queue according to the intended dispatching discipline. Validation is the process of ,ensuring that the model is representing the real system. Since there is no existing real system that can be used to compare the simulation results, the validation process can not be conducted in this manner. Validation has been conducted by comparing the simulation results with similar published research results. Consistence with the literature, the critical ratio rule was found to perfonn the best in most cases, also the shortest processing time was found to be the best rule under very tight due date conditions. Also, the simulation output indicated that the utilization level of the machines, average processing time, and average number of operations corresponded with the expected values. 30 I L c V Results As discussed previously, 12 different system configurations were studied. Table V describes the value of each experimental factor for each of these configurations. Experiment K (due date allowance factor) U (Utilization) pt (penalty tightness factor) ] 3 85% i 1 2 3 85% 2 3 3 92% 1 4 3 92% 2 5 6 85% 1 6 6 85% 2 7 6 92% 1 8 6 92% 2 9 9 85% 1 10 9 85% 2 I 11 9 92% 1 , 12 9 92% 2 Table V Description of Experimental Configurations For each experiment, multiple values of the power factor z were evaluated. These values included zero and one, to generate results equivalent to the EDD and CR rules. In addition, the SPT rule was evaluated (not using the CRz formulation). A search for the best value of z based on relative cost performance was conducted.. A statistical comparison of the perfonnance of modified critical ratio rule at the best identified z value and the SPT, EDD, and CR was conducted using a paired ttest. The primary performance measure of this research is relative cost. Other time based perfonnance measures are monitored to assure that the superior performance of the modified critical ratio is not influenced by the cost structure introduced in this research. The time based performance measure monitored are tardiness, earliness, and absolute deviation from due date. The following results were collected from the simulation model: I l 31 s ~, . 1. average tardiness oftardy jobs, 2. average earliness of early jobs, 3. average relative cost per job, 4. number of early jobs, and 5. number oftardy jobs, In addition to the above measures, average inventory holding cost per job and. average tardiness penalty cost of tardy jobs is collected. However, these statistics were not considered as performance measures; but they are used to help explain and draw conclusions about certain behaviors of the system. The rest of this chapter is organized as follows. First, the performance of the modified critical ratio rule is compared with other benchmarking rules considering relative cost as the performance measure. Second, the results showing performance of different sequencing rules considering supplementary time based peribrrnance measures ale presented. The performance of modified critical ratio rule using different values of the power factor z is discussed next. Finally, the setting of the best value ofz as a function oftbe system parameters is discussed. Results Consid'ering RC P,erformance Measure This section compares the performance of the modified critical ratio rule with EDD, CR, and SPT rules. The results presented in this section regarding the performance of the modified critical ratio rule ale the results achieved by using a z value that yields the best relative cost value at each configuration. Table VI shows the average relative cost achieved by using the SPT, EDD,. CR, and CRz rules ~espectively, in each of the experiment configurations listed in Table V. The improv,ement achieved by using the 32  5 modified critical ratio rule over the best sequencing rule in each experiment configuration is also presented in Table VI. The best performance among SPT, EDD and CR is marked by an asterisk. Experim.ent I Average Average Average Average % Improvement I . RCwben RCwben RCwhen RCwhen compared with I using SPT . using using CR using CRz best rule I EDD I I 1 38.0% , 36.17% *32.24% ~1.95% 0.89% 2 I I i 2].4% 20.29% *18.12% 17.97% 0.79% I 3 *101.8% I 130.46% 119.33% 103.70% 1.85% : 4 *54.4% I 68.42% 62.73% 54.84% 0.79% I 5 i 16.3% 9.36% *8.78% 8.76% 0.26% I 6 I 12.7% 8.74% *8.51% 8.50% 0.19% 7 42.1% I 30.66% *24.81% 23.59% 4.9 1% i 8 I 16.7% 0.66% *0.80% 13.64% 0.17% I 9 26.2% 19.24% *16.20% 15.56% 3.9.5% I 10 15.5% 0.65% *0.79% 13.61% 0.25% I I 11 ! , 15.6% 30.31% *13.74% 13.40% 2.47% 12 14.0% 22.56% *12.77% 12.59% 1.46% Table VI  Results Considering RC Measure A paired ttest was llsed to test whether the results are significantly different at 95% confidence level. For each experiment, the performance of each rule was found significantly different from the performance of other rules. Table VII shows the results obtained by applying the modified critical ratio rule and the critical ratio rul.e for experiment 6 (K=6, U=85%, pt=2). The procedure followed to test the significance of the difference is demonstraied using the values shown in Table VII. Ho: The difference between CR and CR12 is zero H1: The difference between CR and CR1.2 is not zero I I 1 33 L 9 Rejection criterion: Construct a 95% confidence intell'Val for the difference. If the confidence interval contains zero, do not reject the null hypothesis, else reject the null hypothesis. The width of the confidence interval (CIW) is obtained using the following equation: The value of ta12 for a= 95% is 2.228, and the standard deviation for the difference coluIIlll in Table VII is 0.145. Hence, the width of confidence interval CIW will be 0.102. The average of the Difference coluIIlll in Table VII is  0.153. Therefore, the upper bound of the confidence interval is  0.509. Hence, the null hypothesis is rejected and we conclude that the perfonnance of CRI.2 is statistically better than the performanoe of CR. Replication CR Results CR1.2 Results Difference 1 I 84.85 85.03 0.18 2 84.69 85.04 0.35 3 84.31 84.23 0.08 4 85.58 85.86 0.28 5 85.25 85.45 0.2 6 84.36 84.61 0.25 7 85.19 85. 11 0.08 8 85.14 85.36 0.22 9 86.04 86. 19 0.15 10 84.09 84.15 0 . .06 Table VII Results of sample experiment (6) The modified critical ratio rule provides better performance than other tested sequencing rules in all cases except for experiments 3 and 4 at which the utilization level is 92% (high) and the due date allowance factor is 3 (tight). In these cases, the maximum 34  value of z that was tested is 22 due to computer execution limitationsl . Figure 3 shows the performance of 'each sequencing rule at the high utilization level and Figure 4 shows their performance at the low utilization level. It is noteworthy that the penalty tightness factor does not appear to affect the conclusion of this researcb.. The performance of different sequencing rules is consistent at the two levels of the penalty tightness factor pt. Also, the next sections will show that the value of best z does not change when the penalty tightness factor pt is changed from I to 2. RC Relative cost at low utilization 0.4 0.35 0.3 0.25 0.2 0.15 0.1 0.05 o ~ ~ Figure 3 Relative cost results at low utilization ~Edd I:mI S PT IIGR .CIRz I FORTRAN Language gives an execution error if a number is larger than 9.9XloJ8• At z value greater that 22, some of the numbers become greater than 9.9Xl~8 35  Relative cost at: high utilization 1.4 1.2 1 RC 0.8 1m! Edd mSPT i 0.6 III C.R 0.4 .CRz 0.2 0 Figure 4  Relative Cost Results at high utilization Results Considering Time Based Supplementary Performance Measures Tables vrn through X present the perfonnance of the modified critical ratio role compared with other sequencing roles considering tardiness, earliness and absolute deviation from due date measures, respectively. The same set of main experiments shown in table V was used. However, more values of the power factor z were evaluated in some cases to fmd the z value that yields the best performance for each particular performance measure. Since the cost structure is not a factor when time based performance measures are considered, there are six, rather than 12, experimental configurations when timebased performance measures are considered. The same statistical test discussed showed that the performance of each rule is significantly different than the performance of other rules at each experiment. The SPT rule is known to perfonn the best when average flow time performance measure is considered. However,. since we are concerned with a forbidden early shipment environment, a 36  comparison between the SPT rule and the modified critical ratio rule is not conducted. The comparison between the modified critical ratio rule and the SPT rule is conducted to test whether SPT will still outperform the modified critical ratio rule when due date related measures are considered. Experiment Average Tardiness EDD CR CRt; % Improvement When Using SPT 1,2 32.22 , 24.23 21.48 21.28 1.09% 3,4 94.33 I 89.14 86.09 82 . 83 3.79% 5,6 14.59 1.96 1.17 0.82 31.73% 7,8 65.07 33.52 26.43 24.88 5.88% 9,10 7.74 0.09 0.03 0.02 39.64% 11,12 48.41 8.96 4.45 3.75 15.58% , Table VIII  Avernge Tardiness results Experiment SPT EDD CR CRz % Improvement 1,2 14.91 6.69 4.67 3.83 17.96% 3,4 10.88 1.24 0.59 0.48 17.67% 5,6 62.85 60.13 52.88 50.55 4.42% 7,8 56.63 21.67 16.77 13.69 18.39% 9,10 141.07 133.87 122.31 119.45 2.34% 11 ,12 114.95 73.28 63.77 55.39 13.14% Table IX  Average Earliness Results Experiment SPT EDD CR CR~ % ImprovemeDt 1,2 47.13 30.92 26.15 25.50 2.47% 3,4 105.21 90.39 86.68 83.49 3.68% 5,6 77.44 62.10 54.08 52.35 3.20% 7,8 121.70 55.19 43.20 38.77 10.26% 9,10 148.81 133.96 122.34 119.47 2.35% 11,12 163.37 82.23 68.22 60.11 11.88% Table X  Average Absolute Deviation from Due Date Results Figures 5, 6 and 7 show the performance of the modified critical ratio rule compared with other experimented rules. In Figure 5, average tardiness results for experiments 5 and 9, are not included. The average tardiness in these experiments is very small, and it can not be compared with other experimental results on the same scale. 37   Also, in Figure 7, average earliness results for experiment 4 are not shown for the same reason. Perfiorman,ce of Sequencing Rules 100 90 80 70 (I) 60 II) G) c =0 50 ~ ~ l 40 30 20 10 0 K=3,U=85% K=3,U=92% K=6,lI=92% K=9,U=92% Figure 5· Average Tardiness Results Performance o,f Sequencing R'ules II) 180 ,, :Iii c G) 1601 5 140+~~~ III Edd' Ii!SPT IIICR .CRz iE 120 + ,, m~ c 100+o ;:l' CIJ ·t c S ::J "0 CD .Q '" 80 +== 60 + 40 +~I 20 o IiliISPT mCR .CRz Figure 6  Average Absolute Deviation from Due Date Results 38  I t I ! L 160 140 120 GO .G.O .E 100 m 80 t .. 60 <" 40 20 a [/5\0 ,;:f'fi ¥~' IPerforman,~e of Sequen~ing IRules [/5\0 1>\0 !t\o ,;:f'fi ,;:f .;)~' .1" ~' t?' Figure 7 Average Earliness Results IIEdd ~SPT filCR .CRz These results show that the modified critical ratio rule outperforms other tested rules in all configuration settings in each time based performance criteria considered. This assures that the superiority of critical ratio rule is not influenced by the cost structure introduced in this research. On the ,contrary, the cost structure has a negative impact on the performance of the modified critical ratio rule. SPT was the only rule to beat the modified critical ratio in the case of tight due dates and high utilization (experiments 3 and 4). This can be explained by understanding that the SPT rule results in very high variation in the flow time of its jobs. The SPT rule tends to make the jobs of small work content fmish early and the jobs of large work content finish late. The jobs that are late have a high work content and consequently high due date allowance (since TWK is used to set due dates). Therefore, although SPT generates higher tardiness than the modified critical ratio, the relative tardiness of the late jobs are not high. Since the cost structure is concerned with relative tardiness rather than absolute tardiness, the SPT rule performs better than the modified critical ratio even though the modified critical ratio produce lower tardiness, and preferred time based performance. 39 r It is also noteworthy that the improvement achieved by the modified critical ratio rule is higher when time based performance measures are consider,ed. When time based performance measures are considered, the performance of the sequencing rules is compared to an ideal value of zero (the ideal tardiness, earliness, and absolute deviation from due date is zero). On the other hand, the ideal performance when relative cost performance measure is not zero. If a job is completed on its due date, it will still incur some inventory holding cost. Therefore, the difference between the performance of sequencing rullies will be influenced by the minimum cost incurred by a job, and the percentage of improvement will be less than the improvement realized when time based performance measures are considered. Another issue to be considered is the practical significance of the improvement realized by the modified critical ratio rule. Previously, we have shown that this improvement is statistically significant. When relative cost performance measure is concerned, we can see that the improvement realized by the critical ratio rule varies between 0.26% to 4.91 %. This improvement corresponds to an increase in the profitability of the product, which might be practically significant. The simplicity of applying the modified critical ratio rule does indeed add to its practical significance. The Effect Of The P'ower Factor (Z) On Performance Measures The simulation results presented in previous sections demonstrate the superiority of the modified critical ratio rule. In this section, the values of the power factor (z) tbat yield this superiority are discussed. Figur'es 8 through 37 show the values of different I performance measures as a function of the power factor z. I I l 40 rC I i L 37% 36% 35% RC 34% 33% 32% 31% o ~ ~ 0.5 K=3.U=850/0~ pt =1 ~ ~ ~ V' 1 1.5 2 Power Factor (z) Figure 8  Relative Cost versus z for Experiment 1 20.50% 20.00% 19.50% RC 19.00% 18.50% 18.00% 17.50% ~ o ~ ~ 0.5 K=3, U=85%, pt=2 "" ~ ~~ "" 11.5 Puwer Factor (z) 2 Figure 9 Relative Cost versus z for Experiment 2 K=3,U=92%, pt=1 135% 125% K \ RC 115% 105% '¥"~ 95% 0 5 10 15 20 Power Factor (z) Figure 10 Relative Cost versus z for Experiment 3 41 2.5 2.5 25 K=3,U=95%. pt=2 70% ~______________ ~I 1'. 65% +~T~« RC 60% +~~=~ 55% +~~==~~==~~~ 50% +~~~~~ o 5 10 15 20 25 RC RC Power Factor (z) Figure 11 Relative Cost versus z for Experiment 4 K=6,U=85%,pt=1 9.40% 9.30% 9.20% 9.10% 9.00% 8.90% 8.80% "" ~ "'" / "'" /' I , /' 8.70% '" o 0.5 1 1.5 2 Power Factor (z} Figure 12 Relative Cost versus z for Experiment 5 8.75% 8.70% 8.65% 8.60% ~ ~ '" 8.55% 8.50% 8.45% o 0.5 '" ~ / ~ / v 1.5 Power Fadm" (z) 1> 2 Figure 13  Relative Cost versus z for Experiment 6 42 2.5 2.5 K=6,U=92%,pt=1 35%., 30%~~~~ 25%r~~~_ ~_~_~ ====~==~~==~.~ RC 20%+~~~_r~~~ o 0.5 1.5 2 2.5 3 3.5 Power Factor (z) Figure 14  Relati¥e Cost versus z for Experiment 7 K=6,U=92%,pt=2 20.00% +i RC 17.50% +""..,':;;;OO(Ii 15.00% +....,r~~;! o 0.5 1 1.5 2 2.5 3 Power Factor (z) Figure 15 • Relative Cost versus z for Experiment 8 K=~,U=85%.,pt=1 13.85% 13.80% ~ .~ ...() RC 13.75% / / '13.70% I 13.65% 13.60% 1.5 ~ "'0"" , 1 0.5 A o 0.5 1.5 2 Power Factor (z) Figure 16 • Relative Cost versus z for Experiment 9 43 2.5 .... K=9,U=85 %,pt=2 13.85% 13.80% '" ! 1 ~ / "V RC 113.75% RC RC 13.70% 13.65% 13.60% 1.5 6 1 / ~ "V' 0.5 o 0.5 1.5 2 Power Factor (z) Figure 17  Relative Cost versus z for Experiment 10 K=9,U=92 %,pt=l 2.5 17.50% r, 15.00% 1"""'0;;::1 12.50% +1 1 0.00% +...,...rrr.~'T"""I 1 0.5 0 0.5 1.5 2 2.5 3 3.5 Power Factor (z) Figure 18  Relative Cost versus z for Experiment 11 K="U=92%,pt=2 14.50"10 ,.., 14.00% +'~........,.~I 13.50% +~~..:j 13.00% +=....:_j 12.50% l~::::::'Q:::==~=4 12.00% +,.,r'T""".,_j 1 0.5 o 0.5 1 1.5 2 2.5 3 Power Factor (z) Figure 19  Relative Cost versus z for Experiment 12 44 1 .. r K=3,U=85% 25 i III 24 III CD :cc 23 ... II:! I 22 ..... I ~ I I ~ i ~ <> .21 v 20 o 0.5 1 1.5 2 2.5 P01r'Ier !Factor (z) Figure 20  Tardiness versus z for Experiments 1 and 2 K=6,U=85% 2.3 '~" I: 1.9 :s ''""' 1.5 ~ 1.1 p / ~ I ~ / "' ./ 0.7 ... o 0.5 1.5 2 2.5 Power Factor (z) Figure 21 Tardiness versus z for Experiments 3 and 4 K=9,U=85% 0.5 r, 0 .375 +l 0.25 +l 0.125 +,~. 'Qo..,,=___; ·1.5 1 0.5 o 0.5 1 1.5 2 2.5 Power Factor (z) Figure 22  Tardiness versus z for Experiments 5 and 6 45 K=3,U=92% 100 ! ~ 95 c \ :a s.. 90 '" ~ Eo 85 ~ 80 5 0 5 10 15 20 25 Power Fa.ctor (z) Figure 23  Tardiness versus z for Experiments 7 and 8 K=6,U=92% 34 ~ til :!l :ca 30 ~ s.. E'o"< 26  22+._..~~ o 0.5 1.5 2 2.5 Power Factor (z) Figure 24  Tardiness versus z for Experiments 9 and 10 ~ J: =s s.. K=9,U=92% 11 +~ ~ 7+~~~ 3+~._._r~ 1 o 2 3 4 Power !Factor (z) Figure 25  Tardiness versus z for Experiments 11 and 12 46 r f ~ =.=. ~ 7 ~ ~ ~~ 0 6 5 ~ 4 3 o 0.5 1 1.5 2 2.5 Power Factor (z) Figure 26  Earliness versos z for Experiments 1 and 2 K=6,U=85% 62~~ 59+~~ 56+~~~ 53 +~==~~ 50 +O~~T_~ o 0.5 1.5 2 2.5 Power Factor (z) Figure 27  Earliness versus z for Experiments 3 and 4 150 140 130 120 110 , 100 1.5 A K=9,U=85% ~ 0.5 0.5 1.5 Power Factor (z) Figure 28  Earliness versus z for Experiments 5 and 6 47 ! 2.5 ...  K=3,U=92% 1.9 '~" .5 11.4 'i: ~) = ~ ~ 0.9 'l 0.4 " 0 5 10 15 20 25 Power Fador (z) Figure 29  Earliness versus z for Experiments 7 andS K=6,U=92% 21 '" '~" ~ .5 18 'i: ~ ('II ~ 15 ~ 12+r,.r~ o 0.5 1.5 2 2.5 Power Factor (z) Figure 30  Earliness versus z for Experiments 9 and 10 K=9,U=92% 75 ~ '" , ~ .If> v 70 65 60 55 50 1 0.5 o 0.5 1.5 2 2.5 3 3.5 Power lFactor Iz) Figure 31  Earliness versus z for Experiments 11 and 12 48  K=3,U=8S% ~ ~ J'> ~ 0.5 1.5 2 2.5 Power Factor (z) Figure 32  Absolute Deviation From Due Date versus z for Exp. 1 and 2 K=6,U=8.5% .g 62 ~I .:~: =o ".::I a. .~ ~ 56 +'>.,;,___; ~ C 'C ~ :I 1 J: 50 +....,..,.1 < o 0.5 1 1.5 2 2.5 Power Factor (z) Figure 33 . Absolute Deviation From Due Date versus z for Exp. 3 and 4 K=9,U=8.5% .., 1$~=~~~~, 1 "C>I SC~IS 130 +"~ ____l G)'C ~ 'C ~1~+,,~r____; ~'C "..... ! a 120+~~~==~I 00 v III 104 ~~115+~~..,....,.r~ 1.5 1 0.5 o 0.5 1 1.5 2 2.5 Power Factor (z) Figure 34  Absolute Deviation From Due Date versus z for Exp. 5 and 6 49 T ! K=3,U=92% 92~, e Q 90~; ~~ 2 88 +\ 1\; CIS CIS .~ "CI 86 +"'ri "~CIo a=I ~ ; "CI84t~~~~==;:;==~~==~~~ Q v ~ 82 +r~r_,_~ < 0 5 10 15 20 25 Power Fadel" (z) Figure 3S • Absolute Deviation From Due Date versus z for Exp. 7 and 8 K=6,U=92 % 59 ; ~ 55 E ~ eo 51 .!:: ::: ~ eo '.c '" 47 ~ til ... 1:\1 .~ >g 43 '"  ".l:.I 39 "=0 III ..c 35 < 0 0.5 1.5 2 2.5 Power Factor (z) Figure 36  Absolute Deviation From Due Date versus z for Exp. 9 and 10 e 82 Q ..: § 76 ~ .!! 1:\1 1:\1 .;;: "CI 70 ~ ~ 2 "CI 64 Q= ~ 58 < 1 ~ o K=9,U=92% ~ '" '" ~ I 2 3 4 Power Factor (z) Figure 37  Absolute Deviation From Due Date versus z for Exp. 11 and 12 50 Figures 8 through 37 show that a unique optimum exists over the range considered for each of the system configuration when time based performance measures are considered. Tbis is very important because it makes the search for the best value of the power factor z easier. A search for the best value of z will be easier if it is known that there is a unique optimum for the objective perfonnance measure. This property of the modified critical ratio rule is very important, since it makes the search for the best z more structured and facilitates the implementation of the modified critical ratio rule. In the case of loose due dates and low utilization level, Figures 16 and 17 show that two local optima exist when relative cost performance measme is concerned. Results show also that the performance measure is sensitive to the value of the power factor z. This can be observed most markedly at z values near zero where the slopes of the performance curves are steep. Determining the Value of z Based on the System Parameters The above results show that using the appropriate value of z, the modified critical ratio rule yields better performance than other traditional sequenc.ing rules.. The question that arises next is how to choose the best value of z. However, this should not be a limitation for implementing the modified critical ratio rule. If any of the traditional sequencing rules were to be implemented, a search for the best rule is needed to detennine the best rule. Therefore, implementing the modified critical ratio rule should not be eliminated because of the search involved in this implementation. The improvement achieved by using the modified critical ratio should justify the extra experiments needed (if any). Nevertheless, we attempted to fmd a nonsearch based methodology to specify the best value of Z without conducting an extensive search. 51 T I , The methodology considered in this research to determine the best z value is regression modeling. We attempted to model the best value of the power factor (z) as a function of the system parameters. The power factor (z) was modeled as a function of due date tightness, system utilization and penalty tightness factor. However, the adjusted r square parameter that represents the appropriateness of the regression model was 0.448 (maximum value indicating perfect fit is 1.00). One ofthe reasons that perhaps lead to this low value of Adjusted R2 is the lack of data points. This research generated only twelve data points to be used in a regression model. This might explain wby the regression approach did not generate a higher adjusted R2. Future research efforts might provide a more suitable regression model for determining the best value z by investigating more data points andlor other parameters. This research does not provide a nonsearch methodology for determining the best value of the power factor z. A search is still needed to determine the best value of z as a fmding of this research effort. 52 VI Conclusio.n This chapter presents the conclusions, insights, and future directions of this research. The conclusions and insights regarding the use of the modified critical ratio rule are presented fIrst. Then, we attempt to generalize the fmdings of this research and their impact on the sequencing research area. Finally, we conclude this chapter by presenting potential research directions to follow this l'esearch. Sequencing Using the Modifi,ed Critical Ratio. In the previous chapter, we justified that the modified critical ratio does improve the performance of a manufacturing system The modified critical ratio is an extension of the critical ratio rule that has shown good performance in the literature. The advantage of the critical ratio rule is tbat it considers both the remaining slack of the job and its processing time. The critical ratio rule gives priority to the job that has the least ratio of slack time to the processing time. However, there is an underlying assumption when the critical ratio rule is used.. The sequence of the jobs generated by the critical ratio rule assumes that the required time needed for ajob to flow through the manufacturing system is proportional to its processing time processing time only. Therefore,. the job that has the least slack to processing time ratio is given the highest priority. Consider two jobs, the fIrst, job A, has a remaining slack of d days and a remaining processing time of p days, willIe the second, job B, has a remaining slack of 2d days and a remaining processing time of 2p days. Both jobs will have the same priority if the critical ratio rule is used, since their slack to processing time ratio is dip. However, depending on the system confIguration,. a dip slack to processing time ratio may be sufficient for one job and small for another job. For example, if the operation time for each job is the same, job B will 53  bave more remaining operations and consequently it will visit more queues. Therefore, job B is expected to spend more waiting time than job A. Hence,even though job A and job B have the same dip ratio, it will likely be more desirable to give the priority to job B rather than job A. The modified critical ratio avoids the above conflict by modifying the importance of the processing time in assigning the priority to each job. The importance of the processing time is raised to the power z. Therefore, according to the configuration of the system, the importance of the processing time in deciding which job should have the highest priority is varied. The critical ratio rule depends heavily on whetber the due date of a job has passed or not. If the job's due date has not passed yet, the numerator of the critical ratio rule is positive. Therefore, if two jobs have the same remaining slack time, the priority will be given to the job that has the highest remaining processing time. On the other hand, if the job's due date has already passed, the numerator of the ,critical ratio rule win be of a negative value. Therefore, if two jobs have the same remaining slack time, the priority will be given to the job that has the lowest remaining processing time. The same conflict is observed when the modified critical ratio rule is used. Consider a hypothetical case where a z value of a is found to be the best value that yields the best performance for such a configuration. It is not clear whether modifying the weight of the remaining processing time by raising it to the power Ct gives the priority to the jobs that have small remaining processing time, or whether it gives the priority to the jobs that have large remaining processing time. This numerical sensitivity makes it more 54  difficult to understand and explain at which value of the power factor z. the modified critical ratio will yield the best performance. Sequencing Using A Quantified Decision Domain The modified critical ratio bas shown improvement over other tested benchmarking rules in this research. Thits improvement can be explained based on two main factors. 1. The critical ratio rule considers two important characteristics of a job, the remaining slack and the remaining processing time. However. the weight or the importance of each of these characteristics when assigning the priority of each job is fIxed. On the other hand. using the modified critical ratio. rule, the weight or the importance of each of these characteristics is varied according to system parameters. In traditional sequencing rules, choosing the best sequencing rule involves choosing the information considered in the selected sequencing rule. Therefore, the decision domain will be discrete. On the other hand, chQosing the best value of the power fac~or z involves choosing the weight of information considered in the modified critical ratio rule. Therefore the decision domain is continuous. 2. The modified critical ratio rule can react sensil1:ively to the changes in the system parameters. Traditionally, the sequencing problem is a problem that has a continuous range of system parameters and a discrete domain of available sequencing rules. Consider a system configuration A where EDD is the best sequencing rule. If one or more ofthe system parameters (utilization, due date tightness, etc.) is changed, the decisionmaker will have a decision domain ofcbanging the sequencing rule or sticking with EDD Wu and Wysk (1989), Pierreval and Mebark (1997). On the other hand, using 55 ! I I I I the modified critical ratio rule, the sequencing problem is a problem that has continuous range and a continuous domain. Therefore, if any change in the system parameters is introduced, the reaction will be changing the power factor z, which is a continuous reaction domain. This is the second reason tbat contributed into the superiority of the modified critical ratio rule. Researcb Contribution This research has introduced a new sequencing rule, that has been shown to perform statistically better than published sequencing rules in most of the settings experimented in this research. This fmding is important for practitioners as it provides a methodology to improve the performance of a manufacturing syst'em. On a conceptual level, the sequencing rule introduced in this research introduces a new sequencing paradigm. Traditional sequencing is concerned with choosing the best rule that yields the best performance. Sequencing rules differs based on the information content of these rules. Therefore, choosing the best sequencing rule involves choosing the information considered when jobs are prioritized. On the other hand, the sequencing paradigm followed in this research .is not concerned with the information that should be considered when jobs are prioritized, rather, it is concerned with the weight or the effect of the information considered when jobs are prioritized. Future Directions This research has introduced a new sequencing rule that has introduced an extension of the critical ratio rule, that bas shown to perform better than tested sequencing rules. Future clirections to follow this research can be divided into two areas. First, the modified critical ratio rule needs to be studied more thoroughly. The second 56 future direction is in generalizing the sequencing paradigm that has been introduced in this research. Future directions related to the modified critical ratio rule 1. In a. previous chapter, we presented one approach that might be followed to determine the best value of z, regression analysis. However, regression did not generate promising results in this research. We have explained the inappropriateness of the regression model by the lack of sufficient data. One of the future directions that can be pursued is conducting more experiments with diffemnt settings of system parameters in order to achieve an improved regression model. 2. In this research, the factors that have been studied are due date tightness, utilization le¥el, and penalty tightness factor cost. Future research may consider other factors such as number of machines, alternate routing, due date setting procedure, release mechanism, manufacturing system structure, permitted early shipment environment, and many other job shop factors and their interactions. 3. In this msearch, the search for the best value of z was restricted by a computational limitation (numeric overflow), therefore, the maximum experimental value of z was 22. Future research may investigate higber values of the power factor z, especially in the case of high system utilization and tight due dates. At this configuration, a value of z higher than 22 may lead to improved performance. It is noticed in Figure 11 that as the value of z is increased, the average r:elative cost is improved. 57  4. As discussed previously in this chapter, both critical ratio and modified critical ratio rules give higher priority for jobs of high processing time if there is a late job in the queue, and higher priority for jobs of low processing time if all the jobs ill the queue are ,early. This inconsist,ency may have a negative impact on the system's performance. A future dir:ection might be to investigate a modification of the modified critical ratio rule to overcome this inconsistency. F'uture directions related to generalizing tbe seqoencing p'arndigm introduced in this research This research introduced a shift in the sequencing paradigm The traditional sequencing paradigm is concerned with the selection of the best rule that will yield best performance. Sequencing is no longer concerned with choosing the information content of a sequencing rule, rather it is concerned with choosing the importance or the weight of a job information when prioritizing job is considered. This shift in the objective can be used to explore a more generalized rule that considers more information in a job. Such a rule might consider the number of operations for a job, arrivaJi time of a job, and the fmancial aspects of a job such as inventory value, job value and accumulated tardiness penalty cost. This might be a promising approach. Previous research fmdings have found that monetary based sequencing rules do outperform time based sequencing rules. However, by rethinking the importance or the weight of the fmandal information of a job, monetary based or combined timemonetary based rules might show improved performance. 58 References Ahmed, I. (1990), ''The interaction of due date assignment, job order release, and sequencing techniques in job shop scheduling," Unpublished doctoral dissertation, The University of Mississippi. Ahmed, 1. and W. Fisher (1992), "Due date assignment, job order release, and sequencing interaction in job shop scheduling," Decision Sciences, 23(3), 663647. Amar, A. and B. Xiao (1997), "Scheduling on a bottleneck station: a comprehensiJve ,cost model and heuristic algorithms," International Journal of Production Research, 35(4), 10111030. . Baker, K. (1984), "Sequencing rules and duedate assignments in ajob shop," Management Science, 30(9),10931105. Baker, K. and J. Kanet (1983), "Job shop scheduling with modified due dates," Journal of Operations Management, 4(1), 1123. Chang Y., S. Sueyoushi, and R. Sullivan (1996), "Ranking dispatching rules by data envelopment analysis in a job shop environment," IlE Transactions, 28, 631642. Cheng, T. and M. Gupta (1989),"Survey of scheduling research involving due date detemtination decisions," European Journal of Operational Research, 38, 156 166. Christy, D. and J. Kanet (1990), ''Manufacturing systems with forbidden early shipment: implications for choice of scheduling rules," International Journal of Production Research, 28(1), 91100. Hoffmann, T. and G. Scudder (1983), "Priority scheduling with cost considerations," International Journal of Production Research, 21(6),881889. Law, M. and W. Kelton (1991), Simulation Modeling and Anaiysis, Second Edition, McGraw Hill, Inc., New York. Kanet,1. and D. Christy (1989), "Manufacturing systems with forbidden early shipment: implications for setting manufacturing lead times," International Journal of Production Research, 27(5), 783792. Kawtummachai, R., Y. Yanagawa, K. Ohashi and S. Miyazaki (1997), "Scheduling in an automated flow shop to minimize cost: backwordmeta scheduling method," International Journal oj Production Economics, 49, 225235. 59 Montazeri. I. and L. Wassenhove (1990), "Analysis of scheduling rules for anFMS," International Journal of Production Research, 28(4), 785802. Panwalkar, S. and W. Iskander (1977), "A survey of scheduling rules," Operations Research, 25(1 J, 4561. Philipoom. P., M. Malhotra and J. Jensen (]993), "An evaluation of capacity sensitive order review and l'elease procedures in job shop," Decision Sciences, 24(6}, 1109 1133. Pierreval, H. and N. Mebarki (1997), ''Dynamic selection of dispatching rules for manufacturing system scheduling," International Journal of Production Research, 35(6), 15751591. Pritsker, A. A. B. (1995), Introduction to Simulation and SLAM II, Fourth Edition, John WHey & Sons, Inc., New York. Ragatz, G. and V. Mahert (1984), "A simulation analysis of due date assignment rules," Journal of Operations Management, 5(1), 2739. Ragatz, G. and V. Mabert (1988), "An evaluation of order release mechanisms in a jobshop environment," Decision Sciences, 19(1), 167189. Rohleder, T. and G. Scudder (1992), "Scheduling rule selection for forbidden early shipment environment: a comparison of economic objectives," International Journal of Production Research, 30(1), 129140. Scudder, G. and T. Hoffmann (1987), "The use of costbased priorities in random and flow shops,." Journal of Operations Management, 7(1&2), 217232. Scudder, G., T. Hoffmann, and T. Rohleder (1993), "Scheduling with forbidden early shipments: alternative performance criteria and conditions," International Journal of Production Research, 31(10), 22872305. Scudder, G. and D. SmithDaniels (1989), "Application of the net present value in random and flow shop scheduling," Decision Sciences, 20(3), 6'02622. Scudder, G., D. SmithDaniels and T. Rohleder (1990), "Use ofthe net present value criterion in a random job shop where early shipments are forbidden," Journal of Operations Management, 9(4), 527547. Sherrill, R., ED (1970), "APICS dictionary of inventory control terms and production terms'" Third Edition, American Production and Inventory Control Society, Washington, D.C. Vig, M. and K Dooley (1991), "Dynamic rules for duedate assignment," International 60 Journal of Production Research, 29(7), 13611377. Wu, S. and R. Wysk (1989), "An application of discreteevent simulation to online control and scheduling in flexible manufacturing," International Journal of Production Research, 27(9), 16031623. Yang, K and C. Sum (1994), "A comparison of job shop dispatching rules u:sing a total cost criterion," International Journal of Production R,esearch, 32(4),807820. 61 Appendix 1  Interarrival Time Calculations The system studied in this research is presented in Figure I. Orders arrive to tile system at the rate of Ao, which is the parameter we need to determine. The arrival rate at machine i is 14, i.e., Al is the arrival rate to machine 1. The value of ~ can be determined by using equation 1: ~o Al Ml ~ 0 M2 I I I ? I .I. 0 M7 Figure 38  System Representation (Equation 1) Where; ~: the arrival rate for machine i. p: the desired utilization level. /li: the average processing time at machine i. The average departure rate from any machine is same as the average arrival rate to the same machine assuming the utilization is less than or equal !, However, the jobs 62 departing from any machines may either leave the system or stay in the system to be processed by another machine. The rate of jobs staying in the system is denoted as 'Yi. The jobs arriving to machine i consist of two components. The fIrst is the jobs arriving to machine i as the frrst machine, i.e., the first operation for these jobs is to be performed on machine i. Since each machine has the same probability of being the machine for the fIrst operation for a job, the arrival rate of this component is A.o divided by seven (number of machines). The second component is the jobs arriving to machine i after being processed by any machine other than machine i. Therefore, 1..0, can be determined by the following formula: (Equation 2) The frrst term of the above equation represents the rate of jobs arriving to machine i as their fIrst operation. The second term represents the portion of jobs leaving other machines and arriving to machine i. The value of 'Y .... is calculated as follows: r k (Equation 3) Where; j: operation number a: the probability of a job leaving machine k has j operations b: the probability that a job leaving machine k has not completed all its operations The constant a is determined as follows: j a =7 (Equation 4) Ln j"J 63 The factor a in equation 3 and 4 is the probability that a job leaving machine i has j number of operation. Note that a job that has a bigher number of operations circulates more in the system than a job that has, a smaller number of operations. The factor b is determined by the following formula: jl b= j (Equation 5) The above equation calculates the probability that a job did not fmish all its operations. The numerator in equation five consists of the number of visits a job will make to any machine before finishing an its operations. The denominator in equation 5 consists of the number of visits that a job will make to any machine in order to finish its operations. Combining equations 2 through 5, AI( is detennined as follows: A = ,1,0 +.!.. ~ A ~ j 1 t 7 6L k 7 • j =l,j"k In } (Equation 6) n=l Substituting in the above equation, equation 6 reduces to: A A =_0 +O.8JL t 7 k (Equation 7) Combining equations 7 and 1, A.o can be determined by the following formula: A = 1.4,11 o P 64 (Equation 8) Appendix 2  Description of the simulation model The simulation model was coded in the SLAM II simulation language with FORTRAN subroutines inserts (Pritsker, 1995). Figures 39a and b shows Ithe SLAM II network of the sllnulated syste~ and the FORTRAN program is shown in Appendix 3, while the attributes and global variables used in this simulation model are shown in Table XI. Jobs arrive to the system at a calculated interarrival rate. The arrival process is modeled in the CREATE node shown in the network graph. After arrival, the following attributes of each job are assigned in the AWAIT node labeled EVl: 1. the number of operation for the job, 2. the sequence of the operation for the job, 3. the processing time of each operation, 4. the value of the job, and 5. the selling price of the job. After the attributes containing the above information are assigned, the attributes that are specific to next operation are assigned in the AWAIT node labeilied EV2. These attributes are the number of the next operation for the job, the machine number of the next operation, and the processing time of the next operation. Then, the job leaves the AWAIT node labeled EV2 to one of the branches that start with one of the ASSIGN nodes labeled MC1 to MC7. These seven branches (starting with ASSIGN nodes MC1 to MC7) represent the queues in front of machines 1 to 7. In each of these branches, there is one ASSIGN node and one AWAIT node. At the ASSIGN node (labeled MCl, MC2 to MC7), the attribute that stores the current time is updated. This attribute (ATRlB (24) is used to calculate the inventory cost associated with each job. Jobs leave the ASSIGN 65 node in each of these branches and arrive to an AWAIT node that follows each ASSIGN node. At the A WAIT node, a job waits for the machine required for its next operation. The FORTRAN subroutine that starts with the line number 100 is used at each of these AWAIT nodes. The FORTRAN subroutine is called when 1) a job arrives to the Await node or 2) when the resource is freed. In the FORTRAN subroutine, a check is made to detennine if a machine is idle and if there are jobs in the queue. Then, there are two possibilities to execute the subroutine depending on the sequencing rule applied. If the modified critical ratio is applied, the modified critical ratio is calculated for each job. The job that has the least ratio is remoVied from the queue, and is assigned to the idle machine. On the other hand, if the SPT rule is used, the job that has the highest priority in the queue is removed from the queue, and is assigned to the idle machine. The priorities in this case are assigned based on ATRIB (29), which stores the remaining processing time of a job. Jobs leave the AWAIT node and stay in the activity that follows the AWAIT node for the period its operation processing time. After the operation is completed, the resource that represents the machine used by a job is freed in the AWAIT node labeled FREE. Then the attributes that store information about the job value, remaining processing time of the job, and the inventory cost of the job are updated in the AWAIT node labeled EV3. After the jobs attributes are updated, a job is routed again to the AWAIT node labeled EV2 if the job's operations are not completed. Otherwise, if the job's operations are completed, the job is routed to the ASSIGN node labeled LEA VE. At the ASSIGN node labeled LEA VE, the attribute that stores the current time is updated. This attribute (ATRIB (24» is used to calculate the tardiness penalty cost for tardy jobs, and the inventory holding cost of finished goods. Also, at the 66 ASSIGN node labeled LEAVE, the value of A 'fRIB (22), that stores the job's deviation from its due date, is calculated. A job leaves the AWAIT node labeled LEA VB to the branch starting with the AWAIT node labeled EVES if it is completed after its due date, and to the branch starting with the AWAIT node labeled EVE4 if it is completed befm:e its due date. H a job is completed after its due date, its tardiness penalty cost is caliculated in the AWAIT node labeled. Then the average tardiness of tardy jobs, and average penalty cost of tardy jobs are collected in the COLLECT nodes ]abeled LAT and PENC respectively. If a job is fmished early, it is routed to the A WIAT node EVE4 through an activity that last for the time of its earliness. The inventory cost of storing an early finished jobs is calculated in the AWAIT node labeled EVE4, and is added to the total inventory cost incurred by the job. Then the earliness of early jobs is calculated in the COLLECT node labeled EAR. Both early and tardy jobs are joined at the AWAIT node labeled EVE6 at which the relative cost of each job is calculated. After a job leaves the AWAIT node labeled EVE6, the average inventory cost and the average relative cost statistics for all jobs are collected in the COLLECT nodes labeled INVC and RC respectively. The entity that represents ajob is terminated. 67 Attribute Description Attribute( 1) Job's arriving time Attribute(2) Number of operations Attribute(3) Machine of first operation Attnbute( 4) Machine of second operation Attnbute( 5) Machine of third operation Attribute( 6) Machine of fowth operation Attribute(7) Machine of fifth operation Attribute(8) Machine of sixth operation Attribute(9) Machine of seventh o£eration Attnoute( 10) Duration of first oiPeration Attribute( 11 ) Duration of second operation Attribute(l2) Duration ofthird operation i Attribute(l3) Duration of fourth operation Attribute( 14) Duration of fifth o~ation Attribute(15) Duration of sixth operation Attribute( 16) Duration of seventh operation Attribute ( 17) Number of completed operations Attribute ( 18) Machine of next operation Attribute( 19) Duration of next operation Attribute (20) Due Date Attribute(21 ) Selling Price Attribute(22) Waiting time in storage area Attribute(23) I Job's Value 1 Attribute(24 ) Waiting time reference I Attribute(25) Completed processing time Attribute(26) Accumulated holding cost per job Attribute(27) Penalty cost per job Attribute(28) Relative cost Attribute(29) Attribute(30) Total Processing Time DD(1) Due date tightness DD(2) Selling price factor DD(3) Factor of inventory cost (H) DD(4) The value of power factor (z) DD(5) Penalty tightness (pt) DD(6) Scale ofRC 1 DD(7) Scale of processing time I' Table XI  Description of attributes and global variables 68 0\ 'D ItiMetll111 [iJWEfl IllMellllll H0 0WEFl l'IMCSlll sl ~rn Fig 39. a  SLAMll Network Model (part 1) ,.Q t: c: Q., ~ "0 Ii Q .... ~ i ~ ..:.:: 100 Q ~ ~ z =~= j r.J'1 ,.Q e\ :is fI') ~ § 100 ~ = ..b.( ) ~ !:II: .,.. l=!!l § ~ 70 Appendix 3  lFortran Program SUBROUTINE AL,LOC (I, IFLAG) COMMON/SCOM1/ATRIB(100) ,DD(100) ,DDL(100" ,DTNOW, II,MFA,MSTOP,NCLNR 1 , NCRDR, NPRNT,.NNRUN,NNSET ,NTAPE, SS (100) , SSL (100) , TNEXT, TNOW,XX (100) NA=I GOTO ( 100, 100, 100 I 100, 100, 100, 100, 1, 2, 3 ,. 4 , 5 , 6) , I 100 I FLAG = 0 IF (NNRSC (NA) .EQ. 0) RETURN IF (NNQ (NA} . EQ . 0) RETURN IF(DD(8) .EQ. l. ) GOTO 122 DO 110 K=l,NNQ(NA) CALL COPY(K,NA,ATRIB) RNUM=ATRIB(20)TNOW DEN1=ATRIB(30)ATRIB(25) Z=DD(4) DEN=DEN1**Z CRITL=RNUM/DEN IF(K.EQ.1) THEN CRITT=CRITL MCRIT=l ELSE IF (CRITL.LT.CRITT) THEN CRITT=CRITL NCRIT=K ENDIF ENDIF 110 CONTINUE CALL SEIZE(NA,l) CALL COPY {NCRIT, NA,ATRIB) IFLAG=NCRIT IF (IFLAG. EQ. 0) CALL ERROR (NCe1) RETURN 122 IFLAG=1 CALL SEIZE{NA,l) RETURN 1 IF(NNQ(8).NE.1) CALL ERROR (3) CALL COPY(1,8,ATRIB) NOP1=UNFRM(3.,8.,B) ATRIB(2)=NOP1 DO 10 LS1=1,ATRIB(2) 13 NF1=liNFRM(1.,8.,9) IF (LSl. EQ. 1 ) GOTO 15 MAll=LS1+1 IF (NFl.EQ.ATRIB(MAll}) GOTO 13 15 MA12=LS1+2 ATRIB(MA12)=NFl 10 CONTINUE DO 12 LD1=1,ATRIB(2) MA19=LD1+9 ATRIB(MA19)=UNFRM(3.5,6.5,LDl)*DD{7) ATRIB (30) =ATRIB(30) +ATRIB (MA19) 12 CONTINUE ATRIB(21)=ATRIB(30)*DD(2) ATRIB (20) =TNOW+ATRIB (30) *DD (1) ATRIB(23)=ATRIB(21} *0.3 I FLAG= 1 RETURN 2 IF (NNQ (8) .NE .1) CALL ERROR (3) CALL eoPY (1,8, ATRIB) NX01=ATRIB(17) +1 ATRIB( 17)=NX01 NA12=NX01+2 NA19=NX01+9 71 ATRIB (18) =ATRIB (NA12 ) ATRIB (19) =ATRIB (NA19) IFLAG=l RETURN 3 IF(NNQ(8).NE.1) CALL ERROR (3) CALL COPY(1,8,ATRIB} ATRIB(25) =ATRIB(25) +ATRIB(19) ATRIB(23)=(ATRIB(25)/ATRIB(30)*O.2+0.3)*ATRIB(21) ATRIB (26) =ATRIB (26) +DD(3) *ATRIB (23) * (TNOWATRIB (24) ) ATRIB (29) =ATRIB (30) ATRIB (25) I FLAG = 1 RETURN 4 IF(NNQ(8).NE.l) CALL ERROR(3) CALL COPY ( 1, 8 ,.ATRIB) ATRIB(26)=ATRIB(26)+O.75*ATRIB(21)*DD(3)*{TNOWATRIB(24» IFLAG=l RETURN 5 IF(NNQ(8).NE.l) CALL ERROR(3) CALL COPY(1;8,ATRIB) ATRIB(22}=ATRIB(22) ATRIB(27}=ATRIB(21)*ATRIB{22}/(DD{5)*(ATRIB(20)ATRIB(1») IFLAG=l RETURN 6 IF(NNQ{8).NE.l) CALL ERROR(3) CALL COPY(l,8,ATRIB) ATRIB(28)=(DD(6) * (ATRIB(27)+ATRIB(26) ) )/ATRIB(21) IF(DD(9) .EQ.l.} THEN WRITE{NPRNT,61) ATRIB(28) 61 FORMAT {FlO. 2, FlO .. 3) END IF IFLAG=l RETURN END 72 VITA Amr AbuSuleiman Candidate for the degree of Master of Science Thesis: JOB SHOP SCHEDULING: A QUANTIFIED SEQUENCING RULE FOR IMPROVING SYSTEM PERFORMANCE UNDER DIVERSIFIED OPERATIONAL PARAMETERS Major field: Industrial Engineering and Management Biographical: Persona] Data: Born in Amman, Jordan, On March 20, 1973, the son ofSuleaman AbuSuleirnan and Fariouz Shehabi Education: Received Bachelor of Science degree in Mechanical Engineering from Jordan University of Science and Technology, Irbid, Jordan; completed the requirement for a Master of Science degree in Industrial Engineering and Management at Oklahoma State University in May 1998, Experience: Trainee Engineer at Arab Solar Industries, Sahab, Jordan, from Honors: June 1994 to September 1994; Marketing Engineer, AI·Ghanem Trading and Contracting Company, Amman Jordan, from September 1995 to July 1996; Graduate Research Assistant, Center for Computer Integrated Manufacturing, Oklahoma State University, from January 1997 to May 1998; Graduate Teaching Assistant, Oklahoma State University, from August] 997 to May 1998 Alpha Pi Mu Industrial Engineering Honor Society Affiliations: Institute ofIndustrial Engineers (HE), Institute For Operations Research and Management Science (INFORMS) 



A 

B 

C 

D 

E 

F 

I 

J 

K 

L 

O 

P 

R 

S 

T 

U 

V 

W 


