Analysis of classes of heuristics for scheduling a two-stage flow shop with parallel machines at one stage

This paper addresses two-state flow shop scheduling with parallel machines at one stage. For finding a minimum makespan schedule, which is strongly NP-hard, some efficient heuristics have been proposed in the literature. This paper enriches the set of heuristics by introducing a few classes of heuristics, and shows that the existing heuristics can be put into this classification scheme. Furthermore, it gives a complete theoretical analysis of the worst-case performance of the classes. Some empirical evaluations and comparisons for the average-case performance of a few typical heuristics in the classes are also performed.