Abstract: Aiming at the problems of insufficient local search and long computational period in existing evolutionary computation for solving parallel machine scheduling,a fast solution by combining Differential Evolution (DE) algorithm with surrogate model was proposed with problem decomposition and estimated evaluation strategy.Machine-code based differential evolution algorithm was used to search roughly for the machine allocation of upper level.Through analyzing the key characteristics of lower level single machine issue,the surrogate model was built for predicting scheduling performance,which could use approximate value instead of time-consuming exact algorithm to reduce computational cost in excessive evaluations.Based on job sequence-code and multi-mutation strategies,DE algorithm was utilized to determine job processing order in devices under a fixed allocation scheme,and the purpose of two-stage synchronous optimization was achieved.Simulation experiments indicated that the proposed method was more excellent than traditional methods,particularly in larger-size problem instance,which could obtain better solution quality.

Key words: parallel machine scheduling, differential evolution algorithm, surrogate model, synchronous optimization

摘要： 针对目前进化计算求解并行机动态调度中的局部搜索能力不足、计算周期长等问题,引入问题分解思想和估计评价策略,提出一种基于差分进化算法与代理模型相融合的快速求解方法。采用基于机器编码的差分进化算法对上层设备选择问题进行粗搜索。分析下层单机问题的关键性特征,构建能够预测调度性能指标优劣的代理模型,利用估计近似值取代费时的精确求解,降低繁冗评价过程带来的计算代价。在最佳分配方案的指导下,基于工件编码和多变异策略的差分进化算法确定设备上工件加工的前后顺序,实现设备分配与工件排序两个决策层的同步优化。通过仿真实验表明,该方法优于传统的并行机求解方法,尤其对于大规模并行机调度问题的求解质量更好。

关键词: 并行机调度, 差分进化算法, 代理模型, 同步优化