A Genetic Algorithm Methodology for Complex Scheduling Problems Bryan A. Norman University of Pittsburgh James C. Bean University of Michigan Technical Report 94-5 August 22, 1997

A Genetic Algorithm Methodology for Complex Scheduling Problems Bryan A. Norman Department of Industrial Engineering University of Pittsburgh Pittsburgh, PA 15261 and James C. Bean Department of Industrial and Operations Engineering University of Michigan Ann Arbor, MI 48109 August 22, 1997 Abstract This paper considers the scheduling problem to minimize total tardiness given multiple machines, ready times, sequence dependent setups, machine downtime and scarce tools. We develop a genetic algorithm based on random keys representation, elitist reproduction, Bernoulli crossover and immigration type mutation. Convergence of the algorithm is proved. We present computational results on data sets from the auto industry. To demostrtate robustness ofee the approach, problems from the literature of different structure are solved by essentially the same algorithm. n

1 Introduction We present a random keys genetic algorithm to solve complex scheduling problems. For a comprehensive discussion of scheduling problems and terminology see [6] and [33]. The principle problem we investigate arises from an automaker. There are several factors that complicate the automaker scheduling problems. The jobs have ready times and due times that range throughout the study horizon. Each job has a particular tooling requirement. Tooling conflicts arise because there is only one copy of each tool and multiple jobs may require that tool. Setup times are introduced into the problem if consecutive jobs on the same machine require different tools. There is processing flexibility because different jobs can be processed on different subsets of the machines although the machines are not identical. The scheduling objective is to minimize the total tardiness of all of the jobs. The number of jobs ranges from 270 to 360. These scheduling problems are NP hard since the scheduling problem to minimize total tardiness for a single machine problem is NP hard even if the following simplifying assumptions are made: all jobs are ready at time zero, setup times are not sequence dependent, no mlachine downltine, and no special tool requirements ([16]). The vast majority of the papers in tie scheduling literature consider only a subset of these problem complexities. In [23]. [21]. and [43] problems are investigated that contain many of the complexities but each of these assumes away two or more of the factors. The onlS paper of which we are aware that has addressed problems containing all the previously mentioned complexities is the Matchup Scheduling work of [10]. They propose different priority rules and heuristic methods based on an integer programming formulation of the problem. Section 3 provides a comparison of the Matchup algorithm with the proposed 1

genetic algorithm. Because of the difficulty of using branch-and-bound and special purpose heuristics for many scheduling problems, general heuristic search techniques have been applied to scheduling problems in recent years. Tabu search ([17] and [18]) has been applied to scheduling problems by [8], [15], [32], and [40]. Both [32] and [40] succeeded in finding new best solutions for several problems that do not yet have known optimal solutions. Simulated annealing ([26] and [12]) applications to the job shop problem are discussed in [41] and [1]. Good results have been found for several of the classic test problems from [27] and [2]. However, none of the problems tested had all of the complexities found in the automaker data. Genetic algorithms have also demonstrated potential for solving scheduling problems. Genetic algorithms (GAs) were introduced by [24] as a method for modeling complex systems. GAs apply concepts from biological evolution to a mathematical context. The general idea is to start with randomly generated solutions and, implementing a "survival-ofthe-fittest" strategy, evolve good solutions. See [20], [14], or [28] for details. GAs have been applied to scheduling problems by several authors. The primary strategy used is a literal permutation ordering encoding ([4], [13], [29], [39]). Specialized operators have been developed to insure the feasibility of generated solutions including PMX Crossover ([19]), the subsequence-swap operator ([22]). other subsequence operators ([13]), edge recombination ([42]), order-based and position-based crossover ([38]), and forcing ([29]). Two of the more innovative applications of GAs to scheduling problems are the Problem Space and Heuristic Space methods of [36]. Storer, Wu, and Vaccari begin from the premise C)

