A special case of three machine flow shop scheduling

Research output: Contribution to journalArticlepeer-review


This paper considers a special case of a three machine flow shop scheduling problem in which operation processing time of each job is ordered such that machine 1 has the longest processing time, whereas machine 3, the shortest processing time. The objective of the problem is the minimization of the total completion time. Although the problem is simple, its complexity is yet to be established to our best knowledge. This paper first introduces the problem and presents some optimal properties of the problem. Then, it establishes several special cases in which a polynomial-time optimal solution procedure can be found. In addition, the paper proves that the recognition version of the problem is at least binary NP-complete. The complexity of the problem has been open despite its simple structure and this paper finally establishes its complexity. Finally, a simple and intuitive heuristic is developed and the tight worst case bound on relative error of 6/5 is established.

Original languageEnglish
Pages (from-to)32-40
Number of pages9
JournalIndustrial Engineering and Management Systems
Issue number1
StatePublished - 1 Mar 2016


  • Computational complexity
  • Three machine flow shop
  • Total completion time


Dive into the research topics of 'A special case of three machine flow shop scheduling'. Together they form a unique fingerprint.

Cite this