Minimizing schedule length subject to minimum flow time

Joseph Y.T. Leung, Gilbert H. Young

Research output: Contribution to journalArticlepeer-review

27 Scopus citations

Abstract

The problem of scheduling n independent tasks on m ≥ 1 identical processors, with the objective of minimizing the schedule length under the constraint that it must have minimum flow time, is considered. For nonpreemptive scheduling, it is known that the problem is NP-hard. This paper shows that the problem is a lot easier for preemptive scheduling. Specifically, an O(n log n) time algorithm to find an optimal preemptive schedule is given. This algorithm generates schedules with at most m - 1 preemptions. It is also shown that an optimal nonpreemptive schedule can be almost twice as long as an optimal preemptive schedule. The results suggest that preemption is extremely beneficial in simultaneously minimizing the flow time and the schedule length.

Original languageEnglish (US)
Pages (from-to)314-326
Number of pages13
JournalSIAM Journal on Computing
Volume18
Issue number2
DOIs
StatePublished - 1989
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Computer Science(all)
  • Mathematics(all)

Fingerprint

Dive into the research topics of 'Minimizing schedule length subject to minimum flow time'. Together they form a unique fingerprint.

Cite this