Minimizing mean flow time with error constraint

J. Y.T. Leung, T. W. Tam, C. S. Wong, G. H. Young

Research output: Contribution to journalArticlepeer-review

2 Scopus citations

Abstract

We consider the problem of minimizing mean flow time for the Imprecise Computation Model introduced by Lin et al. A task system TS = ({Ti}, {r(Ti)}, {d(Ti)}, {m(Ti)}, {o(Ti)}) consists of a set of n independent tasks, where r(Ti), d(Ti), m(Ti), and o(Ti) denote the ready time, deadline, execution time of the mandatory part, and execution time of the optional part of Ti, respectively. Given a task system TS and an error threshold K, our goal is to find a preemptive schedule on one processor such that the average error is no more than K and the mean flow time of the schedule is minimized. Such a schedule is called an optimal schedule. In this article we show that the problem of finding an optimal schedule is NP-hard, even if all tasks have identical ready times and deadlines. A pseudopolynomial-time algorithm is given for a set of tasks with identical ready times and deadlines, and oppositely ordered mandatory execution times and total execution times (i.e., there is a labeling of tasks such that m(Ti) ≤ m(Ti+1) and m(Ti) + o(Ti) ≥ m(Ti+1) + o(Ti+1) for each 1 ≤ i ≤ n). Finally, polynomial-time algorithms are given for (1) a set of tasks with identical ready times, and similarly ordered mandatory execution times and total execution times and (2) a set of tasks with similarly ordered ready times, deadlines, mandatory execution times, and total execution times.

Original languageEnglish (US)
Pages (from-to)101-118
Number of pages18
JournalAlgorithmica (New York)
Volume20
Issue number1
DOIs
StatePublished - Jan 1 1998

All Science Journal Classification (ASJC) codes

  • Computer Science(all)
  • Computer Science Applications
  • Applied Mathematics

Keywords

  • Average error
  • Deadline
  • Imprecise computation
  • Mean flow time
  • NP-hard
  • Nonpreemptive scheduling
  • Polynomial time
  • Preemptive scheduling
  • Pseudopolynomial time
  • Ready time
  • Real-time system

Fingerprint Dive into the research topics of 'Minimizing mean flow time with error constraint'. Together they form a unique fingerprint.

Cite this