预知两种信息的两台并行处理器半在线调度

• 作者: 何勇 卢璐 谈之奕
• 来源期刊: 浙江大学学报（理学版）
• 学科: 工学
• 关键词: 并行处理器 近似算法 半在线 竞争比
• 年，卷（期）: 2005,（6）
• 所属期刊栏目: 数学与计算机科学
• 页码范围: 638-643
• 页数: 6页
• 分类号: O221.7|O223|TP393
• 字数: 7181字
• 语种: 中文
• DOI: 10.3321/j.issn:1008-9497.2005.06.010

摘要

在调度理论中,问题常常被分为"在线"和"离线"两类,但在实际生产生活中,情况经常介于两者之间,即预先知道任务的部分信息,人们希望通过这些附加的部分信息改进算法的性能,此类问题即为"半在线"问题.文章讨论了经典并行处理器调度的两个半在线问题,目标为极大化处理器最早完工时间.对已知所有任务总加工时间和最大任务加工时间的半在线问题,给出了竞争比为4/5的最优半在线算法;对已知所有任务总加工时间,并且任务按加工时间非增顺序到达的半在线问题,给出了竞争比为8/9的最优半在线算法.从结果可以看出,预知两种信息比只知道一种信息的情况能更有效地解决问题.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	何勇	浙江大学数学系	511	9054	45.0	65.0
2	谈之奕	浙江大学数学系	8	151	4.0	8.0
3	卢璐	浙江大学数学系	1	4	1.0	1.0