## Abstract

We consider the problem of minimizing mean flow time for the Imprecise Computation Model introduced by Lin et al. A task system TS = ({T_{i}}, {r(T_{i})}, {d(T_{i})}, {m(T_{i})}, {o(T_{i})}) consists of a set of n independent tasks, where r(T_{i}), d(T_{i}), m(T_{i}), and o(T_{i}) denote the ready time, deadline, execution time of the mandatory part, and execution time of the optional part of T_{i}, respectively. Given a task system TS and an error threshold K, our goal is to find a preemptive schedule on one processor such that the average error is no more than K and the mean flow time of the schedule is minimized. Such a schedule is called an optimal schedule. In this article we show that the problem of finding an optimal schedule is NP-hard, even if all tasks have identical ready times and deadlines. A pseudopolynomial-time algorithm is given for a set of tasks with identical ready times and deadlines, and oppositely ordered mandatory execution times and total execution times (i.e., there is a labeling of tasks such that m(T_{i}) ≤ m(T_{i+1}) and m(T_{i}) + o(T_{i}) ≥ m(T_{i+1}) + o(T_{i+1}) for each 1 ≤ i ≤ n). Finally, polynomial-time algorithms are given for (1) a set of tasks with identical ready times, and similarly ordered mandatory execution times and total execution times and (2) a set of tasks with similarly ordered ready times, deadlines, mandatory execution times, and total execution times.

Original language | English (US) |
---|---|

Pages (from-to) | 101-118 |

Number of pages | 18 |

Journal | Algorithmica (New York) |

Volume | 20 |

Issue number | 1 |

DOIs | |

State | Published - 1998 |

Externally published | Yes |

## All Science Journal Classification (ASJC) codes

- General Computer Science
- Computer Science Applications
- Applied Mathematics

## Keywords

- Average error
- Deadline
- Imprecise computation
- Mean flow time
- NP-hard
- Nonpreemptive scheduling
- Polynomial time
- Preemptive scheduling
- Pseudopolynomial time
- Ready time
- Real-time system