文献类型：期刊文章

作　　者：闵啸[1] 张玉才[2]

机构地区：[1]嘉兴学院数学与信息科学学院,浙江嘉兴314001 [2]嘉兴学院人文社科训练中心,浙江嘉兴314001

出　　处：《浙江大学学报（理学版）》

年　　份：2007

卷　　号：34

期　　号：5

起止页码：509-514

语　　种：中文

收录情况：AJ、BDHX、BDHX2004、CAB、CAS、CSA、CSA-PROQEUST、CSCD、CSCD2011_2012、IC、JST、MR、PROQUEST、RCCSE、SCOPUS、WOS、ZGKJHX、ZMATH、ZR、核心刊

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

关 键 词：半在线 排序 可拒绝  可中断  同型机 近似算法  竞争比

分 类 号：O223]