Lot Scheduling to Minimize Makespan in Permutation Flowshop

This work investigates the permutation flowshop scheduling problem where each operation of any job is performed on a lot processing machine with uniform capacity. More than one job can be processed in the same lot, and the operations of all jobs in the lot are of the same completion time. Any job can be split and processed in consecutive lots, if necessary. The objective is to minimize the maximum completion time of the last operation of job, i.e., the makespan. We first examine the complexity of the considered problem, and provide a polynomial approximation algorithm when there are [Formula: see text] operations in the flowshop. We further explore three special cases with [Formula: see text] and present optimal solutions for each case, respectively. Moreover, we provide an [Formula: see text]-approximation algorithm for the situation where there are [Formula: see text] operations. Finally, the efficiency of the approximation algorithm is demonstrated via numerical experiments.