Flow shops with machine maintenance: Ordered and proportionate cases

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

Research output: Contribution to journalArticlepeer-review

22 Scopus citations


We consider the m-machine ordered flow shop scheduling problem with machines subject to maintenance and with the makespan as objective. It is assumed that the maintenances are scheduled in advance and that the jobs are resumable. We consider permutation schedules and show that the problem is strongly NP-hard; it remains NP-hard in the ordinary sense even in the case of a single maintenance. We show that if the first (last) machine is the slowest and if maintenances occur only on the first (last) machine, then sequencing the jobs in the LPT (SPT) order yields an optimal schedule for the m-machine problem. As a special case of the ordered flow shop, we focus on the proportionate flow shop where the processing times of any given job on all the machines are identical. We prove that the proportionate flow shop problem with two maintenance periods is NP-hard, while the problem with a single maintenance period can be solved in polynomial time. Furthermore, we show that the optimal algorithm for the single maintenance case is a frac(3, 2)-approximation algorithm for the two maintenance case. In our conclusion we discuss also the computational complexity of other objective functions.

Original languageEnglish (US)
Pages (from-to)97-104
Number of pages8
JournalEuropean Journal of Operational Research
Issue number1
StatePublished - Nov 16 2010

All Science Journal Classification (ASJC) codes

  • General Computer Science
  • Modeling and Simulation
  • Management Science and Operations Research
  • Information Systems and Management


  • Approximation algorithm
  • Computational complexity
  • Maintenance
  • Ordered flow shop
  • Proportionate flow shop


Dive into the research topics of 'Flow shops with machine maintenance: Ordered and proportionate cases'. Together they form a unique fingerprint.

Cite this