×

Analysis of classes of heuristics for scheduling a two-stage flow shop with parallel machines at one stage. (English) Zbl 0827.90070

Summary: This paper addresses two-stage 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. 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.

MSC:

90B35 Deterministic scheduling theory in operations research
PDFBibTeX XMLCite
Full Text: DOI