direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments

Es gibt keine deutsche Übersetzung dieser Webseite.

All publications

Dynamic scheduling on parallel machines
Zitatschlüssel FST-DSPM-94
Autor Feldmann, Anja and Sgall, Jiri and Teng, Shang-Hua
Seiten 49–72
Jahr 1994
ISSN 0304-3975
DOI http://dx.doi.org/10.1016/0304-3975(94)90152-X
Adresse Essex, UK
Journal Theoretical Computer Science
Jahrgang 130
Nummer 1
Verlag Elsevier Science Publishers Ltd.
Zusammenfassung We study the problem of online job-scheduling on parallel machines with different network topologies. An online scheduling algorithm schedules a collection of parallel jobs with known resource requirements but unknown running times on a parallel machine. We give an O(sqrtloglog N)-competitive algorithm for online scheduling on a two-dimensional mesh of N processors and we prove a matching lower bound of Ω(sqrtloglog N) on the competitive ratio. Furthermore, we show tight constant bounds of 2 for PRAMs and hypercubes, and present a 2.5-competitive algorithm for lines. We also generalize our two-dimensional mesh result to higher dimensions. Surprisingly, our algorithms become less and less greedy as the geometric structure of the network topology becomes more complicated. The proof of our lower bound for the two-dimensional mesh actually shows that no greedy-like algorithm can perform well.
Link zur Publikation Download Bibtex Eintrag

Zusatzinformationen / Extras


Schnellnavigation zur Seite über Nummerneingabe