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

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

摘要

研究多处理机任务调度模型Pm|fix,pj=1|Cmax,即在m个处理机系统中调度n个时间长度都为1的多处理机任务,每个任务指派到所需一组处理机上不可剥夺地执行.其更一般的问题是Pm|fix|Cmax,在网络并行计算、多播系统及工程规划等领域都有广泛的应用.该问题早已证明为NP难问题,而且也不存在常数近似算法.基于部分调度和宽度优先原则构造了该问题的一个多项式时间近似算法,并从理论上证明了该算法在最坏情况下的近似比为√2m+1,优于已有文献中2√m的目前最好结果.

作者信息

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