任意处理时间的多处理机任务调度近似算法

摘要：

研究多处理机任务调度模型Pm|fix|Cmax,即在m个处理机系统中调度n个多处理机任务,每个任务指派到所需一组处理机上不可剥夺地执行.该问题应用广泛但早已证明为NP难问题,而且也不存在常数近似算法.在E.Bampis等人提出的SplitRound技术基础上,提出了该问题的一个改进的多项式时间近似算法,并从理论上证明了该算法在最坏情况下的近似比为2

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

所属期刊栏目：44

分类号：TP393(计算技术、计算机技术)

资助基金：湖南省自然科学基金the Natural Science Foundation of Hunan Province of China under Grant 06JJ50105

在线出版日期：2009-02-10（万方平台首次上网日期，不代表论文的发表时间）

页数：共3页

页码：7-9