应用团划分方法改进多处理机任务近似调度

• 作者: 黄金贵
• 来源期刊: 计算机工程与应用
• 学科: 工学
• 关键词: 多处理机任务 调度 近似算法 NP难问题 团划分
• 年，卷（期）: 2009,（4）
• 所属期刊栏目: 博士论坛
• 页码范围: 4-8
• 页数: 5页
• 分类号: TP393
• 字数: 4234字
• 语种: 中文
• DOI: 10.3778/j.issn.1002-8331.2009.04.002

摘要

研究多处理机任务调度模型Pmㄧfix,pj=1ㄧCmax,即在m个处理杌系统中调度n个时间长度都为1的多处理机任务,每个任务指派到所需一组处理机上不可剥夺地执行.这类问题在网络并行计算、多播系统及工程规划等领域都有广泛的应用,但早已被证明为NP难问题,而且也不存在常数近似算法.基于团划分方法构造了该问题的多项式时间近似算法,通过模拟实验进行了验证,和最大宽度优先(LWF)算法相比,该算法花费时间较长,近似比性能要好.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	黄金贵	湖南师范大学计算机教学部	14	69	5.0	8.0