论文部分内容阅读
提出一种混合分布估计算法用于求解具有随机工时的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种算法作为混合分布估计算法的对比算法,仿真试验结果表明混合分布估计算法在优化性能方面具有明显优势。
A hybrid distribution estimation algorithm is proposed to solve Job shop scheduling problem with random working hours. The stochastic Job shop scheduling problem (SJSSP) mathematical model is established and the evaluation method of random expectation value model is given. In order to improve the population diversity, we introduced the (μ + λ) - evolutionary strategy (ES) recombination and mutation process into the Estimation of distribution algorithm (EDA) to construct a hybrid distribution estimation algorithm. ES-EDA . According to the process-based encoding adopted, the definition of the inheritance rate of the parent process is defined and the individual recombination method based on the inheritance rate of the parent process is designed for the recombination process. This method not only enables the offspring to inherit the success of the parent Excellent features, while avoiding the generation of illegal solutions. Based on the standard examples FT06, FT10 and FT20, three sets of examples with random processing time are selected and five kinds of algorithms in the literature are selected as the comparison algorithm of the mixture distribution estimation algorithm. The simulation results show that the hybrid distribution estimation algorithm has better performance in optimizing performance Has obvious advantages.