ICS Theory Group

ICS 269, Winter 1997: Theory Seminar


14 Mar 1997:
More Multiprocessor Scheduling with Rejection
Steve Seiden, ICS, UC Irvine

Multiprocessor scheduling with rejection was introduced by Bartal, Leonardi, Marchetti-Spaccamela, Sgall and Stougie in SODA`96. These authors show a deterministic 2.61803-competitive algorithm for this problem, and show that no algorithm achieves a lower competitive ratio. We introduce a new variant of scheduling with rejection where the accepted jobs may be be scheduled preemptively as in Chen, van Vliet and Woeginger ESA`94. We show that with preemption it is possible to do better. We present a deterministic algorithm for preemptive multiprocessor scheduling with rejection and show that it is 2.38743-competitive.