Minimizing mean flow time with release time and deadline constraints

Jian Zhong Du, Joseph Y.T. Leung

Research output: Contribution to journalArticlepeer-review

15 Scopus citations


The problem of preemptively scheduling a set of n independent tasks on a single processor so as to minimize the mean flow time is considered. Each task has associated with it a processing time, a release time, and a deadline. A feasible schedule is one in which each task is completely processed within its interval of release time and deadline. The problem is to find a feasible schedule with the minimum mean flow time. It is known that two special cases of the problem can be solved in O(n log n) time: the case of identical deadlines by the smallest remaining processing time rule as described by Baker and the case of identical release times by the deadline rule as described by Smith. In this paper we generalize both algorithms and show that they solve a much broader class of problem instances, namely those which contain no triple of tasks satisfying certain conditions. The generalized algorithms, and an algorithm that recognizes problem instances satisfying the condition, can all be implemented in O(n2) time. Finally, we show that the general problem is NP-hard, answering an open question posed by Lawler.

Original languageEnglish (US)
Pages (from-to)45-68
Number of pages24
JournalJournal of Algorithms
Issue number1
StatePublished - Jan 1993
Externally publishedYes

All Science Journal Classification (ASJC) codes

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


Dive into the research topics of 'Minimizing mean flow time with release time and deadline constraints'. Together they form a unique fingerprint.

Cite this