Two-stage hybrid flow shop scheduling with dynamic job arrivals

Frank S. Yao, Mei Zhao, Hui Zhang

Research output: Contribution to journalArticleResearchpeer-review

27 Citations (Scopus)


Motivated by applications in semiconductor manufacturing industry, we consider a two-stage hybrid flow shop where a discrete machine is followed by a batching machine. In this paper, we analyze the computational complexity of a class of two-machine problems with dynamic job arrivals. For the problems belonging to P we present polynomial algorithms. For the NP-complete problems we propose the heuristics, and then establish the upper bounds on the worst case performance ratios of the heuristics. In addition, we give the improved heuristics that can achieve better performances.

Original languageEnglish
Pages (from-to)1701-1712
Number of pages12
JournalComputers and Operations Research
Issue number7
Publication statusPublished - Jul 2012
Externally publishedYes


  • Batch scheduling
  • Dynamic programming
  • Heuristics

Cite this