Total completion time minimization in a 2-stage differentiation flowshop with fixed sequences per job type

Miao-Tsong Lin, F. J. Hwang

Research output: Contribution to journalArticle

19 Scopus citations

Abstract

This paper addresses the total completion time minimization in a two-stage differentiation flowshop where the sequences of jobs per type are predetermined. The two-stage differentiation flowshop consists of a stage-1 common machine and m stage-2 parallel dedicated machines. The goal is to determine an optimal interleaved processing sequence of all jobs at the first stage. We propose an O(m2mk=1nm+1k) dynamic programming algorithm, where nk is the number of type-k jobs. The running time is polynomial when m is constant.

Original languageEnglish
Pages (from-to)208-212
Number of pages5
JournalInformation Processing Letters
Volume111
Issue number5
DOIs
StatePublished - 1 Feb 2011

Keywords

  • Design of algorithms
  • Differentiation flowshop
  • Dynamic programming
  • Fixed sequences
  • Scheduling

Fingerprint Dive into the research topics of 'Total completion time minimization in a 2-stage differentiation flowshop with fixed sequences per job type'. Together they form a unique fingerprint.

  • Cite this