TY - GEN

T1 - Minimizing the number of late tasks with error constraint

AU - Leung, Joseph Y.T.

AU - Wong, C. S.

N1 - Copyright:
Copyright 2013 Elsevier B.V., All rights reserved.

PY - 1990

Y1 - 1990

N2 - The problem of minimizing the number of late tasks in the imprecise computation model is considered. Each task consists of two subtasks, mandatory and optional. A task is said to be on-time if its mandatory part is completed by its deadline, otherwise, it is said to be late. An on-time task incurs an error if its optional part is not completed by its deadline, and the error is simply the execution time of the unfinished portion. In this paper we consider the problem of finding a preemptive schedule for a set of tasks on p 2 1 identical processors, such that the number of on-time tasks is maximized, (or equivalently, the number of late tasks is minimized), and the total error of the on-time tasks is no more than a given threshold K. Such a schedule is called an optimal schedule. It is shown that the problem of finding an optimal schedule is NP-hard for each fixed p 2 1, even if all tasks have the same ready time and the same deadline. Motivated by the complexity of the problem, we consider the case of a single processor and a set of tasks with oppositely ordered ready times and deadlines. We give a pseudo-polynomial time algorithm and a fast heuristic for this special case. The heuristic is shown to have an asymptotic worst-case ratio of 3. Finally, we give a polynomial time algorithm for a set of tasks with oppositely ordered ready times and deadlines, and similarly ordered mandatory execution times and total execution times.

AB - The problem of minimizing the number of late tasks in the imprecise computation model is considered. Each task consists of two subtasks, mandatory and optional. A task is said to be on-time if its mandatory part is completed by its deadline, otherwise, it is said to be late. An on-time task incurs an error if its optional part is not completed by its deadline, and the error is simply the execution time of the unfinished portion. In this paper we consider the problem of finding a preemptive schedule for a set of tasks on p 2 1 identical processors, such that the number of on-time tasks is maximized, (or equivalently, the number of late tasks is minimized), and the total error of the on-time tasks is no more than a given threshold K. Such a schedule is called an optimal schedule. It is shown that the problem of finding an optimal schedule is NP-hard for each fixed p 2 1, even if all tasks have the same ready time and the same deadline. Motivated by the complexity of the problem, we consider the case of a single processor and a set of tasks with oppositely ordered ready times and deadlines. We give a pseudo-polynomial time algorithm and a fast heuristic for this special case. The heuristic is shown to have an asymptotic worst-case ratio of 3. Finally, we give a polynomial time algorithm for a set of tasks with oppositely ordered ready times and deadlines, and similarly ordered mandatory execution times and total execution times.

UR - http://www.scopus.com/inward/record.url?scp=84880860631&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84880860631&partnerID=8YFLogxK

U2 - 10.1109/REAL.1990.128726

DO - 10.1109/REAL.1990.128726

M3 - Conference contribution

AN - SCOPUS:84880860631

SN - 0818621125

SN - 9780818621123

T3 - Proceedings - Real-Time Systems Symposium

SP - 32

EP - 40

BT - 1990 Proceedings 11th Real-Time Systems Symposium, RTSS 1990

T2 - 1990 11th Real-Time Systems Symposium, RTSS 1990

Y2 - 5 December 1990 through 7 December 1990

ER -