两台同型机M_1,M_2, 加工速度一致, 但拥有不同的加工能力，用其服务等级表示, M_1的服务等级为1, M_2的服务等级为2. 工件j按列表在线到达，每个工件带有三个参数: 长度t_j,等级g_j=1或2, 罚值p_j. 当j到达时, 可以被拒绝, 但要付出相应的罚值p_j, 也可以被接受并分配给服务等级不超过该工件等级的机器加工，事实上等级为1的工件只能分给M_1加工, 等级为2的工件可以分给M_1或M_2加工, 加工不允许中断. 目标为极小化加工工件集的最晚完工时间(makespan)和拒绝工件集的总罚值之和. 对于该问题给出了一个在线算法, 其竞争比为11/6, 以及问题一个下界5/3.

 Two identical machines M_{1}, M_{2} with same speed but different processing capabilities labeled by their hierarchies are provided. M_{1} has the hierarchy 1 and that of M_2 is 2. Jobs come one by one over list. Each job has three parameters: size t_{j}, hierarchy g_{j}=1,2, penalty p_{j}. When a job arrives, which can be rejected by paying its penalty or be accepted and scheduled on some machine whose hierarchy does not exceed the job's hierarchy. In fact, the job with hierarchy 1 can only be assigned to M_{1}, but the job with hierarchy 2 can be assigned to M_{1} or M_{2} . Preemption is not allowed. The objective is to minimize the sum of makespan yielded by all accepted jobs and the total penalties of all rejected jobs. For this problem, we present an online algorithm with a competitive ratio 11/6 and a relative lower bound 5/3.