Scheduling imprecise computation tasks with 0/1-constraint

Kevin I.J. Ho, Joseph Y.T. Leung, W. D. Wei

Research output: Contribution to journalArticlepeer-review

12 Scopus citations

Abstract

We consider the problem of preemptively scheduling a set of imprecise computation tasks on a single processor, with the added constraint that each optional subtask is either fully executed or entirely discarded. Two performance metrics are considered: (1) the total error; (2) the number of imprecisely scheduled tasks (i.e., tasks whose optional subtasks are entirely discarded). Since the problem of minimizing the total error is NP-hard, we consider an O(n2)-time heuristic for it, where n is the number of tasks. It is shown that the total error of the schedule produced by the heuristic is at most three times that of an optimal schedule and the bound is tight. For the problem of minimizing the number of imprecisely scheduled tasks, we show that it can be solved in O(n5) time. Since the time complexity is unacceptably high, we consider an O(n2)-time heuristic for it. It is shown that the number of imprecisely scheduled tasks in the schedule produced by the heuristic is at most twice that in an optimal schedule and the bound is tight. Interestingly, the number of precisely scheduled tasks (i.e., tasks whose optional subtasks are fully executed) in an optimal schedule is also at most twice that in the schedule produced by the heuristic and the bound is tight.

Original languageEnglish (US)
Pages (from-to)117-132
Number of pages16
JournalDiscrete Applied Mathematics
Volume78
Issue number1-3
DOIs
StatePublished - Oct 21 1997

All Science Journal Classification (ASJC) codes

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics

Keywords

  • Heuristics
  • Imprecise computation task
  • NP-hard
  • Polynomial-time algorithm
  • Preemptive scheduling
  • Real-time system
  • Single processor
  • Worst-case analysis

Fingerprint

Dive into the research topics of 'Scheduling imprecise computation tasks with 0/1-constraint'. Together they form a unique fingerprint.

Cite this