一特殊情形不可中断的两台可拒绝同型平行机在线排序问题

• 作者: 闵啸
• 来源期刊: 数学的实践与认识
• 学科: 数学
• 关键词: 在线排序 可拒绝 不可中断 同型机 竞争比
• 年，卷（期）: 2006,（6）
• 所属期刊栏目: 应用
• 页码范围: 176-181
• 页数: 6页
• 分类号: O1
• 字数: 4104字
• 语种: 中文
• DOI: 10.3969/j.issn.1000-0984.2006.06.028

摘要

讨论一特殊情况的两台可拒绝同型机在线排序问题的近似算法.设有两台同型机,工件逐个到达,可以被接受加工,消耗一定的加工时间tj,也可以被拒绝,但要付出一定的罚值pj,目标是要使被加工工件的最大完工时间(makespan)和拒绝工件的罚值之和最小.假设每个工件的罚值和加工长度成固定的比例α∈[0,+∞),即pj=atj,针对工件加工不可中断情形,设计出算法NPRL,证明其参数竞争比,同时又给出总是下界,它们均为α的分段函数.算法NPRL在α∈[0,2/2)U[1,+∞)已达到最优.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	闵啸	嘉兴学院数学与信息科学学院	20	105	7.0	9.0