Parallel-serial batch no-wait flowshop scheduling for makespan minimization

This paper investigates a parallel-serial batch no-wait flowshop scheduling problem with the objective of minimising the makespan. The system consists of a parallel-batch machine at the first stage, where the batch processing time is determined by the longest job, and a serial-batch machine at the second stage, where the batch processing time is equal to the sum of job processing times within this batch plus a constant setup time. The batch capacity is limited, and all jobs have identical processing times on the second machine. We propose a mixed-integer linear programming model and establish a series of structural properties that precisely characterise the form of optimal schedules. Based on these properties, we propose a dynamic programming algorithm that computes optimal solutions in polynomial time O(n4). Computational experiments demonstrate that, compared with the existing algorithm, the proposed algorithm consistently finds optimal solutions, while being significantly more efficient than Gurobi.