LIP6 2004/007

• Rapports de recherche
  Ordonnancements périodiques pour contraintes de précédence linéaires
• C. Hanen, A. Munier-Kordon
• 17 pages - 25/05/2004- document en - http://www.lip6.fr/lip6/reports/2004/lip6.2004.007.pdf - 169 Ko
• Contact : Alix.Munier (at) nulllip6.fr
• Ancien Thème : ASIM
On considère le calcul d'un ordonnancement périodique pour un ensemble de tâches soumises à des contraintes de précédences linéaires: une contrainte de précédence linéaire est définie entre deux tâches et correspond à un ensemble de contraintes de précédence entre deux exécutions dont la différence d'itération est une fonction linéaire. L'ensemble des contraintes linéaires est modélisable par un graphe de précédence linéaire. L'objectif est de minimiser la période maximale d'une tâche pour un graphe de précédences linéaires fixé. Dans un premier temps, nous rappelons que ce problème est modélisable par un programme linéaire. Puis, nous développons un algorithme polynomial pour le résoudre pour les graphes unitaires, qui est une sous-classe particulière de graphes de précédences linéaires. Nous montrons également qu'un ordonnancement périodique peut ne pas exister dans ce cas. Dans le cas général, nous calculons une décomposition du graphe en composantes unitaires et nous supposons que, pour chacune de ces composantes, il existe un ordonnancement périodique. Nous calculons alors des bornes inférieures de la période, et nous montrons qu'elles ne sont pas forcément atteintes par un ordonnancement périodique. Nous introduisons alors la notion d'ordonnancement quasi-périodique, et nous montrons que cette nouvelle classe d'ordonnancement atteint toujours ces valeurs.

• Mots clés : Ordonnancements périodiques, Ordonnancements cycliques, contraintes de précédence linéaires
• Directeur de la publication : Francois.Dromard (at) nulllip6.fr