Imprecise computation model: Bicriteria and other related problems

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).