求解随机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种算法作为混合分布估计算法的对比算法，仿真试验结果表明混合分布估计算法在优化性能方面具有明显优势。

关键词：随机Job Shop调度问题、混合分布估计算法、父代工序继承率、进化策略

分类号：TP18(自动化基础理论)

资助基金：国家自然科学基金资助项目51075337,51475383。

在线出版日期：2015-12-08（万方平台首次上网日期，不代表论文的发表时间）

页数：共9页

页码：27-35