Minimizing total flow time in two-stage hybrid flowshop with parallel machines and a single batching machine

This paper studies a two-stage hybrid flowshop scheduling problem with identical parallel machines in the first stage and a single batching machine in the second stage. Each job is first processed on the parallel machines. The jobs are partitioned into batches and processed on the batching machine. The batching machine can process several jobs as a batch simultaneously. The processing time of a batch is equal to the largest processing time among all jobs assigned into the batch. The objective is to find a feasible schedule which minimizes the total flow time. We prove that the general problem is strongly NP-hard and develop an optimal algorithm for a special case with a chain constraint. Then we propose a heuristic algorithm for the problem and analyze its worst-case performance ratio compared with the lower bound. Computational results show that the proposed algorithm for the problem can generate near optimal solutions.