工件从大到小到达的带处理器费用的半在线调度算法

• 作者: 何勇 蔡圣义
• 来源期刊: 自动化学报
• 学科: 工学
• 关键词: 半在线 算法 竞争比 调度 处理器费用
• 年，卷（期）: 2003,（6）
• 所属期刊栏目: 短文
• 页码范围: 917-921
• 页数: 5页
• 分类号: TP301
• 字数: 3735字
• 语种: 中文

摘要

对大多数调度问题来说,处理器集往往是事先给定的,而且在算法进行过程中,它是不变的.Imreh和Noga第一次提出了在调度中考虑处理器有费用的模型.他们研究了所谓的List Model问题,给出了竞争比为1.618的在线算法,同时证明了任意在线算法的竞争比至少是4/3.该文研究List Model问题的一个半在线情形,即假设工件是从大到小到达的,给出一个竞争比为3/2的半在线算法.同时证明对该问题的这一半在线情形,任意半在线算法的竞争比至少是4/3.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	何勇	浙江大学数学系	511	9054	45.0	65.0
2	蔡圣义	浙江大学数学系	4	19	3.0	4.0