Approximate algorithm of semi online scheduling on two uniform machines with a rejecting buffer(拒绝可缓冲的2台同类机半在线排序问题的近似算法)

Abstract

研究了 2个拒绝可缓冲的同类机半在线排序问题.设有2台同类机M1,M2，速度分别为1和s∈[1，+ ∞),加工不允许中断，工件Jj按照列表在线到达，每个工件带有2个参数：加工长度tj、拒绝罚值pj（模型1中）或拒绝获益pj（模型2中），当工件到达时，可以被接受并分给某台机器加工，也可以被拒绝，需付出一定的罚值（模型1)或取得一定的收益（模型2），目标是在第1个模型中要求极小化机器最大负荷和拒绝工件的总罚值之和；第2个模型中要求极大化机器最小负荷和总收益之和.此外，在接受或拒绝的决策环节上提供一个缓冲区B，其容量为k≥1,任一时刻至多可以存放k个工件，当工件到达时，若缓冲区未饱和，则可暂时存入B；若已饱和，则必须在新工件和缓冲区内工件中选择一个进行接受或拒绝的决策.本模型所研究的是经典可拒绝模型中的一个松弛问题，属半在线可拒绝模型.最后针对以上2个模型，分别给出了s在区间[1，+∞）上的近似算法，并证明了各自关于s的参数竞争比.

Keywords

• 同类机
• 半在线
• 可拒绝
• 排序
• 缓冲区
• 竞争比