Résolution des problèmes d'ordonnancement stochastique par les processus bandits

Abstract

« N » tâches sont à exécuter sur une seule machine. Dans beaucoup d’applications industrielles, une incertitude sur les temps d’exécution est à considérer. Ils sont supposés aléatoires de distributions de probabilité connues. Ces problèmes d’ordonnancement sont incertains et sont dits stochastiques. Passer d’une tâche à une autre nécessite en général que la machine soit réglée une seconde fois. Ce temps de réglage est parfois inconnu et non apprécié. L’arrivée de l’information sur les tâches, tel leur temps d’exécution, peut ne pas être disponible. Des généralités et définitions de processus sont énoncées succinctement où les notions de la propriété de Markov et du graphe de transition sont évoquées. Notre fonction objectif est défini par l’espérance du coût prévisionnel. Elle vérifie une équation fonctionnelle. Nous exposons une méthode de détermination d’une politique optimale d’exécution de processus. Nous caractérisons l'existence d'une politique optimale et nous donnons des méthodes récentes de sa détermination. Un exemple d’une politique optimale de remplacement d’une machine est fourni. Les algorithmes de Howard [22] et de l’ « itération sur les valeurs », des algorithmes efficaces de détermination de politiques optimales, sont exposés en détail. Ils ont été implémentés en utilisant un langage évolué. Des exemples d’application sont fournis. Une comparaison en temps d’exécution des algorithmes est aussi faite. Un graphe, temps d’exécution en fonction des états du processus, est tracé donnant une allure meilleure de celui de Howard. On a étudié le cas où le processus à décision est non markovien. Durant une transition d’un processus, des actions peuvent être entreprises. Nous présentons une politique optimale de résolution, une politique d’indices. On associe à chaque tâche, une priorité ou un indice d’allocation dynamique. Nous exposons cette méthodologie due à Glazebrook succinctement. Nous avons implémenté un algorithme de leur détermination. Un exemple d’application est même fourni. Nous avons fourni un logiciel de gestion Log-version 1.0 de détermination de politique optimale pour un processus à 2-décisions markovien, conçu par nos soins. Dans une partie annexe, des programmes sont insérés.