| Issue |
RAIRO-Oper. Res.
Volume 49, Number 2, April-May 2015
New challenges in scheduling theory
|
|
|---|---|---|
| Page(s) | 369 - 381 | |
| DOI | https://doi.org/10.1051/ro/2014048 | |
| Published online | 19 January 2015 | |
Scheduling 2-dimensional grids with large communication delays∗
1 University Mohammed I, Faculty of
Sciences, LaRI laboratory, Oujda, Morocco.
m.daoudi@fso.ump.ma
2 Grenoble Institute of
Technology, France.
trystram@imag.fr; Frederic.Wagner@imag.fr
3 Institut Universitaire de
France
Received:
2
October
2012
Accepted:
26
September
2014
Most parallel and distributed platforms available today show a large unbalance between slow communications and fast local computations which makes the scheduling of tasks much harder to handle efficiently. The so called scheduling with large communication delays problem has been proved to be NP-hard even in some restricted cases. Its status regarding approximation is still unknown. In this work, we propose to study this challenging problem for graphs with a specific structure of 2-dimensional grids. More precisely, we provide lower and upper bounds for both sub-problems of unbounded number of processors and two processors. We show in both cases that the proposed scheduling algorithms are close to lower bounds.
Mathematics Subject Classification: 90B35
Key words: Parallel processing / scheduling / large communication delays
© EDP Sciences, ROADEF, SMAI 2015
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.