Clustering and Scheduling Method Based on Task Duplication  

作　　者：HE Kun ZHAO Yong 

机构地区：[1]Department of Control Science and Engineering, Huazhong University of Science and Technology, Wuhan 430074, Hubei, China

出　　处：《Wuhan University Journal of Natural Sciences》2007年第2期260-266,共7页武汉大学学报（自然科学英文版）

基　　金：Supported by the National Natural Science Foundation of China (7047107);the Ph.D. Programs Foundation of Ministry of Education of China (20020487046)

摘　　要：A new heuristic approach that resembles the evolution of interpersonal relationships in human society is put forward for the problem of scheduling multitasks represented by a directed acyclic graph. The algorithm includes dynamic-group, detachgraph and front-sink components. The priority rules used are new. Relationship number, potentiality, weight and merge degree are defined for cluster＇s priority, and task potentiality for tasks＇ priority. Experiments show the algorithm could get good result in short time. The algorithm produces another optimal solution for the classic MJD benchmark. Its average performance is better than five latter-day representative algorithms, especially six benchmarks of the nines.A new heuristic approach that resembles the evolution of interpersonal relationships in human society is put forward for the problem of scheduling multitasks represented by a directed acyclic graph. The algorithm includes dynamic-group, detachgraph and front-sink components. The priority rules used are new. Relationship number, potentiality, weight and merge degree are defined for cluster＇s priority, and task potentiality for tasks＇ priority. Experiments show the algorithm could get good result in short time. The algorithm produces another optimal solution for the classic MJD benchmark. Its average performance is better than five latter-day representative algorithms, especially six benchmarks of the nines.

关 键 词：CLUSTERING directed acyclic graph task duplication task scheduling 

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