Multistage hybrid flowshop scheduling with identical jobs and uniform parallel machines

The single-stage scheduling problem to minimize the makespan of identical jobs with general release times on uniform parallel machines is known to be solvable in polynomial time using the latest start time (LST) rule to determine the optimal schedule. In this paper, we first show that the two-stage problem is NP-hard using a known result that the three-stage problem with equal job release times is NP-hard. The rest of the paper consists of two parts. In the first part, we compare the extension of the LST rule to the general multistage problem with other heuristics. We compare the heuristics based on the theoretically determined worst-case absolute error bound and on the experimentally determined average deviation from a developed lower bound. The analysis shows that in the presence of many stages, the LST rule does not perform as well as the other heuristics even though they are suboptimal for the single-stage problem. In the second part of this paper, we present a (2 + ϵ)-approximation algorithm for the multi-stage problem.