| 超立方体网络中任务调度的一个新近似算法 |
| |
| 引用本文： | 肖建华,陈建二,陈松乔.超立方体网络中任务调度的一个新近似算法[J].小型微型计算机系统,2001,22(8):913-916. |
| |
| 作者姓名： | 肖建华 陈建二 陈松乔 |
| |
| 作者单位： | 中南工业大学计算机科学系 |
| |
| 基金项目： | 国家海外杰出青年自然科学基金（69928201）、长江学者奖励计划资助 |
| |
| 摘 要： | 本文研究超立方体中的多处理器任务调度问题，我们研究LDLPT算法并指出为什么这种算法对一些实例具有最差的逼近度，然后提出一种类似装箱算法的新算法-BPA算法，证明该算法和LDLPT算法在相互最差逼近度中具有互补性质，最后，组合这两种算法的基本方法提出了一种求解问题的新算法-CBPA算法，并证明新算法具有比LDLPT算法更好的逼近度。
|
| 关 键 词： | 互联网 超立方体网络 任务调度 新近似算法 LDLPT算法 |
| 文章编号： | 1000-1220(2001)08-0913-04 |
NEW ALGORITHM FOR JOBS SCHEDULING IN HYPERCUBE NETWORK |
| |
| XIAO,Jian,hua,CHEN,Jian,er,CHEN,Song,qiao.NEW ALGORITHM FOR JOBS SCHEDULING IN HYPERCUBE NETWORK[J].Mini-micro Systems,2001,22(8):913-916. |
| |
| Authors: | XIAO Jian hua CHEN Jian er CHEN Song qiao |
| |
| Abstract: | In 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. |
| |
| Keywords: | Hypercube Sub hypercube Job scheduling NP hard problem Approximating Algorithm LDLPT algorithm LDF algorithm |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
