CRAN - Campus Sciences
BP 70239 - 54506 VANDOEUVRE Cedex
Tél : +33 (0)3 72 74 52 90 Fax : +33 (0)3 72 74 53 08
cran-secretariat@univ-lorraine.fr
 
 
Sujet de Thèse : Ordonnancement sous incertitudes basé sur les SED : définition d'un cadre de modélisation et de résolution stochastique, application à l'ordonnancement de tâches de production et de maintenance
Dates : 2017/10/01 - 2020/09/30
Directeur(s) CRAN : Jean-François PETIN , Alexis AUBRY
Description : L'ordonnancement consiste à définir des dates de début et de fin à une séquence définie de tâches, en utilisant des ressources dédiées afin de produire un service attendu. Lorsqu'on considère des systèmes de production, ces tâches peuvent être des opérations de production ou de maintenance. Un large scope de problèmes est inclur daîs gette définition générale, dépendant de la structure du système et de son environnement opérationnel.

Afin de traiter ces problèmes, la recherche opérationnelle a proposé beaucoup de méthodes. Cependant, les modèles sous-jacents sont souvent exprimés comme des programmes mathématiques statiques qui considèrent un environnement stable et certain. Ces modèles n'incluent pas la description de la dynamique du système et de son environnement. En pratique, de bonnes performances calculées dans des conditions théoriques peuvent être détériorées lorsque ces conditions sont modifiées suit à une perturbation.
Cela signifie qu'un ordonnancement optimal calculé pour un environnement considéré comme stable et statique doit souvent être complété par un réordonnancement en ligne qui adapte l'ordonnancement initial aux perturbations observées. Ce besoin est particulièrement vrai dans le contexte de l'Usine du Futur ou de l'industrie 4.0 qui devra faire face à un haut degré de variabilité de produits personnalisables et permettra de bénéficier d'informations en temps réel sur l'état du système (observation de l'état des ressources, détection de pannes, observation du vieillissement des ressources) grâce à l'Internet des Objets.

Face aux approches classiques de recherche opérationnelle pour l'ordonnancement de la production, des méthodes basées sur les systèmes à événements discrets (SED) ont émergé pour modéliser et résoudre des problèmes d'optimisation (Lemattre et al., 2011) et des problèmes d'ordonnancement (Panek et al., 2006 ; Kobetski and Fabian, 2006) de la production. L'idée sous-jacente est de modéliser le problème d'ordonnancement comme un modèle Etats-Transitions représentant les séquences d'opérations et les états possibles des ressources puis de réaliser une recherche d'atteignabilité afin de trouver un chemin possible vers un l'état dans lequel toutes les opérations ont été réalisées. L'efficience de la théorie SED pour modéliser et résoudre des problèmes d'ordonnancement a été explorée par plusieurs travaux (Behrmann et al., 2005 ; Panek et al., 2006 ; Subbiah and Engell, 2010).

Les principales conclusions de ces travaux considèrent que les approches basées sur les modèles SED sont des alternatives intéressantes aux approches classiques. Cependant, ces premières approches s'intéressent souvent au problème classique de type JobShop dans sa version non flexible (les opérations sont allouées à des machines uniques). Cela ne permet pas d'utiliser tout le potentiel des modèles SED (modularité, dynamique). L'introduction de la flexibilité dans le problème d'ordonnancement a été étudiée par (Marangé et al., 2011) et a permis la définition d'une action de recherche visant à étudier l'utilisation des SED pour l'ordonnancement, conduite par le CRAN, au sein du GT SED du GDR MACS. L'efficacité des approches SED du point de vue de la modélisation a été étudiée dans (Himmiche et al., 2017).

L'objectif de ce sujet de thèse est d'enrichir les méthodes d'ordonnancement basées sur les modèles SED en tenant compte de la dynamique du système et de ses perturbations inhérentes.
Les problématiques scientifiques sous-jacentes sont liées à la fois aux problèmes de modélisation et d'application :
1) les problématiques de modélisation sont liées à la définition d'un cadre formel SED stochastique pertinent pour :
- représenter un problème d'ordonnancement dans un environnement incertain et plus précisément de résoudre le problème de décomposition intrinsèque aux modèles SED stochastiques
- calculer automatiquement un ordonnancement à partir des modèles SED en enrichissant la trace déterministe obtenue via un graphe d'atteignabilité par une trace stochastique (en utilisant par exemple la théorie des langages probabilistes).
2) les problématiques d'application sont liées aux résultats obtenus :
- trouver un ensemble d'ordonnancements réalisables d'opérations de production et évaluer chacune des solutions par une probabilité de complétude à partir d'un modèle de fiabilité et de disponibilité des ressources ainsi que des données de fabrication stochastiques
- trouver un ordonnancement d'opérations de maintenance prédictive qui permet d'atteindre des objectifs de production et de disponibilité des ressources en tenant compte de modèles de vieillissement du système et capacités résiduelles des machines.

Afin de résoudre ces problèmes, nous proposons de suivre le plan suivant :
1) Réaliser un état de l'art sur les langages SED stochastiques et leurs applications afin de :
- identifier et discuter des différents langages basés sur des données stochastiques et des méthodes de résolutions associées.
- identifier et discuter des différentes approches classiques de recherche opérationnelle
- d'évaluer la capacité de ces approches SED et classiques à modéliser des perturbations, à donner des informations pertinentes, à permettre une interprétation pertinente dans le contexte des systèmes de production
- d'évaluer l'efficacité des méthodes de résolution associées.
2) Proposer une méthode d'ordonnancement basé sur des modèles SED stochastiques en définissant :
- un cadre de modélisation dédié aux problèmes d'ordonnancement en environnement incertain.
- une méthode de résolution associée capable de construire des ordonnancements réactifs suite à l'apparition d'une perturbation. Cela implique de proposer un algorithme capable de calculer une trace entre un état courant et un état désiré et de quantifier ensuite la probabilité d'occurrence de cette trace.
3) Evaluer la proposition par rapport aux approches classiques pour l'ordonnancement de taches de production et de maintenance. Il s'agit ici de :
- appliquer l'approche proposée à un cas d'étude idéalement provenant d'un partenaire industriel
- considérer l'approche de modélisation et évaluer sa complexité, sa généricité et son évolutivité comme définies dans (Himmiche et al., 2017)
- considérer l'approche de résolution et évaluer son efficacité (temps de calcul, passage à l'échelle).
Mots clés : Systèmes Flexibles de production, Ordonnancement, Modèles SED stochastiques
Département(s) :
Ingénierie des Systèmes Eco-Techniques
Financement : Allocation de recherche
Publications : hal-01094679, hal-00627635, hal-00654166    + CRAN - Publications