A dual criteria preemptive scheduling problem for minimax error of imprecise computation tasks

Kevin I J Ho, Joseph Leung

Research output: Contribution to journalArticlepeer-review

4 Scopus citations

Abstract

We consider a hierarchical optimization problem for imprecise computation tasks, where each task is weighted with two weights, w and w'. The primary criterion is to minimize the total w-weighted error of all optional parts of tasks and the secondary criterion is to minimize the maximum w'-weighted error. An algorithm is given with time complexity O(kn3 log2 n) for parallel and identical processors and O(kn2) for a single processor, where k is the number of distinct w-weights.

Original languageEnglish (US)
Pages (from-to)717-731
Number of pages15
JournalInternational Journal of Foundations of Computer Science
Volume15
Issue number5
DOIs
StatePublished - Dec 1 2004

All Science Journal Classification (ASJC) codes

  • Computer Science (miscellaneous)

Keywords

  • Imprecise computation task
  • Maximum weighted error
  • Parallel and identical processors
  • Polynomial time algorithm
  • Preemptive scheduling
  • Real-time system
  • Single processor
  • Total weighted error

Fingerprint Dive into the research topics of 'A dual criteria preemptive scheduling problem for minimax error of imprecise computation tasks'. Together they form a unique fingerprint.

Cite this