ISSN:
1432-0541
Keywords:
Key words. Real-time system, NP-hard, Pseudopolynomial time, Polynomial time, Ready time, Deadline, Imprecise computation, Mean flow time, Average error, Nonpreemptive scheduling, Preemptive scheduling.
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
Notes:
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.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/PL00009185
Permalink
