Minimizing total completion time in two-stage hybrid flow shop with dedicated machines

Research output: Contribution to journalArticlepeer-review

25 Scopus citations

Abstract

We consider the problem of minimizing total completion time in a two-stage hybrid flow shop scheduling problem with dedicated machines at stage 2. There exist one machine at stage 1 and two machines at stage 2. Each job must be processed on the single machine at stage 1 and depending upon the job type, the job is processed on either of the two machines at stage 2. First, we introduce the problem and establish complexity of several variations of the problem. For the general case, we introduce two heuristics and find a worst case bound on relative error for each of the heuristics. Then, we find optimal solution procedures for some special cases. We also develop a heuristic for a special case where processing times on machine 1 are identical and find a worst case bound on relative error. Finally, we empirically evaluate the heuristics.

Original languageEnglish
Pages (from-to)1045-1053
Number of pages9
JournalComputers and Operations Research
Volume38
Issue number7
DOIs
StatePublished - Jul 2011

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 two-stage hybrid flow shop with dedicated machines'. Together they form a unique fingerprint.

Cite this