Scheduling imprecise computation tasks on uniform processors

Guohua Wan, Joseph Y.T. Leung, Michael L. Pinedo

Research output: Contribution to journalArticlepeer-review

4 Scopus citations

Abstract

We consider the problem of preemptively scheduling n imprecise computation tasks on m ≥ 1 uniform processors, with each task Ti having two weights wi and wi. Three objectives are considered: (1) minimizing the maximum w-weighted error; (2) minimizing the total w-weighted error subject to the constraint that the maximum w-weighted error is minimized; (3) minimizing the maximum w-weighted error subject to the constraint that the total w-weighted error is minimized. For these objectives, we give polynomial time algorithms with time complexity O (m n4), O (m n4) and O (k m n4), respectively, where k is the number of distinct w-weights. We also present alternative algorithms for the three objectives, with time complexity O (c m n3), O (c m n3 + m n4) and O (k c m n3), respectively, where c is a parameter-dependent number.

Original languageEnglish (US)
Pages (from-to)45-52
Number of pages8
JournalInformation Processing Letters
Volume104
Issue number2
DOIs
StatePublished - Oct 16 2007

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Signal Processing
  • Information Systems
  • Computer Science Applications

Keywords

  • Algorithms
  • Analysis of algorithms
  • Combinatorial problems
  • Imprecise computation task
  • Polynomial time algorithms
  • Preemptive scheduling
  • Uniform processors

Fingerprint Dive into the research topics of 'Scheduling imprecise computation tasks on uniform processors'. Together they form a unique fingerprint.

Cite this