Problème de commande optimale stochastique

Motivation for using semi-Markov process

Problème de commande optimale stochastique

Tout d’abord, nous voulons présenter le problème de commande optimale. Ce problème est né depuis la Seconde Guerre mondiale et est basé sur une méthode mathématique d’optimisation. Le principe du maximum avait été introduit par Pontryagin3 (1903-1988), qui présentait aussi une commande de type bang-bang, une commande restrictive par des conditions de bord. Dans l’ouvrage publié en 1954 (voir Bellman (1954)), Bellman a présenté une nouvelle technique dite programmation dynamique qui permet de résoudre une lasse de problèmes d’optimisation sous contraintes. Cette méthode s’applique à des problèmes d’optimisation dont la fonction objectif se décrit comme suit : 0 00 0 0 ( ) (.) ( ) ( ) , T T t h t t th J t F ds F s ds F s ds + + ò òò== +  (1.1) où h est suffisamment petit. On définit le terme O(h) comme suit : 0 ( ) lim 0, h O h → h = l’expression (1.1) devient : 00 0 J( ) ( ) ( ) ( ). t Ft h Jt h Oh ≅ + ++ (1.2) Ces développements mathématiques permettent d’obtenir des équations différentielles du problème considéré. Par la suite, les autres contributions relatives à une autre classe de systèmes à états hybridés ont été introduites par Krasovskii et Lidskii (1961) et Lidskii (1963). Ces auteurs ont présenté des problèmes sur un horizon infini dans le cas où l’état du système serait constitué de deux différentes parties; x(t) est l’état continue du système, ξ(t) est l’état discret du système qui est caractérisé par une chaîne de Markov. Puis, Sworder (1969) a traité d’un problème linéaire sur un horizon fini en présentant une nouvelle version du principe du maximum. Le développement de ce principe du maximum a été présenté par Rishel (1975); il a étudié le problème dont les stratégies optimales sont décrites par des lois de commande de rétroaction (feedback control) où les états du système sont dynamiques. La contribution de Rishel a été très importante. Il a bien établi les conditions d’optimum du problème qui sont décrites par des équations différentielles admettant une solution unique. Pour le formalisme de Rishel, le principe de Pontryagin a impliqué les équations différentielles dites équations d’Hamilton-Jacobi-Bellman. Ensuite, les travaux de Davis (1984) ont abordé le même 3 problème que ceux de Rishel. En revanche, dans la contribution de Davis (1984), les états ainsi que les politiques de commande du système sont divisés dans l’échelle du temps (time scale). Ce là pour transformer le problème stochastique à celui déterministe dit processus Markovien déterministe par des morceaux (Piecewise Deterministic Markov process). Contrairement aux travaux de Rishel (1975) et de Davis (1984) où les sauts de transition du système considéré sont perturbés par des processus Markoviens homogènes; dans la thèse de doctorat de Boukas (1987), les processus Markovien non-homogènes sont utilisés afin d’introduire une variable commandée dans l’état discret du système. Cette extension a contribué, dans la classe de commande optimale stochastique, à une nouvelle version. Dans tous les travaux de Rishel (1975), Davis (1984) et Boukas (1987), les conditions d’optimum, incluant celles nécessaires et suffisamment, sont établies par la méthode de programmation dynamique. Nous demandons au lecteur de se référer à l’ouvrage de Fleming et Soner (2006) pour plus de détails en ce qui a trait le problème de commande avec la chaîne de Markov. Dans Fleming et Soner (2006), on peut aussi trouver une méthode de résolution des équations d’Hamilton-Jacobi-Bellman dite solution de viscosité. Devant des complexités des structures des conditions d’optimum dans le modèle Markovien proposé dans la littérature, lorsque la taille du système est plus grande, une nouvelle approche dite hiérarchique est présentée par Sethi et al. (1994). En fait, cette approche des perturbations singulières existait depuis les travaux de Lehoczky et al. (1991). Avec cette hiérarchie, la solution des équations d’Hamilton-Jacobi-Bellman (HJB) devient plus simple en ce qui a trait le problème simplifié équivalent. Récemment, une autre contribution du problème d’optimalisation avec des processus stochastiques a été présentée par Cao (2007) intitulé Stochastic Learning and Optimization (SLO). Dans l’ouvrage de Cao, les lois de commande sont appréciées par l’analyse de sensibilité du système au lieu des stratégies optimales. Malgré l’impossibilité, pour que l’on puisse appliquer directement aux systèmes à états discrets dans le temps réel, l’étude de problèmes d’optimisation des systèmes stochastique (SLO) est appliquée dans les domaines dans le cas où les sauts du système 4 pourraient être considérés comme des pas continus tels que la communication, le mouvement de robots, etc.

