摘要
多处理器系统上的最优任务分配的研究是有效利用系统资源处理实际问题的热点课题，文中在考虑任务可分和任务不可分的两种多处理器最优任务分配问题上，首先提出了这两个问题在处理器的个数大于１时都是ＮＰ－完全问题，其次给出了一个有效的近似算法，并证明了该算法所产生的解与最优解的近似比小于２．
The separable and nonseparable problem associated with a multiprocessor system is studied for optimizing task assignment. Both problems are shown to the NP hard when the number of processors is greater than one. The approximate ratio of the proposed algorithm is less than two.
出处
《西安交通大学学报》
EI
CAS
CSCD
北大核心
1999年第4期98-101,共4页
Journal of Xi'an Jiaotong University
基金
国家自然科学基金
关键词
多处理器
最优任务分配
计算复杂性
近似算法
multiprocessor system
optimal task assignment
computational complexity
approximate algorithm
