Batch scheduling in differentiation flow shops for makespan minimisation

Ting Chih Huang, Miao-Tsong Lin*

*Corresponding author for this work

Research output: Contribution to journalArticle

14 Scopus citations


This paper considers a two-stage three-machine differentiation flow shop that comprises a common machine at stage 1 and two independent dedicated machines at stage 2. Two types of jobs are to be processed. All jobs must visit the stage-1 machine, and then the jobs of each type proceed to their dedicated machine for stage-2 processing. The stage-1 machine processes the jobs in batches, each of which, whenever formed, requires a constant setup time. The objective is to find a schedule that attains the minimum makespan. While the problem is strongly NP-hard, we investigate the case where the processing sequences of the two types of jobs are given and fixed. A polynomial-time dynamic programming algorithm is designed to solve this problem. We then deploy this algorithm to compute the lower bounds of the general problem.

Original languageEnglish
Pages (from-to)5073-5082
Number of pages10
JournalInternational Journal of Production Research
Issue number17
StatePublished - 1 Sep 2013


  • flow shop scheduling
  • makespan
  • mass customization
  • scheduling

Fingerprint Dive into the research topics of 'Batch scheduling in differentiation flow shops for makespan minimisation'. Together they form a unique fingerprint.

Cite this