Dans le cadre des séminaires de l’équipe Cornet, Olivier Bilenne (ENPC) présentera son travail de recherche sur Solutions of Poisson’s equation for first-policy improvement in parallel queueing systems, le 18 novembre 2022 à 11h35 en salle de réunion.
Résumé : Cette présentation aborde le problème de la répartition des tâches (consciente de l’état) pour minimiser le coût moyen à long terme dans un système de files d’attente parallèles avec des arrivées de type Poisson. L’itération de politique est une technique visant à atteindre l’optimalité en améliorant une politique de répartition initiale. Sa mise en œuvre repose sur le calcul de fonctions de valeur. Dans ce contexte, nous examinerons la file M/G/1-FCFS dotée d’une fonction de coût arbitraire pour les temps d’attente des tâches entrantes. La fonction de valeur relative associée est une solution de l’équation de Poisson pour les chaînes de Markov, que je propose de résoudre dans le domaine de la transformée de Laplace en considérant un processus stochastique auxiliaire étendu à des états de retard négatifs (imaginaires). Cette construction nous permet de trouver des solutions analytiques pour des fonctions de coût simples (polynomiales, exponentielles et leurs compositions morcelées), ce qui permet à son tour de dériver des bornes d’intervalle pour les fonctions de valeur relative pour des fonctions de coût plus générales. De telles bornes permettent une mise en œuvre exacte de la première étape d’amélioration de politique dans un système de files d’attente parallèles. L’un des objectifs de cette présentation est d’identifier les principaux obstacles à la mise en œuvre de l’algorithme d’itération de politique dans les systèmes de files d’attente parallèles. Le but est ensuite de discuter des nouvelles orientations que l’analyse dans le domaine de la transformée pourrait offrir au-delà de la première amélioration de politique.
Référence : Olivier Bilenne. Dispatching to parallel servers: solutions of Poisson’s equation for first-policy improvement. Queueing Systems, Springer Verlag, 2021, Queueing Systems, 99 (3), pp.199-230. https://hal.archives-ouvertes.fr/hal-02925284