that most scheduling problems have base heuristics that are fast and obtain good solutions. The authors go on to conjecture that if the data were perturbed, the heuristic may find a solution that is outstanding for the original problem. The problem space approach searches this set of perturbations using different search mechanisms including GAs. Heuristic space ([36]) introduces another level of search. They combine several heuristics to create a superior meta-heuristic. These methods have been tested on several of the classical job shop test problems ([37]) and found to perform well. Our approach is based on the random keys encoding of [9]. The random keys representation ([9]) encodes a solution with random numbers. These values are used as sort keys to decode the solution. Chromosomal encodings are constructed that represent solutions in a soft manner. These encodings are interpreted in the fitness evaluation routine in a way that avoids the feasibility problem. A similar idea was presented by [34] where the authors embedded their encoding in a genetic algorithm that dynamically adjusts its internal representation of the search space according to the problem being solved. The random keys GA (RKGA) operates in two spaces, the chromosome space and the schedule assignment space. For a five job single machine problem, the chromosome space consists of all points within a 5-dimensional hypercube, C = [0, 1]5. Define chromosome x E C where x = {X1,2, X,..., X5}. Let x, represent the random key value for allele i of chromosome x. The schedule assignment space, S, contains all the possible schedules for the problem. For a single machine problem with regular measure, this includes all the possible permutations of the jobs scheduled as early as possible. For the single machine problem, C is Q

