A branch-and-bound algorithm for makespan minimization in differentiation flow shops

Yen Cheng Liu, Kuei Tang Fang, Miao-Tsong Lin*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

9 Scopus citations


This article considers a differentiation flow-shop model, where the jobs are divided into various categories, each of which consists of two stages of operations. All products should be processed first on the single common machine at stage 1. At the second stage, each individual product proceeds to a dedicated machine according to its type. The problem of makespan minimization under the setting with two product types is known to be strongly NP hard. This article considers an arbitrary number of job types by developing a lower bound and two dominance rules, based upon which branch-and-bound algorithms are designed. Computational experiments are carried out to examine the performance of the proposed properties. The statistics show that the proposed properties can substantially reduce the computing efforts required for finding optimal solutions.

Original languageEnglish
Pages (from-to)1397-1408
Number of pages12
JournalEngineering Optimization
Issue number12
StatePublished - 1 Dec 2013


  • Branch-and-bound
  • Differentiation flow shop
  • Makespan

Fingerprint Dive into the research topics of 'A branch-and-bound algorithm for makespan minimization in differentiation flow shops'. Together they form a unique fingerprint.

Cite this