Proportionate flow shop with controllable processing times

Edwin Tai Chiu Cheng, Natalia Shakhlevich

Research output: Journal article publicationJournal articleAcademic researchpeer-review

19 Citations (Scopus)


This paper considers a special class of flow-shop problems, known as the proportionate flow shop. In such a shop, each job flows through the machines in the same order and has equal processing times on the machines. The processing times of different jobs may be different. It is assumed that all operations of a job may be compressed by the same amount which will incur an additional cost. The objective is to minimize the makespan of the schedule together with a compression cost function which is non-decreasing with respect to the amount of compression. For a bicriterion problem of minimizing the makespan and a linear cost function, an O(n log n) algorithm is developed to construct the Pareto optimal set. For a single criterion problem, an O(n2) algorithm is developed to minimize the sum of the makespan and compression cost.
Original languageEnglish
Pages (from-to)253-265
Number of pages13
JournalJournal of Scheduling
Issue number6
Publication statusPublished - 1 Dec 1999


  • Controllable processing times
  • Flow shop scheduling
  • Multiple criteria

ASJC Scopus subject areas

  • Management Science and Operations Research
  • Industrial and Manufacturing Engineering

Cite this