Minimizing mean flow time in two-machine open shops and flow shops

Jian Zhong Du, Joseph Y.T. Leung

Research output: Contribution to journalArticlepeer-review

31 Scopus citations

Abstract

Preemptive scheduling in open shops and flow shops so as to minimize the mean flow time are both known to be strongly NP-hard on three or more machines. However, their complexity on two machines remained open for more than a decade. In this paper we show that open shop is NP-hard in the ordinary sense and flow shop is NP-hard in the strong sense. A linear time algorithm is also given to produce optimal schedules for two-machine open shops if the optimal order of completion times is known in advance. Finally, an O(N log N) time algorithm is given to produce optimal schedules for two-machine flow shops if the optimal order of completion times on the first machine is known in advance, where N is the number of jobs.

Original languageEnglish (US)
Pages (from-to)24-44
Number of pages21
JournalJournal of Algorithms
Volume14
Issue number1
DOIs
StatePublished - Jan 1993

All Science Journal Classification (ASJC) codes

  • Control and Optimization
  • Computational Mathematics
  • Computational Theory and Mathematics

Fingerprint

Dive into the research topics of 'Minimizing mean flow time in two-machine open shops and flow shops'. Together they form a unique fingerprint.

Cite this