Evénements



Calendrier

octobre 2017 :

Rien pour ce mois

septembre 2017 | novembre 2017

Lot-sizing en programmation par contraintes

Accueil > Communauté GOSPI > Thèses

Doctorant : German Grigori

  • Directeur : GAYON Jean-Philippe
  • Laboratoire : G-SCOP

La thèse porte sur la résolution de problème de planification de production (lot-sizing) avec des approches basées sur la programmation par contraintes (CP). La planification de production est un domaine bien étudié en recherche opérationnelle et en optimisation combinatoire, avec de nombreuses applications industrielles. Le problème fondateur [1] ainsi que plusieurs de ses variantes se résolvent par programmation dynamique en temps polynômial. En présence de contraintes additionnelles, ces problèmes sont souvent traités par programmation linéaire en nombres entiers et de nombreuses formulations linéaires ont été étudiées dans ce domaine [2]. Des algorithmes d’approximation ont par ailleurs été proposés pour des variantes NP-difficile du problème [3]. Très récemment, des travaux se sont intéressés à la résolution de problèmes de lot-sizing par la programmation par contraintes [4]. L’objectif de la thèse est de développer un cadre d’étude pour modéliser et résoudre par programmation par contraintes des problèmes de planification de production. La programmation par contraintes pourrait offrir des avantages de modélisation et de passage à l’échelle par rapport à la programmation linéaire. Les industriels ont en effet besoin d’outils plus faciles à utiliser pour modéliser les problèmes pratiques et ne s’intéressent pas nécessairement à la solution optimale mais davantage à l’obtention de bonnes solutions dans un temps raisonnable et pour des problèmes de grandes tailles. De plus, bien que la CP soit souvent perçue comme une technique dédiée à des problèmes difficiles de satisfaction plutôt que d’optimisation, des résultats récents [5] montrent qu’on peut concevoir des approches compétitives en CP pour des grands problèmes d’optimisation. Nous pensons que la planification de production est un domaine qui se prête très bien à la poursuite de cet axe de recherche. Une première étape consistera à identifier les sous-problèmes clefs (qui apparaissent fréquemment dans les modèles réels et plus complexes) et de concevoir des contraintes globales encapsulant des algorithmes de filtrage efficaces pour ces sous-problèmes. On se focalisera d’abord sur la mise au point d’algorithmes de filtrage polynomiaux ou pseudo-polynomiaux. Cependant on s’intéressera également à la mise au point d’algorithmes de filtrage utilisant la Relaxation Lagrangienne pour traiter des cas NP-Difficiles mais importants pour la modélisation de nombreux problèmes réels. Une deuxième étape porte sur la modélisation et résolution de problèmes de Lot-sizing plus complexes en utilisant les briques de résolution mises au point précédemment. Les problèmes abordés dans la thèse seront avant tout académiques mais on cherchera également à mettre en œuvre ce travail sur un problème réel avec des jeux de données industriels. Les approches développées seront comparées aux méthodes plus classiques reposant sur la programmation dynamique et la programmation linéaire en nombres entiers. [1] H. Wagner and T. Whitin (1958), "Dynamic version of the economic lot size model," Management Science, Vol. 5, p. 89-96. [2] Y. Pochet and A. Wolsey (2006). Production planning by mixed integer programming. Springer Series in Operations Research and Financial Engineering. [3] J.P. Gayon, G. Massonnet, C. Rapine and G. Stauffer and (2014) A simple and fast 2-approximation algorithm for the one-warehouse multi-retailers problem. Submitted to Operations Research. [4] Vinasétan Ratheil Houndji, Pierre Schaus, Lawrence Wolsey and Yves Deville. The StockingCost constraint, to be published, CP 2014 [5] H. Cambazard, B. Penz, A Constraint Programming Approach for the Traveling Purchaser Problem. CP 2012 : 735-749