Minimizing mean flow time with release time and deadline constraints

Jianzhong Du, Joseph Y.T. Leung

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2 Scopus citations


The problem of preemptively scheduling a task system consisting of a set of n independent tasks on one processor so as to minimize the mean flow time is considered. The goal is to find a preemptive schedule such that the mean flow time is minimized subject to the constraint that each task Ti is executed within the interval between its release time and its deadline. Such a schedule, if it exists, is called an optimal schedule. It is shown that the problem of finding an optimal schedule is NP-hard. A greedy algorithm is given to find an optimal schedule for a large class of task systems.

Original languageEnglish (US)
Title of host publicationProc Real Time Syst Symp
PublisherPubl by IEEE
Number of pages9
ISBN (Print)0818608943
StatePublished - 1988
Externally publishedYes

Publication series

NameProc Real Time Syst Symp
Volume35 n 6

All Science Journal Classification (ASJC) codes

  • Software
  • Hardware and Architecture
  • Computer Networks and Communications


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

Cite this