Bruno Gaujal, INRIA Sophia-Antipolis
Résume.
Nous allons montrer les propriétés essentielles des fonctions multimodulaires. Ce faisant, nous exposons de nouvelles preuves des propriétés établies par Hajek et nous étendons certains de ses résultats. En particulier, nous montrons la relation qui existe entre multimodularité et convexité. Ensuite, nous obtenons des résultats généraux d'optimisation pour le coût moyen d'une suite de fonctions multimodulaires. En particulier, on exhibe des bornes inférieures et on montre qu'elles sont atteintes pour les suites équilibrées. Finalement, on illustre l'utilité de cette théorie pour le contrôle d'admission dans une file G/G/1 puis avec un systeme (max,+) lineaire, avec des arrivées par paquets, sans information. On montre que la politique équilibrée minimise la charge moyenne dans la file, ou le systeme (max,+). On généralise finalement ce resultat au cas du routage vers plusieurs systèmes.}
mots cles: Multimodularité, convexité, contrôle d'admission, suites équilibrées.