Chen, Bo Analysis of classes of heuristics for scheduling a two-stage flow shop with parallel machines at one stage. (English) Zbl 0827.90070 J. Oper. Res. Soc. 46, No. 2, 234-244 (1995). 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. Cited in 33 Documents MSC: 90B35 Deterministic scheduling theory in operations research Keywords:two-stage flow shop scheduling; parallel machines; minimum makespan; heuristics; worst-case performance PDFBibTeX XMLCite \textit{B. Chen}, J. Oper. Res. Soc. 46, No. 2, 234--244 (1995; Zbl 0827.90070) Full Text: DOI