A genetic algorithm approach to solving stochastic job-shop scheduling problems

摘要

This paper proposes a method for solving stochastic job-shop scheduling problems based on a genetic algorithm. The genetic algorithm was expanded for stochastic programming. In this expansion, the fitness function is regarded as representing fluctuations that may occur under stochastic circumstances specified by the distribution functions of stochastic variable. In this study, the Roulette strategy is adopted for selecting the optimum solution in terms of the expected value. Within this algorithm, it is expected that the individual that appears most frequently must give the optimum solution. The effectiveness of this approach is confimed by applying it to stochastic job-shop scheduling problems. I compare the approximately optimum solutions found by this approach with the truly or approximately optimum solutions obtained by other conventional methods, and discuss the performance and effectiveness of this approach.