Parallel-batch scheduling with release dates and rejection on identical parallel machines

We consider the parallel-batch scheduling with release dates and rejection on identical parallel machines, in which, each job is either accepted and processed on one of the m machines or rejected by paying a rejection penalty. The objective is to minimise the makespan of the accepted jobs plus the total rejection penalty of the rejected jobs. This problem is strongly NP-hard. We first present an approximation algorithm with a constant performance ratio 4. Furthermore, we design and analyse a (3+1m−1mb)-approximation algorithm, where m and b are the number of machines and the capacity of each batch. Then we propose pseudo-polynomial-time dynamic programming algorithms and polynomial-time approximation schemes for the case with identical release dates and the case with k distinct release dates, respectively.