Parallel-machine scheduling with release dates and rejection

In this paper, we consider the parallel‐machine scheduling problem with release dates and rejection. A job is either rejected, in which case a rejection penalty has to be paid, or accepted and processed on one of the m identical parallel machines. The objective is to minimize the sum of the makespan of the accepted jobs and the total rejection penalty of the rejected jobs. When m is a fixed constant, we provide a pseudo‐polynomial‐time algorithm and a fully polynomial‐time approximation scheme for the problem. When m is arbitrary, we present a 2‐approximation algorithm for the problem.