Imprecise computation model: Bicriteria and other related problems

Joseph Leung

Research output: Chapter in Book/Report/Conference proceedingChapter

Abstract

In the last chapter, we have given algorithms for the total w-weighted error and the maximum w′-weighted error problems. In this chapter, we will consider bicriteria scheduling problems. In the bicriteria scheduling problems, we are concerned with (1) minimizing the total w-weighted error, subject to the constraint that the maximum w′-weighted error is minimum and (2) minimizing the maximum w′-weighted error, subject to the constraint that the total w-weighted error is minimum. For a given task system TS, we use ∊w′w (TS) to denote the minimum total w-weighted error, subject to the constraint that the maximum w′-weighted error is minimum. Similarly, we use ϒw w′ (TS) to denote the maximum w′-weighted error, subject to the constraint that the total w-weighted error is minimum. In Sections 8.2 and 8.3, we shall give algorithms to compute ∊w′w (TS) and ϒw w′ (TS), respectively. The Imprecise Computation Model has also been studied under the 0/1-constraint, where each optional subtask is either fully executed or totally discarded. With the 0/1-constraint, two problems have been studied: (1) minimize the total error and (2) minimize the number of imprecisely scheduled tasks (i.e., tasks whose optional subtasks have been discarded). The 0/1-constraint is motivated by some practical applications. In real life, many tasks can be implemented by either a fast or a slow algorithm, with the slow algorithm producing better-quality results than the fast one. Owing to deadline constraints, it may not be possible to meet the deadline of every task if each task were to execute the slow version. Thus, the problem of scheduling tasks with primary version (slow algorithm) and alternate version (fast algorithm) can be reduced to one of scheduling with 0/1-constraint. The execution time of the fast algorithm is the mandatory execution time, while the execution time of the slow algorithm is the total execution time (i.e., mandatory plus optional execution time).

Original languageEnglish (US)
Title of host publicationHandbook of Real-Time and Embedded Systems
PublisherCRC Press
Pages8-1-8-11
ISBN (Electronic)9781420011746
ISBN (Print)9781584886785
StatePublished - Jan 1 2007

All Science Journal Classification (ASJC) codes

  • Computer Science(all)
  • Engineering(all)

Fingerprint Dive into the research topics of 'Imprecise computation model: Bicriteria and other related problems'. Together they form a unique fingerprint.

Cite this