Hostname: page-component-7b7567c8c-2n9c9 Total loading time: 0 Render date: 2026-11-17T11:28:54.886Z Has data issue: false hasContentIssue false

Scheduling an interval ordered precedence graph with communication delaysand a limited number of processors

Published online by Cambridge University Press:  07 March 2013

Alix Munier Kordon
Affiliation:
LIP6 – Université Pierre et Marie Curie, 4 place Jussieu, 75252 Paris Cedex 05, France. alix.munier@lip6.fr
Fadi Kacem
Affiliation:
Laboratoire IBISC, 523 place des terrasses, 91000 Evry, France
Benoît Dupont de Dinechin
Affiliation:
Kalray, 445 rue Lavoisier, 38330 Montbonnot Saint Martin, France
Lucian Finta
Affiliation:
LIPN, Laboratoire d’Informatique de l’Université Paris-Nord, 99 avenue Jean-Baptiste Clment, 93430 Villetaneuse, France

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

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.

Information

Type
Research Article
Copyright
© EDP Sciences, ROADEF, SMAI, 2013