Scheduling with Rejection and Non-Identical Job Arrivals

In this paper, we address the scheduling problem with rejection and non-identical job arrivals, in which we may choose not to process certain jobs and each rejected job incurs a penalty. Our goal is to minimize the sum of the total penalties of the rejected jobs and the maximum completion time of the processed ones. For the off-line variant, we prove its NP-hardness and present a PTAS, and for the on-line special case with two job arrivals, we design a best possible algorithm with competitive ratio . The research is supported by National Natural Science Fundation of China under Grant NO. 10671108 and Province Natural Science Foundation of Shandong under Grant NO. Y2005A04.