Scheduling a Flexible Batching Machine

摘要

Minimizing total completion time Σ C_j on normal batching machine is solvable in polynomial time for fixed B(B > 1), while Minimizing total completion time Σ C_j for arbitrary B and minimizing total weighted completion time Σ W_jC_j are open problems. In this paper, we consider the problem of scheduling jobs on a flexible batching machine in order to minimizing the total completion time. We prove that the problem is strongly NP-hard. Then the problem with agreeable is NP-hard even if there have three fixed capacities all the time.