求解一类异构并行机调度问题的分布估计算法

摘要

针对流程工业中广泛存在的一类复杂异构并行机调度问题,即带工件加工约束和序相关设置时间的异构并行机调度问题,提出一种分布估计算法,用于最小化最早完工时间.首先,合理借鉴了蜜蜂养殖中“双王分区春繁法”的思想,提出一种新的概率模型更新方式,并通过子种群概率模型的交叉融合构造采样概率模型,进而引导种群进化方向,用于提高算法全局搜索的深度;其次,设计了一种基于插入法的变异操作,用于保持分布估计算法的种群多样性水平,进而提高算法全局搜索的宽度;最后,引入基于插入法和首次改进跳出原则的局部搜索方法来增强算法的局部开发能力.仿真实验和算法比较验证了所提算法的有效性和鲁棒性.