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

Edwin Tai Chiu Cheng, B. M T Lin, Y. Tian

Research output: Journal article publicationJournal articleAcademic researchpeer-review

22 Citations (Scopus)


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
Issue number11
Publication statusPublished - 1 Nov 2009


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

ASJC Scopus subject areas

  • Computer Science(all)
  • Management Science and Operations Research
  • Modelling and Simulation

Cite this