Application au SPF

Considérant les modèles mathématiques présentés dans la littérature, depuis plus de trente ans, l’application au SPF visait à mesurer la performance du système telle que les taux de production, les stratégies de la maintenance, la stabilité ainsi que le temps de réparation ou de réglage (setup time), etc. Cette sous-section représente l’application relative à l’ordonnancement de la production, de la maintenance préventive et de la stabilité du SPF. En fait, nous n’avons pas présenté le problème du setup du système parce que l’on considère le SPF dans les cas où la flexibilité serait adaptée parfaitement par la gestion de production assistée par ordinateur (Computer Aided Manufacturing-CAM).

Commande optimale des SPF

L’application des théories mathématiques à la commande optimale stochastique des SPF a débuté dans les années 80, notamment dans les travaux d’Older et Suri (1980) dans les cas où les pannes des machines seraient perturbées par des chaînes de Markov; le problème posé est alors l’ordonnancement d’un SPF. Puis, le problème de commande optimale stochastique appliqué aux grands SPF constitués de plusieurs stations de travail (plusieurs machines) a été introduit par les travaux de Kimemia et Gershwin (1983); l’objectif était de trouver des taux de production par minimisation des coûts d’inventaire. Kimemia et Gershwin ont proposé une solution générale associée au concept du seuil critique (hedging point), c’est le point auquel la production du système est optimale. En utilisant la théorie de fille d’attente, Tsitsiklis (1984) a étudié le même problème appliqué au système à trois machines en série. Il a montré que les politiques obtenues sont optimales si et seulement si la fonction coût, l’ensemble des commandes admissibles, ainsi que les espaces d’état sont convexe. Par la suite, en utilisant un processus Markovien, Akella et Kumar (1986), pour un système à une machine traitant un seul type de produit et soumise à des pannes, ont obtenu la politique 5 optimale de type seuil critique exacte par minimisation d’un critère de coût actualisé sur un horizon infini. Cette politique dépend d’un niveau optimal de l’inventaire z*. Le même problème a été étudié par Bielecki et Kumar (1988). En fait, Bielecki et Kumar ont utilisé le modèle de file d’attente de la forme M/M/1 et de la fonction coût linéaire pour déterminer le taux de production. En obtenant une politique optimale, ces auteurs ont montré que le seuil critique est stable si le taux d’utilisation du système est inférieur à 1. Les extensions de la stratégie de commande de type seuil critique sont également discutées par Sharifnia (1988), Malhamé et Boukas (1991). Srivatsant (1993) a présenté une solution exacte du problème pour un SPF à une machine traitant deux types de pièces. En ce qui a trait le problème du seuil critique du SPF à plusieurs types de pièces, celui-ci a été présenté par Perkins et Srikant (1997), Shu et Perkins (2001), et Perkins (2004). Une autre contribution au problème du seuil critique a été présentée par Ciprut et al. (1998); ces auteurs ont directement utilisé les modèles de file d’attente de types M/G/∞, et G/M/∞ de Miller (1963) pour résoudre le problème d’optimisation. Même si on avait obtenu des résultats intéressants au problème du seuil critique, celui-ci devient très complexe lorsque les SPF traitent plusieurs types de pièces. Par conséquent, le problème pourrait devenir celui des polynômes non-déterministes NP; l’opération du SPF pourrait alors être chaotique4 . Comme nous l’avons mentionné ci-dessus (sous-section 1.1.1), Boukas (1987) a contribué à une nouvelle version du problème de commande optimale stochastique par l’extension du modèle de Rishel. Cette version permet de modéliser un SPF dans le cas où les taux de transition incluraient l’usure des machines associées aux actions de maintenance préventive de la machine. Dans les travaux de Boukas, la distribution des probabilités de pannes d’une machine dépend de l’état du système (âge de la machine). Par la suite, Boukas et al. (1995) ont montré que le seuil critique dépend de l’âge de la machine contrairement aux modèles d’Akella et Kumar (1986) et de Bielecki et Kumar (1988). Les prochains paragraphes discutent du problème de maintenance préventive. En ce qui concerne les systèmes complexes et larges, afin de simplifier le problème de commande, chaque événement aléatoire est considéré comme un sous-problème. En conséquence, le problème de commande considéré devient plusieurs sous-problèmes selon le nombre d’événements aléatoires dit commande hiérarchisée. Selon cette technique proposée par Gershwin (1989), la fréquence est une proportion inverse du temps de vie entre deux événements consécutifs et le classement de niveau est à proportion de la fréquence. Soit f1 la fréquence du niveau 1, fk (k > 1) celle du niveau k, alors on a : 0 ≤ f1 << f2 <<< ∞. Exemple : (1) une machine est en panne une fois par 1000 heures, (2) l’action de maintenance préventive est prise une fois par 50 heures, (3) taux de production est 1 unité/heure; on a alors f1 = 1/1000 << f2 = 1/50 << f3 = 1. La prise de décision est consécutive à partir du niveau 1 jusqu’au niveau k. Cette idée fut adoptée afin de réduire la taille du problème de commande des systèmes larges dans les travaux de Sethi et al. (1994- 1997) et de Kenné et Boukas (2003). Gershwin (2002) s’inscrit dans une démarche similaire. Dans les mêmes systèmes complexes et larges, le problème de commande est considéré sur un horizon infini sans taux d’actualisation ρ, la fonction objectif (coût total) peut être infinie. Pour aboutir aux conditions d’optimum, une autre approche est introduite dans certains travaux, par exemple Bertsekas (2001), Sethi et al. (2005), ainsi que Presman et al. (2002). Cette approche offre la possibilité d’optimiser l’espérance des coûts moyens, dite commande optimale avec coût moyen par étage (en anglais, Average cost control). Même si celle-ci est fondée sur la méthode de programmation dynamique, les résultats obtenus du problème de commande optimale ne peuvent plus s’appliquer au système réel car les variables de décision sont quantitatives.

