# ICS 269, Winter 1996: Theory Seminar

## 15 March 1996:

Multiprocessor Scheduling with Rejection

Joseph Wang, ICS, UC Irvine

(Based on a paper by Y. Bartal, S. Leonardi, A.
Marchetti-Spaccamela, J. Sgall, and L. Stougie, 7th *SODA*,
1995, pp. 95-103.)
We consider a version of multiprocessor scheduling with the
special feature that jobs may be rejected for a certain penalty. An
instanace of the problem is given by m identical parallel machines
and a set of *n* jobs, each job characterized by a processing
time and a penalty. In the on-line version the jobs arrive one by
one and we have to schedule or reject a job before we have any
information about future jobs. The objective is to minimize the
makespan of the schedule for accepted jobs plus the sum of the
penalties of rejected jobs.

The main result is a 1+phi = 2.618 competitive algorithm for the
on-line version of the problem, where phi is the golden ratio. A
matching lower bound show that this is the best possible algorithm
working for all *m*. For fixed *m* we give improved
bounds, in particular for *m* = 2 we give an optimal phi =
1.618 competitive algorithm.

For the off-line problem we present a fully polynomial
approximation scheme for fixed *n* and an approximation
algorithm which runs in time O(*n* log *n*) for arbitrary
*m* and guarantees 2 - 1/*m* approximation ratio.

This talk will focus on the first two results of this paper.