改进二元分布估计算法求解置换流水车间调度问题  

Improved Binary Distribution Estimation Algorithm for Permutation Flow-Shop Scheduling Problem

作　　者：裴小兵[1] 赵衡 PEI Xiao-bing;ZHAO Heng(School of Management,Tianjin University of Technology,Tianjin 300384,China)

机构地区：[1]天津理工大学管理学院,天津300384

出　　处：《运筹与管理》2018年第10期193-199,共7页Operations Research and Management Science

基　　金：天津市哲学社会科学项目(TJYY17-013);国家创新方法工作专项项目:(2017IM060200)

摘　　要：针对置换流水车间调度这类组合最优化问题的求解,提出了一种改进二元分布估计算法(Improved binary estimation distribution algorithm,I-EDA)。算法以二元分布估计算法为架构,使用NEH(Nawaz-Enscore-Ham)启发式算法生成初始解,提高了初始解的质量;通过对优势解的统计采样构建位置矩阵模型和链接矩阵模型,依照两个矩阵模型的合并概率组合链接区块产生子代。提出了NEH插入式重组策略和基于位置概率的交换策略和两种全新局部搜索机制替代原二元分布估计算法的相邻交换法,以进一步筛选优势解。最后通过对Reeves标准测试集的仿真实验和算法比较验证了所提出算法的有效性。In this paper, an improved binary estimation distribution algorithm （I-EDA） is proposed to solve the combinatorial optimization problem such as permutation flow-shop scheduling. The algorithm takes binary distri-bution estimation algorithm as architecture, using NEH heuristic method to generate higher quality initial solution. The position matrix model and the link matrix model are constructed by statistics and sampling of the domi- nant solution, and the two matrix models are used to generate the offspring by combining the two probabilities. The two new local search mechanisms are proposed： NEH plug-in recombination strategy and location probabilistic exchange method instead of original adjacent exchange algorithm of the binary distribution estimation algorithm to further filter the optimal solution. The simulation results on Reeves suites and comparisons with other algorithms validate its excellent searching ability and efficiency of the proposed algorithm.

关 键 词：置换流水车间调度 二元分布估计算法 链接区块 NEH算法 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]