Parallel-machine scheduling with job-dependent cumulative deterioration effect and rejection

We study a parallel-machine scheduling problem in which job rejection is allowed and the actual processing time of a job depends on the sum of certain parameters associated with the jobs scheduled earlier. The goal is to minimize the sum of the makespan of the accepted jobs and total rejection penalty of the rejected jobs. When the number of machines is fixed, we develop an exact dynamic programming algorithm and a fully polynomial-time approximation scheme for solving it. When the number of machines is restricted to one, we reformulate the problem as a variant of a half-product problem, which allows us to design a fully polynomial-time approximation scheme with the best possible running time.