Minimizing makespan in flowshops with pallet requirements: Computational complexity

We establish the computational complexity of the problem of minimizing makespan in a flowshop, where each job requires a pallet the entire time, from the start of its first operation until the completion of the last operation. We prove that the problem is NP-hard in the strong sense for m ≥ 2 and K ≥ 3, and for m ≥ 3 and K ≥ 2, where m is the number of machines and K is the number of pallets in the system.