Claire Hanen
LIP6 - Université Paris X

Titre: Ordonnancements périodiques de graphes d'évènements temporisés généralisés;

Issu d'un travail en collaboration avec Alix Munier et Abir Benabid.

Dans cet exposé, nous montrons une condition nécessaire et suffisante d'existence d'ordonnancement périodiques dans un graphe d'évènement temporisé généralisé. Nous verrons qu'elle ne coincide pas, comme dans le cas d'un graphe d'évènement simple, avec la condition d'existence d'un ordonnancement.
Nous verrons comment ce résultat peut être utilisé pour obtenir polynômialement des bornes supérieures du temps de cycle moyen d'un GEG. Enfin, nous montrerons les points de difficulté ne permettant pas à l'heure actuelle d'obtenir le temps de cycle moyen optimal d'un GEG en temps polynômial.