改进二元分布估计算法求解置换流水车间调度问题
|
摘要
针对置换流水车间调度这类组合最优化问题的求解,提出了一种改进二元分布估计算法(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 distribution 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 dominant 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.
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 distribution 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 dominant 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.
引文
[1] Garey E L,Johnson D S,Sethi R. The complexity of flow-shop and job-shop scheduling[J]. Mathematics of Operations Research(S0364-765X),1976,1(1):117-129.
[2]Ruiz R,Maroto C. A comprehensive review and evaluation of permutation flowshop heuristics[J]. European Journal of Operational Research, 2005, 165(2):479-494.
[3]张先超,周泓.变参数量子进化算法及其在求解置换流水车间调度问题中的应用[J].计算机集成制造系统,2016,(03):774-781.
[4]Liu H,Gao L,Pan Q. A hybrid particle swarm optimization with estimation of distribution algorithm for solving permutation flowshop scheduling problem[J]. Expert Systems with Applications,2011,38(4):4348-4360.
[5]刘延风,刘三阳.基于蚁群优化的置换流水车间调度算法[J].系统工程与电子技术,2008,(09):1690-1692.
[6]刘长平,叶春明.置换流水车间调度问题的萤火虫算法求解[J].工业工程与管理,2012,(03):56-59+65.
[7]Liu Y F,Liu S Y. A hybrid discrete artificial bee colony algorithm for permutation flowshop scheduling problem[J]. Applied Soft Computing, 2013, 13(3):1459-1463.
[8]Larranaga P,Lozano J A. Estimation of distribution algorithms:A new tool for evolutionary computation[M].Springer Science&Business Media,2002.
[9]王圣尧,王凌,方晨,等.分布估计算法研究进展[J].控制与决策,2012,27(7):961-966.
[10]Ceberio J,Irurozki E,Mendiburu A,et al. A review on estimation of distribution algorihms in permutation-based combinatorial optimization problems[J]. Progress in Artificial Intelligence,2012,1(1):103-117.
[11]王圣尧,王凌,许烨,等.求解混合流水车间调度问题的分布估计算法[J]. Acta Automatica Sinica,2012,38(3):437-443.
[12]孙良旭,曲殿利,刘国莉.置换流水车间调度问题的两阶段分布估计算法[J].计算机工程与应用,2017,53(2):64-71.
[13]李作成,钱斌,胡蓉,等.求解一类异构并行机调度问题的分布估计算法[J].计算机集成制造系统,2013,19(9):2202-2212.
[14]Chang P C,Chen M H. A block based estimation of distribution algorithm using bivariate model for scheduling problems[J]. Soft Computing, 2014, 18(6):1177-1188.
[15]Nawaz M,Enscore E E,Ham I. A heuristic algorithm for the m-machine,n-job flow-shop sequencing problem[J]. Omega,1983,11(1):91-95.
[16]Chang P C,Chen M H,Tiwari M K,et al. A blockbased evolutionary algorithm for flow-shop scheduling problem[J]. Applied Soft Computing,2013,13(12):4536-4547.
[17]Reeves C R. A genetic algorithm for flowshop sequencing[J]. Computers and Operations Research(S0305-0548),1995,22(1):5-13.
[18]Chang P C,Chen S H,Fan C Y,et al. Generating artificial chromosomes with probability control in genetic algorithm for machine scheduling problems[J]. Annals of Operations Research,2010,180(1):197-211.
[2]Ruiz R,Maroto C. A comprehensive review and evaluation of permutation flowshop heuristics[J]. European Journal of Operational Research, 2005, 165(2):479-494.
[3]张先超,周泓.变参数量子进化算法及其在求解置换流水车间调度问题中的应用[J].计算机集成制造系统,2016,(03):774-781.
[4]Liu H,Gao L,Pan Q. A hybrid particle swarm optimization with estimation of distribution algorithm for solving permutation flowshop scheduling problem[J]. Expert Systems with Applications,2011,38(4):4348-4360.
[5]刘延风,刘三阳.基于蚁群优化的置换流水车间调度算法[J].系统工程与电子技术,2008,(09):1690-1692.
[6]刘长平,叶春明.置换流水车间调度问题的萤火虫算法求解[J].工业工程与管理,2012,(03):56-59+65.
[7]Liu Y F,Liu S Y. A hybrid discrete artificial bee colony algorithm for permutation flowshop scheduling problem[J]. Applied Soft Computing, 2013, 13(3):1459-1463.
[8]Larranaga P,Lozano J A. Estimation of distribution algorithms:A new tool for evolutionary computation[M].Springer Science&Business Media,2002.
[9]王圣尧,王凌,方晨,等.分布估计算法研究进展[J].控制与决策,2012,27(7):961-966.
[10]Ceberio J,Irurozki E,Mendiburu A,et al. A review on estimation of distribution algorihms in permutation-based combinatorial optimization problems[J]. Progress in Artificial Intelligence,2012,1(1):103-117.
[11]王圣尧,王凌,许烨,等.求解混合流水车间调度问题的分布估计算法[J]. Acta Automatica Sinica,2012,38(3):437-443.
[12]孙良旭,曲殿利,刘国莉.置换流水车间调度问题的两阶段分布估计算法[J].计算机工程与应用,2017,53(2):64-71.
[13]李作成,钱斌,胡蓉,等.求解一类异构并行机调度问题的分布估计算法[J].计算机集成制造系统,2013,19(9):2202-2212.
[14]Chang P C,Chen M H. A block based estimation of distribution algorithm using bivariate model for scheduling problems[J]. Soft Computing, 2014, 18(6):1177-1188.
[15]Nawaz M,Enscore E E,Ham I. A heuristic algorithm for the m-machine,n-job flow-shop sequencing problem[J]. Omega,1983,11(1):91-95.
[16]Chang P C,Chen M H,Tiwari M K,et al. A blockbased evolutionary algorithm for flow-shop scheduling problem[J]. Applied Soft Computing,2013,13(12):4536-4547.
[17]Reeves C R. A genetic algorithm for flowshop sequencing[J]. Computers and Operations Research(S0305-0548),1995,22(1):5-13.
[18]Chang P C,Chen S H,Fan C Y,et al. Generating artificial chromosomes with probability control in genetic algorithm for machine scheduling problems[J]. Annals of Operations Research,2010,180(1):197-211.