A note on heuristics of flow-shop scheduling

• 成果类型: Article
• 署名作者: Lai, TC
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.44.4.648
• 发表日期: 1996
• 页码: 648-652
• 关键词: heuristic; Worst-case analysis; Scheduling; flow-shop sequencing

摘要

We present an O(mn) two-group (TG) heuristic for the m-machine, n-job permutation flow-shop scheduling problem. We show that heuristic TG has a worst-case performance ratio of(m + 1)/2. We also establish worst-case bounds for several heuristics proposed in the past.