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

Estimation of distribution algorithm for a kind of heterogeneous parallel machine scheduling problem

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

Aiming at a kind of complex heterogeneous parallel machine scheduling problem that was Heterogeneous Parallel Machine Scheduling Problem with Job Processing Constraints and Sequence-dependent Setup Times （HPMSP_JPCSST） existed in process industry,an Estimation of Distribution Algorithm （EDA） was proposed to minimize the makespan criterion.By making reference to Double King Division Spring Multiplication （DKDSM） method,a new update mode of probability model was presented,and the sampling probability model was constructed by crossing and fusing the sub-probability model Thus the evolutionary direction of population was guided to improve the global search depth of the algorithm.An Insert-based mutation operation was designed to maintain the population diversity level,and the global search wide of the algorithm was improved.To enhance the local exploitation ability,the local search based on insertion method and first move strategy was introduced.Computational experiments and comparisons demonstrated the effectiveness and the robustness of proposed algorithm.