TU Berlin

Internet Network ArchitecturesAll Publications

Page Content

to Navigation

All publications

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


Quick Access

Schnellnavigation zur Seite über Nummerneingabe