Veuillez utiliser cette adresse pour citer ce document : https://di.univ-blida.dz/jspui/handle/123456789/12854
Titre: Les Indices d'allocation dynamiques dans l'ordonnancement stochastique . existence, caractérisations et détermination
Auteur(s): Kali, Abdesselem
Mots-clés: Indices d'allocation dynamiques
Ordonnancement stochastique
Date de publication: 2007
Editeur: Univ.Blida 1
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.
Description: 154 p.- :ill. ; 30 cm.
URI/URL: http://di.univ-blida.dz:8080/jspui/handle/123456789/12854
Collection(s) :Thèse de Magister

Fichier(s) constituant ce document :
Fichier Description TailleFormat 
32-510-71-1.pdfThèse de Magister6,21 MBAdobe PDFVoir/Ouvrir


Tous les documents dans DSpace sont protégés par copyright, avec tous droits réservés.