Randomized on-line scheduling of parallel jobs
Jiřı́ Sgall · 2002
We study randomized on-line scheduling on mesh machines. We show that for scheduling independent jobs randomized algorithms can achieve a significantly better performance than deterministic ones; on the other hand with dependencies randomization does not help.>