Mini-cours : Ordonnancement et Approximation

Le mini-cours (16 heures) se déroulera du 24 juin 14h au 26 juin midi. Le thème retenu pour cette édition est en lien avec l'ordonnancement et l'approximation polynomiale. Les interventions seront assurées par des spécialistes de ces thématiques. Elles couvrent les sujets suivants :

• Ordonnancement : généralités, modèles et complexité
• par Imed KACEM, Université de Lorraine
• Lundi 24 juin 2019 de 14:00 à 18:00 
• Lieu : Petit Amphi, UFR MIM, Université de Lorraine, 3 rue Augustin Fresnel, 57000 METZ
• Résumé : Le but de cet exposé est d'introduire les notions de base sur les problèmes d'ordonnancement. Plus précisément, on décrit les motivations et les applications qui ont conduit à étudier ces problèmes. Ensuite, nous rappelerons ses différentes caractéristiques : tâches, contraintes, ressources, objectifs. Nous abordons également les techniques générales de modélisation, de notation et résolution. Nous terminerons cette intervention par des explications de quelques exemples simples d'approximation pour introduire l'intervention suivante.
• Télécharger la présentation

• Approximation polynomiale : fondements et techniques 
• par Bruno ESCOFFIER, Université de Paris 6
• Mardi 25 juin de 8:30 à 11:45 
• Lieu : Salle BN2-001, UFR MIM, Université de Lorraine, 3 rue Augustin Fresnel, 57000 METZ
• Résumé : Le but de cet exposé est de donner les bases et les idées principales du domaine de l'approximation polynomiale, né il y a bientôt 50 ans. Nous reviendrons tout d'abord sur les débuts de l'approximation polynomiale, puis illustrerons quelques techniques classiques sur des exemples simples. Nous aborderons ensuite les résultats négatifs pour cerner les limites de l'approche. Plusieurs points seront approfondis dans d'autres exposés au cours de la semaine.
• Télécharger la présentation et les compléments

• Résolution exacte ou approchée en temps exponentiel avec application à l’ordonnancement
• par Vincent T'KINDT, Université de Tours
• Mardi 25 juin de 13:30 à 16:00
• Lieu : Petit Amphi, UFR MIM, Université de Lorraine, 3 rue Augustin Fresnel, 57000 METZ
• Résumé : Au cours de cet exposé nous aborderons dans un premier temps l’algorithmique en temps exponentiel lorsque l’on s’intéresse à la résolution exacte de problème d’ordonnancement difficiles. Trois techniques de base seront introduites et illustrées au travers d’exemples et d’exercices. Dans une seconde partie, nous nous focaliserons sur la mise au Notes d’algorithmes d’approximation en temps exponentiel, pour des problèmes d’ordonnancement non approximable en temps polynomial.
• Télécharger la présentation

• Approximation polynomiale et ordonnancement
• par Imed KACEM, Université de Lorraine
• Mardi 25 juin de 16:30 à 18:30
• Lieu : Petit Amphi, UFR MIM, Université de Lorraine, 3 rue Augustin Fresnel, 57000 METZ
• Résumé : L’objectif de ce tutoriel est de présenter les approches de construction des schémas d’approximation polynomiale pour les problèmes d’ordonnancement et de mettre en évidence l’intérêt des techniques classiques (programmation dynamique, programmation linéaire, PLNE,…) dans l’élaboration de tels schémas pour certains cas difficiles. Nous présentons ces différentes approches de construction (simplification de l’instance d’entrée, modification d’un algorithme exact, structuration de l’espace des solutions). Nous présentons également des exemples d’approximation obtenues directement à l’aide de ces techniques classiques.

• Approximation et programmation linéaire 
  • par Kim Thang NGUYEN, Université d'Evry Paris-Saclay
    
  • Mercredi 26 juin de 8:30 à 11:45
  • Lieu : Petit Amphi, UFR MIM, Université de Lorraine, 3 rue Augustin Fresnel, 57000 METZ
  • Résumé: Le but de cet exposé est d’introduire les méthodes basées sur la programmation linéaire, la programmation mathématique pour la conception et l’analyse d’algorithmes d’approximation. Nous présenterons les techniques arrondi, primal-dual récentes et également les perspectives et directions prometteuses. Nous illustrerons ces techniques principalement sur les problèmes d'ordonnancement et de routage.  
  • Télécharger la présentation