具有服务等级的可拒绝平行机排序问题

研究了将服务等级与拒绝费用2种模型复合起来的平行机排序问题.设有2台平行机M₁，M₂，加工速度相同；n个工件J₁，J₂，…，J_n分别按列表在线到达，每个工件J_j含有3个参数：加工长度t_j、拒绝费用p_j以及服务等级g_j=1，2.当工件到达时，可以接收加工，占用一定的加工时间；亦可拒绝，付出相应的罚值.目标为被接收工件的最大完工时间与被拒绝工件的总罚值之和最小.进一步，当且仅当g（M_i）≤g_j时，工件J_j可以分配给机器M_i加工，即机器M₁可以加工所有工件，机器M₂只能加工等级为g_j=2的工件，允许中断加工.设计了在线算法PH，并证明其竞争比为1+(√2)/(2)≈1.707，下界为1.618，上下界差约为0.089.

Parallel machine scheduling with service hierarchy and rejection

The on-line scheduling problem on two parallel machines with rejection and service hierarchy is investigated. Machines M₁, M₂ are provided with the same capabilities. Jobs come one by one over the list. Every job J_j is associated with its length t_j,penalty p_j and service hierarchy g_j=1,2. When a job arrives, it can either be assigned to a certain machine or be rejected by paying the penalty.The objective is to minimize the sum of the makespan of all accepted jobs and the total penalty of rejection. A job J_j can be assigned to machine M_i if and only if g(M_i)≤g_j, i.e, M₁ can process all jobs while M₂ can only process the jobs with g_j=2. Assuming that preemption is allowed, we propose an on-line approximation algorithm PH with competitive ratio 1+(√2