W-prize-collecting scheduling problem on a single machine

In this paper, we consider the W-prize-collecting scheduling problem on a single machine, where each job has a profit. The objective is to minimize the makespan of the accepted jobs and the total rejection cost of the rejected jobs, conditional on their total profit no less than a given threshold. We first analyze the computational complexities when all jobs have the same parameter. Then, we present a 2-approximation algorithm. Furthermore, we provide two pseudo-polynomial time algorithms. Finally, a fully polynomial time approximation scheme (FPTAS) is given for this problem. Our numerical tests indicate that both dynamic programming algorithms can easily solve large-size problems.