In this paper, we consider the W-prize-collecting scheduling problem on parallel machines. In this problem, we are given a set of n jobs, a set of m identical parallel machines and a value W. Each job \(J_j\) has a processing time, a profit and a rejection penalty. Each job is either accepted and processed on one of the machines without preemption, or rejected and paid a rejection penalty. The objective is to minimize the sum of the makespan of accepted jobs and the penalties of rejected jobs, and at the same time the total profit brought by accepted jobs is not less than W. We design a 2-approximation algorithm for the problem based on the greedy method and the list scheduling algorithm.
