Abstract: We consider scheduling problems with rejection for both single machine and identical machines in this paper. For the single machine problems, each job has penalty \alpha times of its processing time. If jobs have release dates, the problem of minimizing the sum of makespan and total penalty can be solved in polynomial time. If all jobs arrive at time zero, the problem of minimizing the sum of total completion time and total penalty also can be solved in polynomial time. For the identical machines problems, jobs arrive over time at two different time points. The objective is to minimize the sum of makespan and total penalty. We design on-line approximation algorithms with competitive ratios 2 or 4-2/m for the two cases when the number of machines is two or m, respectively.

Key words: scheduling, rejection, on-line algorithm, competitive ratio