石家庄铁道大学 四方学院, 石家庄 051132;南京农业大学 理学院, 南京 210095
研究了工件带有拒绝费用的3台平行机半在线算法。工件逐个到达,当工件到达时可以被接收加工,消耗一定的加工时间,也可以被拒绝,但此时要付出一定的拒绝费用。进一步假定工件的加工时间与拒绝费用事先成固定比例α(α≥=0)。目标为被接收工件的最大完工时间与被拒绝工件的总罚值之和最小。针对工件加工可中断情形,设计出半在线算法ARH,并证明算法ARH的竞争比为关于参数α的分段函数,且为紧界。
荣建华,彭丽, 张玲玲, 侯丽英 .一个可中断三台可拒绝平行机半在线排序问题 [J].重庆师范大学学报自然科学版,2016,(3):15-19