Minimizing total completion time in a two-machine flow shop with deteriorating jobs

Ji Bo Wang, Chi To Ng, Edwin Tai Chiu Cheng, Li Li Liu

Research output: Journal article publicationJournal articleAcademic researchpeer-review

68 Citations (Scopus)


This paper considers a two-machine flow shop scheduling problem with deteriorating jobs. By a deteriorating job, we mean that the processing time of a job is an increasing function of its execution start time. A simple linear deterioration function is assumed. The objective is to find a sequence that minimizes total completion time. Optimal solutions are obtained for some special cases. For the general case, several dominance properties and two lower bounds are derived to speed up the elimination process of a branch-and-bound algorithm. A heuristic algorithm is also proposed to overcome the inefficiency of the branch-and-bound algorithm. Computational results show that the proposed heuristic algorithm performs effectively and efficiently.
Original languageEnglish
Pages (from-to)185-193
Number of pages9
JournalApplied Mathematics and Computation
Issue number1
Publication statusPublished - 1 Sept 2006


  • Branch-and-bound algorithm
  • Flow shop
  • Scheduling
  • Simple linear deterioration
  • Total completion time

ASJC Scopus subject areas

  • Applied Mathematics
  • Computational Mathematics
  • Numerical Analysis


Dive into the research topics of 'Minimizing total completion time in a two-machine flow shop with deteriorating jobs'. Together they form a unique fingerprint.

Cite this