求解多处理器任务调度问题的改进差分进化算法

针对多处理器系统任务调度复杂问题, 在自适应差分进化算法基础上增加惯性速度分项, 提出一种称为惯性速度差分进化(IVDE) 的改进算法, 以避免陷入局部最优解. 结合启发式任务列表, 对算法的状态编码提出了处理器列表(PL)、部分偏序任务列表(PTL) 和全部任务列表(CTL) 等3 种形式. 通过求解随机生成的任务调度标准图和真实求解任务问题, 进行了数值仿真验证, 其中PTL-IVDE 算法相比蚁群优化(ACO) 算法、混合遗传算法(TLPLC-GA), 能快速求得更好的任务调度方案.

Multiprocessor task scheduling based on improved differential evolution algorithm

An improved differential evolution algorithm called inertial velocity differential evolution(IVDE) is proposed to solve the multiprocessor task scheduling problem(MTSP). The proposed algorithm consists of an additional inertial velocity factor based on the adaptive differential evolution algorithm with different evolution state representation schemes. Three different representations for the state of differential evolution algorithm, processor list(PL), partial ordered task list(PTL), and complete task list(CTL), are proposed for IVDE. Intensive simulation experiments are conducted on different random benchmarks and real-world application graphs. Comparisons are made with the ant colony optimizer(ACO) algorithm and the hybrid GA(TLPLC-GA) algorithm. The experimental results are satisfactory, and in most cases the presented method has a better makespan closer to global minimum compared to related works.