P_4|fix|C_(max)问题的最优规则调度算法  

An Optimal Algorithm for Normal Scheduling on P_4|fix|C_(max)

作　　者：黄金贵[1] 李荣珩[1] 

机构地区：[1]湖南师范大学计算机教学部,长沙410081

出　　处：《计算机学报》2009年第8期1631-1636,共6页Chinese Journal of Computers

基　　金：国家自然科学基金(60872039;10771060)资助~~

摘　　要：多处理机任务调度问题Pm|fix|Cmax(m3)是典型的强NP难问题,由于其在并行环境中的实际意义而受到越来越多的关注.但在一般情形下,寻求该问题的较为理想的近似算法是极其困难的,通常从较少处理机数的系统着手研究.对于m=4的情形,文中研究了P4|fix|Cmax的规则调度算法,通过引入组调度技术,给出了该问题的一个线性时间的4/3-近似算法,并证明了该算法是4-处理机系统中的最优规则调度算法.With the advanced of the heterogeneous parallel computing technology, Multiprocessor-job scheduling problem has attracted much attention recently. Because of complexity of the general multiprocessor system, it is impossibility to find the approximation scheduling algorithm with the ideal performance. The paper is focused on the smaller processors system, that 4-processor system and its scheduling problem P4｜fix｜Cmax. With introduced the Normal scheduling, and Group scheduling, a linear time algorithm is developed with the 4/3 approximation ratio. It is proved that normal scheduling come from the algorithm is the optimal normal scheduling in 4-processor systems.

关 键 词：多处理机任务调度 规则调度 近似算法 NP-难问题 

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