Minimizing total completion time in a two-stage hybrid flow shop with dedicated machines at the first stage

Research output: Contribution to journalArticlepeer-review

22 Scopus citations

Abstract

This paper considers a two-stage hybrid flow shop scheduling with dedicated machines at stage 1 with the objective of minimizing the total completion time. There exist two machines at stage 1 and one machine at stage 2. Each job must be processed on one of the two dedicated machines at stage 1 depending on the job type; subsequently, the job is processed on the single machine at stage 2. First, we introduce the problem and establish the complexity of the problem. For a special case in which the processing times on the machine at stage 2 are identical, an optimal solution is presented; for three special cases, we show that the decision version is unary NP-complete. For the general case, two simple and intuitive heuristics are introduced, and a worst case bound on the relative error is found for each of the heuristics. Finally, we empirically evaluate the heuristics, including an optimal algorithm for a special case.

Original languageEnglish
Pages (from-to)1-8
Number of pages8
JournalComputers and Operations Research
Volume58
DOIs
StatePublished - Jun 2015

Keywords

  • Computational complexity
  • Heuristic
  • Two-stage hybrid flow shop
  • Worst case bound on relative error

Fingerprint

Dive into the research topics of 'Minimizing total completion time in a two-stage hybrid flow shop with dedicated machines at the first stage'. Together they form a unique fingerprint.

Cite this