Minimizing mean flow time with release time and deadline constraints

Jian Zhong Du, Joseph Y.T. Leung

Research output: Contribution to journalArticlepeer-review

12 Scopus citations

Abstract

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
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 with release time and deadline constraints'. Together they form a unique fingerprint.

Cite this