Online scheduling of parallel jobs on hypercubes : maximizing the throughput

0353476 - MÚ 2011 RIV DE eng C - Conference Paper (international conference)
Zajíček, Ondřej - Sgall, Jiří - Ebenlendr, Tomáš
Online scheduling of parallel jobs on hypercubes : maximizing the throughput.
Parallel Processing and Applied Mathematics. Vol. Part 2. Berlin: Springer, 2010 - (Wyrzykowski, R.; Dongarra, J.; Karczewski, K.), s. 52-61. Lecture Notes in Computer Science, 6068. ISBN 978-3-642-14402-8.
[Parallel processing and applied mathematics. Wroclaw (PL), 13.09.2009-16.09.2009]
R&D Projects: GA AV ČR IAA100190902; GA MŠMT(CZ) 1M0545
Institutional research plan: CEZ:AV0Z10190503
Keywords : scheduling * parallel jobs * throughput
Subject RIV: BA - General Mathematics
http://link.springer.com/chapter/10.1007%2F978-3-642-14403-5_6

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.
Permanent Link: http://hdl.handle.net/11104/0192720