Dynamic Scheduling on Parallel Machines. Anja Feldmann, Jiri Sgall, Shang-Hua Teng; FOCS 1991.
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.

Postscript