Preemptive multiprocessor scheduling with rejection

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.

Recommendations

Cites work

Cited in

(59)

This page was built for publication: Preemptive multiprocessor scheduling with rejection

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5958131)