Scheduling real-time computations with extended deadlines

C. C. Han; K. J. Lin; P. Tu

doi:10.1109/PCCC.1992.200584

Scheduling real-time computations with extended deadlines

C. C. Han, K. J. Lin, P. Tu

University of Illinois at Urbana-Champaign

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

1 Scopus citations

Abstract

Real-time scheduling problem is to find a feasible schedule in which every computation starts execution after its ready time, completes before its deadline and satisfies all of its precedence constraints. In many applications, some real-time job allows part of its computation to be finished after its primary deadline but before its eztended deadline. In this paper, we study the scheduling issues for real-time computations with extended deadlines. We call the part of a computation which must be completed before the primary deadline its hard part, and the rest its soft part. We study two variations of this problem. In the 6rst model, the system receives a penalty for each late soft part. In the second model, there is an extra computation overhead for each late soft part. For each model, we present algorithms to produce a feasible schedule.

Original language	English
Title of host publication	11th Annual International Phoenix Conference on Computers and Communication, IPCCC 1992 - Proceedings
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	403-410
Number of pages	8
ISBN (Electronic)	0780306058, 9780780306059
DOIs	https://doi.org/10.1109/PCCC.1992.200584
State	Published - 1992
Externally published	Yes
Event	11th Annual International Phoenix Conference on Computers and Communication, IPCCC 1992 - Scottsdale, United States Duration: 01 04 1992 → 03 04 1992

Publication series

Name	11th Annual International Phoenix Conference on Computers and Communication, IPCCC 1992 - Proceedings

Conference

Conference	11th Annual International Phoenix Conference on Computers and Communication, IPCCC 1992
Country/Territory	United States
City	Scottsdale
Period	01/04/92 → 03/04/92

Bibliographical note

Publisher Copyright:
© 1992 IEEE.

Access to Document

10.1109/PCCC.1992.200584

Cite this

Han, C. C., Lin, K. J., & Tu, P. (1992). Scheduling real-time computations with extended deadlines. In 11th Annual International Phoenix Conference on Computers and Communication, IPCCC 1992 - Proceedings (pp. 403-410). Article 200584 (11th Annual International Phoenix Conference on Computers and Communication, IPCCC 1992 - Proceedings). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/PCCC.1992.200584

Han, C. C. ; Lin, K. J. ; Tu, P. / Scheduling real-time computations with extended deadlines. 11th Annual International Phoenix Conference on Computers and Communication, IPCCC 1992 - Proceedings. Institute of Electrical and Electronics Engineers Inc., 1992. pp. 403-410 (11th Annual International Phoenix Conference on Computers and Communication, IPCCC 1992 - Proceedings).

@inproceedings{14fc563ce4304481852d7afaae506ff3,

title = "Scheduling real-time computations with extended deadlines",

abstract = "Real-time scheduling problem is to find a feasible schedule in which every computation starts execution after its ready time, completes before its deadline and satisfies all of its precedence constraints. In many applications, some real-time job allows part of its computation to be finished after its primary deadline but before its eztended deadline. In this paper, we study the scheduling issues for real-time computations with extended deadlines. We call the part of a computation which must be completed before the primary deadline its hard part, and the rest its soft part. We study two variations of this problem. In the 6rst model, the system receives a penalty for each late soft part. In the second model, there is an extra computation overhead for each late soft part. For each model, we present algorithms to produce a feasible schedule.",

author = "Han, {C. C.} and Lin, {K. J.} and P. Tu",

note = "Publisher Copyright: {\textcopyright} 1992 IEEE.; 11th Annual International Phoenix Conference on Computers and Communication, IPCCC 1992 ; Conference date: 01-04-1992 Through 03-04-1992",

year = "1992",

doi = "10.1109/PCCC.1992.200584",

language = "英语",

series = "11th Annual International Phoenix Conference on Computers and Communication, IPCCC 1992 - Proceedings",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

pages = "403--410",

booktitle = "11th Annual International Phoenix Conference on Computers and Communication, IPCCC 1992 - Proceedings",

address = "美国",

}

Han, CC, Lin, KJ & Tu, P 1992, Scheduling real-time computations with extended deadlines. in 11th Annual International Phoenix Conference on Computers and Communication, IPCCC 1992 - Proceedings., 200584, 11th Annual International Phoenix Conference on Computers and Communication, IPCCC 1992 - Proceedings, Institute of Electrical and Electronics Engineers Inc., pp. 403-410, 11th Annual International Phoenix Conference on Computers and Communication, IPCCC 1992, Scottsdale, United States, 01/04/92. https://doi.org/10.1109/PCCC.1992.200584

Scheduling real-time computations with extended deadlines. / Han, C. C.; Lin, K. J.; Tu, P.
11th Annual International Phoenix Conference on Computers and Communication, IPCCC 1992 - Proceedings. Institute of Electrical and Electronics Engineers Inc., 1992. p. 403-410 200584 (11th Annual International Phoenix Conference on Computers and Communication, IPCCC 1992 - Proceedings).

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

TY - GEN

T1 - Scheduling real-time computations with extended deadlines

AU - Han, C. C.

AU - Lin, K. J.

AU - Tu, P.

PY - 1992

Y1 - 1992

N2 - Real-time scheduling problem is to find a feasible schedule in which every computation starts execution after its ready time, completes before its deadline and satisfies all of its precedence constraints. In many applications, some real-time job allows part of its computation to be finished after its primary deadline but before its eztended deadline. In this paper, we study the scheduling issues for real-time computations with extended deadlines. We call the part of a computation which must be completed before the primary deadline its hard part, and the rest its soft part. We study two variations of this problem. In the 6rst model, the system receives a penalty for each late soft part. In the second model, there is an extra computation overhead for each late soft part. For each model, we present algorithms to produce a feasible schedule.

AB - Real-time scheduling problem is to find a feasible schedule in which every computation starts execution after its ready time, completes before its deadline and satisfies all of its precedence constraints. In many applications, some real-time job allows part of its computation to be finished after its primary deadline but before its eztended deadline. In this paper, we study the scheduling issues for real-time computations with extended deadlines. We call the part of a computation which must be completed before the primary deadline its hard part, and the rest its soft part. We study two variations of this problem. In the 6rst model, the system receives a penalty for each late soft part. In the second model, there is an extra computation overhead for each late soft part. For each model, we present algorithms to produce a feasible schedule.

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

U2 - 10.1109/PCCC.1992.200584

DO - 10.1109/PCCC.1992.200584

M3 - 会议稿件

AN - SCOPUS:84884687156

T3 - 11th Annual International Phoenix Conference on Computers and Communication, IPCCC 1992 - Proceedings

SP - 403

EP - 410

BT - 11th Annual International Phoenix Conference on Computers and Communication, IPCCC 1992 - Proceedings

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 11th Annual International Phoenix Conference on Computers and Communication, IPCCC 1992

Y2 - 1 April 1992 through 3 April 1992

ER -

Han CC, Lin KJ, Tu P. Scheduling real-time computations with extended deadlines. In 11th Annual International Phoenix Conference on Computers and Communication, IPCCC 1992 - Proceedings. Institute of Electrical and Electronics Engineers Inc. 1992. p. 403-410. 200584. (11th Annual International Phoenix Conference on Computers and Communication, IPCCC 1992 - Proceedings). doi: 10.1109/PCCC.1992.200584

Scheduling real-time computations with extended deadlines

Abstract

Publication series

Conference

Bibliographical note

Access to Document

Other files and links

Fingerprint

Cite this