The NP-hardness of minimizing the total late work on an unbounded batch machine

We consider the problem of minimizing the total late work (SUM Vj) on an unbounded batch processing machine, where Vj = min {Tj, pj} and Tj = max {Cj - dj, 0}. The batch processing machine can process up to B (B ≥ n) jobs simultaneously. The jobs that are processed together form a batch, and all jobs in a batch start and complete at the same time, respectively. For a batch of jobs, the processing time of the batch is equal to the largest processing time among the jobs in this batch. In this paper, we prove that the problem is NP-hard.