Publication at Faculty of Mathematics and Physics |
2010
Abstract
We study the online problem of scheduling unit-time parallel jobs on hypercubes. A parallel job has to be scheduled between its release time and deadline on a subcube of processors/ The objective is to maximize the number of early jobs.
We provide a 1.6-competitive algorithm for the problem and prove that no deterministic algorithm is better than 1.4-competitive