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

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

研究了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的参数竞争比.

The semi online scheduling problems on two uniform machines with a rejecting buffer are studied. Suppo- sing there are two uniform machines M1 and M2 with speed 1 and s∈[1,＋∞）, and the preemption is not allowed. A sequence of jobs J= {J1 ,J2 … ,Jn } arrive one by one over the list. Each job has two parameters, the first one is the size （processing time） denoted by tj, the second one is the rejecting penalty（in the first model） or the rejecting profit （in the second model）, both denoted by Pi. When Jj arrives, it can be accepted and assigned to some ma- chine, or be rejected by paying its penalty pj and or gaining a certain profit pj , in two models respectively. The goal of the first model is to minimize the sum of the maximum load of machines and the total penalty of the rejected jobs, while, the second model is required to maximize the sum of smallest load of machines and the total profit yielded by all rejecting jobs. Moreover, a rejecting buffer B with the length k≥1 which can contain up to k revealed jobs is available in accepting or rejecting decisions. When a new job arrives, it can be stored in B temporarily until the buffer is full. At this moment, one of the jobs in the buffer or the currently incoming one must be decided which one is rejected. These two models are semi online scheduling with rejecting model which solves the relaxation problems of the relevant classic online machine scheduling model with rejection. We design the approximation algorithm and prove the related competitive ratio.