Minimizing makespan in an ordered flow shop with machine-dependent processing times

Byung Cheon Choi, Joseph Y.T. Leung, Michael L. Pinedo

Research output: Contribution to journalArticlepeer-review

10 Scopus citations


We consider a generalization of the proportionate flow shop problem with the makespan objective. Each job has a processing requirement and each machine has a characteristic value. In our case, we assume that the time a job occupies a machine is equal to the processing requirement of the job plus a setup time that is equal to the characteristic value of that machine. In this paper, we consider permutation schedules and show that the problem is solvable in polynomial time when the number of machines is fixed.

Original languageEnglish (US)
Pages (from-to)797-818
Number of pages22
JournalJournal of Combinatorial Optimization
Issue number4
StatePublished - Nov 2011

All Science Journal Classification (ASJC) codes

  • Computer Science Applications
  • Discrete Mathematics and Combinatorics
  • Control and Optimization
  • Computational Theory and Mathematics
  • Applied Mathematics


  • Computational complexity
  • Machine-dependent processing times
  • Makespan
  • Proportionate flow shop


Dive into the research topics of 'Minimizing makespan in an ordered flow shop with machine-dependent processing times'. Together they form a unique fingerprint.

Cite this