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.