ANALYSIS OF CLASSES OF HEURISTICS FOR SCHEDULING A 2-STAGE FLOW-SHOP WITH PARALLEL MACHINES AT ONE-STAGE

This paper addresses two-stage now 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. In this paper we enrich the set of heuristics by introducing a few classes of heuristics, and show that the existing heuristics can be put into this classification scheme. Furthermore, we give 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.