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

Multiprocessor task scheduling based on improved differential evolution algorithm

作　　者：邱晓红[1] 胡玉婷[1] 李渤[1] 

机构地区：[1]江西理工大学软件学院,南昌330013

出　　处：《控制与决策》2016年第2期217-224,共8页Control and Decision

基　　金：江西省自然科学基金项目(20132BAB201044);江西省高等学校科技落地计划项目(KJLD12071)

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

关 键 词：多处理器 任务调度 差分进化 算法 惯性 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]