摘要
讨论一特殊情况的两台可拒绝同型机在线排序问题的近似算法.设有两台同型机,工件逐个到达,可以被接受加工,消耗一定的加工时间tj,也可以被拒绝,但要付出一定的罚值pj,目标是要使被加工工件的最大完工时间(makespan)和拒绝工件的罚值之和最小.假设每个工件的罚值和加工长度成固定的比例α∈[0,+∞),即pj=αtj,针对工件加工不可中断情形,设计出算法NPRL,证明其参数竞争比,同时又给出问题下界,它们均为α的分段函数.算法NPRL在α∈0,2 2∪[1,+∞)已达到最优.
This paper investigates a special case of the on-line scheduling problem on two identical machines with rejection. The job comes one by one, and when a job arrives, one can either assign it to a certain machine or reject it by paying out the penalty, The objective is to minimize the sum of the makespan produced by the accepted jobs and the total penalty of the jobs which have been rejected. We assume that the processing time of each job and its penalty forms the regular proportion denoted by α∈[0,+∞). Preemption is not allowed. For this version, we present an on-line algorithm NPRL and prove the competitive ratio. Finally, a lower bound of this problem is proposed which shows that in the interval of α∈[0,√2/2)∪[1,+∞) our algorithm is optimal.
出处
《数学的实践与认识》
CSCD
北大核心
2006年第6期176-181,共6页
Mathematics in Practice and Theory
关键词
在线排序
可拒绝
不可中断
同型机
竞争比
on-line scheduling
rejection
non-preemptive
identical machines
competitive