Preemptive multiprocessor scheduling with rejection

The problem of online multiprocessor scheduling with rejection was introduced by Bartal et al. (SIAM J, Discrete Math. 13(1) (2000) 64-78). They show that for this problem the competitive ratio is 1 + phi approximate to 2.61803, where phi is the golden ratio. A modified model of multiprocessor scheduling with rejection is presented where preemption is allowed. For this model, it is shown that better performance is possible. An online algorithm which is (4 + root 10/3 < 2.38743-competitive is presented. We prove that the competitive ratio of any online algorithm is at least 2.12457. We say that an algorithm schedules obliviously if the accepted jobs are scheduled without knowledge of the rejection penalties. We also show a lower bound of 2.33246 on the competitive ratio of any online algorithm which schedules obliviously. As a subroutine in our algorithm, we use a new optimal online algorithm for preemptive scheduling without rejection. This algorithm never achieves a larger makespan than that of the previously known algorithm of Chen et al. (Oper, Res. Lett. 18(3) (1995) 127-131), and achieves a smaller makespan for some inputs. <(c)> 2001 Elsevier Science B.V. All rights reserved.