Volume 47, Number 1, January-March 2013
|Page(s)||73 - 87|
|Published online||07 March 2013|
Scheduling an interval ordered precedence graph with communication delays and a limited number of processors
LIP6 – Université Pierre et Marie Curie,
4 place Jussieu,
Paris Cedex 05,
2 Laboratoire IBISC, 523 place des terrasses, 91000 Evry, France
3 Kalray, 445 rue Lavoisier, 38330 Montbonnot Saint Martin, France
4 LIPN, Laboratoire d’Informatique de l’Université Paris-Nord, 99 avenue Jean-Baptiste Clment, 93430 Villetaneuse, France
Received: 1 September 2009
Accepted: 24 January 2013
We consider the scheduling of an interval order precedence graph of unit execution time tasks with communication delays, release dates and deadlines. Tasks must be executed by a set of processors partitioned into K classes; each task requires one processor from a fixed class. The aim of this paper is to study the extension of the Leung–Palem–Pnueli (in short LPP) algorithm to this problem. The main result is to prove that the LPP algorithm can be extended to dedicated processors and monotone communication delays. It is also proved that the problem is NP–complete for two dedicated processors if communication delays are non monotone. Lastly, we show that list scheduling algorithm cannot provide a solution for identical processors.
Mathematics Subject Classification: 90B35
Key words: Approximation and complexity / combinatorial optimization / scheduling
© EDP Sciences, ROADEF, SMAI, 2013
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.