Hybrid flow shop with parallel machines at the first stage and dedicated machines at the second stage

Research output: Contribution to journalArticlepeer-review

9 Scopus citations

Abstract

In this paper, a two-stage hybrid flow shop problem is considered. Specifically, there exist identical parallel machines at stage 1 and two dedicated machines at stage 2, and the objective of the problem is to minimize makespan. After being processed by any machine at stage 1, a job must be processed by a specific machine at stage 2 depending on the job type, and one type of jobs can have different processing times on each machine. First, we introduce the problem and establish complexity of several variations of the problem. For some special cases, we develop optimal polynomial time solution procedures. Then, we establish some simple lower bounds for the problem. In order to solve this NP-hard problem, three heuristics based on simple rules such as the Johnson's rule and the LPT (Longest Processing Time first) rule are developed. For each of the heuristics, we provide some theoretical analysis and find some worst case bound on relative error. Finally, we empirically evaluate the heuristics.

Original languageEnglish
Pages (from-to)22-31
Number of pages10
JournalIndustrial Engineering and Management Systems
Volume14
Issue number1
DOIs
StatePublished - 1 Mar 2015

Keywords

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

Fingerprint

Dive into the research topics of 'Hybrid flow shop with parallel machines at the first stage and dedicated machines at the second stage'. Together they form a unique fingerprint.

Cite this