A genetic algorithm and the Monte Carlo method for stochastic job-shop scheduling

摘要

This paper proposes a method for solving stochastic job-shop scheduling problems using a hybrid of a genetic algorithm in uncertain environments and the Monte Carlo method. First, the genetic algorithm in uncertain environments is applied to stochastic job-shop scheduling problems where the processing times are treated as stochastic variables. The roulette strategy is adopted for selecting the optimum solution having the minimum expected value for makespan. Applying crossover based on Giffler and Thompson's algorithm results in two offspring inheriting the ancestor's characteristics as the operation completion times averaged up to the parent's generation. Individuals having very high frequency through all generations are selected as the good solutions. Second, the Monte Carlo method is effectively used for finding out the approximately optimum solution among these good solutions.