Multiprocessor scheduling with rejection

We consider a version of multiprocessor scheduling with the special feature that jobs may be rejected at a certain penalty. An instance of the problem is given by m identical parallel machines and a set of n jobs, with each j ob characterized by a processing time and a penalty. In the on-line version the jobs become available one by one and we have to schedule or reject a j ob before we have any information about future jobs. The objective is to mi nimize the makespan of the schedule for accepted jobs plus the sum of the p enalties of rejected jobs. The main result is a 1 + phi approximate to 2.618 competitive algorithm for the on-line version of the problem, where phi is the golden ratio. A match ing lower bound shows that this is the best possible algorithm working for all m. For fixed m we give improved bounds; in particular, for m = 2 we giv e a phi approximate to 1.618 competitive algorithm, which is best possible. For the off-line problem we present a fully polynomial approximation scheme for fixed m and a polynomial approximation scheme for arbitrary m. Moreove r, we present an approximation algorithm which runs in time O(n log n) for arbitrary m and guarantees a 2 - 1/m approximation ratio.