Batch scheduling in the no-wait two-machine flowshop to minimize the makespan

We consider a scheduling problem where a set of jobs are simultaneously available for processing in a no-wait two-machine flowshop. The objective is to minimize the makespan, i.e. the maximum completion time of the jobs. The operations of all jobs are processed on both machines in batches. A constant setup time is incurred whenever a batch is formed on the machines. The processing time of a batch is defined as the setup time plus the sum of all processing times of the jobs it contains. The completion time of a job is defined as the time at which the batch containing it is completely processed on machine two. The no-wait scheduling problem in the two-machine flowshop without batching is known as polynomially solvable. We show that several restricted versions of the problem under study in this paper are strongly NP-hard, which implies that the general problem is also strongly NP-hard. We then establish some interesting properties and exploit them to design solution methods for two special cases.