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

Parallel Machine Scheduling with Hierarchical and Rejection

研究了工件具有服务等级且可拒绝的平行机排序问题.设有两台平行机,加工速度相同;n个工件分别按列表在线到达,每个工件含有三个参数:加工长度,拒绝费用以及服务等级g_j=1,2.当且仅当g(Mi)≤gj时,工件J_j可由机器M_i加工,且加工不允许中断.进一步,当工件到达时,可以选择被加工,花费一定的加工时间;也可以被拒绝,此时要付出相应的罚值.目标为使被接收工件的最大完工时间与被拒绝工件的总罚值之和最小.文中设计出在线算法H,并证明算法的竞争比为1+(2^(1/2)/2)≈1.707,下界为5/3≈1.667,上下界大约相差0.04.

An on-line scheduling problem on two parallel machines with rejection and hierarchical is investigated.Machines are provided with the same capabilities.Jobs come one by one over list.Euch job is associated with its length,penalty and hierarchical. A job Ji can be assigned to machine Mi if and only if g（Mi）≤gj .Preemption is not allowed.When a job arrives,it can either be assigned to a certain machine or rejected by paying out the penalty.The objective is to minimize the sum of the makespan produced by the accepted jobs and the total penalty of the jobs which have been rejected. An on-line approximation algorithms H is designed with competitive ratio 1＋（√2/2）≈1.707 while the lower bound being 5/3≈1.667.