Projet ANR-11-JS02-0002 – LotRelax : Étude de relaxations semi-définies pour des problèmes de dimensionnement et ordonnancement de lots de production
Programme : JCJC - SIMI 2 - Science informatique et applications (JCJC SIMI 2)
Année de financement : 2011
Coordinateur du projet : Madame CELINE GICQUEL (UNIVERSITE DE PARIS XI [PARIS- SUD])
Partenaires : Laboratoire de Recherche en Informatique
Montant : 65000.0 euros
Date de début : 2011
Durée : 36 mois
Résumé : Comment les mathématiques appliquées peuvent-elles aider à mieux gérer une usine ?Résolution de problèmes liés à la planification de production industrielle par la programmation mathématique
Enjeux des problèmes de dimensionnement de lots de productionAujourd'hui, la concurrence mondiale oblige les entreprises industrielles à mieux concevoir et gérer leurs chaines logistiques. Notamment, il devient de plus en plus important de prendre les bonnes décisions concernant un des processus clés de la chaine logistique, la production de biens, car cela affecte directement la productivité et donc la compétitivité des entreprises. Une bonne gestion de la production industrielle implique entre autres de décider quels produits devront être fabriqués dans les prochaines semaines ou les prochains mois, quand et en quelle quantité. Malgré cette définition simple, la planification de production se révèle le plus souvent une tâche très complexe pour des gestionnaires industriels. Ceci est particulièrement vrai quand la planification de production comprend des décisions sur la taille et l'ordonnancement des lots de production. Ce cas se produit lorsque des opérations de préparation des machines (telles qu'un changement d'outils) sont nécessaires entre deux séries de production. Il s'agit alors de décider de la quantité à fabriquer après chaque opération de préparation, c'est-à-dire de la taille du lot, de façon à obtenir le meilleur compromis entre différents objectifs contradictoires.La détermination de la taille et de l'ordonnancement des lots de production nécessite de résoudre des problèmes d'optimisation combinatoire difficiles. Le défi scientifique est de réussir à développer des méthodes d'optimisation capables de fournir rapidement des plans de production quasi-optimaux tout en conservant une représentation du système de production suffisamment précise et réaliste. L'objectif du projet LotRelax est de contribuer à résoudre ce défi scientifique, notamment en s'appuyant sur une branche des mathématiques appliquées : la programmation mathématique.
Modélisation mathématique et résolution algorithmiquePour aborder les problèmes de dimensionnement de lots de production, nous nous plaçons dans le cadre de la programmation mathématique. Il s’agit d’abord de modéliser le problème d'optimisation et d’en construire une représentation abstraite prenant la forme d’un programme mathématique. Ensuite il est nécessaire de développer et d’implémenter des algorithmes de résolution permettant d'identifier la meilleure solution de ce programme mathématique : cette solution correspondra au plan de production à mettre en œuvre dans l’usine.Une première partie du travail a porté sur une variante dite « déterministe » du problème, c.à.d. une variante dans laquelle tous les paramètres d’entrée du problème (demande des clients, capacité de production, coûts…) sont supposés parfaitement connus au moment où on doit construire le plan de production. Une deuxième partie du travail a porté sur une variante dite « stochastique » du problème, c.à.d. une variante où certains paramètres d’entrée du problème (en particulier la demande des clients) sont sujets à incertitude.
Résumé de la soumission : Aujourd'hui, la concurrence mondiale oblige les entreprises industrielles à mieux concevoir et gérer leurs chaines logistiques. Notamment, il devient de plus en plus important de prendre les bonnes décisions concernant un des processus clés de la chaine logistique, la production de biens, car cela affecte directement la productivité et donc la compétitivité des entreprises. Une bonne gestion de la production industrielle implique entre autres de décider quels produits devront être fabriqués dans les prochaines semaines ou les prochains mois, quand et en quelle quantité. Malgré cette définition simple, la planification de production se révèle le plus souvent une tâche très complexe pour des gestionnaires industriels. Ceci est particulièrement vrai lorsque des opérations de préparation des machines (telles qu'un changement d'outils) sont nécessaires entre deux séries de production. Il s'agit alors de décider de la quantité à fabriquer après chaque opération de préparation, c'est-à-dire de la taille des lots, ainsi que de l'ordre de traitement des lots de façon à satisfaire la demande des clients et à minimiser les coûts pour l'entreprise.                                                                                                                                                                                                                   La détermination de la taille et de l'ordonnancement des lots de production nécessite de résoudre des problèmes d'optimisation combinatoire difficiles pour lesquels un grand nombre de techniques de résolution issues des mathématiques appliquées  (recherche opérationnelle, programmation mathématique) ont été proposées. Le défi scientifique ici est de réussir à développer des méthodes d'optimisation capables de fournir rapidement des plans de production quasi-optimaux tout en conservant une représentation du système de production suffisamment précise et réaliste.                                                                                                                                                                                                                Dans ce contexte, le projet LotRelax se concentre sur deux aspects :                                                                                                                          (i) la représentation plus réaliste du système de production grâce à la prise en compte d'un aspect opérationnel : la présence de coûts de préparation des machines dépendant de la séquence de production,                                                                                                                         (ii) l'obtention de plans de productions quasi-optimaux grâce à l'utilisation des dernières avancées théoriques en programmation mathématique, en particulier de la programmation semi-définie.                                                                                                                                                        Ce domaine relativement récent de la programmation mathématique peut être décrit comme l'extension de la programmation linéaire de l'espace des vecteurs réels à l'espace des matrices symétriques. La programmation semi-définie a connu des développements importants ces vingt dernieres années et a notamment permis de résoudre d'éminents problèmes d'optimisation combinatoires, en particulier ceux se formulant comme des programmes quadratiques en nombres entiers. Cependant, comme le montrent plusieurs revues de littératures récentes, la programmation semi-définie n'a pas encore été utilisée pour résoudre des problèmes de dimensionnement de lots de production. L'objectif du projet LotRelax est donc développer une approche de résolution fondée sur l'utilisation de relaxations semi-définies pour des problèmes de dimensionnement de lots de production avec coût de démarrage dépendant de la séquence.
Résultats : Nous nous sommes d’abord concentrés sur la résolution de la variante déterministe du problème de dimensionnement des lots de production. Nous avons principalement exploré deux voies : la mise au point d’une nouvelle approche de résolution fondée sur une relaxation semi-définie du problème et le développement d’une nouvelle famille d’inégalités valides renforçant la relaxation linéaire du problème. Ce travail nous a permis de réduire le temps d’exécution des algorithmes utilisés pour la résolution du programme mathématique : le temps de calcul nécessaire pour obtenir le plan de production optimal à implémenter dans l’usine a ainsi été réduit en moyenne de 30%.
Nous avons ensuite proposé un nouveau modèle pour la variante stochastique du problème de dimensionnement des lots de production. Ce modèle permet notamment aux gestionnaires de production de gérer le risque de rupture de stock et de non satisfaction de la demande des clients au niveau de tout l’horizon de planification, et non période par période comme cela est fait habituellement.  Une nouvelle approche de résolution réduisant sensiblement les temps de calcul pour ce problème a également été proposée.
Perspectives : Les principales perspectives du travail réalisé au cours de ce projet concernent la modélisation et la résolution des problèmes de dimensionnement de production sous incertitude.
Publications et brevets : Les principaux résultats scientifiques du projet ont été publiés dans deux articles de revue internationale, cinq articles de conférence internationale avec actes et cinq  communications dans des conférences internationales sans actes. L’article publié dans la conférence ICORES 2014 a été récompensé par le prix du meilleur article applicatif.
- Articles de revue internationale
C. Gicquel, M. Minoux. Multi-product valid inequalities for the discrete lot-sizing and scheduling problem. Computers & Operations Research, 2015, vol. 54, pp 12-20.
C. Gicquel,  M. Minoux, A. Lisser. An evaluation of semidefinite programming based approaches for discrete lot-sizing problems. European Journal of Operational Research, 2014, vol. 137(2), pp 498–507.
- Article récompensé dans une conférence internationale avec actes 
C. Gicquel and M. Minoux. New multi-product valid inequalities for a discrete lot-sizing problem. 3rd International Conference on Operations Research and Enterprise Systems. March 2014, Angers, France. Best Application Paper Award.