@inproceedings{1bb61a25b85d46089e55baa4eb1f31ba,
title = "Scheduling interval ordered tasks on multiprocessor architecture",
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.",
author = "Ali, {Hesham H.} and Hesham El-Rewini",
year = "1992",
doi = "10.1145/130069.130091",
language = "English (US)",
isbn = "089791502X",
series = "Applied Computing: Technological Challenges of the 1990's",
publisher = "Publ by ACM",
pages = "792--797",
booktitle = "Applied Computing",
note = "Proceedings of the 1992 ACM/SIGAPP Symposium on Applied Computing SAC '92 ; Conference date: 01-03-1992 Through 03-03-1992",
}