基于遗传算法的任务分配与调度

TASK MATCHING AND SCHEDULING BY USING GENETIC ALGORITHMS

应用遗传算法 (GAs)进行任务分配与调度已被越来越多的学者所关注 .针对传统遗传算法中初始解群构造和遗传算子的局限性 ,结合遗传算法和演化策略的优点 ,提出了一个异构系统中任务分配与调度的进化算法 .在列表编码知识表示的基础上 ,首先对初始解群的构造给出了一种相对均衡的生成方法 ,然后有针对性地设计出 3个遗传算子 ,即由标准算子改进的杂交算子 (IMCX)、基于一个调度内任务交换的内部杂交算子 (INCX)和一种类似变异的迁移算子 (m igration) ,最后给出了算法的仿真结果 .

Task matching and scheduling by using genetic algorithm based approaches have been the attractive problems, while the construction of initial population and genetic operators in most of the previous work have some limitations. In this paper, an improved algorithm is proposed based on the integration of genetic algorithm (GA) and evolution strategy (ES). Using permutation representation, the improved algorithm concentrates on constructing the initial population and on designing genetic operators, such as internal crossover(INCX) which swaps two list tasks within a schedule, improved crossover(IMCX) which exchanges tasks between two schedules, and migration which transfers a task from a list to another within a schedule as a kind of mutation operator. Finally, the simulation results of the algorithm and conclusions are given.