摘要
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 （√5＋1/2） .
基金
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.
