融合代理模型和差分进化算法的并行机动态调度方法

来源：计算机集成制造系统杂志2017年第1期北京时间：

作者：张嘉琦,曹政才,刘民

单位：1.北京化工大学信息科学与技术学院2.清华大学自动化系

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

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

基金资助：国家自然科学基金资助项目(51375038);高等学校博士学科点专项科研基金博导类资助项目(20130010110009);吉林大学符号计算与知识工程教育部重点实验室开放课题资助项目(93K172014K05);北京市自然科学基金资助项目(4162046)。