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

【Abstract】 Two identical machines M₁, M₂ with same speed but different processing capabilities labeled by their hierarchies are provided. M₁ has the hierarchy 1 and that of M₂ is 2. Jobs come one by one over list. Each job has three parameters: size tj, 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₁, but the job with hierarchy 2 can be assigned to M₁ or M₂. 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 ratio11/6 and a relative lower bound 5/3. Keywords online scheduling, identical machines,hierarchy, rejected, competitive ratio更多还原