TY - GEN
T1 - Minimizing mean flow time with error constraint
AU - Leung, Joseph
AU - Tam, Tommy W.
AU - Wong, C. S.
AU - Young, Gilbert H.
PY - 1989/12/1
Y1 - 1989/12/1
N2 - In a new model of task systems studied by J. W. S. Liu et al. (ibid., pp. 252-260, 1987) each task is logically decomposed into two subtasks, mandatory and optional. The authors discuss preemptively scheduling this kind of task system on p ≥ 1 identical processors so as to minimize the mean flow time. Given a task system and an error threshold K, the goal is to find a preemptive schedule such that each task is executed in the interval of its release time and deadline, 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. It is shown that the problem of finding an optimal schedule is NP-hard for each p ≥ 1, even if all tasks have the same ready time and deadline. For a single processor, a pseudo-polynomial time algorithm and polynomial time algorithms for various special cases of the problem are given.
AB - In a new model of task systems studied by J. W. S. Liu et al. (ibid., pp. 252-260, 1987) each task is logically decomposed into two subtasks, mandatory and optional. The authors discuss preemptively scheduling this kind of task system on p ≥ 1 identical processors so as to minimize the mean flow time. Given a task system and an error threshold K, the goal is to find a preemptive schedule such that each task is executed in the interval of its release time and deadline, 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. It is shown that the problem of finding an optimal schedule is NP-hard for each p ≥ 1, even if all tasks have the same ready time and deadline. For a single processor, a pseudo-polynomial time algorithm and polynomial time algorithms for various special cases of the problem are given.
UR - http://www.scopus.com/inward/record.url?scp=0024891392&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0024891392&partnerID=8YFLogxK
M3 - Conference contribution
AN - SCOPUS:0024891392
SN - 0818620048
T3 - Proceedings - Real-Time Systems Symposium
SP - 2
EP - 11
BT - Proceedings - Real-Time Systems Symposium
A2 - Anon, null
PB - Publ by IEEE
T2 - Proceedings - Real-Time Systems Symposium
Y2 - 5 December 1989 through 7 December 1989
ER -