Abstract：The on-line scheduling problem on two parallel machines with rejection and service hierarchy is investigated. Machines M1, M2 are provided with the same capabilities. Jobs come one by one over the list. Every job Jj is associated with its length tj,penalty pj and service hierarchy gj=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 Jj can be assigned to machine Mi if and only if g(Mi)≤gj, i.e, M1 can process all jobs while M2 can only process the jobs with gj=2. Assuming that preemption is allowed, we propose an on-line approximation algorithm PH with competitive ratio 1+(√2)/(2)≈1.707 while the lower bound is 1.618.
荣建华. 具有服务等级的可拒绝平行机排序问题[J]. 浙江大学学报（理学版）, 2016, 43(6): 685-688.
RONG Jianhua. Parallel machine scheduling with service hierarchy and rejection. Journal of ZheJIang University(Science Edition), 2016, 43(6): 685-688.
[1] BARTAL Y, LEONARDI S, MARCHETTI-SPACCAMELA A, et al. Multiprocessor scheduling with rejection[J]. SIAM J on Discrete Mathematics,2000,13:64-78.
[2] HE Y,MIN X.On-line uniform machine scheduling with rejection[J]. Operations Research Transactions,2009,13(1):29-36.
[3] DOSA G, HE Y. Preemptive and non-preemptive on-line algorithms for scheduling with rejection on two uniform machines[J]. Computing,2006,76:149-164.
[4] JIANG Y W, HE Y, TANG C M. Optimal online algorithm for scheduling on identical machines under a grader of service[J]. Journal of Zhejiang University:Science A,2006,7(3):309-314.
[5] PARK J, CHANG S Y, LEE K. Online and semi-online scheduling of two machines under a grader of service provision[J]. Operations Research Letters,2006,34:692-696.
[6] JIANG Y. Online scheduling on parallel machines with two GoS levels[J]. Journal of Combinatorial Optimization,2008,16:28-38.
[7] ZHANG A, JIANG Y, TAN Z. Online parallel machines scheduling with two hierarchies[J]. Theoretical Computer Science,2009,410:3597-3605.
[8] TAN Z, ZHANG A. A note on hierarchical scheduling on two uniform machines[J]. Journal of Combinatorial Optimization, 2010,20:85-95.
2016, Vol. 43 
