Optimal combined task and message scheduling in distributed real-time systems

Tarek F. Abdelzaher, Kang G. Shin

Research output: Contribution to conferencePaper

Abstract

In this paper we present a branch-and-bound (B&B) algorithm for combined task and message scheduling in distributed hard real-time systems. The algorithm finds an optimal schedule for a set of communicating tasks with known arrival times, precedence constraints, and resource requirements in conjunction with the assignment and scheduling of intertask messages over communication links. The schedule is 'optimal' in the sense of minimizing maximum task lateness under a heuristic message priority assignment found during the search. A robotics application is used to illustrate the utility and potential of the algorithm. Results of an extensive simulation study analyzing its performance are also presented.

Original languageEnglish (US)
Pages162-171
Number of pages10
StatePublished - Dec 1 1995
Externally publishedYes
EventProceedings of the 1995 16th IEEE Real-Time Systems Symposium - Pisa, Italy
Duration: Dec 5 1995Dec 7 1995

Other

OtherProceedings of the 1995 16th IEEE Real-Time Systems Symposium
CityPisa, Italy
Period12/5/9512/7/95

Fingerprint

Real time systems
Scheduling
Telecommunication links
Robotics

ASJC Scopus subject areas

  • Software
  • Hardware and Architecture
  • Computer Networks and Communications

Cite this

Abdelzaher, T. F., & Shin, K. G. (1995). Optimal combined task and message scheduling in distributed real-time systems. 162-171. Paper presented at Proceedings of the 1995 16th IEEE Real-Time Systems Symposium, Pisa, Italy, .

Optimal combined task and message scheduling in distributed real-time systems. / Abdelzaher, Tarek F.; Shin, Kang G.

1995. 162-171 Paper presented at Proceedings of the 1995 16th IEEE Real-Time Systems Symposium, Pisa, Italy, .

Research output: Contribution to conferencePaper

Abdelzaher, TF & Shin, KG 1995, 'Optimal combined task and message scheduling in distributed real-time systems' Paper presented at Proceedings of the 1995 16th IEEE Real-Time Systems Symposium, Pisa, Italy, 12/5/95 - 12/7/95, pp. 162-171.
Abdelzaher TF, Shin KG. Optimal combined task and message scheduling in distributed real-time systems. 1995. Paper presented at Proceedings of the 1995 16th IEEE Real-Time Systems Symposium, Pisa, Italy, .
Abdelzaher, Tarek F. ; Shin, Kang G. / Optimal combined task and message scheduling in distributed real-time systems. Paper presented at Proceedings of the 1995 16th IEEE Real-Time Systems Symposium, Pisa, Italy, .10 p.
@conference{0bc7522c49134b6d82119680cb005e20,
title = "Optimal combined task and message scheduling in distributed real-time systems",
abstract = "In this paper we present a branch-and-bound (B&B) algorithm for combined task and message scheduling in distributed hard real-time systems. The algorithm finds an optimal schedule for a set of communicating tasks with known arrival times, precedence constraints, and resource requirements in conjunction with the assignment and scheduling of intertask messages over communication links. The schedule is 'optimal' in the sense of minimizing maximum task lateness under a heuristic message priority assignment found during the search. A robotics application is used to illustrate the utility and potential of the algorithm. Results of an extensive simulation study analyzing its performance are also presented.",
author = "Abdelzaher, {Tarek F.} and Shin, {Kang G.}",
year = "1995",
month = "12",
day = "1",
language = "English (US)",
pages = "162--171",
note = "Proceedings of the 1995 16th IEEE Real-Time Systems Symposium ; Conference date: 05-12-1995 Through 07-12-1995",

}

TY - CONF

T1 - Optimal combined task and message scheduling in distributed real-time systems

AU - Abdelzaher, Tarek F.

AU - Shin, Kang G.

PY - 1995/12/1

Y1 - 1995/12/1

N2 - In this paper we present a branch-and-bound (B&B) algorithm for combined task and message scheduling in distributed hard real-time systems. The algorithm finds an optimal schedule for a set of communicating tasks with known arrival times, precedence constraints, and resource requirements in conjunction with the assignment and scheduling of intertask messages over communication links. The schedule is 'optimal' in the sense of minimizing maximum task lateness under a heuristic message priority assignment found during the search. A robotics application is used to illustrate the utility and potential of the algorithm. Results of an extensive simulation study analyzing its performance are also presented.

AB - In this paper we present a branch-and-bound (B&B) algorithm for combined task and message scheduling in distributed hard real-time systems. The algorithm finds an optimal schedule for a set of communicating tasks with known arrival times, precedence constraints, and resource requirements in conjunction with the assignment and scheduling of intertask messages over communication links. The schedule is 'optimal' in the sense of minimizing maximum task lateness under a heuristic message priority assignment found during the search. A robotics application is used to illustrate the utility and potential of the algorithm. Results of an extensive simulation study analyzing its performance are also presented.

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

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

M3 - Paper

AN - SCOPUS:0029489058

SP - 162

EP - 171

ER -