两台可拒绝同类机在线排序问题近似算法的参数性能比

• 作者: 何勇 闵啸
• 来源期刊: 高校应用数学学报A辑
• 学科: 数学
• 关键词: 在线排序 近似算法 参数性能比
• 年，卷（期）: 2000,（3）
• 页码范围: 326-332
• 页数: 7页
• 分类号: O223
• 字数: 3872字
• 语种: 中文
• DOI: 10.3969/j.issn.1000-4424.2000.03.012

摘要

讨论两台可拒绝同类机在线排序问题的近似算法.设两台机器的速度之比为s(≥1).工件逐个到位,可以被加工,也可以被拒绝,但要付出相应的罚值pj·并且只有在安排完当前工件之后,下一个工件才到达.目标函数要求被加工工件集的最迟工件完工时间与被拒绝工件集的总罚值之和达到最小.文中设计出线性时间的RLS(α)算法,并证明了其关于s的参数紧界,这个界于s＝1以及s≥(√5+1)/2均是不可改进的.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	何勇	浙江大学应用数学系	511	9054	45.0	65.0
2	闵啸	浙江经济高等专科学校数学教研室	1	1	1.0	1.0