Preemptive multiprocessor scheduling with rejection (Q5958131)

The problem of online multiprocessor scheduling with rejection was introduced by \textit{Y. Bartal, S. Leonardi, A. Marchetti-Spaccamela, J. Sgall} and \textit{L. Stougie} [SIAM J. Discrete Math. 13, No. 1, 64-78 (2000; Zbl 0936.68012)]. They show that for this problem the competitive ratio is \(1+\phi \approx 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+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 \textit{B. Chen, A. van Vliet} and \textit{G. J. Woeginger} [Oper. Res. Lett. 18, No. 3, 127-131 (1995; Zbl 0855.90069)], and achieves a smaller makespan for some inputs.