DYNAMIC SCHEDULING ON PARALLEL MACHINES

We study the problem of on-line job-scheduling on parallel machines wi th different network topologies. An on-line scheduling algorithm sched ules a collection of parallel jobs with known resource requirements bu t unknown running times on a parallel machine. We give an O(square-roo t log log N)-competitive algorithm for on-line scheduling on a two-dim ensional mesh of N processors and we prove a matching lower bound of O MEGA(square-root log log 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-dime nsional 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 t he two-dimensional mesh actually shows that no greedy-like algorithm c an perform well.