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

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