研究了工件带有拒绝费用的两台同类机在线算法,两台机器的速度分别为 1 和 s ,s ∈ [ 1 , +∞ ),工件逐个到达,当工件到达时,可以选择被分配到机器上进行加工并花费一定的加工时间;也可以被拒绝,但此时需付出一定的拒绝费用。进一步假定每个工件的加工时间与拒绝费用成固定比例 α ( α ≥0 ),即 pj =αtj 。目标函数为使被加工工件的最大完工时间与被拒绝工件的总罚值之和最小,工件的加工不可中断。本研究设计一种在线算法 URLS ,并证明该算法的竞争比和下界均为关于参数 α 的分段函数,且当 * 时上下界相吻合,算法达到最优。(注：*处代表公式)