Scheduling interval ordered tasks on multiprocessor architecture

Hesham H. Ali, Hesham El-Rewini

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

The problem of scheduling task graphs on multiprocessor systems have received considerable attention in recent years. This problem is known to be NP-hard in its most general form. the complexity of the problem rises even more when communication among tasks is considered. It has been proven that by taking communication into consideration, the problem remains computationally intractable even in several restricted cases. In this paper, we study the problem of scheduling task graphs with communication on arbitrary many processors when the task graph is restricted to be an interval order. We introduce an optimal algorithm for solving the scheduling problem when the execution cost of the system tasks is identical and equal to the communication cost between any pair of processors.

Original languageEnglish (US)
Title of host publicationApplied Computing
Subtitle of host publicationTechnological Challenges of the 1990's
PublisherPubl by ACM
Pages792-797
Number of pages6
ISBN (Print)089791502X, 9780897915021
DOIs
StatePublished - 1992
EventProceedings of the 1992 ACM/SIGAPP Symposium on Applied Computing SAC '92 - Kansas City, KS, USA
Duration: Mar 1 1992Mar 3 1992

Publication series

NameApplied Computing: Technological Challenges of the 1990's

Other

OtherProceedings of the 1992 ACM/SIGAPP Symposium on Applied Computing SAC '92
CityKansas City, KS, USA
Period3/1/923/3/92

ASJC Scopus subject areas

  • Engineering(all)

Fingerprint Dive into the research topics of 'Scheduling interval ordered tasks on multiprocessor architecture'. Together they form a unique fingerprint.

Cite this