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_{j=1}^{n}\, V_j)$ 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 $1|B \geq n|\sum_{j=1}^{n}V_j$ is NP-hard.