A genetic algorithm as applied to the jobshop scheduling

The genetic algorithm (GA) is a method for approximate optimization simulating the process of natural evolution, and it has been successfully applied to several optimization problems, such as traveling salesman problems and pattern recognition problems, which are difficult so solve exactly by conventional methods of the mathematical programming. However, few researchers have been reported on application of GA to scheduling problems. This paper proposes a GA for jobshop scheduling problems. The Keynote points of the present algorithm are how to represent individuals and how to calculate the fitness of each individual. The genetic operators are standard ones, e.g., a pure selection, a 2-point crossover and a mutation. The paper confirms effectiveness of the GA through several computational experiments where its ability in computational time and quality of obtained solutions are compared with those of a branch-and-bound method and some typical heuristics. [In Japanese.]