一个可中断两台可拒绝同型机半在线排序问题

• 作者: 张玉才 闵啸
• 来源期刊: 浙江大学学报（理学版）
• 学科: 数学
• 关键词: 半在线 排序 可拒绝 可中断 同型机 近似算法 竞争比
• 年，卷（期）: 2007,（5）
• 所属期刊栏目: 数学与计算机科学
• 页码范围: 509-514
• 页数: 6页
• 分类号: O223
• 字数: 5177字
• 语种: 中文

摘要

讨论一个两台可拒绝同型机半在线排序问题的近似算法.设有两台同型机,工件逐个到达,可以被接收加工,消耗一定的加工时间tj,也可以被拒绝,但要付出一定的罚值pj,目标是使被加工工件集的最大完工时间(makespan)和被拒绝工件集的罚值之和最小.此外,进一步假定每个工件的罚值和加工长度事先形成固定的比例α∈[0,+∞),即pj=αt,针对工件加工可中断情形,设计出近似算法PRH,证明其竞争比.同时又给出该问题的下界,它们均为α的分段函数,且算法PRH在α∈[0,√2/2)U[5/6,+∞)达到最优.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	张玉才	嘉兴学院人文社科训练中心	9	45	3.0	6.0
2	闵啸	嘉兴学院数学与信息科学学院	20	105	7.0	9.0