mapped to S by sequencing the jobs based on the sorted random key values. Consider a five job problem. If a schedule were represented by the random key vector (.31,.12,.73,.91,.44), sorting to decode the schedule would result in the sequence 2, 1, 5, 3, 4. The initial random keys are randomly generated. During the progress of the algorithm, jobs that should be early in the sequence attain low keys and those which should be later in the sequence develop high keys. The random keys encoding has the advantage, over a literal encoding, that all crossovers produce feasible sequences. Crossovers are executed on the chromosomes, the random keys, not on the sequences. Therefore the offspring always contain random keys that can be sorted into an ordered set. Since any ordered set of random keys can be interpreted as a job sequence, all offspring are feasible solutions. 2 Proposed Solution Methodology We now extend the RKGA concept to include the following complexities: multiple, nonidentical machines, nonzero rea(dl tinmes. sequence dependent setups, tool constraints, and precedence. Changes are required in the c(od(ling and in the function evaluation routine. We then describe the specific GA operators usle in the algorithm. Finally, we demonstrate that there is a region with nonzero volume in the chromosome space, C, that maps to the set of optimal schedules. This leads to a simple proof of convergence. A

2.1 Modifying the GA for Additional Problem Complexities The random keys approach can be extended to multiple machine problems by extending the encoding. As an intermediate step, consider the m identical machine n job problem to minimize total tardiness. For each job generate an integer randomly in {1,..., m} and add a uniform (0, 1) variate. The integer part of any random key is interpreted as the machine assignment for that job. Sorting the fractional parts provides the job sequence on each machine. Assuming that jobs are processed at their earliest possible time, a schedule can be constructed and evaluated for total tardiness. The schedule can contain unforced idle time by preserving the sorted order of the job sequence. If the machines are not identical, generate the integer randomly from the set AlMi where Mi contains all machines that can be used to process job i. After the random keys are sorted, the job sequence and machine assignments for each job have been determined. Nonzero ready times, sequence dependent setups, and tool availability can all be considered simultaneously in calculating a job's start time The mechanisms for incorporating nonzero ready times and tool constraints into the schedule may appear inefficient tb(cause tlhey mlIay' introduce idle time into the schedule. However, the ability to create schedules t lhat contain unforced idle time is one of the principle advantages of using a job sequence Las tihe foundation for schedule construction. It is not difficult to construct example problems wliere inserting idle time into the schedule improves the overall objective. Where inserte(d idle time is not desirable, the RKGA will gradually select schedules without it.

Precedence constraints can also be captured by the RKGA. Recall that the sorted random keys provide a job sequence. Jobs are scheduled using this sequence subject to the constraint that a job cannot be scheduled unless its predecessor(s) have been scheduled. A pseudocode for handling precedence constraints is presented in [30]. The mechanisms for incorporating nonzero ready times, sequence dependent setups, tool constraints, and precedence are computationally simple. This is important because the GA must perform numerous function evaluations. 2.2 Genetic Algorithm Operators There are several types of genetic operators that may be used in the reproduction stage of a GA (see [20]). Because the random keys encoding preserves feasibility there is no need to use the specialized operators discussed in Section 1. The code described here uses elitist reproduction, Bernoulli crossover, immigration, and post-tournament selection to fill the next generation. The random keys representation is not limited to these operators. Other operators remain to be investigated. However, these operators have performed well in tests completed at this time. Elitist reproduction ([20]) is accomplished by copying the best individuals from one generation to the next. This method has the advantage of maintaining a best solution that is monotonically improving. However, it has the potential for premature convergence. This is overcome by introducing high mutation rates. Bernoulli crossover (called parameterized uniform crossover in [35]) is used in place of the g

traditional single-point or multiple-point crossover. Two chromosomes are selected randomly with replacement from the current population to function as "parents." Let X = (xl, x2,...z) and Y = (Y, Y2,...yi) be the 1 random key alleles in these two chromosomes, respectively. Let Z = (z1,2,...zl) be I independent uniform (0, 1) variates and Pc be the probability of crossover for each gene. Let W = (wl1, 2,...w1) and V = (v1,2 2,...vl) be the 1 random key alleles for the two offspring that will result from the crossover of the two parent chromosomes. Determine W and V as Wi = x and vi = yi if zi < Pc wi = yi and vi = xi if zi > P. Since P is not necessarily 0.5, this procedure can be used to bias selection toward one parent. We have found PC = 0.7 to work for mnanv problems. It appears to support development of a generalized form of building blocks. Implementing a mutation operator for a real coded GA presents difficulties. As a result, we use immigration as described in [9]. It involves random generation of at least one chromosome each generation. Since our imnplemnentation of elitism only copies a few members from one generation to the next, immnigrants are Inot automatically eliminated via that operator. Then the random parent selection mixes the new genetic material from the immigrants into the population in subsequent generations. Ii1 this way immigration maintains diversity as in traditional mutation. A type of tournament selection, which we label post-tournament selection, is used in conjunction with the crossover operation to fill the next generation. Two chromosomes are 7

chosen randomly with replacement from the entire previous generation to serve as parents for the crossover operation. Performing crossover on these two chromosomes, X and Y, results in the two offspring V and W. Both of these chromosomes are evaluated and only that with better fitness is permitted to enter the pool of potential parents for the next generation. Empirical results indicate that if the GA does not improve the current best solution for 30 successive generations then additional searching yields little improvement. For this study, population convergence is assumed if the best solution does not change for 30 generations. Having discussed the random keys encoding and the operators used in the RKGA, a pseudocode for the algorithm is presented below. Step 2 is repeated for each generation until either the population converges or until the maximum number of generations is reached. Step 2.2 implements the elitist strategy and copies the number-of clones best members from the entire previous generation. Step 2.3 represents the reproduction step of the algorithm. The crossover operation is performed using two parents that are randomly selected from the previous generation. This step is repeated to create all members of the new population that are not copied over directly from the previous generation. Then the population is ranked based on fitness and the number of immigrants worst members of the population are replaced with immigrants in order to enhance diversity in the gene pool. Q

Pseudocode for the Random Keys GA 1. Initialize population. Rank the population based on fitness. Set stop = 0, count = 0. 2. While stop = 0 2.1 Count = Count + 1 2.2 Copy the number-of clones best members from the previous generation to the new generation 2.3 For i=1 to populationsize - numberof clones 2.3.1 Randomly select two parents from the previous generation. 2.3.2 Perform the Bernoulli crossover operation. 2.3.3 Evaluate the fitness of the two offspring. 2.3.4 Keep the better of the two offspring and place it in the next generation. Discard the other offspring. 2.4 Rank the population based on fitness. 2.5 Replace the number-of immigrants worst members of the population with immigrants. 2.6 If the population has converged set stop = 1. 2.7 If count=maximum.number.of.generations set stop = 1. 3. Output the final solution. 2.3 Mapping from C to S It is essential that therandom keys encoding ensure that there exists a region in C, with nonzero volume, that the evaluator maps to the optimal schedule set in S. Then a search for this region in C can be used as a surrogate for a search of S for an optimal schedule. Constructing schedules in the manner described in Section 2.1, Theorem 1 shows that such a region exists within C for problems with a regular measure. We assume that there is no job preemption. The proof of Theorem 1 and supporting results use the following notation: 0

i Index of job, i E {1, 2,..., n}. ai The random key value for job i, Li E [0, 1] for all i = 1, 2,..., n. [i] Order statistic notation for the jobs from a sort of the ai values. j, k Indices of machines, j, k E Mi. TOi The tool requirement for job i. Si The start time of job i. MAj The time when machine j is next available for processing. TAj The time when tool j is next available for use. LTk The last tool used on machine k. MTLj The last machine on which tool j was used. ri The ready time for job i. di The due time for job i. Pi The processing time for job i. Mi The set of machines that can perform job i. d The total number of tools in the problem. SA The set of semi-active schedules. Remark: TOi is assumed scalar in the following proofs but is readily generalizable to a set. The RKGA uses the procedure y(x), described below, to map from C to S. Let x E C have xi = (mi.,) where rn, E A l, ai E [0, 1] for all i = 1,2,..., n. Procedure y(x) Sort {(i}=l to obtain [1]. [2]....[n]. Set M Ak= 0, LTk = V k = 1.2,....... Set TAh =0 Vh = 1, 2,....d. For(i = 1; i < n; + +) { if TO[i] = LTm,,l and.\TLro,; = rn[,] Setupt ire=0 else Setuptime=Set upvalulle S[i] = max{mnax{MAm1A,. T.4-r70l } + Setuptime, r[]} MAAm, = TATro,, = S[,; + pf,! LTmli = TO[,i MTLTOil = i[,] } in

The outcome of y is a set of start times, Si, that combines with the machine assignments from the random keys to describe a schedule. Using the definition of y the following two results are readily verifiable (see [30]). Lemma 1 For all x E C, y(x) is a feasible schedule. Lemma 2 The image of C under y is exactly the set of semi-active schedules. In Theorem 1 we prove that the GA finds an optimal solution with probability 1. Note that the algorithm presented in Section 2.2 generates a random sample at least once per generation. Let xt be the best solution found after t generations and Y C S be the set of optimal schedules. The driver of the proof of Theorem 1 is the random generation of an immigrant each generation. The Theorem establishes that there is some point in C that maps to an optimal schedule il S. W\e then show that there is an open ball (n-dimensional sphere of positive volume) in C. centered at the given point, such that all points in the ball also map to that optimal solution. Since this ball has positive volume, the random sampling of immigration will eventually hit it. pro(lucing the optimal schedule. Theorem 1 limto P((xt) E Y) = 1. Proof: For a regllar measure. [5] proved (Y n SA): 0. By Lemma 2, ~y-(y n SA) $ 0. Let x E -f'(Y n SA). Then x = {(rn,. wi,)Lce there mi E li and ai i a random variate from a uniform (0, 1). Let A = min {mIni,i - cl, mini(i, 1 - oi)}. Since there are a finite 11

number of jobs and the ai are generated from a uniform (0,1), A > 0 almost surely. Define the neighborhood of x, N(x) = {x': m' = mi, ' - i = 1, 2,..., n}. If x' E N(x) then 7y(x') = y(x) E Y. When randomly generating x' E C, n 1 P(x' E N(x)) > (In j An = E > 0. i=1 Mi Now, in each generation, the immigrant, x, which is uniformly generated from C, has probability > E of being optimal. The result follows immediately. c This result is of value as it establishes the asymptotic convergence of the algorithm. It is unsatisfying in that it relies on immigration rather than crossover to drive the theoretical convergence. Empirically, crossover is much more important. Understanding the theoretical rate of convergence, based on crossover, is an open research question. As problem complexities are added, the schedule assignment space, S, becomes increasingly complicated. Each point in this space must, essentially, be a Gantt chart of the schedule including: job to machine assignments, the job sequence for each machine, and possible interactions between jobs on different machines. These interactions may include precedence constraints and competition for scarce resources such as tooling. Due to the complexity of S, it is impractical to search it directly. In the RKGA, all operators are defined on C which is stable. The mapping 7y is altered to absorb these complexities. The robust nature of the GA is demonstrated by the fact that the same algorithm can solve different scheduling problems by making changes only to the encoding and the fitness evaluation function. The mechanisms of reproduction and mutation are unaffected. 10

3 Computational Results To determine the effectiveness of the RKGA for scheduling complex settings we tested two data sets of actual problems from an automaker. We are not aware of additional data sets in the literature that contain the types of complications found in the automaker data. To demonstrate robustness, tests on randomly generated makespan job shop problems are referenced. 3.1 Real Auto Problems In this section we will describe the problems against which the algorithm was tested, describe the testing process, and present results. The first and second data sets comprise a total of twelve problems from a large automaker ([10]). The seven problems in the first data set each contain approximately 360 jobs that are to be scheduled on two identical machines. Recall from Section 1 that these problems contain the following complexities: nonzero ready times, due times, tooling constraints, sequence dependent setup times. machiine flexibility, and total tardiness objective. The seven problems are derived frorn a single (dtae set and represent seven disruptions of that data set. The first problem is the utndisrupted case. The remaining six problems contain data disruptions including: periods of mlachine downtime, periods of tool unavailability, and changes in pi, r,, and di. The presence of disruptions significantly changes the data set and creates a different scheduling problem. The second data set contains five disruptions of a data set with approximately 270 jobs 1 Q

to be scheduled on ten nonidentical machines. The additional complexities are the same as those for the first data set. They are captured from a different auto plant than data set one. Due to the large size and complexity of the problems in the first and second data sets, it was not possible to compute optimal solutions for these problems. Therefore, the RKGA's solutions can be compared to total tardiness lower bounds for each of the problems. A lower bound for each problem is: n LB= A max(O, ri +p - di). i=l The RKGA's results are compared to the three scheduling methods presented in [10]: dynamic dispatching rules, a multiple choice integer programming based method, and Matchup scheduling. In addition, we provide comparisons with two additional dispatching heuristics that we developed and with random search. These additional heuristics utilize the Earliest Due Date (EDD, [25]) and Modified Due Date (MDD, [7]) list processing rules. These list processing rules provide a job sequence but do not provide job to machine assignments. Therefore, a GA was used to determine good job to machine assignments given a job sequence that resulted from a list processing rule. The mechanics and parameter settings of the GA were similar to the RKGA except that the job sequencing was based on the dispatching rule and the GA only determined the machine assignments. The results produced by any run a GA are a function of the random seed used. It is disconcerting if the same algorithm, on the same data set, can perform well or poorly depending on the random seed used. To study this issue, the GA was run ten times for each problem using a different random seed for each run. The minimum, median, and maximum 1 A

values over the ten random seeds are presented. The minimum and maximum values provide best and worst case performance measures. The median is used rather than the mean in order to reduce the effect of extreme minimum and maximum values. In all runs the following parameter settings were used: populationsize = 1024, numberof clones = 60, numberof immigrants = 40, maximum numberof generations = 500. In order to assure fair comparisons, each competitor must have at least the same computation resources available to it as was provided the RKGA. The DISP, MCIP and MUSA algorithms were run to their logical conclusions (e.g., the branch-and-bound ran to optimal stop). Hence, additional computation time would not have changed the results of these methods. The EDD and MDD based heuristic methods and the random search were all permitted to evaluate the maximum number of solutions that could be investigated by the RKGA. However, the RKGA always converged prior to examining this maximum quantity. Thus these other methods were Iermritted to examine more solutionutions and utilize more computation time. From Table 1 we can compare the loNwer bound for each of the twelve problems in the first and second data sets with the best solution obtained using the GA. The results indicate that solutions within 0.4% to 6.6/ of the lower bound can be found for the seven disruptions of data set one. For the five problems in the second data set the percent deviation from the lower bound is not meaningful because the lower bound is zero for four of the five instances. 1 r

However, the maximum total tardiness was less than 23 units above the lower bound for all seeds tested across all the problems. The data in Table 1 also indicate that the RKGA was consistent across the different random number seeds. Insert Table 1 here. Table 1 provides a comparison between the RKGA and the solution methods found in [10]. For data set one, the RKGA consistently found solutions that were better than those found using alternative methods. The median (across the seeds) solution found by the RKGA was on average 18% better than that found using dynamic dispatching rules (DISP), 9% better than that found by the multiple choice integer programming (MCIP) method, and 7% better than those found by the Matchup Scheduling Algorithm (MUSA). In addition to exhibiting the best average performance across the problemls in data set one, the data of Table 1 also indicate that the RKGA was the best performer for every problem instance. For data set two the RKGA also demonstrated better average performance than DISP, ICIP, and MUSA. On average, the solutions found by the DISP, MCIP, and MUSA methods have. respectively. 63%. 1957. anld 48',. more total tardiness than the median RKGA solution. Note that these percentages are IImch( larger than those for data set one because the actual total tardiness values for thae problletls of data set two are much smaller numbers. However, the RKGA is clearly better on averacge. Analvzing all twelve problemls of the two data sets together, statistical testing using a paired t-test found that the differences for DISP and MUSA were significant at alpha levels of.012 and.019, respectively. If all twelve problems are considered the alpha level for MCIP 1 r,

is.130. This may seem counterintuitive since MCIP provides larger total tardiness values, in general, than MUSA. The cause of the large alpha level value is the large tardiness on problem four of the second data set. This large tardiness value results in a large standard deviation in the difference between the RKGA median and MCIP. This results in a smaller value of the test statistic which leads to the large alpha value. If this problem is dropped and the paired t-test is rerun with only the remaining 11 problems then the difference between the RKGA median and MCIP is significant at an alpha level of.012. Thus, eliminating problem four of the second data set, which provides the best example of the RKGA outperforming the MCIP, actually reduces the alpha level. This is a good example of how statistical significance can differ from practical significance. Table 1 shows only the best result found over all ten seeds for both the EDD and MDD rules. For data set one both methods find solutions that on average have 24% higher total tardiness than the average mnedian seed value of the RKGA. For the second data set the average deviation increases to 51% and 48%c respectively, for the EDD and MDD based heuristics. A paired t-test indicated that there was a difference between the median RKGA solution and the EDD and MIDD biased heulristics that was significant at alpha levels of.0002 and.0005, respectively. Note that these mlethlods exhibited much more variation over the random seeds than the RKGA. We also compared the results of tihe RiKG A withl a random search. Due to the complexity of the problem random searcl p)erforlle(ld very poorly. Results are not listed in Table 1 but can be summarized. For data set one. tihe random search found solutions with total tardiness that was 2.5 to 5 times more thian the RKGA. For data set two, the solutions found had 1 7

total tardiness on the order of 10,000 to 15,000 as opposed to 35 or less for the RKGA. RKGA was able to solve all twelve problems of data sets one and two, for a single random number seed, on average in nine minutes on a Sun 4 Ultra 2 processor. Test results for data set one show that the RKGA can find solutions within 5% of the lower bound in about one half the time required to converge to a final solution. This demonstrates how the RKGA quickly finds good solutions and then spends additional time to obtain the final improvements. This is a useful property for real scheduling implementations since the algorithm can be terminated sooner with only a small reduction in performance. The time to find solutions within 5% of the lower bound is not meaningful for the second data set because the lower bound is 0 for four of the five problems. 3.2 Makespan Job Shops The robust nature of the RKGA has been verified by conducting additional testing on the n/m/J/Cmax problem. In this problem there are n jobs to be processed on m machines. Each job contains m operations and must visit each of the m machines. The operations must be completed in a specific order and each operation can only be completed on one machine. Therefore, there is a strict precedence ordering of the machine sequence for each job. However, the machine sequences for different jobs may vary. The objective is to minimize the completion time of the job that completes last. The n/m/J/Cmax problem represents a significant departure from the automaker problems since there are no tooling constraints, alternative routings, sequence dependent setup

times, release times, or due times. However, the n/m/J/Cmax problem is still NP hard (see for example [33]) and represents a difficult scheduling problem that has been analyzed by a number of researchers ([30]). Experiments were conducted using the well known data sets from [27]. These problems contain 10 to 30 jobs and 5 to 15 machines. The RKGA found solutions that were on average within 1-2% of the best known solutions. Details of the implementation and comparison can be found in [31]. The good performance of the RKGA on the n/m/J/Cmax problem provides further validation of this solution approach and demonstrates that the methodology can be applied to multiple problem contexts. 4 Summary and Conclusions We have presented a scheduling algorithm that utilizes the random keys encoding within the context of a GA. This representation and algorithm are proven to find an optimal solution if run long enough. This algorithm was originally developed to solve complex scheduling problems that arise in the auto industry. Computational tests indicate that the RKGA performed well on all of the auto plaIlt prol)lems tested. The RKGA produced consistent results across the different random seed values. Tile median (over the ten seeds) best solution found was within 1.5%e of the lower bound for all of the problems in the first data set except 1.1 (it was 5.8%o) and was within 5 units of the tardiness lower bound for the second data set. The maximum deviation from tle lower bound over all seeds was less than 6.6% for all seven problems of data set one and 23 tardiness units for all five problems of the second data set. The RKGA consistently found schedules with less total tardiness than those found by 10

the other scheduling procedures that have been applied to these problems, given equivalent computational resources. Thus, the RKGA provides a good method for generating schedules for problemswith the complexities found in the automaker data sets. The robust nature of the RKGA was discussed also. The same methodology used for the automaker problems yielded high quality solutions when applied to the n/m/J/Cmax problem. Additionally, the RKGA can also be extended to include other problem complexities not found in the automaker data such as limited buffer space for each machine. The RKGA methodology can also be applied to other objective function measures. Combined with the uniformity of performance over random seeds and reasonable computation times, these results suggest that the RKGA could be useful in an application setting. 5 Acknowledgment This research was supported in part by National Science Foundation grants DPM-9018515 and DPMI-9308432 to the University of Michigan and by the National Science Foundation Graduate Fellowship Prograni. Thle alltlors would like to thank Rosemary D'Onofrio for helping with the data set preparation. References [1] Aarts. E. H. L., P. J. IM. Van Laarhoven, J. K. Lenstra, and N. L. J. Ulder, "A Computational Study of Local Search Algorithms for Job Shop Scheduling," ORSA Journal on

on Computing, 6, 118-125, (1994). [2] Adams, J., E. Balas, and D. Zawack, "The shifting bottleneck procedure for job shop scheduling," Management Science, 34, 391-401 (1988). [3] Back, T., F. Hoffmeister, and H. Schwefel, "A Survey of Evolution Strategies," Proceedings of the Fourth International Conference on Genetic Algorithms, 2-9, (1991). [4] Bagchi, S., S. Uckun, Y. Miyabe, and K. Kawamura, "Exploring Problem-Specific Recombination Operators for Job Shop Scheduling," Proceedings of the Fourth International Conference on Genetic Algorithms, 10-17, (1991). [5] Baker, K., Introduction to Sequencing and Scheduling, Wiley, 1974. [6] Baker, K., Elements of Sequencing and Scheduling, Amos Tuck School of Business Administration, Dartmouth College, Hanover, NH, 1995. [7] Baker, K. and J. Kanet. "Job Shop Scheduling With Modified Due Dates", Journal of Operations Management. 4, 11-22. (1983). [8] Barnes, J. W. and M. Laguna. "A Tabu Search Experience in Production Scheduling," Annals of Operations Research. 41. 141-15G, (1993). [9] Bean. J. C.. "Genetics and RanldoIll Keys for Sequencing and Optimization," ORSA Journal on Computing. 6. 154-160(). (1994). [10] Bean, J. C., J. R. Birge, J. Iittenthal, and C. Noon, "Matchup Scheduling with Multiple Resources. Release Dates and Disruptions," Operations Research, 39, 470-483, (1991). 01

[11] Brindle, A., "Genetic algorithms for function optimization" (Doctoral dissertation and Technical Report TR 81-2) Edmonton: University of Alberta, Department of Computer Science, 1981. [12] Cerny, V., "Thermodynamical Approach to the Traveling Salesman Problem: An Efficient Simulation Algorithm," Journal of Optimization Theory and Applications, 45, 41-51, (1985). [13] Cleveland, G.A. and S. F. Smith. "Using Genetic Algorithms to Schedule Flow Shop Releases," Proceedings of the Third International Conference on Genetic Algorithms, 160-169, (1989). [14] Davis, L., Handbook of Genetic Algorithms, (ed. L. Davis), Van Nostrand, 1991. [15] Dell'Amico M. and NI. Trubian. "App1lyiilg Tabu Search to the Job-Shop Scheduling Problem," Annals of Operations Research. 41. 231-252, (1993). [16] Du, J. and J.Y.-T. Leung. "lIiniIniiziIg Total Tardiness on One Machine is NP-Hard," Mathematics of Operations Research. 15. 483-495, (1991). [17] Glover. F.. "Tabu Search - Part I." ()RS.AI ournal on Computing, 1, 190-206, (1989). [18] Glover. F., "Tabu Search - Part II." ORSA Journal on Computing, 2, 4-32, (1990). [19] Goldberg, D. E. and R. Linglel Jr.. "Alleles. Loci. and the Traveling Salesman ProbleIm. 'Proceedings of the First Internatlonal Conference on Genetic Algorithms, 154-159, (1985). 90

[20] Goldberg, D. E., Genetic Algorithms in Search Optimization and Machine Learning, Addison Wesley, 1989. [21] Grabowski, J., E. Nowicki, and S. Zdrzalka, "A Block Approach for Single-Machine Scheduling with Release Dates and Due Dates," European Journal of Operational Research, 26, 278-285, (1986). [22] Grefenstette, J. J., R. Gopal, B. Rosmaita, and D. Van Gucht, "Genetic Algorithms for the Traveling Salesman Problem." Proceedings of the First International Conference on Genetic Algorithms, (1985). [23] Hoitomt, D. J., P. B. Luh. and IK. R. Pattipati, "A Practical Approach to Job-Shop Scheduling Problems," IEEE Transactions on Robotics and Automation, 9, 1-13, (1993). [24] Holland, J. H., Adaptation in Natural and Artificial Systems, The University of Michigan Press, Ann Arbor, 1975. [25] Jackson, J.R.,,"Scheduliln g Produlctioll Lille to Minimize Maximum Tardiness," Research Report 43. NfIlaageiletllt S(cincIes Research Program, UCLA, 1955. [26] Kirkpatrick, S.. C. D. Gelatt. Jr.. anld NI. P. Vecchi, "Optimization by Simulated Annealing." Science. 220. 671-68(). (19S3:). [27] Lawrence. S., "Resource Constraiiled Project Scheduling: An Experimental Investigation of Heuristic Sche(diling Tech.llii ies (Supplement)." Graduate School of Industrial Administration, Carnegie Melloii University. Pittsburgh, 1984.

[28] Michalewicz, Z., Genetic Algorithms + Data Structures = Evolution Programs, SpringerVerlag, 1994. [29] Nakano, R., "Conventional Genetic Algorithm for Job Shop Problems," Proceedings of the Fourth International Conference on Genetic Algorithms, 474-479, (1991). [30] Norman, B. A., "The Random Keys Genetic Algorithm for Complex Scheduling Problems," Unpublished Ph.D. Dissertation, University of Michigan, Ann Arbor, 1995. [31] Norman, Bryan A. and J. C. Bean, "A Random Keys Genetic Algorithm for Job Shop Scheduling Problems," Engineering Design and Automation, 3, No. 2, 145-156, (1997). [32] Nowicki, E. and C. Smutnicki, "A Fast Taboo Search Algorithm for the Job Shop Problem," Management Science, 42, 797-813, (1996). [33] Pinedo, M., Scheduling Theory, Algorithms, and Systems, Prentice Hall, 1995. [34] Shaefer, C. G. and S. J. Smith, "The ARGOT Strategy II: Combinatorial Optimizations," Technical Report, Thinking Machine Corporation, 1988. [35] Spears, W. M. and K. A. De Jong, "On the Virtues of Parameterized Uniform Crossover," Proceedings of the Fourth International Conference on Genetic Algorithms, 230-236, (1991). [36] Storer, R. H., S. D. Wu, and R. Vaccari, "New Search Spaces for Sequencing Problems With'Application to Job Shop Scheduling," Management Science, 38, No. 10, 1495 -1509, (1992). 9/1

[37] Storer, R. H., S. D. Wu, and I. Park, "Genetic Algorithms in Problem Space for Sequencing Problems," Proceedings of a Joint US-German Conference on Operations Research in Production Planning and Control, 584-597, (1992). [38] Syswerda, G. [1989], "Schedule Optimization Using Genetic Algorithms," in Handbook of Genetic Algorithms, (ed. L. Davis), Van Nostrand, 332-349, (1989). [39] Syswerda, G., "The Application of Genetic Algorithms to Resource Scheduling," Proceedings of the Fourth International Conference on Genetic Algorithms, 502-508, (1991). [40] Taillard, E., "Parallel Tabu Search Techniques," ORSA Journal on Computing, 6, 108 -117, (1994). [41] Van Laarhoven, P. J. M.. Aarts. E. H. L., and J. K. Lenstra, "Job Shop Scheduling by Simulated Annealing", Operations Research, 40, 113-125, (1992). [42] Whitley, D., T. Starkweather. and D. Fuquay, "Scheduling Problems and Traveling Salesman: The Genetic Edge Reconbination Operator," Proceedings of the Third International Conference on Genetic Algorithms, 133-140, (1989). [43] Widmer, M., "Job Shlop Schedulling withl Tooling Constraints: a Tabu Search Approach." Journal of the Operational Rtsearch Society, 42, 75-82, (1991).