文献类型：期刊文章

作　　者：闵啸[1]

机构地区：[1]嘉兴学院数学与信息科学学院,浙江嘉兴314001

出　　处：《数学的实践与认识》

年　　份：2006

卷　　号：36

期　　号：6

起止页码：176-181

语　　种：中文

收录情况：BDHX、BDHX2004、CSCD、CSCD_E2011_2012、MR、RCCSE、ZGKJHX、ZMATH、核心刊

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

关 键 词：在线排序  可拒绝  不可中断  同型机 竞争比

分 类 号：O223] TN710.2[数学类]