Abstract
We consider the problem of minimizing mean flow time for the Imprecise Computation Model introduced by Lin et al. A task system TS = ({Ti}, {r(Ti)}, {d(Ti)}, {m(Ti)}, {o(Ti)}) consists of a set of n independent tasks, where r(Ti), d(Ti), m(Ti), and o(Ti) denote the ready time, deadline, execution time of the mandatory part, and execution time of the optional part of Ti, 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(Ti) ≤ m(Ti+1) and m(Ti) + o(Ti) ≥ m(Ti+1) + o(Ti+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