摘要
多处理机任务调度问题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.
出处
《计算机学报》
EI
CSCD
北大核心
2009年第8期1631-1636,共6页
Chinese Journal of Computers
基金
国家自然科学基金(60872039
10771060)资助~~
关键词
多处理机任务调度
规则调度
近似算法
NP-难问题
multiprocessor-job scheduling
normal scheduling
approximation algorithm
NP-hard problem
