Soutenance de thèse

Mohamed Amine MKADEM

Flow-shop avec temps de transport, modélisation linéaire et approches de résolution exacte


Le jeudi 7 décembre 2017 à 14 h en amphi Gauss (Centre de recherche de l’UTC), à l’université de technologie Compiègne


Membres du Jury :

  • M. Jacques Carlier, professeur émérite, université de technologie de Compiègne, laboratoire Heudiasyc
  • M. Aziz Moukrim, professeur des universités, université de technologie de Compiègne, laboratoire Heudiasyc
  • M. Ammar Oulamara, professeur des universités, université de Lorraine, LORIA, Vandoeuvre-Les-Nancy
  • M. Éric Sanlaville, professeur des universités, université du Havre, LITIS
  • M. Mehdi Serairi, enseignant chercheur, université de technologie de Compiègne, laboratoire Heudiasyc
  • M. Nikolay Tchernev, professeur des universités, université Clermont Auvergne, ISIMA, Aubière
  • Mme Alice Yalaoui, maître de conférences, université de technologie de Troyes, LOSI


Résumé :

Dans le cadre de cette thèse, nous traitons le problème de flow-shop à deux machines avec temps de transport où l’objectif consiste à minimiser le temps de complétion maximal. Dans un premier temps, nous nous sommes intéressés à la modélisation de ce problème. Nous avons proposé plusieurs programmes linéaires en nombres entiers. En particulier, nous avons introduit une formulation linéaire basée sur une généralisation non triviale du modèle d’affectation pour le cas où les durées des opérations sur une même machine sont identiques. Dans un deuxième temps, nous avons élargi la portée de ces formulations mathématiques pour développer plusieurs bornes inférieures et un algorithme exact basé sur la méthode de coupe et branchement (Branch-and- Cut). En effet, un ensemble d’inégalités valides a été considéré afin d’améliorer la relaxation linéaire de ces programmes et d’accélérer leur convergence. Ces inégalités sont basées sur la proposition de nouvelles règles de dominance et l’identification de sous-instances faciles à résoudre. L’identification de ces sous-instances revient à déterminer les cliques maximales dans un graphe d’intervalles. En plus des inégalités valides, la méthode exacte proposée inclut la considération d’une méthode heuristique et d’une procédure visant à élaguer les noeuds Enfin, nous avons proposé un algorithme par séparation et évaluation (Branch-and-Bound ) pour lequel, nous avons introduit des règles de dominance et une méthode heuristique basée sur la recherche locale. Nos expérimentations montrent l’efficacité de nos approches qui dominent celles de la littérature. Ces expérimentations ont été conduites sur plusieurs classes d’instances qui incluent celles de la littérature, ainsi que des nouvelles classes d’instances où les algorithmes de la littérature se sont montrés peu efficaces.
Mots Clés : recherche opérationnelle, flow-shop, temps de transport, programmation linéaire en nombres entiers, bornes inférieures, règles de dominance, heuristiques, inégalités valides, branch-and-cut, branch-andbound.



Actualités
Vidéothèque
Téléchargements
Annuaire



FR SHIC 3272

Collegium UTC/CNRS