Abstract:

 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.

Key words: online scheduling, identical machines, hierarchy, rejection, competitive ratio