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

发布时间：2018-04-20 07:44

本文选题：并行机调度 + 差分进化算法　；参考：《计算机集成制造系统》2017年01期

【摘要】：针对目前进化计算求解并行机动态调度中的局部搜索能力不足、计算周期长等问题,引入问题分解思想和估计评价策略,提出一种基于差分进化算法与代理模型相融合的快速求解方法。采用基于机器编码的差分进化算法对上层设备选择问题进行粗搜索。分析下层单机问题的关键性特征,构建能够预测调度性能指标优劣的代理模型,利用估计近似值取代费时的精确求解,降低繁冗评价过程带来的计算代价。在最佳分配方案的指导下,基于工件编码和多变异策略的差分进化算法确定设备上工件加工的前后顺序,实现设备分配与工件排序两个决策层的同步优化。通过仿真实验表明,该方法优于传统的并行机求解方法,尤其对于大规模并行机调度问题的求解质量更好。
[Abstract]:In order to solve the problems of local search ability and long calculation period in evolutionary computing for dynamic scheduling of parallel machines, the idea of problem decomposition and estimation and evaluation strategy are introduced. A fast solution method based on the fusion of differential evolution algorithm and agent model is proposed. The differential evolution algorithm based on machine coding is used to search the upper layer device selection problem. Based on the analysis of the key characteristics of the lower layer single machine problem, the agent model which can predict the scheduling performance index is constructed, and the estimated approximate value is used to replace the time-consuming and accurate solution to reduce the computational cost brought by the redundant evaluation process. Under the guidance of the optimal allocation scheme, a differential evolutionary algorithm based on job coding and multi-mutation strategy is used to determine the processing sequence of the workpiece on the equipment, and to realize the synchronous optimization of the two decision layers of the equipment allocation and job sorting. The simulation results show that the proposed method is superior to the traditional parallel machine solution method, especially for large-scale parallel machine scheduling problems.
【作者单位】：北京化工大学信息科学与技术学院;清华大学自动化系;
【基金】：国家自然科学基金资助项目(51375038) 高等学校博士学科点专项科研基金博导类资助项目(20130010110009) 吉林大学符号计算与知识工程教育部重点实验室开放课题资助项目(93K172014K05) 北京市自然科学基金资助项目(4162046)~~
【分类号】：TP18

【参考文献】