Abstract: A hybrid estimation of distribution algorithm(EDA) is proposed to solve the stochastic job shop scheduling problem (SJSSP) with stochastic processing times. The mathematic model of the SJSSP and the evaluation method of stochastically expected model are constructed. To enhance the population diversity, the recombination and mutation process of (μ+λ)-Evolutionary strategy are incorporated in the EDA, thus a hybrid EDA, i.e. ES-EDA is constructed. Based on the encoding method of chromosome adopted in this research, the concept of Inherit rate of the operations in parent individual is defined. Then a new recombination method based on the Inherit rate of the operations in parent individual is designed. This recombination method can not only make the offspring inheriting the excellent characteristics of the parent effectively, but also avoiding infeasible solutions. Three problem instances with stochastic processing times for simulation experiment are constructed based on the benchmark instances FT06, FT10 and FT20, the comparison with the simulation results obtained by the 5 algorithms in literatures shows that the ES-EDA has significant advantages in aspect of optimal performance.

Key words: evolutionary strategy, hybrid estimation of distribution algorithms, inherit rate of the operations in parent chromosome, stochastic Job Shop scheduling problem