THE STUDY OF PASSING IN FLOW SHOP SCHEDULING PROBLEMS Dissertation for the Degree'of Ph. D. MICHIGAN STATE UNIVERSITY JAGDISH MANUBHAI MEHTA 1975 IIlIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIllIIIlIIlll K 3 1293 10380 8584 LIBRAR Y luflkifiwfini.gidfla Univcrsi i; y v—w WV“ This is to certify that the thesis entitled THE STUDY OF PASSING IN FLOW SHOP SCHEDULING PROBLEMS presented by JAGDI SH MANUBHAI MEHTA has been accepted towards fulfillment of the requirements for PH. D. degree in MANAGEMENT £ajor professor May I14, I975 Date 1 0-7639 ; ‘H “#3. AI} (if V-."‘ I ( l I 3: p 2 6 I273 <\::> I ABSTRACT THE STUDY OF PASSING IN FLOW SHOP SCHEDULING PROBLEMS BY Jagdish Manubhai Mehta In 1954, Johnson provided a simple algorithm to find an Optimum solution minimizing the total make-span for a general N job, 2 machine and a special N job, 3 machine flow shop scheduling problem. Since then his 13—14 assumptions- restrictions and performance criterion for minimizing the total make-span have become popularized, being referred to as the "classical flow shop scheduling problem." Other researchers in the field have applied techniques such.as combinatorial analysis, mathematical programming, heuristics, and Monte Carlo sampling to find optimum solutions to N job, M machine classical flow shop scheduling problems where M is equal to or greater than three, but with limited success. Then in 1965, almost simultaneously, Ignall and Schrage in the United States, and Lomnicki in Great Britain discovered the Branch and Bound technique was useful for find- ing optimum solutions to large N job, M machine classical flow shop scheduling problems. Others have since tried to obtain optimum solutions to these problems, with one or more assumptions-restrictions removed, also with limited success. Jagdish Manubhai Mehta In this dissertation, a study of the classical flow shop scheduling problem has been undertaken with the no pass- ing restriction removed. The no passing restriction implies that once a job sequence has been selected for the first machine in the flow shop, the same job sequence should be used for all subsequent machines. In the last 20 years, all but a few researchers have assumed in flow sh0p scheduling problems there is no need to change job sequences between machines. They probably thought any change in job sequence would only delay and in no way improve the value of the minimum total make-span. In pre- liminary analysis for this dissertation, a hundred 4 job, 4 machine flow shop scheduling problems were solved to see the effects of removing the no passing restriction from classical flow shop scheduling problems. Different job sequences on the first two machines than from the last two machines were permitted. The results were that in ten problems, passing was beneficial, while in the other ninety, it made no differ- ence as far as minimizing the total make-span was concerned. The total make—span improvement in the ten problems where passing was permitted, was fairly small. Conway, Maxwell, and Miller in Theory of Scheduling showed that changing the job sequence between the first and second machines, as well as between the last and second to last, does not improve the performance criterion of minimiz— ing the total make-span. Thus, in a 3 machine flow shop, there is no need to change sequences between any two machines Jagdish Manubhai Mehta but in a 4 machine flow shop, changing the job sequence between the first and last two machines could prove useful. Taking this into account, a thousand problems each for 3 job, 4 machine; 4 job, 4 machine; and 5 job, 4 machine flow shOp scheduling problems were constructed, using integer random numbers from Uniform probability distribution between 0 and 100 for processing times. The experiments on these 3,000 problems was divided into two parts: Phase One where the no passing restriction was maintained; and Phase Two where pass- ing was permitted between the first two machines and the last two machines. Complete enumeration of all possible sequences in both phases was conducted for each problem, with any decrease in the total make—span in Phase Two compared to the minimum total make-span of Phase One noted. The number of Optimum solutions of both phases and any correlation between them for each problem was noted. Previously, almost all researchers used processing times either chosen arbitrarily or generated from Uniform probability distribution. In research for this paper, Uniform probability distribution as well as Beta probability distribution were used to generate processing times for an additional 15,000 problems.- Five sets of values for parameters of Beta probability distribu- tion were chosen, and for each of them random numbers were generated for a thousand 3 job, 4 machine; 4 job, 4 machine; and 5 job, 4 machine flow Shop scheduling problems. Complete enumeration studies of both phases for each of these problems were conducted. Jagdish Manubhai Mehta It was determined that under the no passing restric- tion, the range between the maximum and minimum total make- spans is narrow. When the processing times are uniformly distributed, the range is only 24, 31, and 37 percent of the minimum total.make-span for 3 job, 4 job, and 5 job, 4 machine flow shop scheduling problems and, as values of AB-- parameters of Beta probability distribution--increase, values of the range decrease significantly. It was also found that 10.5, 13.0, and 18.5 percent of the 3 job, 4 job, and 5 job, 4 machine flow shop scheduling problems provide a lower value of the total make-span if passing is permitted, than that for the minimum total make-span under a no passing restriction when processing times are uniformly distributed. Therefore, as the number of jobs in the flow shop scheduling problem increase, the number of problems for which permitting passing lowered the minimum total make—span of Phase One in Phase Two also increases. This phenomenon was also observed in all five sets of problems whose processing times were Beta-distributed. The average reduction in the minimum total make-span where passing was permitted for 3 job, 4 job, and 5 job, 4 machine flow shop scheduling problems amounts to 0.415, 0.426,and 0.519 percent, respectively, when processing times are uniformly distributed. Although the average reduction in the minimum total make-span is small, it increases by 21.5 percent when the size of the flow shop scheduling problem increases by one job. Similar increases have been noted in the average reduction when processing times are Beta-distributed. Jagdish Manubhai Mehta A most important finding in this dissertation is that as values of the parameters of Beta distribution for processing times increases, the number of problems for which permitting passing lowered the minimum total make—span of Phase One, and the average percentage of reduction in the minimum total make-span of Phase One, decrease significantly. In addition, this dissertation provides three differ- ent heuristics or "search plans," each of which can provide solutions very close to the optimum solutions obtained with passing permitted, and with only a fraction of the effort. For example, for the one thousand 5 job, 4 machine flow sh0p scheduling problems, Plans One, Two, and Three provided 99.41, 80.80, and 80.13 percent of the possible reduction of the minimum total make-span with only 8.42, 4.24, and 0.36 per- cent of the computational efforts as compared to that required with complete enumeration. THE STUDY OF PASSING IN FLOW SHOP SCHEDULING PROBLEMS BY Jagdish Manubhai Mehta A DISSERTATION Submitted to Michigan State University in partial fulfillment of the requirements for the degree of DOCTOR OF PHILOSOPHY Department of Management 1975 © Copyright by JAGDISH MANUBHAI MEHTA 1975 ii ACKNOWLEDGMENTS Many people have assisted me in assembling this dissertation. I would like to acknowledge them here. My special thanks goes to Professor Phillip Carter, who as dissertation committee chairman, encouraged and motivated me whenever I needed it. His insight, sugges- tions, and constructive criticism were a constant help to me. Professor Richard Gonzalez as a dissertation committee member and department chairman, was extremely helpful in solving all problems that came up during the process of preparing this paper. He was more than generous with his time, knowledge, and resources. And Professor Kamalesh Banerjee was always available whenever I needed help. His knowledge of the problem and his suggestions along the way were quite useful. These men all deserve a special note of thanks for the guidance they gave me. I am extremely grate- ful to them. Many faculty and staff members of Bowling Green State University also assisted me and provided valuable resources. Professors Chan Hahn, David Hyslop, Michael Delaney, and Ms. Charlene McComas were especially helpful. iii I am also indebted to Professors Leo Erickson and Richard Henshaw of Michigan State University and Professor Jan Kmenta of the University of Michigan for their help. Finally, a special note of appreciation goes to my wife, Devyani, who was a constant sourceuof help and encouragement to me along the way. iv TABLE OF CONTENTS ACKNOWLEDGMENTS . . . . . . . . . . LIST OF LIST OF Chapter I. II. TABLES . . . . . . . . . . FIGURES O O O I O O O O O 0 INTRODUCTION . . . . . . . . Brief Overview of Some Scheduling Concepts . . . . . Statement of the Problem . . . Importance of the Problem . . PAST RESEARCH ON THE STATIC FLOW SHOP SCHEDULING PROBLEM . . . . . Combinatorial Analysis . . . S. M. Johnson . . . . . Dudek and Teuton . . . . Smith and Dudek . . . . Branch and Bound Method . . . Ignall and Schrage . . Lomnicki, Brown and Gupta . McMahon and Burton . . . Mathematical Programming Approach. Wagner . . . . . . Story and Wagner Giglio and Wagner . . . . Heuristics . . . . . . . Giglio and Wagner . . . . Palmer . . . . . Campbell, Dudek and Smith . Gupta . . . . . . . . Monte Carlo Sampling . . . . Heller . . . . . . . Non-Classical Flow Shop Krone and Steiglitz . . . Page iii .viii xi Chapter Page III. RESEARCH METHODOLOGY . . . . . . . . . 72 Phase One . . . . . . . . . . . . 74 Complete Enumeration . . . . 74 Modified Branch and Bound Algorithm . . 77 Phase Two . . . . . . . . . . . 81 Standard of Measurement of Passing . . 81 Preliminary Observations . . . . . 84 Generation of Processing Times . . . 86 Measurement Functions . . . . . . 93 IV. RESULTS OF ANALYSES WITH UNIFORMITY DISTRIBUTED PROCESSING TIMES . . . . . . . . . . 96 3 Job, 4 Machine Flow Shop Scheduling Problems . . . . . . . . . . . 104 Phase One . . . . . . . . . . 104 Phase Two . . . . . 109 4 Job, 4 Machine Flow Shop Scheduling Problems . . . . . . . . . . . 120 Phase One . . . . . . . . . . 120 Phase Two . . . . . . 124 5 Job, 4 Machine Flow Shop Scheduling Problems . . . . . . . . . . . 137 Phase One . . . . . . . . . . 137 Phase Two . . . . . . . . . . 141 V. RESULTS OF ANALYSES WITH BETA DISTRIBUTED PROCESSING TIMES . . . . . . . . . . 160 Explanation of Terms . . . . . 161 3 Job, 4 Machine Flow Shop Scheduling Problems . . . . . 162 4 Job, 4 Machine Flow Shop Scheduling Problems . . . . 167 5 Job, 4 Machine Flow ShOp Scheduling Problems . . . . . . . . . . . 173 Summary . . . . . . . . . . . . 176 VI. SUMMARY OF FINDINGS AND RECOMMENDATIONS FOR FURTHER RESEARCH . . . . . . . . . . 183 Findings and Conclusions . . . . . . . 183 Suggestions for Further Research . . . . 188 vi Page BIBLIOGRAPHY . . . . . . . . . . . . . . . 191 APPENDICES A. . . . . . . . . . . . . . . . 195 B. . . . . . . . . . . . . . . . 198 C. . . . . . . . . . . . . . . . 203 D. . . . . . . . . . . . . . . . 210 vii Table 2.1. 3.L1. 3..2. 4.11. 4.12. 404. 4.5. 4.6. LIST OF TABLES Page Processing Time of 6 Job, 2 Machine PIOblem O I O O O O O O O O O O 0 25 Processing Time of 6 Job, 3 Machine PrOblem O O O O O O O O O O O O O 29 Modified Processing Time of 6 Job, 3 Machine Problem . . . . . . . . . . 29 Numbers in Sequences for the 4 Job, 4 Machine Flow ShOp Scheduling Problem . . . 76 Frequency Distribution of Random Numbers Generated Using Beta Probability . Distributions O O O O O O O O O O O 90 Frequency Distribution of 3 Job, 4 Machine Problems According to the Minimum Total Make-spans Under No Passing . . . . . . 105 Frequency Distribution of 3 Job, 4 Machine Problems According to the Maximum Total Make-spans Under No Passing . . . . . . 106 Frequency Distribution of Problems According to the Number of Optimal Sequences Under No Passing . . . . . . . . . . . . 107 Frequency Distribution of Optimal Sequences of Phase One According to the Different* Possible Permutations of 3 Jobs . . . . . 108 3 Job, 4 Machine Flow Shop Scheduling Problems-- Replication 1 . . . . . . . . . . . 3 Job, 4 Machine Flow ShOp Scheduling Problems-- Replication 2 . . . . . . . . . . . viii 111 114 Table Page 4.7. Amount of Savings in the Total Make-span and the Amount of Search WOrk Involved with PaSSing O O I I O O O O O O O O O 118 4.8. Frequency Distribution of 4 Job, 4 Machine Problems According to the Minimum Total 4.9. Frequency Distribution of 4 Job, 4 Machine Problems According to the Maximum Total Make-spans Under No Passing . . . . . . 122 4.10. Frequency Distributions of Problems According to the Number of Optimal Sequences Under No Passing . . . . . . . . . . . . 123 4.11. Frequency Distribution of Optimal Sequences of Phase One According to the Different Possible Permutations of 4 Jobs . . . . . . . . 125 4.12. 4 Job, 4 Machine Flow Shop Scheduling Problems-- Replication 1 . . . . . . . . . . . 127 4.13. 4 Job, 4 Machine Flow Shop Scheduling Problems-- Replication 2 . . . . . . . . . . . 131 4.14. Amount of Savings in Make-spans and Amount of Search Work Involved with Passing . . . . 136 4.15. Frequency Distribution of 5 Job, 4 Machine Problems According to Minimum Total Make- spans 0 O O O O O O O O O O O 1 38 4.16. Frequency Distribution of 4 Job, 4 Machine Problems According to Maximum Total Make-spans . . . . . . . . . . . . 139 4.17. Frequency Distribution of the Number of PrOblems According to the Number of Optimal Sequences . 140 4.18. 5 Job, 4 Machine Flow Shop Scheduling Problems-- Replication 1 . . . . . . . . . . . 142 4.19. 5 Job, 4 Machine Flow Shop Scheduling Problems-- Replication 2 . . . . . . . . . . . 147 4.20. Amount of Savings in the Total Make-span and the Amount of Search work Involved with Passing . . . . . . . . . . . . . 154 ix Table Page 4.21. Results of Phases One and Two in Summary Form for 3 Job, 4 Job and 5 Job, 4 Machine Flow Shop Scheduling Problems . . . . . . . 156 5.1. Results of Phase One Experiments of 3 Job, 4 Machine Flow Shop Scheduling Problems . . . 163 5.2. Results of Phase Two Experiments of 3 Job, 4 Machine Flow Shop Scheduling Problems . . . 166 5.3. Value of the Measurement Function £4 for 3 Job, 4 Machine Flow Shop Scheduling Problems . . 168 5.4. Results of Phase One Experiments of 4 Job, 4 Machine Flow Shop Scheduling Problems . . . 169 5.5. Results of Phase Two Experiments of 4 Job, 4 Machine Flow Shop Scheduling Problems . . . 171 5.6. Value of the Measurement Function £4 for 4 Job, 4 Machine Flow Shop Scheduling Problems . . 172 5.7. . 5.7. Results of Phase One Experiments of 5 Job, 4 Machine Flow Shop Scheduling Problems . '. . 174 5.8. Results of Phase Two Experiments of 5 Job, 4 Machine Flow ShOp Scheduling Problems . . . 175 5.9. value of Measurement Function £4 for 5 Job, 4 Machine Flow ShOp Scheduling Problems . . . 177 5.10. Number of Problems Where Passing Improved the Total Make-span (Nop) . . . . . . . . 178 5.11. value of the Measurement Function f4 in Percent . . . . . . . . . . . . . 180 LIST OF FIGURES Figure Page 1.1. Refining of Crude Oil . . . . . . . . . 17 1.2. Polymerization of Styrene . . . . . . . . 19 3.1. Frequency Distribution of Random Numbers Generated Using Beta Probability Distributions C O O O O O I O O I O 91 5.1. Number of Problems where Passing Improved the Total Make-Span (Nop) . . . . . . . . 179 5.2. Value of the Measurement Function f4 . . . . 181 xi CHAPTER I INTRODUCTION The following statement, although written in 1967 for the book Theory of Scheduling, indicates to a large extent the present state of knowledge in the field of scheduling. Scheduling is a field in which there are some intriguing problems and some interesting answers. So far, however, the subject has not received the attention it deserves; work on it has been frag- mented at best . . . In an industrial society such as ours, efficient and effective scheduling of operations of any kind is very important to utilize our resources of men and machines to the fullest extent. This fact, though very simple to under- stand and agree with, is generally not acted upon by indus- trialists responsible for the job of scheduling production operations. The organizational environment for them is such that neither an efficient schedule rewards nor an inefficient schedule punishes them. Professor W. F. Pounds 1Conway, Maxwell, and Miller, Preface of Theory of Scheduling_(Reading, Mass.: Addison-Wesley, 19677: studied the scheduling environment of our industries in great detail and reported: The job-shop scheduling problem is not recognized by most factory schedulers because for them, in most cases, no scheduling problem exists. That is, there is no scheduling problem for them because the organization which surrounds the schedulers reacts to protect them from strongly interdependent sequencing problems. On the other hand, some schedulers realize the scheduling problem, only to get frustrated by its extent and their inability to deal with it. In both of these situations--the lack of knowledge of the problem and the lack of ability to handle it--people consciously or unconsciously schedule Operations guided by their intuition. And scheduling on the basis of mere intuition, contrary to many people's beliefs, is not advis- able because it does not produce good results in most cases. Although some peOple have a better scheduling intuition than others, most of us need some rules, guidelines and procedures to schedule operations effectively and efficiently. Thus, the job for researchers of the scheduling area is two-fold. The first task is to make schedulers aware of the nature of the scheduling problem, its characteristics, and its effect on daily production efficiency. The second task is to help solve the problem of inefficient production 2W. F. Pounds, "The Scheduling Environment," Chapter 1 of Industrial Scheduling, edited by J. F. Muth and G. L. Thompson (Englewood Cliffs, New Jersey: Prentice-Hall, scheduling by using guidelines, procedures, and rules so that the utilization of resources can be maximized or optimized. This does not seem particularly difficult except for the fact that researchers themselves do not have solutions to various scheduling problems. The situation is especially acute in the flow shOp scheduling problem as few useful results have been Obtained finding its solution. This lack of achievement is highlighted and analyzed in Chapter II where the present state of knowledge of the flow shop schedul- ing problem will be discussed. Brief Overview of Some Scheduling Concepts To understand the area of scheduling, it is first necessary to become familiar with some key concepts.’ SHOP, JOB, OPERATION and MACHINE are four inter- related basic terms that are used widely. The term "SHOP" refers to manufacturing facilities where various work func- tions are being completed. "JOB" refers to an item or a commodity that is being transformed in a shop from a stage which requires some work to be done to a stage where the required work is completed. The term "OPERATION" denotes a partial or full transformation process that is being applied to a job. Finally, the term "MACHINE" represents the trans- forming agent that performs an operation on a job in a shop. A shop can have one or more machines. The letter "M" is generally used to denote the number of machines in a shOp. If a shOp has only one machine, the scheduling prob— lem is sometimes known as "THE TRAVELING SALESMAN PROBLEM." A shop having two or more machines could be either a "FLOW SHOP“ or a "JOB SHOP." The scheduling problem in these respective cases would be a "FLOW SHOP PROBLEM" and a "JOB SHOP PROBLEM." In a "FLOW SHOP" there is a natural ordering of M machines such that all the jobs that come to the shop to be processed go to machine 1 for their first Operation, machine 2 for their second Operation, . . . go to machine K for the Kth Operation, where K is less than or equal to M. Thus a job in a "FLOW SHOP" with M machines has to go through exactly M number of Operations, although a few of these Operations may not be significant. In a "JOB SHOP" there is no natural ordering of machines and jobs, depending upon their technical nature, a job might go to any one machine for the first operation, another machine for the second operation, and so on. In the course of transformation, a job might not visit some machines and perhaps visit some machines more than once. Thus, in a "JOB SHOP" the number of Operations a job goes through has no direct relationship with the number of machines in a shop. A shOp when operating usually processes many jobs simultaneously. The letter "N" generally denotes the number of jobs in a shop at a particular time. A shop processes jobs in a batch style or a continuous style depending upon how it is set up. When a shop is set up to process jobs in batch style, all of the N jobs enter the shop simultaneously at a time t1 and after processing, leave the shOp simul— taneously at a time t2. Thus the shop has none of these N jobs just before the time t or just after t but exactly 1 2' N jobs during the time period t to t . This batch style 1 2 of operation is known as "STATIC" Operation since the number of jobs in a shop during a particular time period remains static. ‘ Different from this batch Operation is the case where the shop processes jobs in a continuous style. Jobs are allowed to enter individually at random times and to leave individually, when their own processing is completed. Thus, a shop has N number of jobs at any time where the value of N is fluctuating; going up, when a new job enters, and going down when a job which is processed leaves. Since the.number of jobs in a shop which is Operating on a continuous style fluctuate with time, it is known as a "DYNAMIC" operation. In a shop each job undergoes many operations before it leaves the shop. Each of these operations, depending upon the job, the machine, and the amount of work involved in the operation, will require a certain amount of time. Trans— porting the job from one machine to another, cleaning and setting up the job and the machine will also require a certain amount of time. The total of the transportation, cleaning, setting up, and operation times is known as the "PROCESSING TIME" for the operation. The processing time generally is different for each Operation and occasionally is dependent on the sequence of machines a job follows. In studying scheduling problems, these processing times may be obtained from actual industrial situations or by sampling from theoretical probability distributions such as the Uniform, Normal, Lognormal, Exponential, Beta, and Gamma. The usage of the two important terms "SCHEDULING" and "SEQUENCING" has created problems for many researchers. For many years some researchers used them arbitrarily as can be seen in the following excerpts: Sequencing Theory, when considered from an academic standpoint, is a combination of three specific areas within the field of operations research. The first is Se uencin , the second is Queueing or Dispatching, while the third is Scheduling.3 It seems to be becoming fairly generally accepted that the central scheduling problem can be more usefully described as sequencing (or dispatching . . .). After some controversy, many people began to realize that no useful purpose.is served by differentiating these 'two words. Furthermore, as expressed by Elmaghraby, Conway 2121-: In many instances the word SEQUENCING is used synon- ymously with SCHEDULING. I would like to reserve the latter to the exact Specification of the points in time at which certain events take place (similar to a train schedule). It is easy to see the reason for the frequent use by many authors of the two words interchangeably; a sequence also designates a schedule if the processing time of the first job on each facilitity is known and we are willing to 3A. H. Spinner, "Sequencing Theory--Development to Date," Naval Research Logistics Quarterly, Vol. 15, NO. 2 (1968), 319-330. 4P. Mellor, "A Review of Job Shop Scheduling," Operation Research Quarterly, Vol. 17, No. 2 (1966), 161-171. AI assume that each activity is started as early as possible. The two words will be used interchange- ably in this paper, but only when these two condi- tions can be safely assumed. We considered drawing a fine distinction between Sequencing and Scheduling; to hold that the former is concerned only with the ordering of operations on a single machine, while the latter is a simul— taneous and synchronized sequence on several machines. However, we found that no greater clarity resulted from such a distinction and the two terms are used essentially as synonyms in the following chapter.6 The American Heritage Dictionary defines scheduling as a production plan allocating work to be done and Specify- ing deadlines, whereas sequencing is a following of one thing after another, succession.7 O'Brien, in his analysis of scheduling states that, "Scheduling involves the arrangement, coordination, and planning of the utilization of resources to achieve an objective."8 O'Brien divides scheduling techniques into four classes: Time Scheduling, Resource Scheduling, Production Scheduling, and General Scheduling. Each of these four classes have anywhere from two to five separate techniques. He also gives three areas of scheduling applications, namely, Functional Scheduling, Topical Scheduling, and Production 5S. E. Elmaghraby, "The.Machine Sequencing Problem-- Review and Extension," Naval Research Logistics Quarterly, 6Conway, Maxwell, and Miller, Theory of Scheduling op; cit. u . 7The American Heritage Dictionary of the English Language YHOughton-Mifflin Company, 1971). 8J. J. O' Brien, Scheduling Handbook (New York, New York: McGraw-Hill, 1969), p. 2. applications. Each of these classes of applications have three to seven separate applications. Thus it is clear that both terms, scheduling and sequencing, have far reaching meanings and a wide variety of applications. Without putting forth any more arguments and illus- trations, the two terms "SCHEDULING" and "SEQUENCING" will be used interchangeably in the remainder of this paper. The ultimate aim of operating any shop is to maximize the profitability. Unfortunately, it is very difficult to determine precisely what variables will affect this profit- ability. Considering the need for customers and the avail— ability of resources such as men, materials, and machines, some variables are chosen which conceivably can maximize the profitability of a shop. These variables are known as "THE MEASURES OF PERFORMANCE" or "THE PERFORMANCE CRITERIA." Then out of many possible alternatives of the scheduling problem, a solution is selected which optimizes the measure of performance. Numerous measures of performance are used in practice and research. Some of them include: 1. Finish flmalast job in the batch as soon as possible; that is, minimize the interval of time from start until finish of the batch processing. This measure is popularly known as the total make-span. 2. Finish each job as soon as possible, that is, minimize the sum of completion time of all jobs, or minimize the mean of the completion time of N jobs. 3. Minimize the in-process inventory costs. 4. Minimize the costs that occur due to not meeting due dates exactly. 5. Minimize the distribution of lateness of jobs-- the length of time between the actual comple- tion of a job and the desired completion. It is inconceivable to assume that optimizing a single measure of performance will optimize the profitability of a shop. Attempts have been made to construct functions consisting of more than one measure of performance and then finding solutions to the scheduling problem to optimize value of the function. These attempts have been largely unsuccessful. Statement of the Problem The term "THEORY" implies a collection of systemati- cally organized knowledge applicable in a relatively wide variety of circumstances; especially, a system of assump- tions, accepted principles, and rules of procedure devised to analyze, predict, or otherwise explain the nature or behavior of a specified set of phenomena. Thus the "THEORY OF SCHEDULING" implies collection of knowledge as described above applicable to the scheduling problem. 9P. Meller, "A Review of Job ShOp Scheduling," Opera- tion Research Quarterly, Vol. 17, No. 2 (1966), 161-171. 10 This dissertation will be concerned with a small part of the scheduling theory. The problem and the reasons for selecting it are described below. Flow Shop and Job Shop problems are closely related in the sense that the flow shop problem is considered a special case of the job shop problem. Many researchers have worked exclusively on the job shOp problem, while others have worked on the job shop problem and applied their findings on the flow shop problem. Also, a few researchers have worked exclusively on the flow shop problem. Overall, the flow shop problem has received considerably less atten- tion than the job shop problem. Surprisingly, the flow shop problem is not even mentioned, let alone discussed in the otherwise complete Scheduling Handbook written by James O'Brien in 1969. After my search for a suitable disserta- tion topic, I decided to work exclusively on the flow shop problem. It seemed clear to me then and more so now that there are many challenges and opportunities in the area of the flow shop scheduling problem. After selecting the flow shop problem, I decided to work on its static operation rather than the dynamic opera- tion. Traditionally, many of the researchers who have worked on the flow shop problem have chosen the static operation. The static Operation is easier to work with, more basic and amenable to a mathematical formulation than a dynamic Operation. Thus it is wiser to study the static 11 operation first and then utilize the knowledge gained to understand the dynamic operation. In 1954, S. M. Johnson provided a neat and simple algorithm to find an optimum sequence which minimizes the total make-span for a general N job, 2 machine and a special N job, 3 machine flow shop scheduling problem. He used fourteen assumptions and restrictions to define the flow shop scheduling problem and used the minimization of the total make-span as the performance criterion. This package of assumptions, restrictions, performance criterion and problem definition used by Johnson is used by many researchers; it will be referred to henceforth as the "classical flow shop scheduling problem." For the research of this paper, I used all except one of Johnson's assumptions and restrictions. In this dissertation "Passing" is permitted in the solution of flow shop scheduling problems. Johnson assumed that a sequence of N jobs selected for the first machine of the flow shop should also be the sequence of the remaining M-l machines. In other words, all of the M machines should have the same job sequence for processing N jobs. When a solution to a flow shop scheduling problem is such that it has different job sequences on different machines, then some jobs will bypass or "pass" over other jobs. Such.a solution is not permitted under the no passing restriction used by Johnson, but is allowed when passing is permitted. 12 For whatever reason Johnson used the no passing restriction in his research on the classical flow shop scheduling problem, it was an intelligent decision. Later it was proved10 that for the N job, 2 or 3 machine flow shop scheduling problem, the no passing restriction does not adversely affect the minimum value of the total make— span but effectively reduces the set of possible solutions, and in effect reduces efforts required for the search of an optimal solution. For example, under the no passing restriction for an N job, M machine flow shOp problem there are only N! possible solutions, but if passing is permitted there are (N!)M possible solutions. Since Johnson worked with only 2 and 3 machine flow shop scheduling problems, using the no passing restriction was a good choice for him. On the other hand, most of the researchers who have since worked on larger than 3 machine problems should not have used the no passing restriction. During preliminary research for this paper, it was discovered that for a 4 machine flow shop scheduling problem, removing the no passing restriction provides a lower value of the total make-span in some cases. On the basis of the preliminary work and the realization that very few researchers have attempted to remove the no passing restriction, I decided to study various effects of permitting passing loConway, Maxwell, and Miller, Theory of Scheduling, op. cit., p. 83. 13 between sequences in a flow shop scheduling problem for this dissertation. The performance criterion I have chosen is minimiza- tion of the total make-span. In most of the research work on the static flow shop problem, two criteria are predomi- nantly used, namely minimization of the total make-span and minimization of the mean completion time. Regarding this, Conway gt_gl. states: Probably the most frequently cited paper in the field of scheduling is Johnson's solution to the two-machine flow shop problem. He gives an algorithm for sequencing n jobs, all simultaneously available, in a two-machine flow shop so as to minimize the maximum flow-time. This paper important, not only for its own content, but also for the influence it has had on subsequent work. In particular, it is likely that the general acceptance of minimizing the maximum flow-time as a criterion for the general job-shop problem can be attributed to Johnson's result.1 Following Johnson's lead and considering the prime advantage of easy comparability between solutions to the static flow shop problem, most of the researchers have used the total make-span criterion for their research. The scheduling problem that emerges from the preced- ing discussion is defined as follows: Given N jobs to be processed on M machines in a flow shop and given processing times tij' for jobs i=l,2,...N, and for machines j=l,3,...M, the problem is to find the sequence of jobs on each of the M machines, so that the total make—span is minimized. 11Conway, Maxwell, and Miller, Theory of Scheduling, OE. cit., p. 83. 14 There are 14 assumptions and conditions that go with the problem definition: 1. 3. All n jobs are simultaneously available at the beginning of planning period. All jobs are of equal importance, i.e., no job has differential degrees of priority. A single job cannot be processed simultaneously by more than one machine. The processing time of each job is known and deterministic. Set-up time and transportation time of a job is included in its processing time. The processing time of a job is independent of the job sequence on any machine. Every job requires processing on every machine and no job is processed more than once by any machine. If a certain job does not require processing on a particular machine, the corres- ponding operation will have a zero processing time. There is no unexpected delay in processing. In other words, jobs are processed as soon as possible, subject to routing and sequencing requirements. There is only one of each type of machine. 15 10. A11 M machines are available at the beginning of the planning period and are ready to take up any of the N jobs. 11. At most, only one job can be processed on a specific machine at any given time. 12. In-process inventory is allowable. 13. Each job follows the same machine sequence, i.e., each job goes to machine A first, then machine B, then machine C and so on. 14. No job splitting. Importance of the Problem Looking at all those conditions and restrictions imposed on the problem listed in the problem definition section, one could assume that the way the problem is defined has no direct resemblance to any actual practice in the industry. Actually, the problem, even the way it is defined, has quite a bit of applicability in actual practice. This will be illustrated with some examples. Example 1. A port with a nearby refinery has a docking facility for only one oil tanker. The tanker which brings crude oil to the port waits in the dock until the crude is refined and then carries the refined products back. The refinery tries to refine all the crude oil the tanker brings as soon as possible because keeping the tanker waiting for refined products and keeping the dock occupied with the tanker are both expensive. Moreover, other ships might be waiting to enter the dock. 16 The refinery has four chemical units which are similar to four machines in a flow shop. Crude has to be processed by all four units in a particular sequence as shown in Figure 1.1. Usually a tanker delivers as few as three and as many as five grades of crude oil. Each of these grades of crude has to be processed separately and the processing times of each of the four chemical units differ from any other grade of crude. Each grade is tested in the labora- tory first and its processing time on each.of the chemical units is determined. When the testing of all the grades is completed, the processing time data are given to the scheduler. He then decides the sequence in which the grades of crude oil are to be processed in the refinery, to mini- mize the total make-span. The scheduler usually keeps the sequence of different grades of oil the same on all four chemical units, although if he wanted to, he could change it since the refinery has plenty of storage tank space for any in-process material. Thus in this situation, the refinery is a flow shop with four machines. The number of jobs could be anywhere from three to five. The performance criterion is the mini- mization of the total make-span. Example 2. This example is similar to the previous example. A company named Polychem makes polystyrene from styrene- Since the chemical styrene is in short supply, Polychem gets its limited varying daily quota at 8 a.m. l7 muosooum smashes AI . .Hno means no unassumm H.H masses use: mcaecmsm DHCD coHuMHHHNmHQ mnmoooomm uwco coeumnmmom a moaxomuu HmEHooe HHGD coflomaaflumwa aumswum AI mosuu 18 every day. The plastic polystyrene can be made in various grades of shape, color, strength and Opacity. The conver— sation process from styrene to polystyrene needs processing on four chemical units as shown in Figure 1.2. As soon as the plant manager gets the information about the amount of styrene available for a particular day, he checks the pile of outstanding orders and decides which orders will be filled from that day's availability of styrene. He then calculates the processing time, temperature and pressure conditions for each of the four units for each of the orders. Since it is not advisable to store styrene overnight, it is all processed on the same day. The sooner it is done, the sooner all the employees can go home. Thus, in scheduling orders the performance criterion should be minimization of the total make-span. Example 3. A dye company, El Chippo Dyes, has a steady demand for different color dyes. To minimize various production and storage costs the company manufactures only red, blue, yellow, and white dyes. Whenever an order for a particular dye arrives, the manager mixes these four basic colors in an appropriate amount and fills the order.‘ As soon as one of the four basic dyes reaches a specified minimum level, production of all the basic dyes is triggered. The amount Of production of the four dyes is decided on the basis of present inventory and future usage expectation. Each of the four basic dyes have to go through three vats in a particular sequence. The processing time of each 19 .Eaflm no mamumwno ocoumum Iaaom .ATI menuuso a cowmsnuxm .ocmumum mo coflumuflumfimaom N.H mmsmflm manecmsm aohumssflumao coaomNflumfihaom mcmuhom lmll 20 basic dye on each of the vats depends on the dye and the amount to be processed. Since all four dyes are needed before an order is filled, the performance criterion is minimizing the total make-span. All three examples given above show a static flow shop structure and present a definite need for rules, guide- lines, and procedures to schedule jobs on machines to minimize the total make—span. CHAPTER II PAST RESEARCH ON THE STATIC FLOW SHOP SCHEDULING PROBLEM There has been very little research work published in the area of the flow shop scheduling problem. It seems the widespread interest in developing the theory of the flow shop scheduling problem and its application in the industry has not materialized. Many experts of Management Science and Production-Operations Management consider the flow shop scheduling problem the stepchild of the job shOp scheduling problem. They believe that once we have all the knowledge of the theory and application of the Job Shop Scheduling problem, the Flow Shop scheduling problem will be solved automatically. Perhaps this might happen, but I for one believe the Flow Shop scheduling problem is more amenable to analytical and optimizing techniques than the Job Shop scheduling problem. Pioneer research in the Flow Shop scheduling area and efforts done in the past to apply analytical and optimizing techniques to the Flow ShOp are presented in this chapter. 21 22 Several mathematical techniques—-combinatoria1 analysis, branch and bound technique, mathematical program- ming, heuristics, and Monte Carlo sampling--have been applied to solve the Static Flow shOp scheduling problem. Combinatorial Analysis The combinatorial optimization problem can be des- cribed in general terms as follows: Given a structure which can be arranged in a large but finite number of possible configurations--permulation or combination and some numeri- cal data which allows a real valued cost or profit to be associated with each configuration, design the structure so as to optimize the cost or profit. In the static flow shop problem being discussed, the structure consists of N jobs, M machines (the configurations are partial or complete sequences of N jobs). The completion of processing time of these sequences on M machines are the costs that should be minimized. The solution procedure in the combinatorial analysis of the static flow shop problem involves changing one configuration or sequence of jobs to another by switch- ing around jobs or choosing one job over others for a particular position in the configuration to reduce the total make-span, ultimately achieving the configuration that minimized the total make-Span. The work of Johnson (23), Dudek and Teuton (11), and Smith and Dudek (37) are prominent examples of combina- torial analysis applied to the classical flow shop problem. 23 Johnson's work (23), published in 1954, has proved to be a guidelight for the research done in the last twenty years. Although the procedure Johnson presented in that paper is applicable to finding solutions of only (i) the N job, two machine classical flow shOp problem and (ii) the special case of N job, three machine classical flow shOp problems, it is widely discussed in flow shop scheduling literature. Therefore, the procedure is described and explained in detail in the following pages. S. M. Johnson N Job, 2 Machine Problem Johnson gave an algorithm based on the combinatOrial analysis to find an optimum solution to any N job, 2 machine flow shop problem when the fourteen conditions listed on pages 14-15 of this dissertation are applicable and when the performance criterion is minimization of the total make-span. The algorithm given by him does not consider any "Passing" solution, i.e., any solution in which job sequences on dif- ferent machines are different. Conway, Maxwell and Miller (8) proved that in a 2 or 3 machine flow shop problem with minimization of the total make-span as performance criterion, any ”Passing" solution cannot be better than the best "Non- Passing" solution. The necessary steps in this algorithm to achieve an optimum job sequence are listed and explained below. 24 1. Construct a table of the processing times tij' with columns for different jobs and rows for different machines or vice versa. 2. Construct two rectangular blocks, 1 and 2, in which you will put selected job numbers. 3. From the table of processing times, select the smallest processing time and note its job and machine number, e.g., tij' i and j. In case there is more than one, choose randomly. 4. If the machine number j is 1, put the job number i of that processing time in block 1, behind all the pre- viously selected jobs of that block. If the machine number j is 2, put the job number 1 in block 2, ahgag_of all the previously selected jobs of that block. 5. Remove all processing times of the job i from the table of processing times. 6. If some processing times are left in the table, repeat steps 2-5. 7. If the processing time table has been exhausted, construct the Optimum job sequence by putting the job sequence of block 1 ahead of the job sequence of block 2 and combine them. Example: Processing time of a 6 job, 2 machine flow shop scheduling problem are given in Table 2.1. In the processing time table, the smallest number is 1, corresponding to job 2, machine 1 and job 5, machine 2. 25 Table 2.1 Processing Time of 6 Job, 2 Machine Problem Jobs Machines 1 2 3 4 5 6 l 7 l 2 10 9 7 2 3 9 15 6 l 4 Choosing randomly, job 2 goes to block 1 as the first number and job 5 goes to block 2 as the last number behind all future jobs. Block 1 Block 2 Then the processing times of jobs 2 and 5 are removed from the table. Jobs 1 3 4 . 1 7 2 10 7 Machine 2 3 15 6 4 Then the smallest number, 2, as processing time for job 3, machine 1 is selected and job number 3 is put in block 1 behind job number 2. Block 1 Block 2 26 Repeating the steps of the algorithm, we will even- tually have all six job numbers in two blocks as shown below: 2 3 4 6 1 5 The optimum sequence will then be "234615." The sequence 234615 is the best and optimum sequence out of the possible 6! = 720 sequences. The total make-span for it is 39 time units. = Machine 1 § = Machine 2 6 S 5 Ziaagaaiaaagi 3§339 Figure 2.1. Gantt Chart for a 6 Job, 2 Machine Flow Shop Scheduling Problem. 27 Many researchers have attempted to extend the appli- cability of Johnson's N job, 2 machine flow shop algorithm to an N job, 3 machine or more than 3 machine flow shOp problem. However, there has been only limited success. Johnson himself could not successfully extend the algorithm except for a Special N job, 3 machine flow shop problem. The special case and the algorithm to Obtain a solution for it are explained below. N Job, 3 Machine Problem The algorithm used for N job, 2 machine can be utilized for the N job, 3 machine problem only if all the previously-mentioned assumptions-conditions of N job, 2- machine are satisfied and the following conditions for pro- cessing times hold true. ) . . . . . 2 . Max1mum [Minimum (til), Minimum (t13)] Max1mum (t12 In other words, the largest of all the processing times on machine 2 should be no bigger than the smallest of all the processing times on either machine 1 or machine 2 or both. If this condition holds for an N job, 3 machine prob- lem, the algorithm that follows can be utilized to obtain an Optimum solution to the problem. 1. The processing times of job 1 on machines 1 and 2 are added and the result is denoted as the processing time of job 1 on machine 1'. Similarly, the processing times of job 1 on machines 2 and 3 are added and the result is denoted 28 as the processing time of job 1 on machine 2'. The conversion process of processing times of machines 1, 2, and 3 to two machines 1' and 2' for job 1 is repeated for jobs 2, 3,. . . and N. As a result of the conversion, a table of processing times of N jobs, 2 machines is Obtained. ' = o ' = til ti1 + ti2 , t. t. + t. The algorithm presented earlier for N jobs, 2 machines is applied to the table of processing times Obtained (in Step 1, and the Optimum sequence is computed. The optimum sequence obtained in Step 2 is utilized for the original N jobs, 3 machines problem and the. total make-span is computed. S. M. Johnson proved the above procedure provides a sequence with a minimum total make-span as compared to any other possible sequence for that particular flow shop problem. Example: An N job, 3 machine flow shop problem has processing times as shown in Table 2.2. The condition is satisfied, so the problem is a special case to which the Johnson's 2 machine algorithm can be applied to compute the sequence which minimizes the total make-span. First, by adding the processing times of machines 1 and 2, as well as 2 and 3, the processing times shown in Table 2.3 are obtained. Then the N job, 2 machine algorithm is applied to the above processing times table and the optimum sequence is determined. 29 Table 2.2 Processing Time of 6 Job, 3 Machine Problem Jobs Machines 1 2 3 4 5 6 l 6 7 14 5 10 7 Min (til)=5 2 2 4 l 3 4 5 Max (t12)=5 3 3 10 8 7 9 2 Min (t. )=2 13 o o o 2 - Max1mum [Min (til), Min (ti3)] Max1mum (tlz) Maximum [ 5 , 2 ] Z 5 Table 2.3 Modified Processing Time of 6 Job, 3 Machine Problem- Jobs Machines 1 2 3 4 5 6 l' 8 ll 15 8 14 12 2' 5 10 9 10 13 7 4 5 2 3 6 1 Block 1 Block 2 The sequence "452361" for the original N job, 3 machine problem gives 54 time units as the total make-span. Out of the total 6! 720 combination, this particular sequence ”452361" gives the minimum total make-span. 30 .\\V = Machine 2 \\\V = Machine 3 36 42 :8 g: 43 49 51 54 Figure 2.2 Gantt Chart for a 6 Job, 3 Machine Flow Shop Scheduling Problem. Dudek and Teuton (ll) worked on the N job, 3 machine classical flow shop problem, publishing their findings in 1964. In that paper they presented: 1) the theoretical development utilizing the combinatorial analysis to analyze the N job, M machine classical flow shop problem; 2) an algorithm to find a solution to the problem; and 3) an example and its solution. They claimed the algorithm will yield an optimum sequence to any N job, M machine classical flow shop problem. In response to the claim, William Karush (24), in a paper published in 1965, gave an example for 31 which Dudek-Teuton's algorithm could not produce an optimal solution and showed that the claim of producing at least one Optimum sequence to every N job, M machine classical flow shop problem by Dudek-Teuton's algorithm was not justi- fied. Smith and Dudek (37), in a paper published in 1967, presented a modified Dudek-Teuton algorithm and gave theore- tical proof that the modified algorithm would produce at least one optimum sequence to every N job, M machine classi- cal flow shop problem. In the following pages Dudek-Teuton's algorithm, Karush's argument against the algorithm, and Smith-Dudek's modifications will be discussed. Dudek and Teuton Dudek and Teuton's algorithm states the accumulated idle time on the last machine during the processing of N jobs is minimized, the total make-span will automatically be minimized. This is because: Total make-span of N jobs on M machines = Total idle N time on the Mth machine + 2 t. i=1 1“ Where tim is the processing time of ith.job on Mth (last) machine. Therefore, Minimization (Total make-span) = Minimization (Total idle time on the Mth machine) N + 1:1 tim ; in a .- db» 4 III-#- V~IVI 1 lytv in». I ‘3’ 0.: ‘UI I by“ I ~‘.. <5 I 1. v!) n) 32 Since i§l tim is constant for a given problem. Starting from the Objective of the minimization of the total idle time on the Mth machine, Dudek and Teuton obtained an algorithm and a decision rule, which are explained below. The set of N jobs is divided into two exclusive subsets, namely 0 and H. The first subset 0 consists of J-l jobs which are already scheduled for the first J-l position respectively in the sequence of N positions. The second subset H consists of yet unscheduled jobs. At the beginning of the algorithm, 0 will be null and at the end H will be null. The algorithm in general consists of three steps: 1) choosing a job from the subset H; 2) testing to see - whether it meets the decision rule; and 3) scheduling it for the Jth position in the sequence. Out of all the jobs in the subset H, a job having the smallest sum of the processing times on the machine 1 through M-l is chosen as the prospective candidate for the position J and is denoted by the sumbol 'A.‘ If more than one job has the smallest sum, the job having the maximum processing time on the Mth machine is chosen. Then the job A is removed from the subset H, which is left with N-J jobs. After deciding a job from the subset H as A, another job is chosen from H and denoted by the symbol 'B.‘ The symbol 'A' indicates the best prospective candidate or the defender for the position J in the sequence and the symbol L) 6') f (I (7 I 33 '3' indicates a challenger for the same position. One by one, each of the N-J jobs from H, in any predetermined order takes its place as the challenger B against the defender A. To determine the superiority of A over B for the position J, two sequences 8' and s" are constructed as S' = oAB and S" = oBA. The decision rule is applied to the two sequences 8' and S" and to the processing times of the jobs in these sequences on the machines 1 through M. The decision rule consisting of M-l inequality equations, M being the number of machines in the flow shop, is formulated by Dudek and Teuton from the initial objective of the minimization of the idle time on the last machine in the flow shop. These M-l inequality equations would require too detailed a des- cription to be explained here. For an accurate explanation, the reader should refer to the original article. If 8' gives the smaller idle time on the last machine compared to S" or, in other words, the decision rule indi- cates that S' is better than S", it means the job denoted by A is better suited than the job denoted by B for the posi- tion J in the sequence. Once this happens, a different job from H is denoted by B and the whole procedure of applying the decision rule on S' and S" is repeated. Now, if all of the jobs in H as B have "challenged" the job in A and have "lost," the job in A is assigned to the position J. The size of the subset and the value of J both are increased by 1, since one more job has been scheduled and a new job from H is chosen as the best prOSpective candidate for the 34 for the next position in the sequence. Occasionally, a particular job in B makes the sequence 8' inferior to S". In that case, the job in B replaces the job in A as the new prospective candidate and defender for the position J. The remaining jobs in H will challenge the new defender one by one. When the new A weathers the challenge from the remain- ing jobs, it is assigned to the position J in the sequence. Sometimes for a particular job in A and a particular job in B, both 8' and 8“ have equal results, indicating the job in A and the job in B are equally suitable for the position J. In this case, two as are constructed, one 0 having the job of defender and the other having a second job as defender. The remaining jobs in H are that of challenger of the defender with the end result of occasionally more than two sequences with different jobs for the position J. If there is more than one sequence at the end of the algorithm, the choice of the optimal sequence is made on the basis of the minimum total make-Span among those sequences. Dudek and Teuton claimed that the algorithm produces at least one Optimum sequence for the classical flow shop ‘problem. This paper describes an algorithm that will yield an optimum sequence for N jobs requiring processing through M machines when no passing is allowed.1 1R. A. Dudek, and O. F. Teuton, "Development of M-Stage Decision Rule for Scheduling N Jobs Through M Machines," Operations Research, Vol. 12, NO. 3 (1964), p. 471. 35 William Karush gave a simple example of a 3 job, 3 machine classical flow shop. Job Machine . 1 2 3 l 3 22 20 2 22' 20 14 3 2 20 18 When the Dudek-Teuton algorithm was applied to this problem, it gave an Optimum sequence 1 2 3 with a total make-span of 83 time units. There are 3! = 6 possible sequences for the 3 job, 3 machine problem. Determining the total make-span for each of the six sequences indicates the minimum total make-span is 82 time units for the sequence 2 3 1. Thus the sequence produced by the Dudek-Teuton algorithm is not optimum. The reason for this serious shortcoming of the Dudek- Teuton algorithm is that it compares the partial sequence GAB with GBA and concludes that if GAB is better than GBA, the job A is more suitable in the position J irrespective of where the job B will be. Now, if GAB is better than GBA, then GAB H' H" will be better than GBA H' H", but GA H' B H" may not be better than GB H' A H". The H' and H" are exclusive subsets of the subset H. This means that although GAB is better than GBA, A is not necessarily better suited for the position J as compared to B. If the Dudek—Teuton 36 algorithm is applied to Karush's example, the partial sequence 1 2 will be better than 2 l and the partial sequence 1 3 will be better than 3 1. Therefore, Dudek and Teuton would conclude that job 1 is better suited for position 1 as compared to jobs 2 and 3. The fallacy in this conclusion is that just because 1 2 is better than 2 1, it does not mean that 1 3 2 is better than 2 3 1. In fact, the total make- span of the sequence 1 3 2 is 85 whereas for the sequence 2 3 1, it is only 82. There is another disadvantage in the Dudek-Teuton algorithm--the computational time requirement on the com- puter. Dudek and Teuton, in the same paper, reported that for a 3 machine, 3 job or 4 job and 5 machine, 3 job, 4-job, or 5 job problem, their algorithm would take approximately three times as much time as the complete enumeration would. take on an IBM 1620 computer. Only for a 3 machine, 5 job, 6 job, 6 job or 7 job problem would their algorithm save time as compared to the complete enumeration. Thus, it seems clear that for a 3-5 machine problem it would be much better to attempt complete enumeration rather than the Dudek-Teuton algorithm. Smith and Dudek Two years after Karush pointed out the fallacy in the Dudek-Teuton algorithm, Smith and Dudek in their paper (37) presented an improved algorithm correcting the fallacy. They redefined the two sequences 8' and S" as S' = GAB H' H" ‘ A All “I \ .‘n‘ b Q ‘I-A. 60an A‘LA‘ um,“ . .'~~ 9““ '1»... s r.) ‘. [I ‘A‘. '3‘... "I ‘U‘ u an t 7 o 1 (I) l l . I» ‘H t y ‘ (D 37 and S" = GB H'aH", where H' and H" represent any possible exclusive subsets of H. The algorithm utilizing the decision rule determines whether 8' is better than S" for each of the B's from the subset H and for each of the possible permuta- tions of H' and H". If the decision rule indicates S' is indeed better than S", A is scheduled for the position J. Otherwise, for any one or more B's, S' is not better than S" and A and those B's are each scheduled for the position J, creating that many possible sequences. The decision rule, which involves M—l inequality equations, is too technical to describe here. Smith and Dudek in their algorithm demonstrated the computational time required to do 3 or 5 machine, and up to 8 job problems is almost half as much as would be required by the complete enumeration. Although this is quite an improvement over the Dudek-Teuton algorithm requirement of computational time, it is not as advanced as the computa- tional time requirement of the Branch and Bound algorithm. J. N. D. Gupta in his paper (18), published in 1969, indi- cated the Branch and Bound algorithm given by McMOhan and Burton (28), requires about 50 to 90 percent less time than the Smith-Dudek algorithm. Thus, it seems more than 2 machine classical flow shop problems, the computational time requirement of the algorithm of combinatorial analysis might be too great compared to other methods. 38 Branch and Bound Meth'gd As previously discussed, the combinatorial analysis gives an optimal solution for the N job, 3 or more machine classical flow shop problem, but the computational time requirement is very large. The Branch and Bound method can give Optimal solutions to the classical flow shop problem with a reasonable computational time requirement. As explained by Conway, Maxwell, and Miller (8, pp. 56) the Branch and Bound technique first used by Little, Murty, Sweeny, and Karel is an ingenious recursive computa- tional procedure. The procedure involves the maintenance of a list of unsolved, closely-related problems and three pro- cessing routines to apply to the problems on the list. Initially, one places the original problem on the list. The original problem is then processed (and hence, removed from the list), by one of the routines, which will sometimes create other problems to be placed on the list. One simply continues applying these same routines to each problem until there are no more on the list, at which point the solution to the original problem has been revealed. The three rou- tines are: l. A solution routine, which directly solves a problem from the list if the problem is easy (small) enough. 2. An elimination routine, which discards a problem from the list if it can show that u I.” a neon 'vn. 'tvu . 1 (I) -p ~ 0" s In. 39 the problem can make no contribution to the solution of the original problem. 3. A partitioning routine which replaces a problem too difficult to solve with several related subproblems. For the classical flow shop problem in the Branch and Bound procedure, the set of all possible sequences is progressively divided into subsets in a systematic manner by "branching." After every division the newly-created subsets must be mutually exclusive and exhaustive. A partial sequence (one with less than N jobs sequences) is used to identify the subset of all possible sequences arising from the partial sequence. A lower bound on each subset is determined in such a way that the total make—span for any sequence in the subset is greater than or equal to this bound. After every branching, the subset with the lowest bound is chosen for further exploration. The procedure terminates when a complete sequence is obtained for which the total make-span is equal to or less than the lower bounds on all unexplored subsets. The complete sequence is then Optimal. At present, there are five published papers which show the utilization of the Branch and Bound technique to Obtain Optimal solutions to the classical flow shop problem. They are: Lomnicki (27); Ignall and Schrage (22); Brown and Lomnicki (6); McMahon and Burton (28); and Gupta (18). Only two of these five—-that of Ignall and Schrage and one by McMahon and Burton--are useful enough to be discussed here 40 in detail. The remaining three papers combine the infor- mation of the other two papers and thus will be mentioned only briefly. Ignall and Schrage A paper published in 1965 in Ignall and Schrage (22) was the first to clearly exemplify the applicability of the Branch and Bound technique for the classical flow shop problem. The Objective function they used to compute the lower bound for each of the nodes in the tree is simple and easy to use. The Objective function for the lower bound for a partial or complete sequence JS is as follows: Time A(JS) + Z ai + Min (bi + Ci);I NJS NJS LB (JS) = Max Time B(JS) + 2 bi + Min (c1); NJS NJS Time C(JS) + 2 Ci; NJS The time A (JS), B (JS), and C (JS) are the times at which machines A, B, and C, respectively, complete processing on the last job of the sequence JS. The term 'NJS' indicates the set of all jobs which are not on the sequence JS. The terms ai, bi, and ci represent the processing times of the ith job on machines A, B, and C respectively. In comparison with the complete enumeration, the Branch and Bound technique is faster. The computational 41 time and effort for the Branch and Bound technique is directly proportional to the number of nodes generated for a problem. For an N job, M machine classical flow problem, in the most difficult case, there will be 1 + N + N (N-l) + . . . + N! nodes. In the best possible case there will be 1 + 2 + . . . + N = 1/2 N (N + 1) nodes. For a 10 job problem solved by the Branch and Bound technique, at worst there will be 6,235,301 nodes and at best there will be 55 nodes. Using the objective function they devised, Ignall and Schrage worked 50 of the 10 job, 3 machine problems and found that on an average, each problem needs generation of only 212 nodes and 8.7 seconds on a CDC 1604 computer to arrive at an optimum solution. Since Ignall and Schrage did not make any comparisons of their method with other methods it is not possible to state definitely how efficient their method is. If a 10 job, 3 machine problem was done using the complete enumeration, there would have been a need for generation of 10! = 3,628,000 sequences. The generation of each sequence and computation of its make-span would require roughly the same amount of time as the generation of a node and computation of its lower bound. Therefore, the complete enumeration for one 10 job, 3 machine would require approximately §§%%%QQ * 8.7 seconds or 41.3 hours on CDC 1604. Although the complete enumeration would likely generate more than one optimum sequence, compared to only one optimum sequence by the Branch.and Bound technique, the difference in computation times—-4l.3 hours compared to 8.7 42 seconds-~is too great to consider any other factors. Actually, there seems to be no need for more than one optimum sequence. Thus the work of Ignall and Schrage appears quite impressive and useful for the classical flow shop problem. Besides giving an objective function for the lower bound, explaining the Branch and Bound technique and the results for the previously published jobsets of Giglio and Wagner (15), Ignall and Schrage discussed the concept of dominated nodes in their work. They explained that if JS and IS are two different sequences on two different nodes, both containing the same set of jobs, then one of these two sequences may be dominated by the other sequence. For example, the sequence JS is such that the last job in it is completed on each of the machines A, B, . . . M at the same time or before the last of the jobs of IS on each of the machines A through M, thus the sequence JS is dominating the sequence IS. Any schedule which contains IS at the begin- ning cannot be hurt by replacing IS by JS. Thus even though the lower bound on the node with the IS as the partial sequence might be lower than the lower bound of the node with JS, it will not be necessary to branch from IS, and the node with IS can easily be discarded from the list of nodes that are under active consideration. In the example that Ignall and Schrage used to illustrate the Branch and Bound technique, the lower bound of the partial sequence 1, as well as partial sequence 2, 43 were both 55. [LB (1) = LB (2) 55.] Therefore, it was necessary to branch from 1 as well as 2. The LB (12) was equal to 55 and LB (21) was 56. However, the sequence 12 was dominated by the sequence 21, so it was not necessary to branch from 12 so it was discarded even though LB (12) was smaller than LB (21). Lomnicki, Brown and Gupta The paper by Limnicki (27) was published in Great Britain at almost the same time as the paper by Ignall and Schrage in the United States. Both of these papers pub- lished in 1965 are based on the work of Little, Murty, Sweeny, and Karel,2 On the traveling salesman problem,- although Lomnicki also made use of Roy‘s Graph-theoretical interpretation of the job shOp published in France in 1962.3 Even though the objective function to find the lower bound used by Lomnicki is exactly the same as that of Ignall and Schrage, it is very difficult to see any similarity between them. The deceiving differences are caused by the use of unusual and strange notations by Lomnicki. In his paper Lomnicki briefly mentions a concept of a reversed order of 2Little, Murty, Sweeney, and Karel, "An Algorithm for the Traveling Salesman Problem," Operations Research, 11, 972-989, (1963). 3B. Roy, Cheminement et connexite dans les graphes - Applications aux problemes d'ordinnancement. Metra, serie speciale No. l, Societe d'economie et de mathematiques appliquees, Paris. (1962). .. 'Q ‘ Cndné is raw M‘Ar s “Ht“ 0 ‘l ‘NI 1.. $8 I “'flia bu'v‘. b l ’ R‘Iu r t 8&5; I 1.. SG.iEI 4,4. ‘3 I .Y‘h‘ t‘v: 44 machines. If the order of the M.machines A, B, C, . . . M is reversed to M, L, J . . . A for a problem, the optimum sequence obtained will be the exact reverse of the original job sequence. The advantage of this concept lies in the choice it offers the problem solver. One of these two ways requires less effort and computation time. If the problem solver can determine for a particular problem which of the two orders of machines-~the original or the reverse--would result in the smaller number of nodes generated and less computation time, a lot of time can be saved. Lomnicki suggested the concept but did not use it. McMahon and Burton, whose work is discussed a little later, used it effectively. The paper by Brown and Lomnicki (6) published in 1966 is an extension of Lomnicki's work of the previous year. Brown and Lomnicki gave a simple explanation of Lomnicki's previous work, presenting the objective function in slightly better form. The objective functions given by Lomnicki as well as Ignall and Schrage are particularly for 3 machine classical flow shop problems only. Brown and Lomnicki extended the objective function of Lomnicki so that it can be useful for more than 3 machine classical flow shop problems. The objective function given by Ignall and Schrage is in a fairly simple form so that anyone can extend it to cover more than a 3 machine problem. Brown and Lomnicki also gave some experimental results and analysis of the application of the Branch and Bound technique to some rvr buv bu» at. Afi. vu- n h, "f‘ UV 0—1 ‘ (n l D (I) rt- r1 I'll 45 problems and gave an algorithm in a form that can be used if the Branch and Bound technique is to be programmed into a computer. J. N. D. Gupta published a paper (18) giving an algorithm to obtain an optimum to the classical flow shOp scheduling problem. According to Gupta, the algorithm is based on the lexicographic search concept. The American Heritage Dictionary defines lexicography as the writing or compilation of a dictionary. What Gupta seems to be doing is "compiling a word from appropriate letters" or appro- priately compiling a sequence from jobs. Actually, the algorithm Gupta presented in 1969 is no different from the earlier Branch and Bound technique. The objective function of Gupta can easily be put into the following form: LB (JS) = Time M(JS) + 2 Mi NJS Once in this form, it is easy to see the function is the same as the last part of Ignall and Schrage's objective function with M instead of C. The M is the last machine in the flow shop. Other notations are the same as the one used for Ignall and Schrage, as well as Brown and Lomnicki, in the previous few pages. Gupta compared the computation time his algorithm required on IBM 7040 for 3 to 7 jobs and 4, 6 and 8 machines with the computation times of Brown and Limnicki and Smith and Dudek. His algorithm requires about 10 to 20 percent 46 less time than Smith and Dudek's algorithm. Thus, if nothing else, Gupta demonstrates Smith and Dudek's algorithm is inefficient compared to that of Brown and Lomnicki. McMahon and Burton In a paper published in 1967, McMahon and Burton presented some new concepts which are useful in applying the Branch and Bound technique to classical flow shop problems. The bounds that are obtained from the objective functions given by Ignall and Schrage, Lomnicki and Brown, and Lomnicki, are called "machine-based bounds" by McMahon and Burton. Against these "machine-based bounds," their own bounds from a different objective function are referred to as "job-- based bounds." is as follows: LB (.13) Time A(JS) + Max NJS Time B(JS) + MaxNJS Time C(JS) + Z NJS C The objective function for job-based bounds [ai + bi + ci + NKZ Min (ak, ck)]; [bi + ci + NK E Min (bk, ck)]; o I i ___J. The LB(JS) is the lower bound for any node with a partial or complete sequence JS. Time A (JS), Time B (JS) and Time C (JS) are the completion times of the last job in the sequence, JS on the machines A, B, and C, respectively. The notations J. A, B and C, respectively. a., bi and ci are processing times of job i on the machines The NJS represents a job set 47 containing jobs that are not yet assigned to the sequence JS. The term NK represents a set of jobs in the set NJS, minus the job i. The subscripts i and k represent one job from the jobset of NJS and NK, reSpectively. The a b kl kl and ck are processing times of the job K on machines A, B, and C, respectively. The composite bound of McMahon and Burton is the bound equal to the greater of the machine-based bound and the job-based bound. Composite bound = Max [Machine-based bound, Job-based bound] It would have been nice if McMahon and Burton had experimented to determine the relative efficiency of machine-based bounds versus job-based bounds. It would have proved the superiority of one over the other. Instead, McMahon and Burton experimented with the classical flow shop problems of Branch and Bound technique using the machine-based bounds of Ignall and Schrage versus their own composite bounds. They concluded the composite bound is far better than machine-based bounds. They solved 50 problems each for the 4 to 10 jobs, 3 machine classical flow shop problems by the Branch and Bound technique, using both machine-based bounds and composite bounds. The mean number of nodes generated reduced from machine-based bounds to composite bounds by 22 percent, 28 percent, 39 percent, 40 percent, 48 percent, 40 percent, and 37 percent, respec- tively. The reduction in the mean computation times were 20 percent, 31 percent, 55 percent, 82 percent, 78 percent, 48 75 percent and 82 percent, respectively, for the same seven sets of 50 problems. A significant reduction in the number of nodes generated and the computation time should convince anyone of the superiority of composite bounds for the Branch and Bound technique over machine-based bounds. On the other hand, it raises a question. If for each node generated the calculation of the lower bound by composite bounds requires almost double the amount of calculations required by machine-based bounds, (for composite bounds it is necessary to compute machine-based bounds as well as job-based bounds), how can the percentage reduction in the computation time from machine-based to composite bounds be greater than the percentage reduction in the number of nodes generated? For instance, for the 50 problems of the 10 job, 3 machine case, the average nodes generated decreased by 37 percent from machine-based to composite bounds. However, the computation time went down a whole 82 percent. Common sense suggests the percentage reduction in the total computation time should be less than the reduction in the total number of nodes generated, if each node generated required more computation in composite bounds than in machine-based bounds. In six out of seven sets of those 50 problems, the reduction in computation time is much greater than the reduction in the number of nodes generated. It seems McMahon and Burton should have tried to examine and explain this obvious dis- crepancy, but unfortunately they did not. 49 In the algorithm McMahon and Burton skillfully used the concept of reversed order. To determine which of the two orders, the original or the reversed should be used to solve the problem, they introduced a concept of the domi- nant machine. Of the two machines A and C, the one which has the greater total processing time is referred to as the dominant machine. From experiments of 50 problems for 4 to 10 jobs, they determined that the total number of nodes generated and the total computation time required is much. less if the dominant machine is last compared to the number of nodes and computation times required if the dominant machine is first. Thus, between the two machines, A and C, if C is dominant, then the original order of the machines, i.e., ABC is used, but if the machine A is dominant, then the reversed order CBA should be used. In case the reversed order is used, the optimum sequence obtained by the Branch and Bound technique should be reversed to obtain the optimum sequence for the original problem. Mathematical Programming Approach During the years 1958-1965 there was great interest among researchers in solving various scheduling problems using many mathematical programming techniques. Techniques like Linear Programming, Integer Programming, and Dynamic Programming were repeatedly used for the traveling salesman, job shop scheduling and flow shop scheduling 50 problems. The work done to find a solution to the job ShOp was mainly carried out by Wagner in 1959 (42), Bowman in 1959 (5), Manne in 1960 (29, Chapter 12) and Giffler and Thompson in 1960 (14). Wagner in 1959 (42), Story and Wagner in 1961 (40), Giglio and Wagner in 1964 (15) spec- ifically worked on solving flow ShOp scheduling problems using the integer linear prOgramming technique. In spite of the SOphisticated techniques and inven- tiveness of the researchers, the mathematical programming approach did not prove a viable means of efficiently solv- ing flow shop scheduling problems. Wagner wagner in his paper (42), derived and presented an integer, linear programming model capable of representing the job shop scheduling problem. In the second section of his paper, he modified his model to specifically represent the flow shop scheduling problem. It is interesting to note that the model for the flow shop is capable of handling a problem even when the restriction of the same job sequence on different machines is removed. In other words, even when "no passing" or "no switching" restrictions are removed, the model for the flow shop can be used. In the third section, Wagner simplifies the model even further so that it can be used when there are only three machines in the flow shop and passing or switching is not necessary. Thus, wagner has given three levels of the integer linear 51 programming model, first for the job shop, then for the flow shop, and finally for the 3 machine classical flow shop problem. He does not attempt to present a solution to any problem in that paper, although some of his comments indi- cate a difficulty of solving a problem with his models. "The model in its present form is computationally unwieldy except perhaps for situations with a very few machines and a limited number of items (jobs)." Thus, we have derived a fundamental system of the order of 4*N equa- tions which probably can be solved for N 5 25 on high-speed computing machinery; but it of course remains questionable whether or not such a computational proposal for finding an optimal solution is economically sound." (The above- comment is in reference to the three machine classical flow shop problem.) Story and Wagner Story and Wagner (40) reported experiments on 4 to 9 jobs, 3 machine classical flow shop problems. First, they attempted to obtain optimum solutions to the 4 job, 3 machine classical flow shop problem by a few heuristic techniques like: a) Pairwise exchanges; b) end around cycling; and c) order reversal of jobs; starting from an arbitrary sequence. None of the three heuristics helped them to achieve the optimum solution. At this point, they set out to experiment with.the N job, 3 machine classical flow shop given by Wagner (42). The integer programming 52 algorithm they used was based on the approach suggested by R. Gomory,4 and the integer programming package IP03 avail- able for the IBM 7090 computer, by IBM Corporation. They arbitrarily constructed six problems each for 4 to 9 jobs, 3 machine classical flow shops. If they failed to obtain a solution to any problem in less than 1,000 iterations they terminated computations for that problem. For six 4 job, 3 machine problems, they obtained optimum solutions at an average of 119 iterations per problem. If they would have attempted to find optimum solutions to the 4 job, 3 machine problems they would have to do only twenty-four permutations per problem, instead of 119 iterations. Besides, the amount of computations in an iteration is much more than the amount of computation in a permutation. This fact in itself shows how inefficient integer programming can be in solving classi- cal flow shop problems. Because of the thousand iterations limit on problems they could obtain Optimum solutions to only 5, 4, 3, 2, and 1 problems out of six problems each for the 5 job, 6 job, 7 job, 8 job and 9 job, 3 machine classi- cal flow sh0p cases. After this dismal performance story, wagner also attempted to solve some 4 job, 3 machine problems by Gomory's mixed-integer programming method with very little success. 4R. E. Gomory, "An All-Integer Programming Algorithm," Chapter 13, in the reference, 29. 5R. E. Gomory, "Mixed Integer Programming Algorithm," Unpublished Rand Memorandum, RM2597, 1960. ‘ ~ ta. “V 'A ‘H ‘n '1 U o "v- D" 53 Our conclusion is evident from the tests: We have not yet found an integer programming method that can be relied upon to solve most machine sequencing problems rapidly. Giglio and Wagner In their paper (15) of 1964, Giglio and Wagner tested integer linear programming,.ordinary linear program- ming with answers rounded to integers, a heuristic algorithm and random sampling of six of the previously-used (40) 6 job, 3 machine classical flow shop problems. The heuristic algorithm and random sampling methods will be discussed later on in this chapter. Giglio and Wagner applied Gomory's all-integer programming algorithm available as SHARE PKIP91 on IBM 7090 to the 3 machine flow shop model given by Wagner (42).6 Giglio and Wagner in their paper (15, page 310) state that "previous experience with integer programming problems has demonstrated that the convergence prOperties of the algorithm are highly sensitive to the form in which the problem is stated initially. Consequently, we examined the effect on convergence of specifying six different input formats." The main differences among the six input formats were few extra constrains, or the presence of a lower bound on the objective function. They attempted to solve all six prob- lems using each of the six different starting input formats 6R. E. Gomory, "An All-Integer Integer Programming Algorithm," Chapter 13 in the reference 29. — bllv , WV .4. I. 'r ‘N- ‘ ~ 5“ All r( , LII 54 and restricting the maximum number of iterations to 10,000. They presented the actual number of iterations required for each of the 6 x 6 problems and Conway, Maxwell, and Miller (8, pp. 96) commented on the number of iterations by saying: This data does not appear very encouraging. In many cases the number of iterations is of the same order of magnitude as the number of possible permutations (720) and an iteration involves more computations than the generation of a permutation. However, they do confirm that the exact form in which the problem is stated has an important effect on the efficiency of the algorithm and further work is being directed at the development of more effi- cient constrains and bounds. At least, at the moment, the Branch and Bound technique appears to have a substantial advantage over integer program- ming as a practical computational procedure for the problem. In the second part of their testing Giglio and Wagner generated a hundred 6 job, 3 machine problems. The processing times were randomly picked from the uniform distribution between 1 and 30, inclusively. For each of the 100 problems, they calculated the total make-span for each of the 6! = 720 permutations, computed the mean total make-span and noted the minimum make-span. Then they found the best sequences for each of those 100 problems by using the algorithm of linear programming on the model presented by wagner (42), removing the restriction of the integer values only. The answers were rounded to the nearest integers to obtain the best sequences and the total make- span was computed for them. When Giglio and Wagner compared the total make-span obtained by linear programming with the v '- ¢ .5” .. ‘. u v. npa V.» 4 it I 55 make-spans obtained by complete enumeration of each of the 100 problems, they found the linear programming make-spans were overall only a little better than the mean make-spans. If the minimum, mean, and maximum make—spans are given ranks of l, 360 and 720, the best make—span obtained by linear programming would achieve an overall rank of 206. This result is far from satisfactory and Giglio and Wagner reported: In summary, we can conclude that the rounding process tends to produce solutions that are better than could be obtained from a single permutation drawn at random, but the method by no means produces optimal or nearly optimal solutions with a high degree of success. Heuristics A heuristic is a rule of thumb which.may have little, if any, theoretical foundation, but is found to generate very good, although not necessarily optimum, solutions. The advantages of a heuristic algorithm are that it would give a very good solution with relatively little computational time. In the classical flow shop scheduling area many researchers have given some of the best heuristics, Giglio and Wagner (15), Palmer (33), Campbell, Dudek and Smith (7) and Gupta (16) are some of them. Giglio and Wagner In the previously mentioned paper (15) Giglio and Wagner provide a heuristic for N job, 3 machine classical flow shop problems. The algorithm is quite simple and gives 56 reliable solutions. The steps of the algorithm are as follows: For any N job, 3 machine problem the processing times of machine A and machine B for each of the N jobs are added and the sum is referred to as the processing time of machine A' for that particular job. Similarly, the pro- cessing times for machine B and machine C for each of the N jobs are added and referred to as the processing time of machine 3' for that job. Finally, there will be two processing times for each of the N jobs. Johnson's algorithm for N job, 2 machine is applied over here and a sequence is obtained which should be a very close approxi- mation to the optimum sequence for that problem. Giglio and Wagner applied this heuristic on 20 problems whose processing times were randomly distributed from the uniform distribution over 1 to 30 both inclusive. In nine of the 20 problems, an optimum solution was produced and in eight of the remaining cases the solution produced was only one interchange away from the optimum. The average total make-span by heuristic was 1317 compared to the aver- age minimum make-span of 1279. Thus, the heuristic seems to be quite useful. Palmer Palmer in 1965 presented a heuristic (33) for the N job, M machine classical flow shOp problem. Considering the fact that this was a first attempt at devising a 57 heuristic for more than a three machine flow shOp, it is very efficient. The algorithm is based on the principle of giving priority to jobs whose processing times increase with the increase in the machine number. The algorithm simply involves calculating a quantity called the slope index for each of the N jobs. Slope index for job i = Si = _ M-l - M—3 _ M-S . . . M—3 M-1 ’7‘ til “—2 ti2 T ti3 + “—2 tim-l + "“2 tim The jobs are then sequenced in the decreasing order of the slopes. Palmer randomly generated 4 to 9 job, 3 machine problems and applied his heuristic on them. His solutions were very close to the optimum solutions. The sum of all six minimum make-spans was 418 units whereas the sum of the six make-spans by Palmer's heuristic was 437. Giglio and Wagner (15) had used six problems for a linear programming algorithm. To check the comparative effectiveness of the heuristics of Giglio and Wagner with the heuristics of Palmer, I applied both heuristics to the six problems. The sum of the minimum make-spans for the optimum solutions was 397. Palmer's heuristic gave a make-span sum of 417 whereas Giglio and Wagner's heuristic resulted in 418. Thus it appears that for a very small 58 sample, both heuristics are almost equally efficient. Palmer himself concluded his paper in this way: All general results must be approximations subject to the influence of single items or processes not being too great; they are upset if the schedule is dominated by one item or one process. Campbell, Dudek and Smith Campbell, Dudek and Smith in a paper (7) published in 1970 presented a reliable heuristic which has been fairly well received and is frequently reported by other researchers in the classical flow shOp field. The heuristic involves converting an N job, 2 machine size which can be solved by using Johnson's N job, 2 machine algorithm. The conversion of one problem of N job, M machine size to M-l auxiliary problems of N job, 2 machine size is very simple. The original problem has processing times in N rows and M columns. Each of the auxiliary problems has two columns of processing times for the two machines and N rows for the N jobs. The first column of the processing times of the Kth auxiliary problem is constructed by adding row by row the processing times of the £i£§E_K machines of the original problem. The second column of the same Kth auxiliary problem is constructed by adding row by row the processing times of the lEEE.K machines of the original problem. The value of K will progressively increase from 1 to M-l for the M-1 auxiliary problems. For the first auxiliary problem, the first and second columns will be 59 the same as the first and last column of the original problem. For each of the M-1 auxiliary problems the optimum sequence and the minimum make-span is computed by using Johnson's N job, 2 machine algorithm. The lowest make-span from the M-1 make-spans and the corresponding N job sequence is noted. The sequence is chosen as the heuristic approxi- mation of the optimum sequence and the make-span for the original problem using that sequence is computed. These three men adOpted a policy for error calcula- tion on the basis of the percentage deviation of the make- span of the heuristic sequence from the optimum make-span. Heuristic make span - Optimum make span Optimum make span Error = Then Campbell, Dudek and Smith generated integer random numbers from a uniform distribution between 01 to 99 for processing times of 340 problems ranging in size from 3 job, 3 machine to 8 job, 5 machines. For each of the 340 prob- lems they computed the optimum solutions, solutions by their heuristic, and the solutions by Palmer's heuristics. They also calculated the percentage of errors and noted computa- tion time required for both heuristics. The average amount of error percentages for their heuristics were about 2 percent compared to about 4.5 percent for Palmer's heuris- tics. The computation times for Campbell's heuristic were anywhere from two to three times the time required for 60 Palmer's heuristic. Thus it seems clear that Campbell, Dudek and Smith's algorithm provides closer approximations to the optimum solutions. The computation time comparison between their heuristic and Palmer's does not give a lot of insight except that Palmer's heuristic demands half or one-third as much time as Campbell's heuristic. A compu- tation time comparison of Campbell, et_al,'s heuristic, Palmer's heuristic, and any algorithm for optimum solutions, would have been beneficial. Gupta In 1971 Gupta published a paper (16) presenting a simple heuristic for the N job, M machine classical flow shop problem. This heuristic involves much less calculation than either Campbell, Dudek, and Smith's or Palmer's heuristics. In the heuristic, a function of (i) is calcu- lated for each of the N jobs and the heuristic sequence is obtained by arranging jobs in the increasing order of the value of the function. . A f (1) = . Min < < _ l - K _ M 1 (tiK + tiK+l) where A = +1 1f tim S‘til' where A = -l otherW1se; Gupta used the same error function used by Campbell, Dudek, and Smith. He generated processing times from the uniform distribution between 0 and 999 from the 195 problems of 4 to 8 jobs, 4 to 8 machines classical flow shop problem. 61 For each of these 195 problems, Gupta computed the Optimum solution, minimum make-span, the heuristic solution, and its make-span by his heuristic and by Palmer's heuristic. He also calculated error and computation time required by both his and Palmer's heuristics. The average error per- centages of Gupta's heuristic ranged anywhere from 3 to 10.5 percent but Palmer's heuristic error percentage ranged from seven to twenty-two. The computation time required for Gupta's heuristic was on an average about 10 percent less than for Palmer's heuristic. Thus Gupta's heuristic seems to be better on both counts--closeness to optimum and computation time. However, an important question arises from the data presented by Gupta. Why did Campbell, Dudek and Smith find (7) on an average only 4.5 percent error with Palmer's heuristic, while Gupta found seven to 22 percent error with it when he used the same error function and similar size problems as Campbell and others? 'Monte Carlo Sampling In many decision-making situations the Monte Carlo Sampling has proved to be a very useful and efficient technique to decide between many alternatives. Although it does not necessarily provide the best alternative, if used properly it can provide an excellent choice. On the other hand, if analytical methods are available to make a decision then the Monte Carlo technique might not measure up to the analytical methods in terms of optimality of the solution. 62 Heller in 1960 had published a paper showing some use of the Monte Carlo Sampling technique to find a good solution to the flow shop scheduling problem. Heller In 1960, Heller published a paper (19) showing the results of his experiments with a 100 job, 10 machine and a 20 job, 10 machine problem. From his results he made two conclusions. (1) The total make-spans are (approximately) normally distributed for a large number of jobs. This characteristic, together with the cost of sampling and the cost due to the amount of suboptimization, can be used to determine the size of the sample. And (2) that if we were looking for the minimum total make-span, we would sample (only) from those schedules which have the same ordering on all machines. These two conclusions, although erroneous, appeared to make sense to many of the other researchers at that time. Besides these erroneous conclusions there is another inaccuracy in the paper. Heller generated a total of 1000 integer processing times distributed between 0 and 9 for the 100 job, 10 machine problem. He gave the impression that these 1000 numbers came from uniform distribution. Conway, Maxwell and Miller stated, "He generated a set of 100 jobs with integer processing times apparently uniformly distributed between zero and nine.“ (8, pp. 100.) Unfortunately, the distribution of where the numbers came from seems far from 63 uniform and similar to a bell shape. This stems from the fact that there are only 31 zeros and 62 nines in the 1000 numbers, whereas there are 191 fives. (If the distribution were uniform, the expected number of zeros, nines, and fives should all be 100.) Heller, for his experiment on the 100 job, 10 machine problem did 3000 trials. For each trial he randomly chose a permutation of 100 jobs, assumed this permutation as the job sequence on all of the 10 machines, and computed the total make—span. He drew a graph of make-spans versus the probability of obtaining them. The range of make-spans was 580 to 725 units. The shape of this graph.was bell-like and thus he assumed that the make-spans are approximately normally distributed for large numbers of jobs. The con- clusion of normality is not justified for two reasons, one of which is given by Conway, Maxwell, and Miller (8, pp. 100). If the distribution of schedule times (make spans) is approximately, and/or asymptotically, normal, the departures from normality will be most pro- nounced in the tails of the distribution, which is precisely the area of interest. No one is concerned with estimating the mean of the schedule-time distribution for a particular problem. The second reason was that his sample size is only 3000, whereas the population size is 100! or approximately 1.26*10.157 For the second problem, the 20 job, 10 machine one, he used the processing times of the first 20 jobs from the 100 job problem. He examined and experimented with this 64 problem in two different parts. In the first part he had the same job sequence on all of the 10 machines whereas in the second part he selected different job sequences on each of the 10 machines. In the first part of the study for each trial he randomly generated a permutation of 20 jobs, used it as a job sequence for all the machines, computed the total make span and did 12,000 trials. In the second part, for each trial he randomly generated 10 different permutations of 20 jobs for each of the 10 machines and computed the total make-span. He repeated the procedure for 9037 trials. The make-spans versus the probability of obtaining it were drawn for both of the parts on the same paper using the same scale. Graphs for both parts were bell-shaped with the mean make- spans 169.93 and 727.82, respectively. The sample variances were 1.24 and 32.14, respectively, for the first and second part. Both of the graphs were far apart without a single point in common. From this observation Heller concluded that if the interest is in obtaining the minimum make-span, it is worthless to sample from the population of the second part. The fallacy of the above conclusion is not difficult to understand. The pOpulation size of the first part (same job order or sequence on all machines) is 20! or approxi- 17 mately 2.43*10 and the population size of the second part (different job order on each of the 10 machines) is (20!)10 or approximately 7.24*10173. The first part population is 65 also a part of the second part population. In fact, if a member from the second part is randomly selected there is a probability of 10"10 that it might be a member of the first one. With 9037 trials, there is a probability of .0000009037 that a solution could be the member that might be found in the first as well as the second parts. Obviously the probability is very small and Heller did not hit upon it. Another fact is that there are some members in the second part which are not members of the first part but still have lower make-spans than any member of the first part. With the total population of 7.24*10173 and sample size of only 9037 there is very little probability of finding any unusual member. (It is a fact that very few members of the second part might have a smaller make-span than the lowest make-span member of the first part.) In fact, Nugent work- ing on the Monte Carlo Sampling for job shop scheduling examined the 20 job, 10 machine problem. Considering it as a special case of job shop scheduling, he applied his "probabilistic priority rules" and found a total make-span of 144 with slightly different job sequences on different machines. Nugent's work definitely proved that Heller's conclusion was erroneous. To examine how a simple heuristic would perform, I applied Palmer's heuristic to Heller's 20 machine, 10 job problem. In half an hour's work, without the help of any electronic instrument, a (no passing) sequence was obtained which gave a total make-span of 156. Adding the processing 66 times of the last five machines for each of the 20 jobs, then applying Johnson's algorithm of the N job, 2 machine case, a sequence was obtained. This second sequence, although quite different from the first, also resulted in a total make-span of 156. The second trial also took approximately thirty minutes. Heller had obtained make~ spans between 150 and 200 for the problem doing 12,000 trials. Thus it is obvious that if some analytical or even heuristic techniques are available, the Monte Carlo Sampling technique would not be competitive. Non—Classical Flow Shop There has been a fair amount of work done in the non-classical flow shOp scheduling area (1, 2, 9, 19, 20, 21, 25, 26, 34). Out of these, only two, one by Heller (19, 20, 21), and the other by Krone (25, 26) would serve some useful purpose to launch a lengthy discussion here. Heller's classical and non-classical work is discussed in detail in the Monte Carlo Sampling section. Krone and Steiglitz Krone and Steiglitz published a paper (26) in 1974 essentially based on the doctoral dissertation work of Krone (25) which he did in the department of electric engineering at Princeton University in 1970. In the flow shop scheduling area, Krone has chosen a very difficult performance measure, the minimization of 67 the mean completion time. The measure is seldom mentioned let alone used by many researchers in the flow shop scheduling area. The only other work done with the mean completion time on the N job, 2 machine flow shop is by Ignall and Schrage (22). There are two facts which show the amount of difficulty working with the minimization of the mean completion time. The first is that even for a 2 machine flow shop problem there is no simple algorithm to find an optimum solution if the performance measure is minimization of the mean completion time. Johnson's 2 machine procedure does not give an algorithm solution, nor according to Conway, Maxwell and Miller, does it produce good results. The second fact is that if the performanCe measure is minimization of the mean completion time, the 2 machine case is the only one where examining different sequences on different machines (passing) is not necessary. For the 3 machine case, passing between the first and second machines is not necessary, but between the second and third machines passing might produce better results than non passing. Thus for an N job 3 machine flow shOp problem, the total number of permutations are (N!)2 with minimization of the mean completion time whereas with the minimization of the total make-span only N! permutations need be examined. These two facts should convince anyone that the minimization of the mean completion time is a more difficult performance measure to work with than the minimization of the total make-span. 68 In his research, Krone finds the final solution for an N job, M machine flow shop problem with minimization of the mean completion time as the performance measure in two phases. In the first phase of his algorithm, he begins with a sequence of jobs which is the same for all M machines and is obtained by generating a pseudorandom starting solu- tion. He then progressively improves the sequence by apply- ing a local transformation or switching of jobs until the sequence can no longer be imporved. He calls this sequence the locally optimum sequence. He calls the local transfor- mation a ”perturbation" rule. The restriction of no passing is maintained throughout phase 1. (However, it is released in Phase 2.) "The program terminates when local Optimality of the current trial solution is verified by searching its neighborhood exhaustively." In the second phase he starts out with the locally optimum sequence he obtained in the first phase. The same "perturbation" rule is used to change the sequences of only some of the machines if the change improves the value of the mean completion time. In other words, he attempts to release the no passing restriction of phase one tO' further improve the value of the performance measure. When the "neighborhood is searched exhaustively" the algorithm in the second phase is completed. For experimental work, Krone generated integer numbers uniformly distributed between 0 and 100, sufficient for fifty problems of 10 job, 5 machine size. For each of 69 these fifty problems, he executed his two-phase algorithm twenty times. Since the final solution of his algorithm is dependent upon the initial solution, and since everytime he executed his algorithm he obtained a different initial solution for phase one, he obtained twenty intermediate solutions (solutions at the end of phase one), and twenty final solutions (solutions at the end of phase two). For each problem, he chose a best final solution and "normalized" the twenty intermediate and twenty final solutions assigning a value of 1.0 to the best final solution. By following this procedure he Obtained 1000 intermediate and 1000 final solutions with at least fifty of the final solutions having a value of 1.0. He plotted a histogram for his 1000 inter- mediate and 1000 final solutions. The values of the inter- mediate solutions varied between 1.02 to 1.5 and the values of the final solutions varied between 1.0 and 1.05. From his experience with.these fifty problems and with a few other problems, he concluded that all the mini- mization of the mean flow time is accomplished in phase one, with phase two of the Optimization process providing only slight improvement in general. Overall, he found an improvement of 0.66 percent in phase two. From the wide range of intermediate solutions (1.02 to 1.50) Krone obtained a much narrowed (1.00 to 1.05) range of final solutions. Based on this fact and that both the intermediate and the final solution histograms start at almost the same values (1.02 versus 1.00) it seems fairly 70 clear that a lot of "bad" intermediate solutions improve a great amount, but a lot of "good" intermediate solutions do not improve significantly during phase two. One could conclude then that if the task of finding locally optimum solutions in phase one is accomplished successfully, the task of improving them in phase two may not be necessary. As mentioned earlier in the Branch and Bound sec- tion, Ignall and Schrage's algorithm to Obtain Optimum solutions for a 3 machine flow shop can easily be extended in cases of more than 3 machine flow shops (no passing) if the performance measure is minimization of the total make- span. This extension will be useful in this dissertation to obtain Optimum solutions in the first phase. Ignall and Schrage also presented an algorithm to Obtain an Optimum solution for an N job, 2 machine flow shop when the per- formance measure is minimization Of the mean completion time. Krone probably could have extended this algorithm (based on the Branch and Bound technique) to Obtain solutions for more than a 2 machine flow shOp (no passing) with the per- formance measure of the mean completion time. There are some important similarities between Krone's dissertation work and this particular dissertation. Until all the conceptual work and experimental studies were done for this dissertation, Krone's work had not been examined. Both dissertations are motivated by a similar need, the critical evaluation of the effects of the removal of no passing restrictions from the N job, M machine flow 71 shop. Both dissertations have an algorithm in two phases. The first phase solutions to flow shop under the no passing restriction are obtained and studied. In the second phase, the solutions of the first phase are improved upon by removing the no passing restrictions. At this point, the similarities end. As discussed earlier, Krone uses a more difficult performance measure than the one used for this dissertation. Another difference is in the quality of the solutions obtained in the first phase. Krone obtains locally optimum solutions whereas in this dissertation globally optimum solutions will be obtained in the first phase. In Krone's work, very little is achieved in the second phase. The efforts in the second phase are wasted on improving-the "bad" solutions of the first phase. In this paper, although efforts in the second phase might seem greater than the achievements Obtained, extra effort will not be useless. These efforts will bring definite results. CHAPTER III RESEARCH METHODOLOGY This dissertation will attempt to examine the effects of removing the No Passing restriction from the classical flow shop problems. The implication of the No Passing restriction is that the same sequence of jobs should be used on different machines of the flow shop. In other words, once a job sequence is chosen for the first machine, the same job sequence is utilized for all subsequent machines and no job is allowed to "pass" over another job or jobs. In the last twenty years, all except for a few researchers have assumed that for the flow shop there is no need to change the job sequence from one machine to another. They must have assumed that any job "passing" could only delay and in no way improve the total make-span. During preliminary research with one hundred of 4 job, 4 machine problems for this dissertation, it became clear that in approximately 10-15 percent of the problems, the optimum solutions obtained under the NO Passing restriction could be improved to a small extent by removing the restriction 72 73 and permitting judicious differences between job sequences of the first two machines and the last two machines. Conway, Maxwell and Miller provided proof that for a flow shop with the minimization of the total make-span as the performance measure, changing the job sequence between the first and second machines as well as changing the job sequence between the second to last and last machines is not necessary, and doing it will not improve the Optimum solution (8, p. 81). This implies that for a two machine and a three machine flow shop, considering different job sequences on different machines is not necessary. For a four machine flow shop, "passing" between the first and second as well as the third and the fourth is not necessary. However, "passing" between the second and third machines can prove beneficial as far as the Optimum values of the solution is concerned. With the no passing restriction on any size flow shop, N! permutations need be examined, but M-Z permutations (M Z 3) should with Passing permitted (N!) be examined. The number of permutations to be examined in a flow shOp when passing is permitted increases very rapidly.‘ For example, for a 4 machine flow shop with 4, 5 and 6 jobs, the total number of permutations are 576; 14,400; and 518,400. Thus, when the number of jobs in a 4 machine shop increases from 4 to 6, the total number of permutations increases from 576 to half a million. No wonder many researchers who are aware of the benefit of passing, hesitate to work with it. 74 The IBM 360 computer requires roughly about six to seven minutes to do a complete enumeration for a 6 job, 4 machine flow shop problem with passing permitted. Taking this tremendous computational burden into account, it was decided to work with 3 to 5 job, 4 machine flow shop problems for this dissertation. The various results Obtained here will be applicable to larger flow shop problems once some trends in results are established, going from 3 job to 5 job problems. The procedure used to Obtain solutions for any problem in this dissertation is divided into two phases. In the first phase, optimum solutions are obtained under N0 Passing restrictions. In the second phase, first phase' solutions are improved by permitting Passing between the second and third machines of the N job, 4 machine flow shop problem. Phase One Two different algorithms are employed for finding Optimum solutions in the first phase. One method employs the complete enumeration while the other uses a modified Branch and Bound procedure. Complete Enumeration Although few other algorithms are available to obtain Optimum solutions under the No Passing restriction, the com- plete enumeration algorithm is used for experiments reported 75 in the fourth chapter of this dissertation. There are some advantages in using the complete enumeration for finding solutions to classical flow shop problems. For one, it not only gives the minimum total make-span for a problem, but if needed, provides a maximum total make—span and the com- plete frequency distribution of total make-spans for a problem. The range between the minimum and maximum total make-spans or frequency distribution of the total make-spans can be very useful in experimentation. Another advantage Of complete enumeration is that if there is more than one sequence having the same minimum total make-span, complete enumeration can provide all of them. To obtain a satisfac- tory solution from a second phase algorithm, it is necessary that all optimum solutions of a problem in the first phase are known. The Branch and Bound technique normally provides only one optimum solution although there might be more than one present, and thus has to be modified to cause it to produce all of the optimum solutions a problem has. One disadvantage of the complete enumeration algorithm is that it requires more computation time as compared to most other algorithms. The computer problem used for the complete enumeration algorithm in this dissertation is explained below and listed in Appendix A. The complete enumeration computer program consists of a main problem and three subroutines: SCHED, FCALCI, and FCALCZ. The input required for the main program are the number of jobs N, the number of machines M, and the total 76 N*M processing times for a problem. The main program first determines the value of N! and then for each of the natural positive integers between 1 and N! calls the subroutine SCHED to generate an appropriate sequence of N jobs. For example, for a 4 job, 4 machine flow shop, the following table shows the number between 1 and N! and their corres- ponding sequences. For each of the N! sequences that the Table 3.1 Numbers in Sequences for the 4 Job, 4 Machine Flow Shop Scheduling Problem Number Sequences 1234 1243 1324 1342 1423 1432 2134 :flO‘U‘IIh-UJNH 4321 N ab main program has obtained from the subroutine SCHED, it calls the subroutines FCALCl and FCALCZ to obtain the completion times of different operations of the N jobs on the 4 machines. The input for both the subroutines, FCALCl and FCALCZ, are the N*4 processing times and the sequence generated by the subroutine SCHED. The subroutine FCALCZ also needs as an input the output of FCALCl. The subroutine FCALCl computes the completion time of Operations of N jobs on the first two 77 machines and FCALCZ computes the completion times of N jobs on the last two machines. Although a single subroutine could easily do the job of the two subroutines, FCALCl and FCALCZ, in the first phase, for the sake of computational efficiency, usage of the separate subroutines is necessary in the second phase where the job sequences are different on the first two machines from the last two machines. The total make-span for the particular sequence is equal to the comple- tion time Of the last (Nth) Operation on the fourth machine from the subroutine FCALCZ. Modified Branch and Bound Algorithm For the first phase of experiments in Chapter V, the Branch and Bound algorithm used is essentially the same as the one used by Ignall and Schrage, with three important modifications. The first modification is the extension of Ignall and Schrage's lower bound function of the 3 machine classical flow shop to the lower bound function for the 4 machine classical flow shop. Ignall and Schrage's function was present in the second chapter of this dissertation; the modified lower bound function is given below: 78 Time A(JS) + 2 ai + Min (bi + Ci + di); NJS NJS Time B(JS) + 2 bi + Min (Ci + di); NJS NJS LB(JS) = Max Time C(JS) + 2 ci + Min (di); NJS NJS Time D(JS) + 2 di; ' NJS J_____ __ Where JS is the set of jobs sequences corresponding to the node for which LB(JS) is the lower bound. Time A(JS), Time B(JS), Time C(Js) and Time D(JS) are the comple- tion times of the last job in thessequence JS on machines A, B, C, and D, respectively. The terms ai, bi' ci, and di represent the processing times of job i on machines A. B, C, and D, respectively. The jobset NJS includes jobs which are not sequences in JS. The second modification can save a great amount of computational time and effort when the Branch and Bound technique is used for large flow shop problems. The modifi— cation is based on the work done for the traveling salesman problem by Dannenbring (unpublished) and reported by Starr (39). It involves computing an upper bound to the problem before the tree branching and nodes creation are begun. If an upper bound to the total make-span is obtained, then any node which has a lower bound greater than the upper bound 79 can easily be disposed of without branching from it. Various ways can be devised to obtain an upper bound. However, the upper bound should have a fairly low value so that it can serve some useful purpose without involving a lot of computational effort to find it. After some experi- mentation, a simple technique to compute an upper bound for this dissertation was decided. The technique is an exten— sion of Giglio and Wagner's 3 machine heuristic technique (15) and involves part of Campbell, Dudek and Smith's heuristic algorithm (7). This technique involves adding the processing times of the first two machines and adding the processing times of the third and the fourth machines for each of the N jobs. Thus an N job, 4 machine problem is temporarily converted to an N job, 2 machine problem. Johnson's 2 machine algorithm can be applied to the problem and an "optimum" sequence obtained. The "Optimum" sequence is used with the original N job, 4 machine problem and the total make-span computed. The sequence obtained by Johnson's algorithm will probably not be optimum for the N job, 4 machine problem, but some experience with the technique sug- gests that in most cases it will be quite close to the Optimum. Thus, the total make-span obtained can serve quite well as the upper bound for the problem. The third modification involves obtaining all the Optimum sequences for a problem instead of just one from the Branch and Bound technique. While branching and computing lower bounds for nodes, if more than one node having the same 80 lower bound was found, Ignall and Schrage chose one at random for further branching. At the termination, if any unbranched node or nodes having the same lower bound as the minimum total make-span were present, they were left as they were. Instead, in the Branch and Bound technique used in this dissertation, once an optimum sequence and its total make-span are Obtained, all nodes having the same lower bound as the minimum total make—span are branched until all optimum sequences are found or until all the unbranched nodes have a higher lower-bound than the minimum total make-span. The computer program for the modified Branch and Bound algorithm consists of a main program and five sub~ routines, namely, COMPUTE, SEND, BOUND, INTRO, and DESTRO. The Branch and Bound technique in general, and the modified Ignall and Schrage lower bound function, in particular, are programmed in such a way that they can be used for up to 20 job, 10 machine classical flow shOp problems. The main program reads in the values of the number of jobs, number of machines, and the processing times. It outputs the minimum total make-span and all Of the Optimum sequences for a problem under the No Passing restriction. The subroutine COMPUTE computes an upper bound for a problem (using Johnson's algorithm). The subroutine SEND selects the most promising node from the list of available codes, branches out from it and creates nodes for the branches. The sub- routine BOUND calculates the lower bound for all the newly 81 created nodes. If in the future some other function for calculating lower bounds is to be used, it is necessary to change only the subroutine BOUND. The subroutine INTRO inspects all newly-computed lower bounds and compares them to the upper bound, and the corresponding node is intro- duced to the list of available nodes. The subroutine DESTRO searches for any node that is fully branched and has served its purpose, then eliminates it from the list of available nodes. Once a complete sequence emerges from the subroutine INTRO, the subroutine SEND reduces the value of the upper bound to the total make-span of the complete sequence. The complete listing of the computer prOgram is given in Appen- dix B. Phase Two Standard of Measurement of Passing After preliminary experiments, a need to define and measure the amount of passing between two sequences of a passing solution has emerged. The standard of measurement is named "SHIFT" and the amount of Passing is measured as 1 shift, 2 shift, et cetera. When a job which is in the Kth (Kmm moosmsvmm cmmmlmxmz moosmswmm cmmmlmxmz Hmnesz .Oz ESEmez mo Hmuoe HmEHumo Hmuoa emHnoum HOQEOZ ummzoq mo umhfidz EOEHGHS GMHm an mca>mw msHmmmm osHmmmm Oz H eoeumoHHmmm--memeoue managemeom more 30He wearer: e .noe m m.¢ OHQMB 112 N N N N H Hmm N mmm Ohm Om OH OH OH OH N Nmm H Nmm Ohm mm we we we we m mNm H mum Hum Om 5N mN 5N 5N H hem N Ohm mmm mm N N N N H va N mum mmm Nm 5 h n h H mom H mmm mmm Hm we we we we v HNm H mmm Hmm om m m m m N th H OON Nvm mN O O N N N Hmm H mmm Hmm ON m m m m H mNm H mmm NNm NN N N N N H veN N mvN mNm ON m m m m H hHm H NNm OHm mN m m m m H «ON H NON mom «N Ne Ne Ne Ne w HHN N mmN vom mN NH NH NH NH H mmN N NON OON NN ON ON ON ON H Ohm H mam NON HN m m m m H mvm H hmm HmN ON m m m m HH Ohm H «mm vON mH m m m m H Nmm H mmm OmN OH m N H msH>mm moosmsvmm ommmlmxmz woocmsomm smmmumxmz “$9852 .02 EOEmez mo Hmuoe HmEHumo Hmuoa EOHQOHm HmnEsz ummon mo Honesz EOEHst GMHm an msH>mm OCHmmmm msHmmmm oz .Umchucoo m.¢ mHnt 113 O«.HH O«.HH ««.HH ««.HH Nm.H mH.ONm O«.H mm.Nmm mmmum>¢ mmm mmm mmm mmm HN mmmOH ON «mmNH Hmuoa m m m m H ONm H mNm OOO Nm N N N N N mm« N mO« Om« Hm N N N N H «mm H HOm NN« on O O O m H «Nm N mmm HN« m« m m m m H Omm N ««m NO« O« OH OH OH OH H mOm H «mm O«« N« m m m m H HON N «ON ««« O« NH NH NH NH H NHm H «mm H«« m« m m m m m mmm N Omm O«« «« m m m m H Hmm N mam mN« m« « « « « H «Nm H mNm «H« N« NH NH NH NH H MNN N mmN NO« H« « « « « H Nom H HHm Omm O« NH NH NH NH H «mm N O«m mmm mm OH OH OH OH H NOm H NNm Omm mm OH OH OH OH H H«m N OOm «mm Nm m N H OGH>mm moosmsomm commumxmz mmosmsomm cmmmlmxmz HOQEOZ .oz Esemez mo Hmuoe HOEHuoo HmuOB EmHhoum uOhEdz umm3OH mo nonesz EOEHGHZ COHm an OQH>mm mchmmm OGHmmmm oz .emeeeueoo m.e meee 114 m m m m H NON H ONN HmH NH Nm Nm Nm Nm N NON H ONN ONH OH N N N N H NO« H OH« ONH OH « « « « H HON H mom mOH «H O O m m H mO« H OO« mm mH N N N N H OH« H ON« mm NH HN HN HN HN H mmm H «O« ON HH HH HH HH HH H ONN H mmN NO OH O O O O H «Nm N Omm m« m mm mm mm mm m Omm H Hm« «« O O O «N «N N NNm H HO« mm N mH mH mH mH N can N NO« mm O NH NH NH NH N MNN H O«N mN m m m m m H mNm H Nmm «N « « « « « N Nom H Oom NN m N N N N H Hmm H mmm «H N O O O O H Nmm N mmm m H m N H OQH>mm mmosmsomm commumxmz mmocmdvmm smmmlmxmz HmnEsz .Oz EOEmez mo Hmuoe HmEHumo Hmuoe EOHQOHm Honesz Dmm3OH mo HOQEOZ EOEHQHS GOHm an msH>mm msHmmmm OCHmmmm Oz .N eoHumoHHommunmsmeoue meHHsemeom eoem aon meHeomz e .noe m O.« OHQMB 115 OO OO OO OO H «OO H OOO O«O NO OH OH OH OH H OON N O«N N«O OO « « « « H ONO H OOO NNO OO OH OH OH OH H NNO N NOO «HO «O ON ON ON ON N NOO H OH« OHO OO «N «N «N «N H OOO H «O« NHO NO « « « « H NOO N OOO OOO HO O O OH OH N OOO H O«O ONN OO HN HN HN HN O OHO N «OO HNN ON O O H H H HNO N NNO OON ON H H H H H OOO H HOO OON NN O O N N H OHO H NNO N«N ON «H «H «H «H H NOO H HOO ONN ON N N N N H «OH H OOH OON «N OH OH OH OH N NNN H OON NOH ON «O «O «O «O H OON H ONO OOH NN « « « « H OON H OON OOH HN OO OO OO OO O O«N H ONN «OH ON H H H H H OON H HON H«H OH O O NH NH H OOO H OOO OOH OH O N H OCH>OO mmocwsvwm cmmmlmxmz mmosmsomm cmmmlmxmz Hthdz .Oz EOEHxOS mo Hmuoe HmEHumo Hmuoe EmHhoum umnfisz ummzoq mo HOQEOZ EOEHGHS GOHA an OGH>OO OOHmmOm OCHmmmm oz .emseeueoo e.e mHnee 116 «N.NH «N.NH O0.0H OOWOH N«.H O«.HNO ON.H N«.OOO OOOHO>¢ ONO ONO H«N H«N ON . OOONH OO OONNH Hmuoe O O O O H OON H OON HO« OO O« O« O« O« N ONO H HNO OO« NO O O OH OH N O«O H NOO HO« HO O O HH HH N ONN H «ON OO« OO ON ON ON ON H N«N H NON NO« O« O O O O H NON H HON OO« O« H H H H H NOO N OOO OO« N« NH NH NH NH H NO« N OH« OO« O« HN HN HN HN H N«O H OOO OH« O« OH OH OH OH H HON H HNN NH« «« O O O O O ONO H NOO OH« O« NN NN NN NN H OOO H NH« «H« N« OO OO OO OO N NNO H NOO OH« H« N N N N H OOO N NHO HO« O« NN NN NN NN H OOO N OOO OOO OO NH NH NH NH H HON N ONN ONO OO O N H OsH>mm mmosmnwmm smmmlmxmz mmocmsvmm cmmmlmxmz Hmhfisz .Oz EOEmez mo Hmuoe HmEHumo Hmuoe EmHnoum HOQEOZ umm3OH mo HOQEDZ EOEHCHS cmHm an OQH>mm OsHmmmm OsHmmmm oz .emseeueoo e.e meme 117 is 336.51 units and the average total make-span after com- plete enumeration in Phase Two is 323.79 units. This means an average of 12.72 units (336.51 - 323.79 = 12.72) improve- ment per problem for the 105 problems when passing is per- mitted between sequences. In the remaining 895 problems (1000 - 105 = 895) there was no improvement by permitting passing. The average minimum total make-span under the no passing condition for all 1000 problems, as presented in Phase One results, was 323.28 units. When passing is per- mitted the average total make-span for the 1000 problems was 321.94 units. Thus, by permitting passing, an average savings of 1.34 units in the total make-span (323.28 - 321.94 = 1.34) per problem for the 1000 problems is achieved. At first consideration, this amount of savings does not seem like a lot but if viewed in proper perspective, it can appear worthwhile. Under the no passing restriction, the average minimum total make—span is 323.28 units and the maximum total make-span is 401.96 units (as presented earlier in this chapter), or an average difference of only 78.68 units between the worst and best total make-span. When an average improvement of 1.34 units by permitting passing is compared with the average difference between the best and the worst total make-span of 78.68 units under the no passing restric- tion, the improvement seems worthwhile. According to the measurement function of improvement by passing discussed and selected in Chapter III, the value of improvement is as follows: 118 MTMS - TMSP _ 323.28 a 321.94 _ 1.34 MTMS ‘ 323.28 ‘ 323.28 f4 = .00415 or 0.415% Table 4.7 summarizes the amount of improvement or savings in total make-spans from Phase One to Phase Two by complete enumeration and by the three plans. Table 4.7 Amount of Savings in the Total Make-span and the Amount of Search Work Involved with Passing Plans Complete Enumeration l 2 3 1. Amount of savings in the total make-spans Replication l 595 595 593 593 Replication 2 741 741 675 675 Total 1336 1336 1268 1268 Percent 100 100 94.9 94.9 2. Number of solutions searched per problem Total 30 18.00 11.89 7.14 Percent 100 60.00 39.63 23.78 3. Benefit-cost ratio in terms of total savings divided by number of solutions searched 44.53 74.25 106.78 177.59 119 As can be seen from the tables, the three plans manage to capture most of the possible savings in total make-spans from Phase One to Two. The total amount of savings in Plan One is exactly the same as the savings obtained by complete enumeration for both replications. Although Plan One for 3 job, 4 machine flow shop scheduling problems involves only 60 percent as much work as complete enumeration, it captures 100 percent of the savings. Plan Two saves 99.65 percent of the maximum amount for replica- tion 1 and 91.09 percent for replication 2. The total amount of work involved in Plan Two is just 39.63 percent but for both replications it saves 94.91 percent of the total make-span as compared to complete enumeration. Plan Three involves only 23.78 percent or one fourth as much work as complete enumeration but saves 94.91 percent of the maximum possible total make—span. Thus, it seems these three plans are quite successful in capturing almost all the savings in total make-spans from Phase One to Phase Two while avoiding a large volume of work searching for them in 3 job, 4 machine flow shop scheduling problems. The benefit-cost ratio also increases steadily, and for Plan Three is four times as large as that for the complete enumeration. 120 4 Job, 4 Machine Flow Shop Scheduling Problems The results obtained for the two replications of 500 problems for Phases One and Two are presented in Tables 4.8 and 4.9. Phase One First, the frequency distributions of a number of problems, according to minimum total make-spans and maximum total make-spans, are presented in Tables 4.8 and 4.9. The frequency distribution of the number of problems according to the number of optimal sequences in Phase One is given in Table 4.10. The total number of Optimal sequences a problem has is useful to know for Plans Two to Five in Phase Two. There are a total of 1691 optimal sequences for the 1000 problems, or an average of 1.691 optimal sequences per problem. Plans Four and Five advocate a maximum of only three and two Optimal sequences respectively for 4 job, 4 machine flow shOp scheduling problems. From Table 4,10 it seems there are a total of 77 and 146 problems having more than three and two Optimal sequences, respectively. Using only the first three and two optimal sequences reduces the average number of Optimal sequences from 1.691 per problem to 1.544 and 1.398 per problem, respectively. The relative amount of savings in search work and its conse- quent loss in improving the amount of the total make-span 121 Table 4.8 Frequency Distribution of 4 Job, 4 Machine Problems According to the Minimum Total Make-Spans Under No Passing The Range of Number of Problems Minimum Total Make-Spans Replication l’ Replication 2 Total Less than 220 0 l 1 221-240 4 ‘ 0 4 241-260 8 7 15 261-280 12 11 23 281-300 21 22 43 301-320 35 33 68 321-340 51 51 102 341-360 56 65 121 361-380 74 71 145 381-400 68 72 140 401-420 63 56 119 421-440 42 42 84 441-460 29 32 61 461-480 18 18 36 481-500 9 9 18 501-420 9 8 17 521-540 1 2 3 Total 500 500 1000 Average minimum total make-Span 377.14 377.92 377.53 Std. Dev. of the minimum total make-span 56.49 56.12 56.30 122 Table 4.9 Frequency Distribution of 4 Job, 4 Machine Problems According to the Maximum Total Make-spans Under No Passing The Range of Number of Problems Maximum Total Make-spans Replication 1 Replication 2 Total 321-340 3 3 341-360 361-380 6 4 10 381-400 15 20 35 401-420 23 24 47 421-440 44 35 79 441-460 39 35 74 461-480 61 54 115 481-500 62 62 124 501-520 72 70 ' 142 521-540 57 59 116 541-560 56 58 114 561-580 31 33 64 581-600 16 20 36 Above 600 11 18 .29 Total 500 500 1000 Average minimum total make-span 494.91 498.14 496.52 Std. dev. of minimum total make-span 57.21 59.22 58.22 123 HOOH OOOH NOO OOO «OO OOO HOHOB N H O O N H N OOH ON OO OH OO HH O ON OH O« O OO N O O«H OO OO OH OO ON « NON OO «O .ON ONH H« O «OO NON OON ONH O«N ONH N NOO NOO OOO OOO NON NON H .m.z«.w.0 .m.Z .m.Z«.. .m.z .m.Z*.m.O .m.z .m.O mmosmswmm mEOHQOMm mmocmoomm mEmHhOHm mmoomsvmm mEOHhOHm mmosmsmmm mo HOQEOZ O0 mo Hmhesz m0 m0 HOQEDZ mo HOEHDQO HODOB umbeoz Hmuoe HOQEOZ HODOB HOQEOZ HOQEOZ HODOB N OOHHOOHHmOm H OOHDOOHHQOm OsHmmmm Oz MOOCD mmosmsomm HOEHHQO mo HOOEOZ On» On OGHOuoood OEOHQOHO mo moOHuanuumHn Moomdvmum OH.« OHQOB 124 with other plans will be discussed later in this chapter after the results of the Phase Two experiments are pre- sented. Under the no passing restriction for 4 job, 4 machine flow shop scheduling problems there are a total of 4! = 24 possible sequences or permutations. Each of the 1691 optimal sequences Obtained in Phase One could be any one of the 24 different possible sequences. The frequency distribution of the 1691 Optimal sequences, according to the 24 possible sequences obtained, is presented in Table 4.11. Since there are 1691 total optimal sequences dis- tributed among the 24 possible sequences, each sequence should have an average of 70.46 Optimal sequences. Good- ness of Fit was tested on the frequency distribution using the Chi-square test. For the 23 degrees of freedom X2 .05 is equal to 35.172. The computed value of the Chi-square from the frequency distribution of 1691 Optimal sequences was only 24.75. The number 24.75 being much below 35.172, it is clear each of the 24 possible sequences are equally popular to be optimal. Phase Two For 68 and 62 problems of the 500 problems each for replications l and 2, the best total make-spans in Phase TWO were lower than the minimum total make-spans of Phase One. The actual amount of improvement obtained by complete enumeration for these 68 and 62 problems was anywhere from 125 Table 4.11 Frequency Distribution Of Optimal Sequences of Phase One According to the Different Possible Permutations of 4 Jobs Sequences or NO. Permutations Replication 1 Replication 2 Total 1 l 2 3 4 31 3O 61 2 1 2 4 3 32 26 58 3 1 3 2 4 33 40 73 4 l 3 4 2 35 43 78 5 l 4 2 3 32 30 62 6 l 4 3 2 35 31 66 7 2 1 3 4 46 31 77 8 2 1 4 3 37 31 68 9 2 3 l 4 42 32 74 10 2 3 4 l 36 32 68 ll 2 4 l 3 29 38 57 12 2 4 3 l 31 34 65 13 3 1 2 4 36 23 59 14 3 l 4 2 28 38 66 15 3 2 l 4 33 28 61 16 3 2 4 1 32 45 77 17 3 4 1 2 37 44 81 18 3 4 2 l 40 32 72 19 4 1 2 3 33 34 67 20 4 l 3 2 35 41 76 21 4 2 l 3 37 35 72 22 4 2 3 1 39 41 80 23 4 3 1 2 42 47 89 24 4 3 2 1 43 41 84 Total 854 837 1691 126 one to 48 units, averaging 12.07 and 12.69 units per prob- lem, respectively, for replications 1 and 2. Each of these problems had anywhere from one to 24 passing solutions whose total make-Span values in Phase Two were lower than the minumum total make-spans of Phase One. The average number of passing solutions with lower make-spans than the minimum total make-span of Phase One were 3.24 and 2.73 per problem, respectively. Tables 4.12 and 4.13 are similar to the tables for 3 job, 4 machine flow shop scheduling problems, with the addition of two more columns showing the amount of improvement in total make-spans by Plans Four and Five, respectively. For 4 job, 4 machine flow shop problems there are 68 + 62 = 130 problems of the total 1000 problems in which permitting passing improves the total make-span. The average minimum total make-span at the end of Phase One for these 130 problems is 396.36 units and the average best total make-Span when passing is permitted is 383.99 units. This is an average improvement of 12.37 units per problem for the 130 problems. In the remaining 870 problems, there was improvement in Phase Two computations. The average minimum total make-Span for the 1000 problems in Phase One was 377.53 units and the average total make-span for the same 1000 problems in Phase Two was 375.92 units. Thus, by per- mitting passing, an average reduction of 1.61 units of the total make-span is achieved per problem. 127 OH OH OH OH OH . OH N «HO N OOO NNH NH HN HN HN HN HN HN O ONO N OOO OHH OH O O O O O O H ON« N «O« OHH OH OH OH OH OH OH OH N ON« H OO« OHH «H O O O O O O N OOO N NO« NHH OH OH OH OH OH OH OH N HOO H HO« OOH NH «N «N «N «N «N «N H HO« N OO« OO HH « « « « « « N ONO N «NO OO OH O O OH OH OH OH O OON O OHO OO O O O N N N N N ONO « OOO OO O O O O O N N « NNO H ONO «O N OH OH OH OH OH OH O «NO H NOO OO O O O O O O O H OO« N NO« «N O N N N N N N H «OO N OOO HN « OH OH OH OH OH OH N HOO O ONO NH O NH NH NH NH NH NH N NOO O O«O O N O O O O O O O OOO O OOO O H O « O N H OsH>mm mmosmsomm cmmmlmxmz mmosmsomm cmmmnmxmz HOQEOZ .Oz EOEmeS mo Hmuoe HOEHDQO Hmuoa EmHnoum Hmhesz ummzoq mo HOOEOZ EOEHOHZ msmHm Ochmmm OCHmmmm oz H eoeumoHHemmuumEmeoum meHHsemeum eoem one menace: « .noe e NH.« OHQMB 128 N N ON ON ON ON OH «OO N OH« O«N OO O O O O O O H OOO H NOO O«N OO NH NH NH NH NH NH N ON« O OO« OON «O O O O O HH HH H NN« H OO« ONN OO O« O« O« O« O« O« H NOO H O«« ONN NO O O O O O O H OOO « OOO «NN HO O O O O O O N OOO N OOO ONN OO HH HH HH HH HH HH O OOO O NNO OOH ON O O O O O O H OH« H ON« OOH ON O O O O «H «H N OON H ONN «OH NN OH OH OH mH .OH OH a mNm m mam meH em OH OH OH OH OH OH H HHO N OOO ONH ON 0 O O O OH OH N HO« « HN« OOH «N OO OO OO OO OO OO ON OOO N OOO «OH ON N N N N N N N OON H OON O«H NN O N N N N N O HOO O OOO NOH HN O O O O O O H ONO N ONO HOH ON NH NH NH NH NH NH N OOO H OO« ONH OH O O O O O O H ON« H HO« ONH OH O « O N H OCH>OO mmosmswmm ommmlmxmz mmosmsomm smmmlmxmz HOQEDZ .Oz EOEmeE O0 Hmuoe HOEHDQO Hmuoe EOHQOHO HOOEOZ ummsoH mo HOQEDZ EOEHCHE msmHm OsHmmmm OOHmmmm oz .emscHueoo NH.e meme 129 N N N N N N H NON « OON OOO OO O HH HH HH HH HH H NO« O OO« NNO «O O O O O O O H O«« H O«« OOO OO N N N N N N H OOO H NOO NOO NO O O O O O O N NH« H NN« OOO HO NH NH NH NH NH NH « N«« H «O« OOO OO O O O O N N N OOO H HOO O«O O« N N N N «H «H O OOO H N«O NOO O« O O O O NO NO O OOO H OO« «HO N« OH OH OH OH OH OH « OH« N HO« OOO O« OH OH OH OH OH OH H ONO N OOO NOO O« «H «H «H «H «H «H H OOO N «NO HOO «« «N «N «N «N «N «N O OOO H OH« OON O« O O O O O O N OOO N NOO OON N« O O O O O O H HOO N NOO OON H« OH OH OH OH OH OH H OON H OOO OON O« HO HO HO HO HO HO NH OON H NHO OON OO N N N N N N H OOO O OOO HON OO O O O O H H H NOO H OOO NON NO O « O N H OCH>OO mwocmswwm ommmlmxmz mmocmsvmm cmmmlmxmz HOQEOZ .Oz EOEmez mo Hmpoe HOEHHQO HONOR EOHQOHO HOQEOZ umOBOH mo nmnfisz EDEHGHE mcmHm Ochmmm OsHmmmm oz .ewseHueoo NH.e meee 130 NNO. NNO O«dH O«dH NONH NO.NH ON.O ON.ONO NH.N NN.OOO mmmum>< NOO HOO NON NON HNO HNO ONN O«N.ON ««H OO0.0N Hmuoa HN HN HN HN HN HN N OOO N OOO OO« OO N N N N HN HN NH ON« H N«« ON« NO ON ON ON ON OO OO NH HNO « «O« NN« OO NH NH NH NH OH OH O «OO N NO« OO« OO NH NH NH NH NN NN N O«O N NOO «O« «O O O O O O O N NOO O OOO N«« OO N N N N N N H ON« N ON« ON« NO O O O O O O H NOO N NOO NH« HO H H H H H H N NOO N OOO OO« OO H H H H H H H OO« H O«« NO« OO O O O O O O H OOO H OOO HO« OO N N N N N N H NO« H «O« OO« NO O O O O H H N ON« H OO« NOO OO O « O N H OsH>mm mmosmsomw smmmloxmz mmosmswmm smmmumxmz HOQEOZ .02 Edemez mo Hmuoa HOEHumO Hmuoa EOHQOHO uOhEsz umm3oq mo HOQEOZ ESEHGHS OGMHO OOmemm OsHmmmm oz .OmssHusoo NH.« OHQOB 131 HN HN HN HN HN HN H ON« H O«« «OH NH OH OH OH OH OH OH H OOO N OOO OOH OH N N N N N N H OOO H OOO N«H OH H H H H H H H OO« H NO« ««H «H ON ON ON ON ON ON H NO« N OO« H«H OH. NO NO NO NO NO NO H OOO H OOO OOH NH N N N N « « O OOO H «OO ONH HH N« N« N« N« N« N« «N OOO O NO« NNH OH O « « « « OH N HOO O HOO OHH O O O O O O O H OO« N OO« «OH O O O O O .O O « OOO N OOO «O N HN HN HN HN HN HN H ON« N O«« ON O OH OH OH OH OH OH H OOO H NO« OO O OH OH OH OH OH OH O ON« H N«« NO « OH OH OH OH .OH OH N OOO H NNO NO O O O O O «H «H H OOO H ONO H« N « « ON ON ON OO O OO« « OO« ON H O « O N H OCH>MO mmosmswmm smmmlmxmz mmosmsvmm cmmmlmxmz Hmnfinz .oz snemez Oo Hence HmeHuoo Hmuoe emHnonm Hmnesz umm30H m0 MOQEOZ ESEHOHS msmHm Oonmmm Ousmmm Oz m eoeumoHHemmu-mEmeoue OeHHsemsom norm roHe meHrom: « .non « OH.« OHQMB 132 OH OH OH .OH OH OH O ONO H OOO «ON OO e e m e e . m m mHm O Hum Nmm mm O O O O O O O OH« N OH« O«N «O O OH OH OH OH OH « NOO O OOO O«N OO ON ON ON ON ON ON O OOO H ON« O«N NO N N N N N N H OOO H NOO OON HO O O O O O ,O H NOO N O«O NON OO O O O O O O H OOO H O«O ONN ON « « « « « « H. NO« N HOO ,HHN ON O O O O O O « H«O N ««O NON NN OH. OH OH OH OH OH N OON H OON OOH ON O O O. O O O N OH« H HN« OOH ON O O O O O O H OOO H OOO OOH «N NN NN NN NN NN NN N «OO O ONO ONH ON O O O O O O H O«« N O«« ONH NN OH OH OH OH OH OH O ONO O OOO OOH HN ON ON ON ON ON ON N «O« N OO« OOH ON O O O O O O N OOO H NOO OOH OH N N N N N N H NOO H «OO NOH OH O « O N H OGH>mm mmocmsowm ommmumxmz mmosmsvmm cmmmlmxmz umhesz .oz asstmz mo Hmuoe Hmseueo Hence smHnone umhesz awesoq mo HmnEsz EaeHcHz msmHm OsHmmmm OsHmmmm oz .emeeeueoo MH.e meme 133 OH OH OH OH OH OH H OO« N «N« ON« OO O O OH OH OH OH O N«O O OOO Oo« «O OH OH OH OH OH OH H NON N NOO OO« OO O O O O O O H ONO H «OO OOO NO mm mm mm mm mm mm H HNe m mme Hem HO O O O O O O N O«« N NO« NNO OO « « « « « « H OOO N OOO NOO O« H H H H H H H NO« H OO« N«O O« OH OH OH OH OH OH H OOO N OOO O«O N« O O O O N N H ON« H NN« NOO O« OH OH OH OH OH OH O HO« N OO« HOO O« O O O O O O H OH« N HN« OOO «« ON ON ON ON ON ON N HOO H HO« ONO O« ON ON ON ON ON ON H OOO N «OO NOO N« «H «H «H «H NH ON O ON« H O«« OON H« O O O O ON ON N NOO N OOO OON O« N N N N N N H Oo« O OO« OON OO « « « « « « O «OO H OOO ONN OO OH OH OH OH OH OH H OO« N OO« HNN NO O « O N H OGH>OO wmoomsomm smmmlmxmz mOOOOOOOO smmmlmxmz umhesz .oz EOEmez mo Hmuoa HmEHumo Hmuoa EOHQOHO HOQEOZ umOSOH m0 HOQESZ EOEHGHZ OQMHm msHmmmm msHmmmm oz .emeeHueoo HH.e meme 134 NhOH NQHH HWHH «NHH OONH OO.NH ON.N O0.000 OO.N OO.NO« 0OOHO>¢ OOO OOO ONN ONN ONN NON OOH HNH.«N ONH OO0.0N Hmuoa «H «H «H «H «H «H O NOO N HO« OO« NO H H H H H H N OO« H OO« «O« HO OH OH OH OH OH OH O NOO N OOO OO« OO NO NO NO NO NO NO O NON N «NO OO« OO OH OH OH OH OH OH O OOO O OO« NO« OO N N N N N N H HN« N ON« «O« NO N N N N N N H N«O N O«O NO« OO O « O N H OOH>mm mmosmsvmm cmmmlmxmz mmosmsqmm smmmlmxmz HOQEDZ .Oz EDEmez m0 Hmuoe HOEHumo Hmuoe EOHQOHm Hmnesz umm3OH m0 umhesz EOEHGHE msmHm Ochmmm Ochmmm oz .OmscHucoo OH.« OHQOB 135 The values of the measurement function for improve- ment by passing is as follows: MTMS - TMSP _ 377.53 - 375.92 f4 = MTMS ' 377.53 _ 1.61 _ — m - .00427 or 0.427% Table 4.14 summarizes the amount of improvement or savings in total make-spans from Phase One to Phase Two by either complete enumeration search or by search of the five plans. It also summarizes the amount of search work invovled in the five plans, comparing it to the search.work of complete enumeration, and provides benefit-cost ratios. From Table 4.14 it appears the amount of work involved in Plans One, Two and Three, as compared to com- plete enumeration, decreases very rapidly, starting from 100 percent for complete enumeration to 3.69 percent for Plan Three. However, the amount of savings in total make- spans compared to the maximum possible savings by complete enumeration decreases quite slowly from 100 percent to 88.74 percent. Thus, the benefits involved in Plans One, Two and Three seem clear. Plan Three looks particularly attractive. Plans Four and Five do not seem particularly attractive compared to Plan Three. The reduction of search work in Plans Four and Five does not appear significant. And com- pared to the reduction in work, the loss of savings in total make-spans seems little higher. The benefit cot ratio, as 136 ON.NN OO.NN O0.0N O«.OH OH.HH HO.N Omnoummm msOHusHom O0 HOQEOG an ©OUH>HO mOsH>mm Hmuou OO mane» OH OHumH umOOIHHOOsOm .O «0.0 O0.0 O0.0 OO.«H O0.0N OOH Osmonmm ON.OH O0.0H ON.ON ON.NN ««H NOO Hmuoa EOHQOHQ Hem Umnonmmm msOHusHOO O0 Hmhesz .N OH.HO NN.OO «N.OO «N.OO ««.OO OOH Osmonmm OOOH N«OH NN«H OO«H OOOH OOOH HOOOB OOO OOO ONN ONN ONN NON N ooHumOHHmmm NOO HOO NON NON HNO HNO H GOHHOOHHQOM mammmlmxme Hmuou 0:» CH mOcH>mm O0 OOOOEN .H O « O N H COHumHOEDcm mumHmEOU OGOHO noummm O0 HOSOEO Osm mammmlmxmz GH mmsH>mm O0 OGHmmmm :uH3 OO>H0>GH xuoz «H.« OHQOE OCSOEO 137 can be seen from the table, increases substantially from complete enumeration to Plan Three. For Plans Four and Five the increase is fairly slow. It was decided that for the experiments of Chapter V, involving 4 job, 4 machine flow shop scheduling problems, only Plans One, Two and Three, together with complete enumeration, will be utilized. 5 Job, 4 Machine Flow Shop SchedulingrProblems The results obtained for the two replications of 500 problems for Phases One and Two are presented below. Phase One Frequency distributions of the number of problems according to the minimum total make-span and the maximum total make-span, are presented in Tables 4.15 and 4.16. As previously discussed in the 3 job and 4 job flow shop sections, many flow shOp scheduling problems have more than one Optimal sequence. It is certain that the average number of Optimum sequences per problem increases as the size of the flow shop increases. For the 3 job, 4 machine flow shop, there were 1.189 optimal sequences per problem, and for the 4 job, 4 machine flow shop, there were 1.691 optimal sequences per problem. For the 5 job, 4 machine flow shop, Table 4.17 provides the frequency distribution of the number of problems according to the number of optimal sequences. The average number of Optimal sequences obtained 138 Table 4.15 Frequency Distribution of 5 Job, 4 Machine Problems According to Minimum Total Make Spans The Range of Frequencies Minimum Total Make-spans Replication 1 Replication 2 Total 261-280 1 4 281-300 6 7 301-320 6 8 14 321-340 15 3 '18 341-360 32 30 62 361-380 40 45 85 381-400 60 59 119 401-420 76 77 153 421-440 63 69 132 441-460 73 64 137 461-480 48 45 ' 93 481-500 41 38 79 501-520 19 29 48 521-540 12 16 28 541-560 10 7 17 561-580 0 3 3 581-600 1 0 1 Total 500 500 1000 Average Total Minimum Make- span 426.73 428.97 427.85 Std. dev. of the Total Minimum Make- span 54.33 54.84 54.58 139 Table 4.16 Frequency Distribution Of 4 Job, 4 Machine Problems According to Maximum Total Make-spans The Range of Frequencies Maximum Total Make-spans Replication 1 Replication 2 Total 381-400 1 2 3 401-420 2 2 4 421-440 3 3 6 441-460 4 3 7 461-480 6 12 18 481-500 15 15 30 501-520 30 28 58 521-540 47 45 92 541-560 42 56 98 561-580 59 65 124 581-600 74 59 ’ 133 601-620 70 67 137 621-640 57 49 106 641-660 43 44 87 661-680 25 27 52 681-700 16 14 30 701-720 3 8 11 721-740 2 1 3 741-760 1 0 Total 500 ‘ 500 1000 Average Maximum Total Make-Span 587.71 585.83 586.77 Std. dev. of the Maximum Total Make-span 57.13 59.10 58.20 1’ 140 NOON OOOH NNNH . OOO OONH OOO OON «H OOH N HNH N «NIOH OOH O O« « OO O NH OO O O O OO O HH OO O OO O ON N OH O« O OO « O H O NHH «H NN O O« O O OO O OO O HN O N ONN OO.. OOH OH ONH ON O O«H ON O« O OO OH O OON NN OOH O« ONH NO « HON NN HHH NO ONH O« O ONO NON OON ONH ONN OOH N HO« HO« OON OON ONN ONN H .m.0«.m.z .m.z .m.0«.m.z .m.z .m.0«.m.z .m.z .m.o mmocmsvmm OEOHQOHO mmosmsvmm mEOHhonm mOocmsOOm mEOHhoum mmocmsvmm O0 HOQEOZ O0 O0 HOQEOZ O0 O0 Hmnesz O0 HmEHumo Hmuoa umhssz Hmuoa Hthsz Hmuoe Hmhesz HOnEsz Hmuoa m eoHumoHHemm H aoHumoHHemm mmosmswmm HOEHOQO O0 HOQEOZ may 0» OGH©H000¢ meanoum O0 amnesz On» O0 GOHOSQHHOOHQ mosmsvonm NH.« OHQOB 141 are 2.567 per problem. This number is 51.8 percent higher than the 1.691 optimal sequences per problem for the 4 job, 4 machine flow shop and is 116 percent higher than the 1.189 optimal sequences per problem for the 3 job, 4 machine flow shop scheduling problem. A total of 2567 Optimal sequences for the 1000 problems, computes to an average of 2.567 optimal sequences per problem in Phase One for a 5 job, 4 machine flow shOp' scheduling problem. Each of these 2567 Optimal sequences could be any one of the 5! = 120 different possible sequences. After studying the collected data, it seems clear that all 120 different possible sequences are equitably represented by the 2567 Optimal sequences. Phase Two For a total Of 91 and 94 problems of the 500 problems each for replications l and 2, the best total make- Spans in Phase Two were lower than the minimum total make- spans of Phase One. The actual amount of improvement acquired for these problems varied from 1 to 57 units, averaging 12.58 and 11.38 units per problem, respectively. Each of these problems had anywhere from 1 to 152 passing solutions whose best total make-span was lower than the ndnimum total make-span of Phase One, and it amounted to an average of 7.71 and 8.7 passing solutions per problem for replications 1 and 2. The two tables presented in the following pages correspond to replications l and 2 of the 142 OH OH OH OH OH OH N OO« O HO« OOH OH NH NH NH NH HN HN O OO« H HN« ONH NH H H H H H H H NN« O ON« OOH OH O O O O O O OH «O« N OOO HOH OH N N N N N N OH ONO H OOO NO «H NH NH NH NH «N «N N «o« H ON« OO OH. O O O O ON ON HN OO« N ON« NN NH « « « « « « H ON« « OO« OO HH NO NO NO NO NO NO HN OO« O NOO OO OH HH HH HH HH HH HH O ON« H OO« HO O O O O O NN NN OH OO« N NO« OO O O O O O .O O O ONO N ONO O« N N N N N N N N O«O H OOO OO O « « « « « « N NO« O HOO OO O O O O O N N N OOO H OO« OO « O O O O OH OH OH OOO O ONO ON O NH NH NH NH NH NH OH OOO « OO« OH N N N N N O O N ON« H «O« O H O « O N H OsH>mm mmosmfiomm cmmmlmxmz mmosmsvmm cmmmlmxmz Hmnfisz .Oz again: no H38. HmeHumo H33. 533.... Honesz umm30H O0 Hmnesz EOEHGHZ msmHm Ousmmm OOHmmmm Oz H GOHOOOHHQOMIIOEOHQOHO OsHstmaom monm onm oanomz.« .QOO O OH.« OHQMB 143 O O O O « « « NO« N OO« OHN NO O O O N O N H OO« H OH« OON OO O O O O ON ON HH OOO H NN« NON OO O O O O O O H OOO H Oo« OON «O H H H H H H O «OO « OOO NOH mm H H H H H H N OO« N «O« OOH NO O O O O H H O OO« N OO« OOH HO OH OH OH OH OH OH H OOO H HOO NOH OO NH NH NH NH NH NH H OOO O OH« OOH ON HN HN HN HN HN HN O OO« O HO« OOH ON «H «H «H «H «H «H H ONO N «OO ONH NN OH OH OH OH OH OH N N«« N NO« NNH ON ON ON ON ON ON ON O «O« N OOO ONH ON OH OH OH OH OH OH O HO« O OOO NNH «N O O O O O « O NOO N NOO OOH ON OO OO OO OO OO OO NN OO« N OO« O«H NN OH OH OH OH OH OH OH HO« O «N« H«H HN O O O O ON ON «H OO« N OO« OOH ON O O O O « « « NOO H OOO «OH OH O « O N H OOH>mm mmoswswmm cmmmumxmz OOOGODOOO ommmlmxmz umnfisz .Oz EOEmez O0 Hmuoa HmeHOmo Hmuoe EOHQOHO HOQEOZ ummsoq OO umhesz EOEHGHE msmHm msHmmmm OCHmmmm oz .emeeHueoo eH.e meme 144 O O O O HN HN H NN« O OO« OON OO HN HN HN HN HN HN N NOO « OOO OON OO NN NN NN NN NN NN OH OHO N NOO NON «O O O O O H H H HO« H NO« HON OO O O O O O O O OOO N OHO ONN NO OH OH OH OH OH OH OH HO« H OO« ONN HO « « « « OH OH NN OO« N OH« «NN OO O O O O O O N NH« H ON« OON O« H H H « H « N HO« O OO« OON O« O O O O O O N OO« H ON« «ON N« O O O O O O ON OOO O OOO O«N O« o e H H .w e H «mm em Nmm amm me OO NO NO NO NO NO NO O«« N NN« OON «« OO OO OO OO OO OO OH «O« O «O« OON O« OH OH OH OH OH OH « NN« O OO« NON N« OH OH OH OH OH OH O OOO H OOO OON H« O OH «H «H «H «H O OOO NH NNO ONN O« O O O O O O H ON« H NO« NNN OO OH OH OH OH HN HN NN HO« « NO« OHN OO O « O N H OsH>mm mmoomsqmm smmmlmxmz mmocmsvmm smmmlmxmz Hmnfisz .oz EOEmeS O0 Hmuoe HmEHumo Hmuoe EOHQOHO Hmnssz OOOBOH O0 Hmhesz EDEHOHE msmHm Ochmmm OsHmwmm oz .emseHueoo OH.e mHnme 145 N N N N N N H OOO O OO« NO« ON OH OH OH OH OH. OH NH OOO N HNO OOO «N HH HH HH HH HH .HH « ONO H «OO HOO ON OH OH OH OH OH OH « NO« O OO« ONO NN O O O O O O N NNO « OOO OOO HN HH HH HH HH HH HH H NN« H OO« OOO ON. O O O O O « « «NO N ONO OOO OO NH NH NH NH NH NH O NNO N «OO OOO OO O O O O OH OH O OO« H OOO OOO NO O O O O « « H OH« « OH« O«O OO N N N O N O OH HO« N ON« NOO OO O m m m m n 4 «am N mam «mm 4O N N N N N N O NOO H «OO HOO OO HH HH HH HH HH HH H OO« O «H« NNO NO ON ON ON ON ON ON ON OOO NH «N« OHO HO N N N N N N O «O« H HO« NOO OO O O O O O O H O«O N O«O OOO OO N N N N N N O OO« H NO« OON OO OO OO OO OO OO OO OH OOO H NN« HON NO O « O N H OOH>OO mmosmsvmm ommmlmxmz mmoswswmm smmmumxmz Hmnesz .oz EdemeZ O0 HOOOB HOEHOQO Hmuoa EOHQOHO amnesz ummon O0 Hmnesz EsEHst OGMHO Ochmmm OsHmmmm oz .emseHueoo mH.e mHnee 146 OQO NOO OOO OOO OQNH OO.NH NN.N ON.ON« HH.O OO.H«« OOOHO>¢ «OO HNO ONO OOO OOHH O«HH NON . OH0.00 OON HOH.O« Hmuoa O O O O O O « OO« N OO« OOO HO H H H H H H H O«« H OO« OO« OO, « « « « « « OH OO« O NH« «O« OO O O O O OH OH O HO« H ON« OO« OO O O O O O O O OO« « OO« HO« NO OO OO OO OO OO OO NH OOO N O«« ON« OO NH NH NH NH NH NH N OO« « NN« OO« OO N N N N N N H NOO O «OO O«« «O oH OH OH OH OH OH « NOO O N«O O«« OO N N N N N N H «N« H ON« O«« NO O O O O «H «H H OH« H OO« NO« HO O O O O O O H NOO H OOO OO« OO. O O O O « « H OO« H OO« ON« ON OH OH OH OH OH OH H OO« O OO« OH« ON O O O O O O O «OO H NOO HH« NN OH OH OH OH OH OH O HOO N O«O OO« ON O « O N H OGH>OO mmosmsvmm cmmmlmxmz mmoswswmm cmmmlmxmz Hmhfisz .oz asemez Oo Hmuoe HmeHueo Hmuoe amHnoum umnesz umOBOH O0 umnesz ESEHGHZ OGMHO Ochmmm msHmmmm oz .emseHueoo OH.« meme 147 H H H H H H H OOO O OOO HOH NH O O O O O « O O«« H OO« NO OH NN NN NN NN NN NN « ON« O OO« NO OH OH OH OH OH OH OH « «OO N OH« OO «H O O O O O O H H«« N ««« ON OH. O O O O O O H «O« H OO« OO NH O O O O ON ON ON OOO O «H« NO HH OH OH OH OH OH OH N «H« N «N« OO OH ON ON ON ON ON ON N OO« N OO« NO O O O O O O H H OOO O NOO OO O HO HO HO HO HO HO NO OO« H OO« N« N O O O O ON ON O NO« H NN« OO O H H H H H H O H«« N N«« NO O O O O O O O N OOO « OO« HN « O O O O O O OH «O« NH N«« OH O O O O O O O N OO« H OO« «H N OH OH OH OH OH OH O OOO OH OOO O H O N H OGH>OO mmosmsvmm smmmumxmz mmosmsvmm cmmmlmxmz umnesz .oz EOEmez O0 Hmuoa HOEHumo HOOOB EOHQOHO HOAEOZ ummBOH O0 uOnEdz EOEHGHS msmHm Ochmmm OsHmmmm oz ~ coHueoHHemmnumEmHnoue meHHnemeom more one meHeomz « .noe O OH.« OHQMB 148 OH OH OH OH OH OH H OO« H OH« OON NO « « « « « « « OOO « NOO OON OO ON ON ON ON ON ON O HO« H NN« «ON OO NO NO NO NO NO NO O NOO N ««O OON «O NN NN NN NN «N «N OH «O« H ON« OOH OO H« H« H« H« H« H« O O«O N NOO OOH NO. O O O O N N N HN« H ON« ONH HO NO NO NO NO NO NO O OO« « NO« ONH OO O O O O OH OH N OO« H OOO NNH ON O O O O N N N OOO N NOO OOH ON N N N N N N N «OO N OOO OOH NN ON ON ON ON .ON ON O OO« O NO« «OH ON O O O O H H H «OO N OOO NOH ON HO HO HO HO HO HO OH OOO N ON« O«H «N O O O O O O N ON« H OO« OOH ON O O O O O O O ON« H OO« OOH NN N N N N N N H OOO H OOO «OH HN O« O« O« O« O« O« NOH OO« « OOO OOH ON O O O O « « H OOO N OOO «OH OH oH OH OH OH OH OH « NOO « No« NOH OH O « O N H OOH>mm mmosmswmm cmmmlmxmz mmosmsvmm smmmumxmz umnesz .Oz Esemez O0 Hmuoa HmEHumO Hmuoa EmHhonm Amnesz um030H O0 Henssz EOEHOHZ manm OsHmmmm mchmmm.oz .emseHbeoo aH.e «Heme 149 O« O« O« O« O« O« OH HOO H «N« OOO NO HH HH HH HH ON ON OH O«O H OOO OOO OO HH HH HH HH HH HH N NOO H Oo« HON OO NH NH NH NH NH NH N« OH« OH OO« NON «O N N N N N N H «O« H OO« OON OO OH OH OH OH OH OH N NN« N HO« ONN NO me mm mm mm mm an 4 «He m One ONN Hm. NH NH NH NH NH NH O OOO « NHO «NN OO OH OH OH OH OH OH O O«O H OOO NNN O« O O O O O O N O«O H O«O OON O« H H H H H H N OO« N NO« OON N« « « OH OH .OH OH O« ON« «N OO« OON O« O O O O O O N OO« H OOO OON O« O O O O N N N OO« H OO« O«N «« O O O O O O NH NO« N OH« O«N O« O O O O OH OH «N «H« « ON« O«N N« N. N N N N N O «OO N HO« OON H« « « « « « « H NO« H OO« NON O« «H «H «H «H «H «H N NOO H Oo« «NN OO O O O O « « H OO« N «O« HNN OO O « O N H OGH>OO mmosmswmm smmmumxmz mmosmsvmm smmmumxmz uwnEsz .oz enemez Oo Hence HmeHueo Hmuoe smHnoum umbeoz Ommsoq Oo Hmheoz EOEHOHZ ncmHm OsHmmmm OsHmmmm oz .emseHueoo OH.« «Heme 150 N N N N O O N O«« H OO« OOO NN O O O O O O N N«« O O«« OOO ON H H H H H . H m can m Hem mam me O «H «H «H «H «H O ONO NH OOO OOO «N O O N N N N N OOO HH ONO HOO ON O O OH OH OH OH «O O«« HH OO« OOO NN NH NH NH NH NH OH «H OOO O Oo« «NO HN H H H H H H N OH« O OH« OOO ON O O O O O O O OO« « OO« OOO OO O O O O N N H ONO O NNO OOO OO O O O O O O H OH« H «N« OOO NO O O O O .O O O NH« O NH« O«O OO O O O O O O O NO« O NO« O«O OO « « « « « « O OO« N NO« HOO «O O O O O O O O O«« O O«« NNO OO O O O O O O O OOO N OOO ONO NO N N N N N N H HH« « OH« NNO HO O O O O O O OH OOO « «o« «HO OO O O O O «H «H N OOO N NO« OHO OO HO HO HO HO HO HO ON NO« « OHO OOO OO O « O N H OGH>OO mmocoswmm cmmmumxmz mmosmsvmm cmmmlmxmz HOQEOZ .Oz Esemez O0 Hmuoa HOEHOQO Hmuoa EOHQOHO HOhEsz OOOBQH O0 Hmnesz EseHst mcmHm OsHmmmm OsHmmmm Oz .emseHucoo OH.« «Heme 151 Hea one one mma «HHH me.HH N.m . NN.Ome mm.m aH.eee monumee OOO «NO NOO OOO ONOH «NOH OHO «O0.0« OHO ONO.H« Hmuoe O O O O O O « NO« H OO« OOO «O «N «N «N «N «N «N OH NO« H OO« OO« - OO «H «H «H «H ON ON OH NO« O OOO OO« NO. O O O O H H H OOO H «OO NN« HO O O O O H H N NOO H OOO OO« OO O O O O O O H OO« N H«« «O« OO O O O O O O O OO« O NN« OO« OO O O O O N N N NOO H «NO HO« NO NH NH NH NH .NH NH NH OOO N OO« O«« OO O O OH OH OH OH « NO« NH O«« O«« OO OH OH OH OH OH OH O NO« « NO« ««« «O O O O O O O O OO« H OH« OO« OO O O O O O O H OO« H HH« OO« NO O O O O « « N «H« H OH« ON« HO NH NH NH NH NH NH H NOO H «OO ON« OO O O O O N N H NN« N «N« NN« ON O O O O N N H OO« H OOO OH« ON O « O N H OGH>MO moosmswmm smmmnoxmz mmocmswmm cmmmlmxmz Hmnssz .Oz EOEHXOE O0 Hmuoe HOEHOQO Hmuoa EOHnOHm HOnEsz ummsoq O0 Hmaesz EOEHGHE OGMHO Oonmmm OGHmmmm oz .emseHueoo eH.e «Heme 152 5 job, 4 machine flow shop scheduling problem and are similar to earlier tables for 4 job, 4 machine flow shOp scheduling problems. From these tables it is easy to see the average savings in the total make-span by complete enumeration in Phase Two is 12.59 and 11.44 units per problem for the 91 and 94 problems of replications 1 and 2, respectively. Or for the total 91 + 94 = 185 problems the savings in total. make-spans in Phase Two averages 11.99 units per problem. For the rest of 1000 - 185 = 815 problems there is no savings in total make-spans. Thus, for these 1000 problems, the average savings in total make-Spans amounts to 11.99 * 185/1000 = 2.219 units per problem in Phase Two. The average minimum total make-span in Phase One was 427.85 units; thus the average minimum total make-span in Phase Two will be 427.85 - 2.219 = 425.63 units for the 1000 problems. The value of the measurement function of passing for the 5 job, 4 machine flow shop scheduling problem is: MTMS - TMSP _ 427.85 - 425.63 f4 = MT‘MS " 427.85 _ 2.219 _ _ 427785‘— .00519 or 0.519% The actual values of the measurement function obtained for 3, 4, and 5 job, 4 machine flow shop schedul- ing problems, will be discussed later in this chapter. 153 As previously stated, the tables presented for the Phase Two experiments provide the amount of savings obtained in the total make-Spans by complete enumeration and by the five search plans. Table 4.20 summarizes the relative savings in the total make-span and the amount Of search work involved in the complete enumerations and five plans. From Table 4.20, it seems the amount of search work involved in finding some improvement or savings in the total make-span reduces quickly, beginning at 100 percent for com- plete enumeration to 0.36 percent for Plan Three. But the amount of savings decreases very slowly starting from 100 percent for complete enumeration to 80.13 percent for Plan Three. Thus, the progressive increase in the usefulness of Plans One, Two and Three is established beyond doubt. Relatively speaking, Plan Four involves 87.3 percent as muCh work as Plan Three and provides 98.7 percent as much savings as that plan. Therefore, Plan Four seems advantageous in reducing the 12.7 percent of search work with.a consequent 1.3 percent reduction in savings as compared to Plan Three. Plan Five when compared to Plan Four does not appear attrac- tive. It amounts to 95.6 percent as much work as Plan Four, providing 98.57 percent as much savings as Plan Four. The reduction in the amount of work is 4.4 percent whereas the reduction in savings in the total make-span is 1.43 percent. Thus, although Plan Five seems adequate, it isn't as good as Plan Four. Only Plans One, Two, Three and Four for the 5 job, 4 machine flow shop scheduling problem will be used in Chapter V. 154 OH.O« O0.00 OO.«O OO.N «O.H OH.O Omsonmmm OGOHOOHOO O0 umhfisc On OOUH>HO mOQH>mm HMOOO O0 mane» oH OHOOH OmOOIOHOOOOm .O 0.0 H0.0 O0.0 «N.« N«.O OOH Osmonmm NO.N« OO.«« «O.HO OOO OONH OON«H EOHQOHO , HOO Omaoumwm OOOHOOHOO O0 Hmhesz .N HO.NN «0.0N OH.OO O0.00 H«.OO OOH ucOOHOm ONNH O«NH ONNH OONH OONN OHNN Hmuoa OOO «NO NOO OOO ONOH «NOH N :OHOOOHHQQM emm HNO ONO OOO mmHH meHH H eoHumoHHemm GH smmmnmxmz Hence we meH>mm .H O « O N H GOHOMHOEOGM OOOHQEOU msmHm ON.« OHQOB OGHmmmm AOHS OO>HO>GH xuoz noummm O0 unsoem on» use cmmmamxmz Hmuoe may sH mOGH>mO O0 OOSOEN 155 From Table 4.21, few facts emerge clearly. The total number of problems whose best total make-span in Phase Two is lower than the minimum total make-span of Phase One increases steadily from 105 for the 3 job shop to 130 for the 4 job shop and to 185 for the 5 job, 4 machine flow shop. The average number of passing solutions with a lower total make-span than the corresponding minimum total make-span, increases from 1.39 passing solutions per problem for the 3 job shop to 2.99 passing solutions for the 4 job and to 8.21 passing solutions for the 5 job, 4 machine flow shOp. The average savings in the total make-span per prob- lem decreases slightly from 12.72 units for the 3 job to 12.37 units for the 4 job and to 11.99 units for the 5 job, 4 machine flow shop. This slight decrease in average savings in the total make-span together with a fairly large increase in the number of problems with lower total make-span in Phase Two as compared to Phase One makes the average savings in the 1000 problems increase from 1.34 units per problem for the 3 job to 1.61 units for the 4 job and to 2.22 units for the 5 job, 4 machine flow shop. The value of the measurement function increases with the increase in the size of the flow shop. Table 4.21 also indicates the percent savings in total make-spans compared to complete enumeration in a particular plan decreases from 3 job to 5 job, 4 machine flow shops. For example, in Plan Three, the savings is 94.91 percent for the complete enumeration saving for the 156 Table 4.21 Results of Phases One and Two in Summary Form for 3 Job, 4 Job and 5 Job, 4 Machine Flow Shop Scheduling Problems 3 Job 4 Job 5 Job 10. Phase One Average minimum total make-span Average maximum total make-span Number of Optimal sequences per problem Phase Two Number of problems out of 1000, whose total make- span improved by permit- ting passing between sequences Average number of passing solutions per problem whose total make-spans were lower than the minimum total make-span of Phase One Average savings in the total make-span per problem for number of problems of row 4 Average savings in the total make-Span per problem for 1000 problems Average minimum total make-span in Phase Two for 1000 problems f4 in percent Percent Savings in Total Hake-spans COmpared to Complete Enumeration Complete enumeration ‘323.28 401.96 1.189 105 1.39 12.72 1.34 321.94 0.415 100 377.53 496.52 1.691 130 2.99 12.37 1.61 375.92 0.427 100 427.85 586.77 2.567 185 425.63 0.519 100 157 Table 4.21 continued. 3 Job 4 Job , 5 Job 11. Plan One 100 99.44 99.41 12. Plan Two 94.91 89.24 80.80 13. Plan Three 94.91 88.74 80.13 14. Plan Four --- 83.77 78.64 15. Plan Five --- 81.16 77.51 Number of PasSing Solutions Searched in Phase Two 16. Complete Enumeration 30 552 14280 17. Plan One 18 144 1200 18. Plan Two 11.89 77.79 605 19. Plan Three 7.13 20.29 51.34 20. Plan Four --- 18.53 44.80 21. Plan Five --- 16.78 42.82 Percent Amount of Search Work Compared to Complete Enumeration 22. Complete enumeration 100 100 100 23. Plan One 60 26.09 8.42 24. Plan Two 39.63 14.09 4.24 25. Plan Three 23.78 3.69 0.36 26. Plan Four --- 3.36 0.31 27. Plan Five --- 3.04 0.30 Benefit Cost Ratio in Terms 5f_TOtal Savings Divided by Number of Passing SolutiOns Searched in Phase Two 28. Complete enumeration 44.53 2.91 0.16 29. Plan One 74.25 11.10 1.84 30. Plan Two 106.78 18.45 2.96 31. Plan Three 177.59 70.35 34.60 32. Plan Four --- 72.60 38.95 33. Plan Five --- 77.75 40.15 158 3 job, but is only 88.74 percent in the 5 job, 4 machine flow shop. The reason for this is that the percent of search work done as compared to complete enumeration, decreases significantly from the 3 job to 5 job, 4 machine flow shop. For example, for Plan Three, 23.78 percent of the complete enumeration solutions are examined for the 3 job shop, but only 3.69 percent solutions are examined for the 4 job and just 0.36 percent passing solutions are examined in the 5 job, 4 machine flow shop. Rows 28-33 in Table 4.21 provides values for the benefit-cost ratio. Since benefit and cost are in different measurement units, a value Of the ratio by itself does not provide significant information, but when one value of the ratio is compared with another value, the comparison can provide useful information. It is clear from the table that the values of the benefit-cost ratio for all three sizes of the flow shop, increases with the increase in plan numbers. These increases indicate Plan Three for the 3 job, 4 machine flow shop and Plan Five for 4, and 5 Job, 4 machine flow shops are most efficient as far as the benefit-cost ratio is concerned. For the complete enumeration and all five plans, the value of the benefit-cost ratio decreases with the increase in flow shop sizes. This signifies that for the same amount of savings in the total make-span, increasing amount of search work is necessary with any increase in the size of the flow shOp. 159 Concluding from all presentations discussions and analysis of results in this chapter, removing the no passing restriction is quite useful. Although with passing permitted between sequences, the number of solutions to be examined increases tremendously, the benefit of a lowered total make-span could make the extra search work worthwhile. The results presented in this chapter establish the viability of using partial search plans rather than complete enumera- tion. These various plans, particularly Plan Three, permit more than 80 percent of the benefit of the removal of the no passing restriction to be achieved at a relatively small fraction of the search work of the complete enumeration. CHAPTER V RESULTS OF ANALYSES WITH BETA DISTRIBUTED PROCESSING TIMES The results presented in Chapter IV establish the phenomena of the lower total make-span with the removal Of the no passing restriction. All the results in Chapter IV were obtained from solving flow shop scheduling problems whose processing times were generated using uniform proba- bility distributions between 0 and 100. In this chapter the results are obtained from solving flow shOp scheduling problems whose processing times are generated by using Beta probability distributions. As discussed in Chapter III, Beta probability distribution is quite flexible with an entirely different shape of the density function curve for different values of its parameters A and B. For the experi- :ments of Chapter V, different shapes of probability density functions are obtained by choosing five sets of A and B ‘values equal to 0.5, 1.5, 2.0, 2.5’and 3.0 for each of the 3 job, 4 machines; 4 job, 4 machines and the 5 job, 4 machines flow shop sizes. Two replications of 500 problems 160 161 for each of the five sets of A and B values are generated. In other words, for each of the three sizes of flow shOps, enough random numbers are generated for a total of 5000 problems for the experiments. When the values of A and B are equal to 1.0, the Beta probability distribution is the same as the uniform probability distribution, which is already covered by the experiments whose results are reported in Chapter IV. For purposes of comparison and filling the gap between the values of A and B from 0.5 to 1.5, some of the results of Chapter IV will be used again in this chapter. Explanation of Terms Following is a list of shortened terms which will be used in place of the longer names in this chapter: A_§ refers to the Beta distribution parameters A and B. (Throughout the experiments, parameters A and B have equal values.) Tamin is the mean minimum total make-Span value of Phase One averaged from all the problems of replications 1 and 2. I Tgmax is the mean maximum total make-span value of Phase One, averaged from all the problems of replications l and 2. Trange is Tamax-Tamin = mean value of the difference .between.the maximum and minimum total make-span of Phase 162 One, averaged over the total problems of replications 1 and 2. ng is the total number of problems in both repli- cations for which the lowest total make-span in Phase Two was found to be lower than the minimum total make-span of Phase One. 23295 is the mean value of the number of optimal sequences per problem in Phase One averaged from all the problems of replications 1 and 2. MTMS is the minimum total make-span under no passing. TMSP is the lowest (best) total make-span under passing. 3 Job, 4 Machine Flow Shop Scheduling Problems In the following pages, three tables of results Obtained during experiments on 3 job, 4 machine flow shop scheduling problems are presented. Table 5.1 provides results of Phase One experiments. For each of the six sets of A and B values, it provides the results obtained in replications l and 2, the total of the two replications. Each replication has 500 problems; Table 5.1 also shows the value of the average minimum total make-span, the average maximum total make-span, the range between the average maximum and the minimum total make-span, and the average number of optimal sequences per problem, averaged over the 163 Table 5.1 Results of Phase One Experiments of 3 Job, 4 Machine Flow Shop Scheduling Problems Average Number of Average Average Optimal Minimum Maximum Sequences A and B Repli- Total Total Per- Values cation Make-span Make-span Range Problem 1 330.75 424.86 94.11 1.162 0.5 2 328.50 424.83 96.32 1.200 Total 329.63 424.84 95.21 1.186 1 321.23 400.72 79.49 1.178 1.0 2 325.34 403.21 77.87 1.200 Total 323.28 401.96 78.68 1.189 1 322.41 389.66 67.24 1.166 1.5 2 319.28 385.93 66.64 1.222 Total 320.84 387.79 66.94 1.194 1 315.64 377.14 61.50 1.182 2.0 2 319.66 380.60 60.95 1.208 Total 317.65 378.87 61.22 1.195 1 315.02 371.15 56.13 1.192 2.5 2 317.24 372.58 55.35 1.220 Total 316.13 371.87 55.74 1.201 1 315.04 365.72 50.68 1.220 3.0 2 318.37 368.14 49.78 1.226 Total 316.70 366.93 50.23 1.223 500 problems. The values in the row designated "Total" are averaged from 1000 problems of replications l and 2. As A and B (which will be called AB from now on) values increase from 0.5 to 3.0, the minimum total make- span values average from the total of replications l and 2 (which will be called Tamin from now on), decrease slowly from 329.63 to 316.70. The decrease in Tamin is small and 164 not continuous because as AB increases from 2.5 to 3.0, there is a slight increase in its value. On the other hand, the value of the maximum total make-span averaged over the total of replications 1 and 2 (Tamax) decreases fairly steadily. As a consequence, there is a larger decrease in Tamax and a smaller decrease in Tamin. The range of the total of replications 1 and 2 between Tamix and Tamix (Trange) decreases quite substantially, from 95.21 to 50.53 as AB values increase from 0.5 to 3.0. On the basis of Trange equal to 100, for AB equal to 0.5, other Trange values for AB at 1.0, 1.5, 2.0, 2.5 and 3.0, are 82.6, 70.3, 64.2, 58.5 and 52.8, respectively. The value of Trange indicates amount of difference between the best and worst values of the total make-span. So as the value of Trange decreases with an increase in the value of AB, the discrimination between the best and worst total make-spans becomes less and less. The value of the average number of optimal sequences per problem for the total of replications 1 and 2 (Tanos) increases with the increase in AB's value. As AB increases from 0.5 to 3.0, Tanos increases from 1.186 to 1.223, a total increase of 3.5 percent. Table 5.2 summarizes results of Phase Two experi- ments on 3 job, 4 machine flow shop scheduling problems. For each replication and for the total of both replications for each value of AB, the table provides the number of problems (Nop) for which the best total make-span in Phase Two was found to be lower than the minimum total make-span 165 of Phase One. The table also shows the total savings in the total make-span for all Nop. The total savings for all Nop obtained and presented in Table 5.2 are by the complete enumeration process and by the partial search Plans One, Two and Three. The most significant fact that emerges from Table 5.2 is that with the increase in AB values, the decrease in the Nop is quite substantial. As AB values increase from 0.5 to 3.0, the values of the Nop decreases from 141 to 23, amounting to 83.7 percent decrease. Another obser- vation that can be made from the table is that the value of the total savings obtained by the complete enumeration search, decreases steadily with the increase in the value of AB. As AB values increase from 0.5 to 3.0, the total savings obtained by complete enumeration decreases from 2291 to 166 time units. On the basis of 100 units of total savings for AB equal to 0.5, the total savings value decreases to 7.25 time units for AB equal to 3.0. The amount of savings by the three partial search Plans One, Two and Three for the different values of AB are almost as much as the savings by the complete enumeration search. The total savings by Plan One is almost 100 percent for all the values of AB, and the total savings by Plans Two and Three varies from 90.57 to 98.11 percent. For the six values of AB, overall savings by Plans One, Two and Three are 99.92, 95.19, and 95.19 percent of the savings by complete enumeration. 166 nh.mm hh.~m oo.OOH oo.o0H mmmucmonmm va me mmH mmH mm Hmuoe o.m hm hm hm hm HH N no be mm mm NH H hm.om hm.om oo.o0H oo.QOH mmmpcmoumm ovm ovm mmm mmm mm Hmuoa m.m th mbH omH omH om N Hm Hm mm mm m H HH.mm HH.mm oo.00H oo.ooH mmmucmouom mmm mmm vmm «mm Hm Hmuoe o.m va wwH an th mH N mHH mHH hHH SHH mH H vm.mm vm.~m oo.OOH oo.o0H mmmucmoumm mmv NN« bmv nmv av Hmuoe m.H hmH hmH va va «N N mmm mmm mmm mmm mm H Hm.vm Hm.vm oo.OOH oo.OOH ommucmoumm mmmH mmNH mmMH mmMH mOH Hmuoa o.H mew mew Hen an mm m mmm mmm mmm mmm mm H mm.mm mm.wm mm.mm oo.ooH mmmucmoumm momm momm hmmm Hmmm HvH Hmuoe m.o m>0H mnOH MOHH mOHH on m mNHH mmHH vaH mmHH mm H m N H GOHumumEdcm mEmHQoum GOHpmoHHmmm mmsHm> mumHmEoo mo m can 4 cmHm an mmcw>mm Hmuos Monasz mEmHQoum mcHHspmsom moam 30Hm mcflaomz w .Qon m mo mucwEHHmmxm 039 mmmnm mo wuHsmmm N.m OHQMB 167 Table 5.3 presents the average minimum total make- span under no passing and passing. Using these two values, the values of the measurement function f4 is computed and shown in that table. As the value of AB goes up, the value of f4 decreases. The decrease in f4 values as AB increases from 0.5 to 3.0, amounts to approximately 92.5 percent. 4 Job, 4 Machine Flow Shop Scheduling Problems In the following pages, three tables of results obtained during experiments on 4 job, 4 machine scheduling problems are presented. These tables are similar to the ones presented earlier for 3 job, 4 machine flow shop scheduling problems. In Table 5.4, the values of Tamin, Tamax, Trange, and Tanos are given for the six values of AB. The Tamin values decrease very slowly and unsteadily as the values of AB increase. The total amount of decrease in Tamin is only 3.5 percent. On the other hand, Tamax values decrease fairly steadily as AB values increase. As a result of large and steady decreases in Tamax, and small, unsteady decreases in Tamin, Trange decreases substantially from 142.95 to 75.63, as AB values increase from 0.5 to 3.0. On the basis of Trange equal to 100, for AB equal to 0.5, other Trange values for AB equal to 1.0, 1.5, 2.0, 2.5 and 3.0, are 83.4, 71.0, 64.0, 58.2 and 53.0, reapec- tively. These numbers obtained for 4 job, 4 machine 168 Nmo.o NH.o mm.mHm o>.mHm Hmuoa mmo.o rH.o ON.mHm hm.mHm N o.m Hmo.o mH.o mm.va vo.mHm H mmo.o NN.o om.mHm MH.mHm Hmuoa NHH.o mm.o mm.mHm «N.NHm N m.N mvo.o mH.o hm.va No.mHm H Nmo.o mN.o mm.hHm mm.NHm Hmuoe Hmo.o mN.o hm.mHm mm.mHm N o.N mho.o MN.o Hv.mHm «m.mHm H mvH.o m¢.o mm.0Nm vm.0Nm Hmuoe mHH.o mm.o om.mHm mN.mHm N m.H qu.o mm.o mm.HNm H«.NNm H mH¢.o vm.H vm.HNm mN.MNm Hmuoe mmv.o mv.H mm.MNm vm.mNm N o.H onm.o mH.H v0.0Nm mN.HNm H mmm.o mN.N «N.NNm mm.mNm Hmuoe mnm.o HN.N mN.mNm om.mNm N m.o oNh.o mm.N hm.mNm mn.omm H A mzaz v Ammzaumzezv Ammzev Amzszv cOHuMOHHmmm mmsHm> mmSBImSBE mcflmmmm mafimmmm OZ m can 4 usmoumm goons Hopes cH em cmmmlmxmz cmmmlmxmz Hmuoa Hmuoa ESEHcHz ESEHGHS mmmnm>¢ mmmnm>¢ «carom: s mEmHnoum mcHHapmnom monm 30Hm .non m How cm cowuocsm ucmfimusmmmz may no msHm> m.m OHQMB 169 Table 5.4 Results of Phase One Experiments of 4 Job, 4 Machine Flow Shop Scheduling Problems Average Number of Average Average Optimal Minimum Maximum Sequences A and B Repli- Total Total Per Values cation Make-span Make-span Range Problem 1 381.44 523.43 141.99 1.732 0.5 2 381.42 525.33 143.91 1.650 Total 381.43 524.38 142.95 1.691 1 377.14 494.91 117.77 1.708 1.0 2 377.92 498.14 120.22 1.674 Total 377.53 496.52 118.99 1.691 1 372.73 474.64 101.91 1.746 1.5 2 372.64 473.20 100.56 1.738 Total 372.68 473.92 101.24 1.742 1 368.52 460.31 91.80 1L664 2.0 2 370.73 461.69 90.96 1.654 Total 369.62 461.00 91.38 1.659 1 367.75 449.66 81.91 1.750 2.5 2 367.40 451.48 84.08 1.760 Total 367.57 450.57 83.00 1.755 1 368.63 443.69 75.06 1.880 3.0 2 367.09 443.30 76.21 1.714 Total 367.86 443.49 75.63 1.797 problems are quite similar to the 3 job, 4 machine problems reported earlier. Thus, the discrimination between the best and the worst total make—spans decreases substantially as AB values increase. The values of Tanos shown in Table 5.4 for 4 job, 4 machine problems, do not follow any parti- cular pattern, but instead fluctuate a great deal. The only observation that can be drawn from the Tanos values 170 is that on an average, Tanos for 4 job, 4 machine problems are 44.0 percent higher than the Tanos for 3 job, 4 machine problems. Table 5.5 provides values of Nop and the values of total savings for all N0ps by complete enumeration and by search Plans One, Two and Three. As experienced previously, Nop values decrease substantially from 186 to just 28, as values of AB go from 0.5 to 3.0. On the basis of Nop equal to 100 for AB equal to 0.5, 15.1 Nop are obtained for AB equal to 3.0. The values of the total savings for all Nop by complete enumeration decrease even faster than the decrease in the Nop. The total savings values drop from 3192 time units to 252 time units, obtained by complete enumeration as AB increases from 0.5 to 3.0. The drOp in the total savings value amounts to a 92.1 percent. The amount of savings by partial search plans are almost as much as the savings by complete enumeration. For Plan One, savings vary from 99.30 to 100 percent of the complete enumeration savings, whereas savings by Plans Two and Three vary anywhere from 85.25 to 92.06 percent of the complete enumeration savings. Overall savings by Plans One, Two and Three are 99.53, 89.40, and 89.07 percent of the savings by complete enumeration. Table 5.6 shows the average minimum total make-span under no passing and passing, as well as using these two values to provide the values of the measurement function f4. With an increase in AB values, f4 values decrease 171 mo.~m oo.~m oo.ooH oo.ooH mmmucmoumm NmN NmN NmN NmN mN Hmuoa o.m Hm Hm ooH ooH HH N HHH HHH mmH NmH 5H H mm.mm mm.mm oo.ooH oo.oOH mmmucmoumm 5mm 5mm mum mum on Hmuoa m.~ an NHH hmH hmH «H m . OOH oOH HHH HHH mH H wh.Hm hh.Hm oo.ooH oo.o0H mmmhcmoumm mHm mHm mmm mmm mp Hmuoe o.m mmm mmm «mm 4mm ow m Ham Ham «Hm va mm H Hn.mm ~4.mm om.mm oo.OOH mmmuamonwm mmh mmn mam qmm mm Hmuoe m.H «mm «mm mow mow Hv m ohm mum mmv mvv Ne H «a.mm H~.mm «a.mm oo.o0H momnqmonmm NN«H mmHH mmmH momH omH Hmuoe o.H own mm» man has mm m son now Hmm Hmm mm H mm.mm «a.mm hv.mm oo.ooH mmmucmoumm mmmm Hsmm mNHm mmHm mmH Hmuoa m.o mNmH smmH mmmH mooH mm m 4mmH «mmH ommH hmmH mm H m N H. GOHHMHTEHHGN mEmHQOHm GOHUMUHHQmm mmDHM> mumHmEoU no m can d GMHm an mmcH>mm Hmuos M09852 wEmHQOHm mcHHspwnom monm onm OGHsomE v .306 v «o mucmEHHmmxm 039 mmmcm mo m.m OHQMB manmmm 172 mmo.o mN.o Hm.>mm mm.bmm Hmuoa vmo.o oN.o mm.mmm no.5wm N o.m Hmo.o om.o mm.mmm mm.mmm H mho.o mN.o mN.nmm hm.hmm Hmuoa mho.o NN.o MH.bmm ov.hmm N m.Nh who.o mN.o hv.hwm mb.bmm H HmH.o no.0 mm.wmm Nw.mmm Hmuos NmH.o Hn.o No.obm mw.onm N o.N HNH.o no.0 mm.hmm Nm.mmm H mNN.o mm.o mm.Hhm mm.th Hmuoa ONN.o Nm.o Nm.Hbm vm.th N m.H mm~.o mm.o vm.Hbm mh.me H va.o Hm.H Nm.mnm mm.hnm Hmuoa mHv.o hm.H mm.mhm Nm.hmm N o.H mmv.o «o.H om.m>m vH.n>m H mmm.o mH.m vN.mnm mv.Hmm Hmuoe mnm.o mm.m mo.mnm N¢.Hmm N m.o Nom.o mo.m mm.m>m «v.Hmm H A mzez v Ammzalmzezv Ammzsv Amzazv QOHHMUHHQOM mosHm> mmzanmzsz 9:33 @533 oz m can « usmoumm Hops: Hmpco CH «m cmmmnoxmz commumxmz Hmuoe Hmuoa EDEHGHS EdEHcHS mmmum>m mmmum>m mEmHnoum mcHH5©m£om monm 30Hm m.m magma mcHnomz v .nob c How um GOHuonsm unmEOHSmmmz may «0 03Hm> 173 steadily. The amount of decrease in f4 values is 91.9 percent as AB values increase from 0.5 to 3.0. 5 Job,_4 Machine Flow Shop Scheduling Problems In the following pages, three tables of results obtained during experiments on 5 job, 4 machine flow shop scheduling problems are presented. These tables are similar to the tables presented earlier for 3 and 4 job, 4 machine problems. Table 5.7 provides Tamin, Tamax, Trange and Tanos values. As AB values increase, the values of Tamin, Trange, and Tamax decrease. The decrease in Tamin is small amounting to only 2.88 percent, whereas the decrease in Tamax is a little larger, resulting in 16.45 percent as AB values increase from 0.5 to 3.0. Since the Trange values are the difference of the Tamax and Tamin values, and since the decrease in Tamax is greater than the Tamin, Trange values decrease steadily as AB values go from 0.5 to 3.0. The total decrease in Trange is from 191.80 to 102.07 units, amounting to a 46.75 percent decrease. It indicates the discrimination between the best and the worst total make-span for AB equal to 3.0 is half as much as the discrimination for AB equal to 0.5. As can be seen from the tables, Tanos does not follow any particular pattern of change. Overall, it seems that the Tanos values of 5 job, 4 machine problems are 65 percent greater than the Tanos values of the 4 job, 4 machine problems and are 137 percent 174 Table 5.7 Results of Phase One Experiments of 5 Job, 4 Machine Flow Shop Scheduling Problems Average Number of Average Average Optimal Minimum Maximum Sequences A and B Repli- Total Total Per Values cation Make—span Make—span Range Problem 1 431.02 622.53 191.51 2.820 0.5 2 427.33 619.41 192.08 2.680 Total ‘429.17 620.97 191.80 2.750 1 426.73 587.71 160.98 2.590 1.0 2 428.97 585.83 156.86 2.544 Total 427.85 586.77 158.92 2.567 1 427.66 563.80 136.14 3.030 1.5 2 420.92 556.62 135.70 2.858 Total 424.29 556.62 135.92 2.944 1 422.22 544.68 122.46 2.880 2.0 2 423.28 544.51 121.23 3.278 Total 422.75 544.59 121.84 3.079 1 416.49 526.89 110.39 2.932 2.5 2 418.79 529.07 110.28 2.796 Total 417.64 527.98 110.34 2.864 1 416.78 520.45 103.67 2.786 3.0 2 416.84 517.31 100.47 2.882 Total 416.81 518.88 102.07 2.834 greater than the Tanos values of the 3 job, 4 machine problems. Table 5.8 provides the Nop and the total savings for all Nop by complete enumeration search and by the search of Plans One, Two, Three and Four. As experienced before, Nop values drop tremendously,from 237 to 45, amount- ing to a net 81 percent decrease as AB values increase from 175 mm.Nm mm.Nm mm.Nm oo.00H oo.oOH mmmuswoumm mHN mHN mHN qu va mv Hmuos o.m NHH NvH NHH mmH mmH mN N on mp on moH @0H NH H «a.mm vv.mm m¢.mm No.vm oo.oOH mmmucmoumm mmN mmN Nom mov mmv vm Hmuoa m.N omH omH mvH «NH OON Hm N mmH mmH mmH mmN mmN mm H mm.mh mm.bh mm.hn om.mm oo.o0H mmmusmoumm omm Hmm Hmm was man on Hmuoe o.N NmN mmN mmN Hmm Nmm He N mmN mmN mmN mmm mmm mm H NN.NN Nm.¢m mH.hm om.>m oo.ooH mmmucmonmm mmm vaH HmoH mONH ovNH mNH Hmuoa m.H mmv NHm mvm mmm mHm mm N mmv mmm mmm HNm HNm mm H Hm.Nh em.mh om.om Hv.mm oo.oOH ommuswoumm mehH NNNH mth mONN mHNN mmH Hobos o.H ohm Nom mom mnoH HNOH em N Hum mum mwm mmHH mvHH Hm H oo.ms ms.vs ov.ms om.mm oo.o0H ammunmoumm NmmN mNbN mvhN vmmm memm NmN Hmuoa m.o mmmH NN«H vaH nva ommH ONH N thH mQMH mNmH hmmH mmmH NHH H v m N H GOHumnmEscm wEmHnoum soHumoHHmmm mmsHm> mumHmEou mo m can 4 sMHm an mmcH>mm Hmuos Honssz mEmHnoum mcHHSposow mozm son msHsomz v .non m mo muswEHummxm 038 chasm mo muHsmmm m.m mHan. 176 0.5 to 3.0. The amount of savings by the search plans are not as high as compared to the complete enumeration search as they were for the 3 and 4 job, 4 machine flow shop scheduling problems. Overall, the savings of Plans One, Two, Three and Four amounts to 99.0, 78.6, 77.5, and 75.3 percent of the savings by complete enumeration. Table 5.9 provides the average minimum total make- span under both no passing and passing. Using these two values, the value of the measurement function f4 is computed and shown in the table. The value of the measurement func- tion f4 drops steadily as the values of AB increase. The decrease in f4 values amounts to 92.7 percent as AB values go from 0.5 to 3.0. Summary Table 5.10 shows a number of problems for which permitting passing between sequences improved the minimum total make-span of Phase One in Phase Two for the values of AB equal to 0.5 to 3.0 and for the flow shop sizes of 3 to 5 job, 4 machine. The number of problems given in each category are from a total of 1000 problems. It is obvious from the table that the number of problems increases with the increase in the number of jobs in the flow shop and also with the decrease in AB values. For example, in the case of the 3 job, 4 machine flow shop and for the AB value of 3.0, only 2.3 percent of the problems have a lower total make-span in Phase Two than Phase One whereas 23.7 177 mmo.o mm.o mm.oH¢ Hm.mHe Hmuoa sso.o ~m.o ~m.qu «a.mHH m o.m mmo.o -.o mm.qu ms.mHv H mOH.o mv.o HN.>HH Hm.sH¢ Hmuos mmo.o ov.o mm.mH< as.mH¢ m m.~ mHH.o ne.o No.mHe m¢.mHv H 55H.o ms.o oo.-e mh.m~v Hmuoa osH.o ms.o mm.-e m~.m~v m o.~ NmH.o us.o mv.H~q -.N~¢ H ~m~.o HN.H mo.m~v m~.vmq Hmuoa mm~.o ¢~.H mm.qu ~m.omv N m.H om~.o v~.H «a.mmq om.sma H mHm.o NN.N mm.m~v mm.s~¢ Hmuos Hom.o mH.m «a.mmv sm.m~¢ m o.H smm.o m~.~ va.v~q mn.o~q H omm.o mm.m mm.m~q 5H.m~¢ Hmuoa sHm.o mm.m Hv.m~v mm.s~e m m.o ems.o mm.m em.s~¢ «o.HmH H may: V Ammzsnmzazv Ammzsv Amzazv noHumUHHmmm mmsHm> Ammzanmzaz mchmmm mchmmm oz m can a Uflwoumm HQUGD HGUGD sH em commumxmz commumxmz Hmuoa Hmuoe ESEHGHZ EdEHcHz mmmuo>< mmmnm>< mEmHQonm mcHHapmnom QOSm onm mcHnomz v .non m How on GOHuosdm newsmusmmmz mo OSHM> m.m OHQMB 178 Table 5.10 Number of Problems Where Passing Improved the Total Make-span (Nop) Size of the Flow Shop A and B 3 Job, 4 Job, 5 Job Values 4 Machine 4 Machine 4 Machine 0.5 141 186 237 1.0 105 130 185 1.5 49 83 126 2.0 31 72 79 2.5 29 30 64 3.0 23 28 45 percent of the problems have lower total make-spans in Phase Two compared to Phase One for the 5 job, 4 machine flow shop and AB value of 0.5. Figure 5.1 pictorially shows the effect of the increases in AB values and the effect of increases in the size of the flow shop on the number of problems in which the lowest total make-span of Phase Two was lower than the minimum total make-span of Phase One. The increase in the number of problems with the increase in the size of the flow shop for AB values equal to 0.5, 1.0, and 1.5 is phenomenal. Table 5.11 presents values of the measurement func- tion £4 for 3, 4 and 5 job, 4 machine flow shop scheduling problems and for the AB values of 0.5 to 3.0. The values 179 Number of Problems where Passing Improved the Total Make-Span (Nop) 210‘ [a 'E .i‘.’ _Q 180 o H m m o g 150 z 120 90 60' 30 o \ 3 JOb' 4 JOb, 5 JObI. 4 Machine 4 Machine 4 Machine Size of the Flow Shop Scheduling Problems "*~*+ Figure 5.1 Number of Problems where Passing Improved the Total Make-Span (Nop). 180 Table 5.11 Value of the Measurement Function f4 in Percent Size of the Flow Shop A and B 3 Job, 4 Job, 5 Job, Values 4 Machine 4 Machine 4 Machine 0.5 0.695 0.836 0.850 1.0 0.415 0.426 0.519 1.5 0.143 0.228 0.292 2.0 0.082 0.181 0.171 2.5 0.085 0.075 0.103 3.0 0.052 0.068 0.062 of f4 as given in the table varies from 0.052 to 0.850' percent. The f4 values for each of the three flow shop sizes, except in one instance, decrease with the increase in AB values. Thus it can be safely assumed that the values of f4 will decrease with the increase in AB values for a given size of flow shop scheduling problems. In a similar way, for a given AB value, as the size of the flow shop scheduling problem increases, the value of the measurement function f4 increases, except in a few instances. Figure 5.2 shows pictorially the behavior of the measurement function with the increase in the size of the flow shop and with the increase in AB values. From Table 5.11 and from Figure 5.2, it can be said that in general the value of f4 increases with.both the increase in f4 in percent 181 0.9‘ 0.8‘ A=B=005 0.7J 0.6H 0.5-1 0.44 1-0 0.34 0.2-4 1-5 2.0 0.1‘ / —~i._Z—'—5 A x—fi 3.0 O I I l J 3 Job, 4 Job, 5 Job, 4 Machine 4 Machine 4 Machine Size of the Flow Shop Scheduling Problems -—-§ Figure 5.2 Value of the Measurement Function f4. 182 the number of jobs in the flow shop and with the decrease in the values of AB. CHAPTER VI SUMMARY OF FINDINGS AND RECOMMENDATIONS FOR FURTHER.RESEARCH Findings and Conclusions The main purpose of this dissertation was to study and analyze the effects of permitting passing between sequences of solutions to flow shop scheduling problems. The various results presented in Chapters IV and V proved beyond a doubt that, in a large number of problems, per- mitting passing improves the minimum total make-span obtained with no passing. Thus, if global optimization of a flow shop scheduling problem is desired, it is necessary that complete enumeration of all possible solutions with passing between sequences be considered. The complete enumeration of all no passing and passing solutions for even a small size flow shOp scheduling problem involVes a great deal of effort. So if global optimization in a particular situation is not necessary, then some heuristic, if available, can provide fairly good solutions to flow shop scheduling problems with much less computational efforts. 183 184 Until now not even a single heuristic was available to reduce the minimum total make-span beyond the no passing stage for flow shop scheduling problems where passing was permitted. This dissertation provides three heuristics or plans, each of which can provide solutions which are very close to global optimum solutions With only a small fraction of effort required as compared to that required by complete enumeration. Plans Three, Two, and One gradually require more and more computational efforts to obtain progressively closer approximations to the global optimum solutions to flow shop scheduling problems. For example, for the one thousand of 5 job, 4 machine flow shop scheduling problems, Plans Three, Two and One provided 80.13, 80.80, and 99.41 percent of the possible reduction of the total make—span between the local optimum of no passing and global optimum of passing with 0.36, 4.24, and 8.42 percent computational efforts compared to 100 percent reduction and 100 percent computational efforts by complete enumeration. These three plans can be used only if all or most of the optimal solu- tions under the no passing restriction are available. To obtain all optimal solutions under no passing, two approaches have been suggested in this dissertation. One is the complete enumeration of all the no passing solutions; the other is by a modified version of Ignall and Schrage's branch and bound technique. A user who is look- ing for a heuristic will find three choices in this 185 dissertation, and he can make his choice on the basis of the availability of computational efforts and his needs. Although these three plans are specifically tailored for the smaller flow shop scheduling problems with exactly four machines, they are simple enough so that any user can modify them to make them applicable to larger sizes of flow shOp scheduling problems. The results in Chapter IV illustrate that if the processing times are uniformly generated, then 10.5, 13.0, and 18.5 percent of the 3 job, 4 machine; 4 job, 4 machine; and 5 job, 4 machine flow shop scheduling problems have a lower value of total make-span with passing compared to the minimum total make-spans obtained with no passing. It is easy to see that as the number of jobs in the flow shop scheduling problem increase, the number of problems for which permitting passing lowered the total make-span, also increased. Results presented in Chapter V also support this contention. In fact, in observing the results of Chapter V, it seems that the number of problems for which passing was permitted lowered the minimum total make-span increase on an average of 49.1 percent as the size of the flow shop scheduling problem increases by one job. Such a large increase may or may not continue as the number of jobs in the flow shop increases beyond five. But if it does, it is conceivable that for a relatively large size problem such as a 10 job, 4 machine problem, in each instance 186 passing can provide a lower total make-span compared to the minimum total make—span with no passing. It was discovered through experimentation that the m amount of reduction in the total make-span by permitting passing was relatively small. For example, the expected reduction in the minimum total make-span of no passing, by permitting passing for 3 job, 4 machine, 4 job, 4 machine, and 5 job, 4 machine flow shop scheduling problems, was only 0.415, 0.426, and 0.519 percent, respectively, when the processing times were generated from uniform dis- tribution. These values are comparable to the expected reduction in total make-span obtained by Krone (25), which was 0.66 percent by using the heuristic technique on the 8 job, 5 machine flow shop scheduling problems with the minimization of mean completion time as the performance measure. Although the expected reduction in the total make- span by permitting passing is small, it increases by 21.5 percent with every increase of one job in the flow shop. In the last twenty years of work, almost all researchers have used processing times either chosen arbi- trarily or generated from the uniform probability distribu- tion for their research on flow shop scheduling problems. In this research, besides a uniform probability distribu- tion, beta probability distributions were also used for generating processing times. The beta distribution has two parameters, A and B. For this dissertation, five sets of A and B values were chosen and corresponding probability 187 distribution functions were used to generate five sets of processing times. For each set of processing times, passing and no passing studies were made and reported in Chapter V. These results clearly indicated that as the values of A and B increased, the number of problems for which permitting passing reduced the minimum total make-span of no passing, decreased significantly for each of the three different sizes of flow shops. The expected reduction in the minimum total make-span of no passing by permitting passing decreased even faster as the A and B values increased. For example, for 5 job, 4 machine scheduling problems, the expected value of the reduction in the minimum total make-span of no pass- ing was 0.850 percent when A and B were equal to 0.5, but was only 0.062 percent when A and B were each 3.0. During this investigation it was found that under no passing the range between the maximum and minimum total make-spans was quite narrow. When the processing times were generated from the uniform probability distribution, on an average the range was only 24, 31, and 37 percent of the minimum total make-span for 3 job, 4 job, and 5 job, 4 machine flow shop scheduling problems. Also, as values of A.and B increased in the beta probability distribution, ‘values of the range decreased significantly. For example, ‘when A and B were equal to 3.0, the ranges were only 16, 20, and 24 percent of the minimum total make-span for 3 job, 4 job, and 5 job, 4 machine flow shop scheduling problems. 188 Many researchers have presented heuristics for flow shop scheduling problems under no passing. Few of them have led us to believe that their heuristics are totally reliable, because they provide solutions whose total make- spans are "only" 5 to 15 percent away from the minimum total make-span. In the absence of any knowledge about the range between the maximum total make-span (worst solu- tion) and the minimum total make-span (best solution), their claim might seem justifiable, but if the value of the range is known and if it is narrow compared to the minimum total make-span, then the claim of "good heuristics" can be discounted. Suggestions for Further.Research The most important and useful research in the area of flow shop scheduling at this time would be the develop- ment of the branch and bound technique to obtain global optimum solutions under passing. Since the branch and bound technique for no passing is available, the task of modifying it for passing seems possible. After Spending a great deal of time and effort working with passing in flow shop scheduling problems, the author of this dissertation was convinced that the task of modifying the branch and bound techniques is feasible but will require a lot of effort and analysis by other researchers. Other research that could be quite useful is an extension of the studies and analysis done herein to flow 189 shop scheduling problems with more than four machines. With N job, 4 machine flow shop scheduling problems and minimization of the total make-span as the performance criterion, passing need be considered only between job sequences of the second and third machines. But with M machines in the flow shop where M is more than four, M-3 instances of passing should be considered to obtain a global optimum solution. Various plans (heuristics) pre-. sented here could be modified through further experimentation. The biggest disadvantage of HuaprOposed extension is that for any job larger than a 5 job, 4 machine flow shop sched- uling problem, tremendously large computational efforts would be required. When a complete enumeration of six ' thousand 5 job, 4 machine flow shop scheduling problems with passing permitted was done for this dissertation, more than 72,000 seconds of computational time were needed on an IBM 360/75 computer. By the same token, one problem of 5 job, 5 machine flow shop size with passing permitted would require 1,440 seconds of computer time to do a com- plete enumeration. Unless a much larger computer with plenty of computation time is available, a study involving complete enumeration to obtain globally Optimum solutions is not feasible. Examination of the applicability of the various plans presented in this dissertation for N job, 4 machine flow shop scheduling problems where N > 5 could also be an interesting idea for further research. These plans were 190 quite successful for small flow shOp scheduling problems. Whether they are equally useful for larger (N > 5) flow shop scheduling problems or whether some modifications are required could be explored in future research. Throughout the study and analysis of permitting passing in flow shop scheduling problems, it was assumed that all the optimum solutions a problem has under no passing can be easily obtained; and in this study, were obtained. It would be interesting to develop heuristics and analyze their performance when only one or a few optimum solutions per problem were obtained. Techniques required for obtaining only one optimum solution under no passing per problem will demand less computational effort than techniques providing all the Optimum solutions a problem has under no passing. It would be beneficial to determine whether the initial savings in computational effort by obtaining only one optimum solution under no passing per problem is worthwhile. The list of possible topics for further research is almost endless. Besides the above mentioned tOpics, there are many unanswered questions in the flow shop scheduling field under no passing which could be researched. It is the hope of the author that this dissertation will generate more interest in the flow shop scheduling area and that more people will take it upon themselves to find answers to the remaining questions in this field. BIBLIOGRAPHY 10. BIBLIOGRAPHY Akers, S. B. and Friedman, J. "A Non-Numerical Approach to Production Scheduling Problem." Operations Research, Vol. 3, No. 4 (1955), pp. 429-442. Akers, S. B. "A Graphical Approach to Production Scheduling Problems." Operations Research, Vol. 4, No. 2 (1956), pp. 244—245. Bakshi, M. S. and Arora, S. R. "The Sequencing Prob- lem." Management Science, Vol. 16, No. 4 (1969), pp. B247-B263. Bellmore, M. and Nemhauser, G. L. "The Travelingv Salesman Problem: A Survey." Operations Research, Vol. 16, No. 3 (1968). pp. 538-558. Bowman, Edward H. "The Schedule-Sequencing Problem." Operations Research, Vol. 7, No. 5 (1959), pp. 621— 624. Brown, A. P. G. and Lomnicki, Z. A. "Some Applications of the 'Branch and Bound' Algorithm to Machine Scheduling Problems." Operational Research Quarterly, Vol. 17, No. 2 (1966). pp. 173-186. Campbell, H. G., Dudek, R. A. and Smith, M. L. "A Heuristic Algorithm for the N Job, M Machine Sequencing Problem." Management Science, Vol. 16, No. 10 (1970). PP. B630-B637. Conway, R. W., Maxwell, W. L., and Miller, L. W. Theory of Scheduling. Reading, Mass.: Addison- Wesley, 1967. Corwin, B. D. 'Some Flow ShOp Scheduling Problems Involving Sequence Dependent Setup Times. Ph.D. Thesis, Case Western Reserve University, 1969. Day, J. E. and Hottenstein, M. P. "Review of Sequenc- ing Research." Nav. Res. Log. Quarterly, Vol. 17, No. l (1970): Pp- 11-39. 191 11. 12. l3. 14. 15. 16. 17. 18. 19. 20. 21. 22. 192 Dudek, R. A. and Teuton, O. F. "Development of M-Stage Decision Rule for Scheduling N Jobs Through.M Machines." Operations Research, Vol. 12, No. 3 (1964): PP. 471-497. Elmaghraby, S. E. "The Machine Sequencing Problem-- Review and Extensions." Naval Research LogistiCs ggarterly, Vol. 15, No. 2 (1968), pp. 205-232. Fabrycky, W. J., Ghare, P. M.,and Torgersen, P. E. Industrial Operations Research. Englewood Cliffs, N.J.: Prentice-Hall, Inc., 1972. Giffler, B. and Thompson, G. L. "Algorithms for Solving Production Scheduling Problems." Operations Research, Vol. 8, No. 4 (1960), pp. 487-503. Giglio, R. J. and Wagner, H. M. "Approximate Solutions to the Three—Machine Scheduling Problem." Operations Research, Vol. 12, No. 2 (1964), pp. 305-324: Gupta, J. N. D. "A Functional Heuristic Algorithm for the Flowshop Scheduling Problem." Operational Research Quarterly, Vol. 22, No. l (1971): PP. 39-47. Gupta, J. N. D. "M-Stage Scheduling Problem--a Critical Appraisal." International Journal ofProduction Research, Vol. 9, No. 2 (1971), pp. 267-282. Gupta, J. N. D. "A General Algorithm for the NXM Flowshop Scheduling Problem." International Journal of Production Research, Vol. 7, No. 3 (1969): PP. 241-247. Heller, J. "Some Numerical Experiments for an MXJ Flow Shop and Its Decision--Theoretical Aspects." Operations Research, Vol. 8, No. 2 (1960), pp. 178-184. Heller, J. "Combinatorial Properties of Machine Shop Scheduling." NYO-2879, AEC Research and Develop- ment Report, 1959. Heller, J. "Combinatorial, Probabilistic, and Statis- tical Aspects of an MXJ Scheduling Problem." NYC-2540, AEC Research and Development Report, 1959. Ignall, E. and Schrage, L. "Application of the Branch- ,and Bound Technique to Some Flow Shop Scheduling Problems." Operations'Research, Vol. 13, No. 3 (1965), pp. 4004412. 23. 24. 25. 26. 27. 28. 29. 30. 31. 32. 33. 34. 35. 193 Johnson, S. M. "Optimal Two and Three Stage Production Schedules with.Set~up Times Included." Nav. Res. Log._Opart., Vol. 1 (1954), pp. 61-68. Karush, W. "A Counterexample to a Proposed Algorithm for Optimal Sequencing of Jobs." Operations Research, Vol. 13, No. 3 (1965), pp. 323-325. Krone, M. J. Heuristic Programming Applied to Schedulinquroblems. Ph-D. Thesis, Princeton University, 1970. Krone, M. J. and Steiglitz, K. "Heuristic-Programming Solution of a Flowshop-Scheduling Problem." . Operations Research, Vol. 22, No. 3 (1974), pp. 6293638. Lomnicki, Z. A. "A 'Branch-and-Bound' Algorithm for the Exact Solution of the Three—Machine Scheduling Problem." Operational Research Quarterly, Vol. 16, No. 1 (1965): PP- 89-100. McMohan, G. B. and Burton, P. G. "Flow Shop Scheduling with the Branch-and-Bound Method." Operations Research, Vol. 15, No. 3 (1967): pp. 473-481. Muth, J. F. and Thompson, G. L. Industrial Scheduling. Englewood Cliffs, N.J.: Prentice-Hall, Inc., 1963. Nugent, C. E. On Sampling_Approaches to the Solution of the N-bv-M Static Sequencing Problem. Ph.D. Thesis, Cornell University, 1964. O'Brien, J. J. Scheduling Handbook. New York, New York: McGraw-Hill Book Company, 1969. Page, E. S. "An Approach to Scheduling Jobs on Machines." Journal of Royal Statistical‘Society, Series B, Vol. 23 (1961), pp. 484-492. Palmer, D. S. "Sequencing Jobs Through a Multi-Stage Process in the Minimum Total Time-—A Quick Method of Obtaining a Near Optimum." Operational Research Quarterly, Vol. 23, No. 3 (1972), pp. 323-331. Reddi, S. S. and Ramamoorthy, C. V. "On the Flow-ShOp Sequencing Problem with No Wait in Process." Operational Research Quarterly, Vol. 23, No. 3 (1972), pp. 323-331. Sisson, R. L. "Sequencing in Job Shops-~A Review." Operations Research, Vol. 7 (1959), pp. 10-29. 36. 37. 38. 39. 40. 41. 42. 43. 194 Sisson, R. L. "Sequencing Theory." Chapter 7 in 'Progress in OperatiOns Research. Edited by R. L. Ackoff. New York: Wiley, 1961. Smith, R. D. and Dudek, R. A. "A General Algorithm for the Solution of the N Job, M Machine Sequencing Problem of the Flow Shop." Operations Research, Vol. 15, No. 1 (1967), pp- 71-82. Spinner, A. H. "Sequencing Theory-~Development to Date." Nav. Res. Log. Quart., Vol. 15, No. 2 (1968). pP. 319-330. Starr, M. K. Systems Management of Operations. . Englewood Cliffs, N.J.: Prentice-Hall, Inc., 1971. Story, A. E., and Wagner, H. M. "Computational Experi- ence with Integer Programming for Job-Shop Schedul- ing." Chapter 14 in Industrial Scheduling. Edited by J. F. Muth and G. L. Thompson. Englewood Cliffs, N.J.: Prentice-Hall, 1963. Szware, W. "Solution of the Akers-Friedman Scheduling Problem." Operations Research, Vol. 8, No. 6 (1960): PP. 782-788. Wagner, H. M. "An Integer Programming Model for Machine Scheduling." Nav. Res. Log. Quart., Vol. Wismer, D. A. "Solution of the Flowshop-Scheduling Problem with No Intermediate Queues." Operations Research, Vol. 20, No. 3 (1972), pp. 689-697. APPENDICES APPENDIX A 1L 17 20 40 195 (b,4),A(b),B(b),dl:b),193LT(b), 11g(1§0),1M(1tU),JTOI(120),ETQT(1ZU) 1 UZAFNSICR lSMLUl(1:U),NlU(150),153U(150),IFLASU(150), MI1(500),ILLU1(500),1%H.1(W)0),1A(80) ,PLAN,TIIh /1,2,t,2u,120/ AV1C1(1L),1$ INTEGEF P,t,1,E,TS yaw: IPACT LNFA l?1,LF2/UCl,bUL/ Lfigfi CY/(,2,1,1,I/ L\\I .‘=i+' £18331: Ifflf’2=(‘ 131:1 Bi ’k) (.lj 1 5’: , .H‘(1(£".)=C FIG": (3):" 1.1) '41) (“Nil ."1,I.-'."/. FEAR(% 1)((' ‘ lSflLl ?1(C3LU B-‘ 19 r' 1,1;11 ("LL SCde(;,\,uY,b§b) LALL 1:51L1(A,T,F,nnn) (at? fCA1c7(L,3,z,hxn) 15:5(3(N\£),h) 10r1(1x)::cx1(r3)+us I (TS.IE.IIw01(HN))CG 1) 16 7‘ 19(u)=~ ('(I'N 1133 If". 10:1(wn);*(31(¥L)/1:1 11032=11C12+\ 6,2ua)ww,s,l 1),.‘I17‘1,Y‘.) L". (1!) 0'1 3121,r (I; L n ‘11" (:; 12'. ‘ . F0 =ri -. \ F :r11(ui),Iof1(fln),lL:31(NN) J137(IC(:1))=J1u€(;.(h1))+1 Cu:"15nt conrlnn? «P1¢I(L,.u1)17v12 ~rllt((,gub)(JEC1(L),1=I,IE1) 196 hfl’f(b,kub)(KTOT(L),L=1,IEU 101 EORHAT(414,ZX,QIQ,ZX,N14,ZX,HIQ,ZK) d)1 FORMAT(1h1,30!,15,9x,2010) 202 t0hMAT(1LIb) 203 bORiAI(1}U,IQ,218,II,11,31t,316) £04 FORHAI(1X,315,5X,F5.1,1115) (Ob PUMA?(1!:0,b(2413,//)) 206 F05”A1(1h1,//) 207 EOPEAT(1LO, 83,23U -------- PASSING -------- , 1x 1,24H ------- EC PASSLNu ------- ) 209 EOIWAT(1F0,8X,ZJHPEHLLEA tluldum NURLEE ,1x 1,24H ICILL LLxdaE Pkaabt ,188--SAVIAG BY--- ) 209 l'U:1."5T(T/X,1bff TOTAL (35 ($1.,1x,11A,21i0r',16x,uHHAM 210 {UhMA1(JZH hUHbEE bNUEI NAKLSPAN SEQ. ,1X 1,4“?13’15151'511'1” 51",}. SRVLKU ,1‘”! I Z J) 411 PUP:§AT(//,(1110TC' 1'31, IX,IH,II,1X.JI’3,JIO) 211. POKER?(t‘thAVFEMIit, ‘JX, F5.4,EU.Z,1X,JFH.Z,.5rb.Z) 21.1 F()R"‘.I~'“ (91133:[.[EV.,’4A,£F’1.2) 214 1:05;"): (11”) 215 F’.):1‘."’1!~T(H)L',1t‘,'-',1J,11J) .31'UP If R Li 3031001111 3C113(m,t1,¢x,bbu) LlflENSZC! JA(3),JY(:),K(5),1T(5) 7:1,2221“: 3) 1 . 1 1“(1)=1 Iv=1 an 2 1:1,111 “(l)=((31’1)/JY(1))“ 51:1 so .3 J=1,Nt\ 1r(11(a).rc.0)su TC 1 1F(K(I).LO.V1)3L 1c 4 B1=K1+1 J CONTINUE: 4 JA(I)=1T(J) ’IT(J)=C lY=1Y-(K (1)-1) MIN) 2 CONTINUE RE’L‘WFK END U I 11) f- I 197 150311001135 I‘CI:1C1(A,'1.I',1H\N) urnsxszcn A(51,T(b,u),r(5,«) iflqFflF? A,1,P 1(A(1),1)=T(A(1),1) DO 2 1:2,NNW P(.'§(1),1)=F(I‘s(1‘1),1)i‘2({\(l),1) 3(A(1),2):I(A(1),1)4"l(1*(1) 02) D‘) .3 1: 2'1; N1\ 11‘ (F(A(I’1),2)‘P(A(I),1))b,b,4 F(.‘.(I),2)=“(A(I-l),2)+'i(n(l),2) (40 TC 3 I"(«’=(T) .53)=3 (MI .1)*'IU)(1):3) LUNTIRUI: i‘SI‘UB‘N END :upmlfll M? 1.0“ 162 (5.1.5. MM 'I‘I‘I Etf‘lt? -(“)o'I(‘3o"):H‘J ‘4) 1.’ vn ‘ 1...“.J‘G; (I L" _.'r 1°(’5(I):3)=1('-(I). ’)+T(L‘(I)o3) “(I-(I) ,h)='(:(1),3)+1“{ (1)04) 130711125,“ (A) H 1:2,?13'3 1F(§(E(1-1).J)-P15(l).(d-1)))9.9.10 113(1)“1):?(3-‘(7)’(J‘IH‘IU‘U)oJ) CC ”C t“ T-(‘c (I),d)=1(-(11),J)+'1(73(),J) LtuI‘.HT (ONTIu 11 I'ElIJI‘N if; 1“ L‘ .3 APPENDIX B 198 COH"ON JCBSCH(720),FAIRTX(720,20),LOH30r(IZU),FFOCTI( 120,10),IES(20),LBNE(20),KTIME(10),TIM3(10),LIST,LM1,NJOU 2,MJOP,JONSON,IST0P,NAG,JCB,MACHIN,ITEHP,MARK TNTEGEF IFOCTT,TI"E J03=29 MACHIN=1O JONSOV=156 .mzw F=0 PPAC(5,200)((PFOCTI(I,J),J=1,MACHTH),I=1,J03) ISTOF=0 JOBSCH(1)=0 LIST=1 IOWBCN(1)=1 DO 1 1:1,Jn° MATPIY(1,I)=' CONTINUE 2 CALL SFNI IF (NAG .‘.~‘.r,‘. 0) Gr: '1') 5 CALL TF21“O NAG=0 JAG=0 3 IP(JfiG.LW.10)GO TO u CALL FESZFO JAG=O u JAG=JAG+1 IF (I STOP-1) 2 ,F‘ ,5 5 WPITF(6,206) CALI DISIEO CALL CECCSF GO If 10 6 WRITF(6,201)JONSON DO 7 T=1,IISI HRITY(6,202)(NATRIX(I,J),J=1,JOR) 7 CONTINUE 20“ FORMAT(1012) 201 FOR"AT(1CIS) 202 FORMAT(2”13) 203 FOR"hT(5x,BIS,2013) 206 FORIAT(USP IVER? HEB? F07? THAN 51" ITZIS TV INF L181. 1 THE ”DOCPhr STOPPED AND LILVTED :iPDs.) 10 STO° 75H) q-I J1 \l’fi 9 7 L99 SUBF’PYITI NF. 3 E" f COMDInN JOBFCTI (72()) 'rA'TBi-x (Izn '31) 'I"- 3;: '1" (’2’), ' }I(7le( 120,10),Irs(MLMNEQCLMHEHU,3...“,H'Z .“J“?.JCNSOV.TST”P.“IG.IO£.HACUIN,TTLIY,“ TWTVGFF FFOCTI,TTMF NAG=0 I‘I‘EMP=10CW)’) DO 1 1-31: 1,1'5‘3' I?(JCBSCF(LN).70.JC9)GC 5C 1 TF(TTF?F.YT.16KEOW(Lt))dfl "O 1 TTPF??IOHECF(IR) LM1=13 CONTINUE TF(ITF"F.NF.1WOUHH)SC T4 2 TSTCF=1 aETWFN NJOB=JC3-J039CH(LY1) MJOP= ("TNSCH(TN1) D“ Q T=1,VWC?TN IF(MJPP.EF.O)CC TO 4 TIM?(I)=I‘ G0 TC a TPWV(T)=P?9CTI(‘1T91X(lfl1,1),1) CONTINHE I? (VJI‘B.L".1)N‘- TC 8 DO 7 T=2,NJOE TIM”(1)=TIHP( 1)+FPCCTI(§AT?IX(LM1,I),1) £0 6 J=2,PACH1N IF‘(TT“’~’(J) 37.71913 (Cl-1))4H" ”1‘0 1» TIMF(J)=TIW“(J—1)+PPO("£(?PTQIX(111,I),J) GO Tn ( TIHE(J)=TTFF(J) +FHLCTI(EITTTX(181,1),J) CONTINPE CON"'TNUP 1F(NJOB.“T.1)GC [O H NAG=1 D0 9 I=1,HJUL IRS(1):"WPTY(I"11,F’:JOE+T) CONTINUE 1“.) 1" '=1,‘JJCB T=I”S(1) 195(1)=TF‘T(I) I”:’§(T)=T'T MAPK=0 C51} TBCUVD . V ‘ .1'K :51,Ln1,ngou 10 .b 25 200 IF(nA3x.ro.n)Gn TO 10 IF(NAG.NF.0)JOVSON=IIEMP CALL INTFO CONTINUE LOHBCN(LE1)=190000 RETURN END SUBFCUTIBE BCUNE COMMON JFBSCH(720),HAIRIX(720,20),LOWJOQ(I20),FPOCTI( 120,10),TFS(20),LBNB(20),KTIN€(10),TIME(10),LIST,LH1,NJOU 2,3JOP,J0¥SON,ISTOP,HAG,JOF,fiACHIN,ITEWP,HARK INTEGER FFOCTI,IIM€ ITE"F=0 KTI¥E(1)=TI“F(1)+PFCC11(IE?(1),1) DO 2 T=2,MACPIM IF(TIMB(I).GI.KTIFE(I-1))CO TO 1 KTIHE(1)=KTTHP(I-1)+PROCTI(IPS(1),1) GO TO 2 KTIME(Y)=TINF(T)+PPHCII(IPS(1),I) CONTINUE DO 3 I=1,NICBIN LBND(I)=C IF(NJCD.GT.1)GO TO 6 ILOVAL=0 GO TC u ILOVAL=100000 DO u IKF=2,NJOE LBND(I)=1END(T)+ PEFCTI(LFS(IKR),I) IVAL=0 11=I+1 IF(T1.GT.MACHIN)GO TO 5 D0 5 IM=I1,MACHIN IVAL=IVAI+ PFOCTI(IPS(IKF),IH) CONTINUE IF(IICVAI.CT.IVPL)ILOVAL=IVAL CONTINU? ITEPOJ=KTTHF(I)*LBNE(I)+IICVAL IF(ITEPOJ.GI.JONSON)GC T0 25 IF(TTEEOJ.GT.ITEHP)IIEHP=IIEPOJ CONTINUE HARY=1 RETURN FND 201 SURROU'II 1.". I P-‘TFO conwcn JCESCH‘720),fiATtYX(720,20),LOWRO"(I2“),P“0CTT( 120,10),I?5(zn),LBNP(20),K1IME(1H),TTHH(1U),L151,L11,uaou 2,MJOE,JONSON,ISIOP,NAG,JOP,MACH1N,IT31P,MARK INTEGER EPOCTI,TT!E LIST=IIST+1 LOW“CN(LTST)=ITFMP an 2 T=1,JOP IF(I.G¢.mJnn)no we 1 unrelx(1151,I)=MATRIX(121,1) no "G 2 1 HAT“IX(IIST.I)=IRSIT'FJQb) 2 CONTINUE anascn(rrsm1=waca+1 IF(L13?.1?.7nn)co Tn u STor=2 u PETVFN 5ND SURSOUGIKW DFSTFC COMIC” J‘BQCP(720).“ATFIX(120,20),L01301(131),9?ncwz( '2”'1”I'TISI°CIIIANDIZ“)IETIWT(10),TIM3(1H),L1q 2,MJ0F,JC1901,Isqu,uAC,Jnx,mmcnrn,fraaw,vmrx INTFGFP PPOCTI,TIIE nzrnv=n no 3 I=1,IIST IF(JCHSCL.G?.ICW3CK(1))GO 10 1 IDEMCV=TFFHHV+1 co To 3 1 IF(IFF”CV.FC.2)GJ TC : Lou-mo“ (I -: W MTV) =I.C‘~I’C.‘? (T) JOB°CH(I-TR'ROV)=JOESLt{T) IN) 2 3:1,an HATFIY(I-IFFHOV,J)=FA1F1X(I,J) CONTINUE conmrwvr LIST=LTSi-TFRMCV TP(LIST.GT.")G0 T0 0 TSTOP=1 u RET"FN END WM T,LM1,NJOU a 9'1 201 202 suaaonwtnr cuocsa conncn JCBSCF(720),MATPIX(720,20),LOWBON(120),PROCTT( 120,10),IFS(20),LBND(ZU),KTIME(1U),TIME(1U),LIST,LM1,NJOB 2,naon,aouson,15109,Naa,aop,uncuxu,lr£np,MARK INTEGER EROCTI,TIHE "=0 ITE15=100000 no u 1:1 ,LI 3'! IP(IT=vE-IannN(I))u,:,2 TTEHP=IOFBOV(I) K=n K=K+1 CONTINUE no 5 I=1,LIST IP(ITFMP.NF.IOWEON(I))GO TO 5 HRITE(6,201)T,IOHBOL(I),JOUSCH(T),(AAPRLX(I,J),J=1,JUB) WRITF(7,201)T,lOdBON(l),JOP3CH(l),(MATRIX(I,J),J=1,JOU) LOWBON(I)=100000 CONTINUE n=n+r IP(1.LI.IISI)60 TO 1 POPHAT(QIS,ZOI?) PFTUPN END APPENDIX C 203 DIMENSICB T(5,fl),F(t,U),A(b),B(5),JY(5),IFACT(5), 110(150),IN(150),J121(120),NIOT(120) DIMENSION PLAN(4,J),1]EE(5,16),IDIFF(5UU),IB(80) . [IMEBSICB JOP(6),JOETT(150,4),MIZU(150),!YTOT(1U),KR(80) DIMENSION ISHLUI(150),NIU(150),15HU(150),1ELAGU(150), 1 AVTCT110),15NL11500),1LNO1(500),TOT1(500),IA(80) INTEGEF A,B,T,F,TS,PIPN,TINE DATA IPAc1/1,2,b,2u,120/ DATA 1B1,LR2/001,500/ DATA JY/c,2,1,1,1/ NNN=u JRN=C ITCT2=0 IF1=IFAC1(NNN) 1:01 n=1,11=1 PLAN(I,J)=0 CONTINUE CONTINUE 00 ac NNzLN1,Lr2 NEA015,101)((?(I,J),J=1,4),I=1,NNN) IShL1(HN)=1CCCCU ILNG1(rN)=O TOT1 (M N) =0 DO 19 r=1,1r1 CALL SCHED(N,A,JY,NNN) CALI ECAIC1(L,1,£,NNN) CALL FCA1C2(A,1,E,hhb) Ts=rla(NNN),u) TOT1(NN)=TOI1(NN)+1$ IE(Ts.IE.ILNG1(NN))sc To 1r ILRG1(EN)=TS IF(TS-13PL1(NN))17,1t,19 ISHL1(EN)=TS N=o N=N+1 IQ(N)=H CONTINCE TOT1(Mk)=TC?1(flN)/1E1 20 21 22 23 24 25 26 27 28 204 1TOT2=ITCT2+N iRITP(6,2ou)FN,N,ISNL1(1N),IOT1(NN),1L?31(MN) .(IQ(N1).N1=1.K) KTOT(N)=KTCT(N)+1 DO 20 K1=1,N JTOT(IQ(L1))=JICI(IC(b1))+1 CONTINUE D0 21 J=1,6 JOE(J)=ISML1(NN) CONTINUE HARK=0 N1=N DO 28 E=1,IP1 CALL SCHED(F,A,JY,LLL) CALL ECA 1C 1 (11,1, L, N 4N) DO 27 N=1,IF1 IF(!.EC.L)GC TC 27 CALL SCHLD(N,B,JY,LNL) CALL ECAICZ(£,T,E,NNN) ISM=F(P(NNN),N) 1F(ISM.GP.IS?L1(NN))GC TC 27 CALL SLILI(A,B,NSHL:I,NNL) NEITE(6,203)IS!,M,N,NSLILT NARK=¥AFK+1 IF(JCE(1).LF.ISN)GO Io 22 JOE(1)=I$N IF(NSHIFI.NE.1)GO To 23 IF(JCF(2).LE.IS¥)GC TC 23 JOE(2)=IS! DO 26 NS=1,N1 IF(IC(NS).PC.N)GJ TO 24 IF(IC(NS).EC.N)GC IC 24 60 TC 26 IF(JCF(3).IE.ISP)GL IL 25 JOE(3)=.SN IF(VSHIF7.NF.1)GC 1C 26 IF(JCE(U).LE.ISN)GO 10 2c JOE (10:19.14 CONTINUE CONTINUE CONTINUE IF(!ARK.EQ.U)GC 10 at JRN=JBK§1 HYTOT(1)=MYTCI(1)#ISFI1(NL) HYTOT(2)=HYTCT(2)+N1 205 MYTOI(3)=NYTCT(3)¥JCE(1) HYTOT (u) =NYTCT (u) +NAFK DO 35 J=1,u JOETT(JRL,J)=ISNL1(3h)-JOE(J) NYT31(u+J )=N!101(uoa )+JCETT(JRN,J ) 35 CONTINUE DO 36 K=2,u JLH=1 IF(JOEII(JFN,K).1I.JCEIT(JPN,1))JLM=2 IF(JCETT(JEN,K).EQ.O)JLN=5 , PLAN(K-1,JLM)=PLAN)N-1,JLN)+1- 36 CONTINUE NI20(JHN)=MN ISNLUI1J1N)=ISNL1(NN) NIU(JRN)=N1 ISMU(JLL)=JCE(1) IFLACU¢JFN)=LAPK 40 CONTINUE Q1 CONTINUE L0 62 IJKL=1,6 DO 51 JFL=1,JRL JJR=JFU/25 JJR=JJP*25+1 IE(JJR.NE.JLU)CO TC 51 HRITE(€,200) WRITE(6,207) NRITE(6,208) HRI’I‘E (6, 209) NRITL(6,210) 51 NRITE(6,203)JRU,M12U(JEN),lSHLUI(JLU),N1U(JBU),ISHU(JFU), 1IFLAGU(JEU),(JCETI(JEL,J1),JI=1,u) L0 52 1:1, 8 AVTCT(I)=FLCAT(MYTCT(I))/ILOAT(JRN) 52 CONTINCE HRITE(6,211)(HYTOT(I),I=1,P ) HRITP(6,212)(AV10111),I=1,8) N=LH2-LN1+1 ISTAPT=161 INTEE=20 CALL I‘FEO (1 $321.1 ,II‘I,N,15II\Z