THE NP-HARDNESS OF MINIMIZING THE TOTAL LATE WORK ON AN UNBOUNDED BATCH MACHINE.

We consider the problem of minimizing the total late work (Σ_j=1ⁿ V_j) on an unbounded batch processing machine, where V_j = min{T_j, p_j} and T_j = max{C_j - d_j, O}. 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 ≥ n∣ Σ_j=1ⁿV_j is NP-hard. [ABSTRACT FROM AUTHOR]