Parallel-Machine Scheduling Problem under the Job Rejection Constraint (Extended Abstract)

Given m identical machines and n independent jobs, each job J(j) has a processing time (or size) p(j) and a penalty e(j). A job can be either rejected, in which case its penalty is paid, or scheduled on one of the machines, in which case its processing time contributes to the load of that machine. The objective is to minimize the makespan of the schedule for accepted jobs under the constraint that the total penalty of the rejected jobs is no more than a given bound B. In this paper, we present a 2-approximation algorithm within strongly polynomial time and a polynomial time approximation scheme whose running time is O(nm O(1/e(2)) + mn(2)) for the general case. Moreover, we present a fully polynomial time approximation scheme for the case where the number of machines is a fixed constant. This result improves previous best running time from O(n(m+2) /epsilon(m)) to O(1/epsilon(2m+3) + mn(2)).