Outils pour les problèmes d'ordonnancement et de transport

Objectifs

Ce cours a pour objectifs (i) de former les étudiants aux notions de complexité algorithmique et (ii) de
leur apporter quelques outils pour le traitement de deux problématiques en Aide à la Décision. Ces deux
problèmes sont vus à la fois de manière théorique et pratique, par la mise en application des
connaissances, la résolution et le rendu de rapports.
A l’issue du cours, les étudiants connaissent les différentes classes de complexité et savent identifier les
challenges algorithmiques liés à la résolution de deux types de problèmes NP : le jobshop et le TSP. Ils
savent également résoudre de manière approchée ces problèmes, par le biais d’heuristiques et de
métaheuristiques.

Plan du cours

Chapitre 1 : complexité
Importance
Classes de complexité
Problèmes NP-complets
Méthodes exactes
Méthodes approchées : heuristiques, métaheuristiques
Chapitre 2 : problèmes de production
Modélisation de production en atelier
Problème de Flowshop
Problème de Jobshop
Chapitre 3 : problèmes de transport
Nomenclature des problèmes de transport
Problème de Voyageur de Commerce
Problème de Tournées de Véhicules

Description des TP

A remplir

Connaissances requises

Théorie des graphes, Programmation linéaire, Structures de Données, Algorithmique

RSE (Responsabilité Sociale et Environnementale)

Thèmes:
En optimisation les critères peuvent être le temps de réalisation mais on peut aussi minimiser la durée, la distance, et/ou l'impact environnement (émission de CO2 par exemple). La notion de planning qui soient un compromis entre une efficacité temps et un impact environnemental acceptable est abordée.
Nombre d'heures:

Bibliographie

A remplir