The random keys genetic algorithm for complex scheduling problems.

Abstract

How a company schedules its production activities can have a significant effect on its ability to meet its objectives including on-time delivery and machine utilization. To schedule such complex facilities we propose a genetic algorithm approach that is applicable to a wide range of scheduling problems. Genetic algorithms mimic the "survival of the fittest" paradigm from evolutionary biology. This particular genetic algorithm utilizes the random keys encoding which uses random variates distributed between zero and one to encode the problem. This genetic algorithm also utilizes a unique set of operators including: elitism, Bernoulli crossover, post tournament selection, real valued mutation, and immigration. This combination produces the random keys genetic algorithm which is quite different than other genetic algorithm approaches discussed in the literature. Initially, we apply the random keys genetic algorithm to some complex scheduling problems containing multiple, nonidentical machines, ready times, due times, sequence dependent setup times, tooling constraints, and the total tardiness objective. The random keys genetic algorithm proves to be effective, relative to other methods, for solving these problems. Further computational test results indicate the robust nature of the algorithm demonstrating its effectiveness for a number of other scheduling problems. We also introduce solution methodologies for the sequencing and scheduling of operations for parallel machine tools. Parallel machine tools are Computer Numerically Controlled metal working machines that have multiple spindles and multiple tooling heads which permit the simultaneous machining of one or multiple parts. The presence of simultaneous machining introduces complexities not typically found in scheduling problems and creates several new problem types. To handle these complexities, we propose two different heuristic solution methodologies. The first heuristic method utilizes priority dispatching rules that are modified to reflect the unique characteristics of parallel machine tools. The second heuristic method applies genetic algorithms to solve these problems. For the most difficult problem types we propose a hybrid genetic algorithm that utilizes both genetic algorithms and other operations research ideas. Computational testing indicates that both the dispatching rule and genetic algorithm methods find good solutions in a reasonable amount of computation time. For the most complicated problem variations the hybrid genetic algorithm yields the best performance.