FST-DSPM-94
Anja Feldmann, Jiri Sgall, Shang-Hua Teng. Dynamic scheduling on parallel machines. Theoretical Computer Science, 130(1):49-72, 1994.
Download [help]
Download paper:
Doi page 
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
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(sqrt{loglog N})-competitive algorithm for online scheduling on a two-dimensional mesh of N processors and we prove a matching lower bound of Omega(sqrt{loglog 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.
Keyword
[ Ca ]
Contact
BibTex Reference
@article{FST-DSPM-94,
Author = {Feldmann, Anja and Sgall, Jiri and Teng, Shang-Hua},
Title = {Dynamic scheduling on parallel machines},
Journal = {Theoretical Computer Science},
Volume = {130},
Number = {1},
Pages = {49--72},
Publisher = {Elsevier Science Publishers Ltd},
Address = {Essex, UK},
Year = {1994}
}
EndNote Reference [help]
Get EndNote Reference (.ref)
It has been automatically generated using the bib2html program.