In this paper, we consider the scheduling with rejection. The objective functions are to minimize the maximum completion time of the processed ones when the total compression cost is given. Firstly, we prove that the problem 1|rej | C max /TCP is NP-hard, which implying that P m |rej | C max /TCP , 1 |rej , r j |C max /TCP , 1 |rej , on *** line |C max /TCP are all NP-hard. Secondly, for problem P m |rej | C max /TCP , we design a pseudopolynomial time dynamic programming algorithm that solves it exactly and an FPTAS (full polynomial time approximation scheme) when m is a constant. We also design a pseudopolynomial time dynamic programming algorithm and an FPTAS for the case of non-identical job arrival problem 1 |rej , r j |C max /TCP . In the end, we consider the on-line problem 1 |rej , on *** line |C max /TCP and prove that there doesn't exist any on-line algorithm with a constant competitive ratio for it, even if the jobs only have two different release times.