Minimizing mean flow time with error constraint

Joseph Leung; Tommy W. Tam; C. S. Wong; Gilbert H. Young

Minimizing mean flow time with error constraint

Joseph Leung, Tommy W. Tam, C. S. Wong, Gilbert H. Young

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

8 Scopus citations

Abstract

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.

Original language	English (US)
Title of host publication	Proceedings - Real-Time Systems Symposium
Editors	Anon
Publisher	Publ by IEEE
Pages	2-11
Number of pages	10
ISBN (Print)	0818620048
State	Published - Dec 1 1989
Event	Proceedings - Real-Time Systems Symposium - Santa Monica, CA, USA Duration: Dec 5 1989 → Dec 7 1989

Publication series

Name	Proceedings - Real-Time Systems Symposium

Other

Other	Proceedings - Real-Time Systems Symposium
City	Santa Monica, CA, USA
Period	12/5/89 → 12/7/89

All Science Journal Classification (ASJC) codes

Software
Hardware and Architecture
Computer Networks and Communications

Fingerprint Dive into the research topics of 'Minimizing mean flow time with error constraint'. Together they form a unique fingerprint.

Cite this

@inproceedings{b997594cf1524a07a451145b5e2036e8,

title = "Minimizing mean flow time with error constraint",

abstract = "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.",

author = "Joseph Leung and Tam, {Tommy W.} and Wong, {C. S.} and Young, {Gilbert H.}",

year = "1989",

month = dec,

day = "1",

language = "English (US)",

isbn = "0818620048",

series = "Proceedings - Real-Time Systems Symposium",

publisher = "Publ by IEEE",

pages = "2--11",

editor = "Anon",

booktitle = "Proceedings - Real-Time Systems Symposium",

note = "Proceedings - Real-Time Systems Symposium ; Conference date: 05-12-1989 Through 07-12-1989",

}

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 -