FST-DSPM-91
Anja Feldmann, Jiri Sgall, Shang-Hua Teng. Dynamic scheduling on parallel machines. In Proceedings of the 32nd annual symposium on Foundations of computer science, (Location: San Juan, Puerto Rico), Pages 111-120, IEEE Computer Society Press, Los Alamitos, CA, USA, 1991.
Download [help]
Download paper:
Postscript (ps) 
Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.
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) sqrt{loglog 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.
Keyword
[ Ca ]
Contact
BibTex Reference
@InProceedings{FST-DSPM-91,
Author = {Feldmann, Anja and Sgall, Jiri and Teng, Shang-Hua},
Title = {Dynamic scheduling on parallel machines},
BookTitle = {Proceedings of the 32nd annual symposium on Foundations of computer science},
Pages = {111--120},
Publisher = {IEEE Computer Society Press},
Address = {Los Alamitos, CA, USA},
Location = {San Juan, Puerto Rico},
Year = {1991}
}
EndNote Reference [help]
Get EndNote Reference (.ref)
It has been automatically generated using the bib2html program.