带机器准备时间的平行机ordinal排序及近似算法

• 作者: 何勇 谈之奕
• 来源期刊: 应用数学学报
• 学科: 数学
• 关键词: 半在线排序 近似算法 最坏情况界
• 年，卷（期）: 2002,（2）
• 页码范围: 223-229
• 页数: 7页
• 分类号: O22
• 字数: 5741字
• 语种: 中文
• DOI: 10.3321/j.issn:0254-3079.2002.02.004

摘要

本文研究带机器准备时间的m台平行机ordinal在线排序问题.讨论了在极小化最大机器完工时间和极小化最大工件完工时间两种目标下的不同下界和相应的在线近似算法.对第一个目标,我们得到了3/2的下界和最坏情况界为2-1/m的近似算法.对第二个目标,我们得到了最坏情况界为m的最好近似算法.我们还对一些特殊情况进行了分析.

作者信息

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