基于任务复制的进化调度算法  

Task Duplication Based Evolutionary Scheduling Algorithm

作　　者：姚文胜[1] 薛广涛[1] 张冠华[1] 尤晋元[1] 

机构地区：[1]上海交通大学计算机科学与工程系,上海200030

出　　处：《上海交通大学学报》2004年第5期755-758,762,共5页Journal of Shanghai Jiaotong University

基　　金：国家自然科学基金(60173033);总装备部国防科技重点实验室基金(51484030301JW0301);上海市科技发展基金(03DZ15027)资助项目

摘　　要：并行程序任务调度是NP完全问题.已有的进化调度算法不能很好利用任务复制这一重要手段.为此,利用染色体直接编码和间接编码的优点,并结合任务图的知识,使进化调度算法的搜索能力得到增强,同时染色体的解码过程也得到简化.通过与同类算法的性能比较,表明了本算法在调度问题中的有效性.The problem of scheduling parallel program tasks on network of workstation is known to be NP-complete. It is difficult for the existing GA-based scheduling algorithms to handle task duplications. To overcome the weakness, a new evolutionary scheduling algorithm was proposed, which makes use of the merits of both direct chromosome encoding and indirect chromosome encoding, as well as the knowledge of task digraph. As a result, the searching ability of the algorithm is enhanced and the decoding process of chromosomes is simplified. The algorithm was compared with the same kind of scheduling algorithm in terms of makespan and running-time. The experimental results show the effectiveness of the algorithm to the scheduling problem.

关 键 词：任务复制 任务调度 遗传算法 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]