求解随机Job Shop调度问题的混合分布估计算法

提出一种混合分布估计算法用于求解具有随机工时的Job shop调度问题。建立随机Job shop调度问题(Stochastic Job shop scheduling problem, SJSSP)数学模型并给出随机期望值模型的评价方法。为提高种群多样性，将(μ+λ)-进化策略(Evolutionary strategy, ES)的重组、变异过程引入分布估计算法(Estimation of distribution algorithm, EDA)，构造一种混合分布估计算法，ES-EDA。根据所采用的基于工序的编码方式，对父代工序继承率的概念进行了定义，并为重组过程设计基于父代工序继承率的个体重组方法，该方法不仅能使子代有效继承父代的优良特征，同时可避免非法解的产生。在标准算例FT06、FT10、FT20的基础上构造加工时间随机的3组算例，并选择文献中的5种算法作为混合分布估计算法的对比算法，仿真试验结果表明混合分布估计算法在优化性能方面具有明显优势。

Hybrid Estimation of Distribution Algorithm for Solving the Stochastic Job Shop Scheduling Problem

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.