Les Indices D'allocation Dynamiques Dans L'ordonnancement Stochastique . Existence , Caractérisations Et Détermination
Résumé: 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.
Mots-clès:
Nos services universitaires et académiques
Thèses-Algérie vous propose ses divers services d’édition: mise en page, révision, correction, traduction, analyse du plagiat, ainsi que la réalisation des supports graphiques et de présentation (Slideshows).
Obtenez dès à présent et en toute facilité votre devis gratuit et une estimation de la durée de réalisation et bénéficiez d'une qualité de travail irréprochable et d'un temps de livraison imbattable!
Aucun fichier associé
Si le fichier est volumineux, l'affichage peut échouer. Vous pouvez obtenir le fichier directement en cliquant sur le bouton "Télécharger".
