GENETIC SCHEDULING OF TASK GRAPHS

被引:13
作者
BENTEN, MST
SAIT, SM
机构
[1] Department of Computer Engineering, King Fahd University of Petroleum and Minerals, Dhahran
关键词
D O I
10.1080/00207219408926072
中图分类号
TM [电工技术]; TN [电子技术、通信技术];
学科分类号
0808 ; 0809 ;
摘要
A genetic algorithm for scheduling computational task graphs is presented. The problem of assigning tasks to processing elements as a combinatorial optimization is formulated, and a heuristic based on a genetic algorithm is presented. The objective function to be minimized is the 'time on completion' of all tasks. Results are compared with those published in the literature and with randomly generated task graphs whose optimal schedules are known a priori.
引用
收藏
页码:401 / 415
页数:15
相关论文
共 25 条
[1]   COMPARISON OF LIST SCHEDULES FOR PARALLEL PROCESSING SYSTEMS [J].
ADAM, TL ;
CHANDY, KM ;
DICKSON, JR .
COMMUNICATIONS OF THE ACM, 1974, 17 (12) :685-690
[2]  
ALMAASRANI AMA, 1993, THESIS KING FAHD U P
[3]   LOWER BOUND ON THE NUMBER OF PROCESSORS AND TIME FOR SCHEDULING PRECEDENCE GRAPHS WITH COMMUNICATION COSTS [J].
ALMOUHAMED, MA .
IEEE TRANSACTIONS ON SOFTWARE ENGINEERING, 1990, 16 (12) :1390-1401
[4]   SCHEDULING WITH SUFFICIENT LOOSELY COUPLED PROCESSORS [J].
ANGER, FD ;
HWANG, JJ ;
CHOW, YC .
JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING, 1990, 9 (01) :87-92
[5]  
ASHFORD L, 1990, J PARALLEL DISTRIBUT, V10, P333
[6]  
BENTEN MST, 1989, THESIS U COLORADO BO
[7]   EFFICIENT SCHEDULING ALGORITHMS FOR ROBOT INVERSE DYNAMICS COMPUTATION ON A MULTIPROCESSOR SYSTEM [J].
CHEN, CL ;
LEE, CSG ;
HOU, ESH .
IEEE TRANSACTIONS ON SYSTEMS MAN AND CYBERNETICS, 1988, 18 (05) :729-743
[8]  
COFFMAN EG, 1972, COMPUTER JOB SHOP SC
[9]  
COFFMAN EG, 1972, ACTA INFORM, V1, P200, DOI DOI 10.1007/BF00288685
[10]   GENETIC PLACEMENT [J].
COHOON, JP ;
PARIS, WD .
IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS, 1987, 6 (06) :956-964