Les Indices d'allocation dynamiques dans l'ordonnancement stochastique . existence, caractérisations et détermination

Abstract

Dans un atelier, " N " tâches sont à exécuter sur une machine afin de maximiser l'espérance de la somme des gains linéaires et prévisionnels. Les temps d’exécution des tâches sont supposés aléatoires de lois connues. Les problèmes où les temps d’exécution des tâches sont aléatoires sont dits stochastiques. Une approche théorique pour les résoudre est la théorie des processus bandits, des processus de décision semi-Markoviens. Un exemple de problème d’ordonnancement en temps réel modélisé par ces derniers est exposé. On associe à chaque tâche une priorité dynamique appelée indice d’allocation dynamique et est notée I.A.D. En tout instant, on exécute la tâche qui a le plus grand indice. Ces indices sont calculés en tout instant et durant l’exécution de la tâche. En cas de conflit ou d’égalité entre les plus grands indices, on arbitrera en choisissant une tâche selon une règle connue de type SPT, LPT, FIFO…etc. Si l’objectif du problème d'ordonnancement stochastique est une fonction à coûts séparables, la politique d’indices est montrée optimale. Les preuves de l’existence et de la caractérisation des I.A.D sont données en détail. De la bibliographie, trois algorithmes de détermination des I.A.D existent et ont fait l’objet d'une étude approfondie. Un nouvel algorithme de détermination des I.A.D est proposé et est exposé. Ces quatre algorithmes ont été implémentés en utilisant un langage évolué de programmation. Des expérimentations numériques sur un grand nombre d'exemples de problèmes d’ordonnancement, de l’ordre de mille, ont été effectuées. Un générateur de jeux d'essais est indispensable et est réalisé. Une étude comparative entre ces algorithmes est confectionnée. Si le taux d’actualisation est proche de zéro, notre nouvel algorithme peut prendre en charge des problèmes à cent soixante états. Le temps de calculs est négligeable. Un logiciel I.A.D version 1.0 a été réalisé. Son fonctionnement et aide d'utilisation sont aussi fournis.