超立方体网络中任务调度的一个新近似算法  

NEW ALGORITHM FOR JOBS SCHEDULING IN HYPERCUBE NETWORK

作　　者：肖建华[1] 陈建二[1] 陈松乔[1] 

机构地区：[1]中南工业大学计算机科学系,湖南长沙410083

出　　处：《小型微型计算机系统》2001年第8期913-916,共4页Journal of Chinese Computer Systems

基　　金：国家海外杰出青年自然科学基金( 6 992 82 0 1);长江学者奖励计划资助

摘　　要：本文研究超立方体中的多处理器任务调度问题 .我们研究 L DL PT算法并指出为什么这种算法对一些实例具有最差的逼近度 ,然后提出一种类似装箱算法的新算法— BPA算法 ,证明该算法和 L DL PT算法在相互最差逼近度中具有互补性质 .最后 ,组合这两种算法的基本方法提出了一种求解问题的新算法— CBPA算法 ,并证明新算法具有比L DLIn this paper, we study the problem of multi processor job scheduling on hypercube networks. We first study the LDLPT algorithm and indicate why the algorithm performs poorly for certain situations. We then propose a new algorithm, the Bin Packing Style algorithm (BPA), and show that the BPA algorithm complements the LDLPT algorithm. Finally we combine the ideas in the two algorithms and develop a new algorithm CBPA for the problem. We show that the new algorithm performs better than the LDLPT algorithm.

关 键 词：互联网 超立方体网络 任务调度 新近似算法 LDLPT算法 

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