两台可中断同类机可拒绝半在线排序问题的近似算法

• 作者: 刘静 王玉青 闵啸
• 来源期刊: 浙江大学学报（理学版）
• 学科: 数学
• 关键词: 同类机 半在线 可拒绝 竞争比
• 年，卷（期）: 2010,（5）
• 页码范围: 519-523
• 分类号: O223
• 字数: 4658字
• 语种: 中文
• DOI: 10.3785/j.issn.1008-9497.2010.05.009

摘要

研究一个两台同类机可拒绝半在线排序问题,机器速度一个为1,另一个为s∈[1,+∞),加工允许中断.当工件到达时,可以将其接受加工,占用一定的机器负荷,也可以将其拒绝,付出相应的罚值,目标为使被接受工件集产生的makespan和被拒绝工件集的总罚值之和最小.问题进一步假定每个工件在选择是否加工时有两个拒绝尺度,各自独立决策,最后选择较好的结果作为最终输出.笔者设计了算法H,得到其关于s的参数竞争比为s+2s+1,优于只有一个拒绝尺度的经典情形.最后又给出问题的一个下界(s+1)2s2+s+1,上下界的最大差距在s=1时达到0.167.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	王玉青	嘉兴学院数学与信息工程学院	5	4	2.0	2.0
2	闵啸	嘉兴学院数学与信息工程学院	20	105	7.0	9.0
3	刘静	嘉兴学院数学与信息工程学院	27	89	4.0	8.0