Séminaire (organisé par l’équipe de recherche RO)

Guillaume Pinot

Institut de Recherche en Communications et en Cybernétique de Nantes, IRCCyN


Une méthode exacte pour le meilleur des cas dans un ordonnancement de groupes


13 octobre


Résumé :

L’ordonnancement de groupes permet d’introduire une flexibilité séquentielle importante tout en garantissant une certaine qualité dans le pire des cas. Une évaluation du meilleur des cas d’un ordonnancement de groupes pourrait également être utile. Elle permettrait une description plus complète de l’ordonnancement de groupes dans sa globalité. Son utilisation dans un outil d’aide à la décision en temps réel basée sur l’ordonnancement de groupes pourrait également être bénéfique en apportant plus d’information au décideur.

Nous proposons un algorithme basé sur la relaxation sur les ressources et sur une borne inférieure de la date de fin d’un groupe. Cet algorithme permet de calculer une borne inférieure de la date de début d’une opération dans le meilleur des cas, une borne inférieure de la date de fin d’une opération dans le meilleur des cas, et une borne inférieure de la date de fin d’un groupe dans le meilleur des cas. Ainsi, une borne inférieure de Lmax et de Cmax peut être calculée facilement. Nous proposons également une relaxation en one machine problem de l’ordonnancement de groupes, permettant d’obtenir une borne inférieure de meilleure qualité pour le Cmax.

Pour compléter notre étude sur le meilleur des cas, nous avons développé un algorithme de résolution exacte adapté à tout objectif régulier. Cet algorithme se base sur l’énumération des ordonnancements actifs. Le parcours de l’arbre de recherche se fait en largeur jusqu’à un certain nombre de nœuds stockés, puis en profondeur. Pour en améliorer les performances, nous avons trouvé une condition suffisante permettant d’ordonnancer un groupe complet tout en conservant la solution optimale.

Seminars


Mardi 10 mai 2016

Séminaire à 14 h 30 en GI042 présenté par Christophe DENIS, Chargé de Formation et de Recherche au Centre de mathématiques et de leurs applications (CMLA), ENS Cachan. « Verificarlo : checking the floating point accuracy of scientific codes »


Lundi 14 mars 2016

Séminaire à 9 h en GI042, présenté par Ahcène Bounceur, Maître de conférence, HDR, à l’Université de Bretagne Occidentale (UBO). « CupCarbon : A New Platform for Simulating Smart Wireless Sensor Networks (SWSN) »


Mardi 9 février 2016

Séminaire à 14 h en GI042 présenté par Fabio D’Andreagiovanni, Chercheur senior et Directeur de projet au département d’optimisation de Zuse Institute Berlin (ZIB), Berlin (Allemagne). « Multiband Robust Optimization : theory and applications »


Jeudi 28 janvier 2016

Séminaire à 15 h 30 en GI042 présenté par Said Tabli, stagiaire au sein du laboratoire Heudiasyc. « Trust Management in Clustered Wireless Sensor Networks »


Pages 1 | 2 | 3 | 4 | 5 | 6 | 7




Actualités
Vidéothèque
Téléchargements
Annuaire



FR SHIC 3272

Collegium UTC/CNRS