"Raisonnement energétique / solution préemptive pour le problème
à machines parallèles"

F. Tercinet*, E. Néron*, Ch. Lenté* and J.Carlier**

*  Laboratoire d'Informatique de l'Université de Tours
** Heudiasyc Université de Technologie de Compiègne

Notre exposé portera sur une étude comparative entre le
"raisonnemment énergétique" proposé par [Erschler et al, 91] et
le "raisonnement par flot pour le calcul de la solution
préemptive" proposé par [Horn,73] sur le problème Pm|ri,di|-.
Après la présentation de ces deux méthodes dans leur version de
base, nous montrons sur des petits exemples qu'aucune de ces deux
méthodes ne domine l'autre même dans le cas où nous ajoutons des
ajustements (itératifs ou non) au raisonnement énergétique.
Ensuite, nous proposons une amélioration du calcul de la solution
du flot en ajoutant des capacités minimum sur certains arcs du
graphe. D'autre part, nous proposons une nette amélioration du
raisonnement énergétique en introduisant la notion de capacité
constante par morceaux sur les intervalles considérés dans cette
méthode.  Cette capacité est ensuite introduite dans le test de
faisabilité. Enfin, nous présentons une version améliorée de
l'algorithme en O(n²) proposé par [Baptiste, Le Pape and Nuijten,
99] pour la prise en compte de la capacité constante par
morceaux, ainsi que nos résultats éxpérimentaux.