SEDDIK Yasmina

Docteur
Équipe : DECISION
Date de départ : 31/08/2013
https://lip6.fr/Yasmina.Seddik

Direction de recherche : Christophe GONZALES

Co-encadrement : KEDAD-SIDHOUM Safia

Ordonnancement avec dates de livraison et gains cumulatifs

Le problème étudié dans cette thèse est issu d'une problématique réelle, concernant l'optimisation du processus de numérisation des ouvrages de la Bibliothèque Nationale de France (BNF). La modélisation de ce problème met en évidence un critère d'optimisation nouveau en ordonnancement, tenant compte de gains cumulatifs liés à des dates de livraison communes à toutes les tâches.
Dans le but d'identifier les structures des solutions optimales liées à ce nouveau critère et à des dates de disponibilité des tâches, nous nous sommes surtout concentrés sur un problème d'ordonnancement à une machine. Nous avons identifié les classes de complexité de ce problème, et proposé une méthode de résolution exacte de type Branch and Bound pour le problème général, s'appuyant sur des bornes et des règles de dominance dédiées. Nous avons également considéré le problème à deux dates de livraison (NP-difficile au sens faible), pour lequel nous avons proposé un algorithme pseudopolynomial de programmation dynamique et un algorithme d'approximation polynomial avec une performance de garantie absolue égale à 1.
Enfin, dans le but de nous rapprocher de la problématique industrielle, nous nous sommes intéressés à un problème de flowshop de permutation, avec le même critère d'optimisation. Pour ce problème, nous avons proposé plusieurs heuristiques : des algorithmes constructifs, des algorithmes de recherche locale, et une métaheuristique de type GRASP.
Tous les algorithmes ont été implémentés, en particulier le Branch and Bound pour le problème à une machine et la recherche locale pour le flowshop permettent d'obtenir de bonnes solutions en temps raisonnable.

Soutenance : 07/12/2012

Membres du jury :

M. Jacques Carlier [Rapporteur]
M. Stéphane Dauzère-Pérès [Rapporteur]
M. Philippe Chrétienne
M. Federico Della Croce
M. Christophe Gonzales
Mme. Safia Kedad-Sidhoum
M. Pascal Wirth [Invité]

Date de départ : 31/08/2013

Publications 2011-2017

Mentions légales
Carte du site