logo EDITE Sujets de doctorat

Approche polyédrale pour les problèmes d'ordonnancement juste-à-temps

Sujet proposé par
Directeur de thèse:
Doctorant: Anne-Elisabeth FALQ
Unité de recherche UMR 7606 Laboratoire d'informatique de Paris 6

Domaine: Sciences et technologies de l'information et de la communication

Projet

Ce sujet de thèse s'inscrit dans le domaine de l'optimisation combinatoire. Il s'agit d'étudier la problématique de l'ordonnancement juste-à-temps au travers de la programmation mathématique discrète et des approches polyédrales. Les travaux académiques dans le domaine de l'ordonnancement juste-à-temps présente plusieurs études algorithmiques du problème dans l'objectif d'une résolution exacte ou heuristique. Si la littérature scientifique en ordonnancement est très riche, elle comporte proportionnellement peu de résultats en programmation mathématique sur les problèmes centraux comme l'ordonnancement juste-à-temps. Des problèmes d'ordonnancement avec critères réguliers ont toutefois été étudiés en utilisant la programmation mathématique et les approches polyédrales. Une littérature assez étendue étudie des formulations linéaires en nombres entiers des problèmes classiques d'ordonnancement en général. De plus, des approches polyédrales ont été conduites pour des cas d'ordonnancement polynomiaux.

Enjeux

-Objectif 1: Formulation disjonctive

Nous nous intéressons dans le cadre de cette thèse à différentes classes de l'ordonnancement juste-à-temps et en particulier, les cas suivants: L'ordonnancement juste-à-temps avec un nombre infini de machines, pour lequel les résultats de la littérature s'étendent naturellement et le problème juste-à-temps à machine unique et date d'échéance commune pour toutes les tâches. Ce problème est polynomial si la date d'échéance est suffisamment éloignée de la date 0 et NP-difficile dans le cas contraire. Une approche polyédrale pour ce cas particulier serait particulièrement intéressante pour étudier en profondeur les limites de complexité de cette classe de problèmes.

-Objectif 2: Résolution par programmation mathématique

Au delà de l'étude théorique des formulations, celles utilisées dans la première phase de cette thèse peuvent être à la base de méthodes efficaces de résolution. Un objectif de cette thèse sera de mettre en oeuvre des algorithmes de Branch-and-Cut basés sur l'approche polyédrale des problèmes. Pour cela, nous étudierons des classes d'inégalités valides pour le problème juste-à-temps ainsi que les formulations étendues afin de prendre en compte le caractère irrégulier de ce critère d'ordonnancement.

-Objectif 3: Ouverture vers d'autres problèmes d'optimisation combinatoire

La thématique juste-à-temps est elle-même très intéressante, qu'elle soit regardée en ordonnancement classique ou sous l'angle de nouveaux problèmes de décision où interviennent plusieurs agents; ou qu'elle soit regardée sous l'angle de l'optimisation combinatoire par exemple dans les problèmes de voyageur de commerce ou de tournées de véhicules. En fonction des résultats obtenus, il sera intéressant d'étudier l'impact du critère juste-à-temps pour d'autres problèmes d'optimisation combinatoire.

Remarques additionnelles

Co-encadrement: Pierre Fouilhoux (MCF, LIP6 - équipe RO)