direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments

Publications by Type: Conference and Workshop Publications

see also conference papers, workshop papers, demos, and posters. (under construction)

Dynamic scheduling on parallel machines
Citation key FST-DSPM-91
Author Feldmann, Anja and Sgall, Jiri and Teng, Shang-Hua
Title of Book Proceedings of the 32nd annual symposium on Foundations of computer science
Pages 111–120
Year 1991
ISBN 0-8186-2445-0
Location San Juan, Puerto Rico
Address Los Alamitos, CA, USA
Publisher IEEE Computer Society Press
Abstract In this paper, we study the problem of on-line job-scheduling on various parallel architectures. In particular, we give an O(sqrt(loglog n))-competitive algorithm for on-line dynamic scheduling on an nxn mesh. We prove that this algorithm is optimal up to a constant factor–-no on-line algorithm can achieve a competitive ratio better than (1/42) sqrtloglog n. Our algorithm is not greedy and the lower bound proof shows that no greedy-like algorithm can be very good. Our upper bound result can be generalized to any fixed dimensional meshes. We also present competitive scheduling algorithms for other architectures including hypercubes, trees, meshes of trees, and PRAMs.
Link to publication Download Bibtex entry

Zusatzinformationen / Extras

Quick Access:

Schnellnavigation zur Seite über Nummerneingabe

Auxiliary Functions

Under Construction

This page/section is
still under construc-
tion. Please try again