拒绝可缓冲的2台同类机半在线排序问题的近似算法

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

Approximate algorithm of semi online scheduling on two uniform machines with a rejecting buffer