Scheduling of a two-stage differentiation flowshop to minimize weighted sum of machine completion times

T. C.E. Cheng, Bertrand M.T. Lin*, Y. Tian

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

22 Scopus citations

Abstract

This paper considers the problem of scheduling a two-stage flowshop that consists of a common critical machine in stage one and two independent dedicated machines in stage two. All the jobs require processing first on the common critical machine. Each job after completing its critical operation in stage one will proceed to the dedicated machine of its type for further processing in stage two. The objective is to minimize the weighted sum of stage-two machine completion times. We show that the problem is strongly NP-hard, and develop an O (n3) polynomial time algorithm to solve the special case where the sequences of both types of jobs are given. We also design an approximation algorithm with a tight performance ratio of frac(4, 3) for the general case.

Original languageEnglish
Pages (from-to)3031-3040
Number of pages10
JournalComputers and Operations Research
Volume36
Issue number11
DOIs
StatePublished - Nov 2009

Keywords

  • Approximation algorithm
  • Flowshop
  • Machine completion time
  • Performance ratio

Fingerprint Dive into the research topics of 'Scheduling of a two-stage differentiation flowshop to minimize weighted sum of machine completion times'. Together they form a unique fingerprint.

Cite this