Table des matières

CHAPITRE 1 INTRODUCTION GÉNÉRALE
1.1 Revue de la littérature
1.1.1 Problème de commande optimale stochastique
1.1.2 Application au SPF
1.2 Motivation de la recherche
1.3 Méthodologie
1.4 Contribution du travail de mémoire
1.5 Organisation du mémoire
CHAPITRE 2 ARTICLE # 1 OPTIMAL CONTROL OF PRODUCTION ON FAILUREPRONE MACHINE SYSTEMS WITH SEMI-MARKOV JUMP
2.1 Introduction
2.1.1 Literature review
2.1.2 Motivation for using semi-Markov process
2.1.3 Contribution of this paper
2.2 Problem statement
2.3 Optimality conditions
2.4 Optimal Feedback Control
2.5 Application to single-machine, single part-type
2.5.1 System description
2.5.2 HJB equations for the Optimal Control Problem
2.5.3 Numerical example
2.6 Application analysis to two-machine in parallel
2.6.1 Production system description
2.6.2 Numerical example
2.7 Conclusion
CHAPITRE 3 ARTICLE # 2 FEEDBACK OPTIMAL CONTROL OF DYNAMIC
STOCHASTIC TWO-MACHINE FLOWSHOP
3.1 Introduction
3.1.1 Literature review
3.1.2 Motivation for using the Semi-Markov process
3.1.3 Contribution of this paper
3.2 Problem formulation
3.3 Optimal feedback control
3.4 Dynamic system
3.5 Hedging point policy with feedback control
3.6 System behaviour under the optimal policy
3.6.1 Analysis of state 1 of the system
3.6.2 Analysis of state 2 of the system
3.6.3 Analysis of state 3 of the system
3.6.4 Analysis of state 0 of the system
3.7 Result analysis with constant demand
3.7.1 Interpretation of the results for case A in Table 3.2
3.7.2 Interpretation of the results for case B in Table 3.2
3.8 Result analysis with varying demand
3.9 Conclusion
3.9.1 Summary and extensions
3.9.2 Future Research
CONCLUSIONS GÉNÉRALES
ANNEXE I RISHEL’S ASSUMPTIONS
ANNEXE II APPENDIX OF THE ARTICLE 1
ANNEXE III APPENDIX OF THE ARTICLE 2
ANNEXE V MÉTHODE NUMÉRIQUE
ANNEXE VI SYSTÈME DE PRODUCTION À UNE MACHINE
TRAITANT DEUX TYPES DE PIÈCES
ANNEXE VII MODÈLE MARKOVIEN VS SEMI-MAKOVIEN
ET MÉTHODES D’ÉTUDE
ANNEXE VII MODÈLE DU SYSTÈME MANUFACTURIER
BIBLIOGRAPHIE

Télécharger le rapport complet