Soutenance de thèse de Yasmina Seddik

Bonjour,

j'ai le plaisir de vous inviter à ma soutenance de thèse, intitulée
"Ordonnancement avec dates de livraison et gains cumulatifs".

La soutenance se tiendra le :

========
Vendredi 7 décembre à 10h30 en salle 55-65-211 (2ème étage), à l'UPMC (4
place Jussieu 75005 Paris)
========

et sera suivie d'un pot, auquel vous êtes également conviés.


========
Résumé
========
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.

========
Abstract
========
Starting from a real world digitization workflow issue, we identified a
scheduling problem with a new criterion involving common delivery dates
for the jobs. In order to focus on this new criterion and on the jobs'
release dates, we mainly worked on a single machine problem.
We delimited the complexity classes of the problem, and provided a Branch
and Bound algorithm for the general problem, based on dedicated bounds and
dominance rules.
We also considered the weakly NP-hard problem with two delivery dates, for
which we designed a pseudopolynomial dynamic programming algorithm and an
approximation algorithm with an absolute performance guarantee of 1.
Finally, in order to consider a problem more closely related to the
industrial issue, we studied a permutation flowshop problem with the same
criterion. For this problem, we proposed several heuristic methods:
constructive algorithms, local search, and a GRASP algorithm.
All the algorithms were implemented. In particular the Branch and Bound
method for the single machine problem and the local search algorithms for
the flowshop provide good solutions in a reasonable time.


========
Jury
========
M. Jacques CARLIER, Professeur à l'Université de Technologie de Compiègne
[Rapporteur]
M. Philippe CHRETIENNE, Professeur à l'Université Pierre et Marie Curie
[Examinateur]
M. Stéphane DAUZERE-PERES, Professeur à l'Ecole des Mines de Saint-Etienne
[Rapporteur]
M. Federico DELLA CROCE, Professeur au Politecnico di Torino, Italie
[Examinateur]
M. Christophe GONZALES, Professeur à l'Université Pierre et Marie Curie
[Directeur de thèse]
Mme. Safia KEDAD-SIDOHUM, Maître de Conférence HDR à l'Université Pierre
et Marie Curie [Directrice de thèse]
M. Pascal WIRTH, Président Directeur Général de Banctec France [Invité]



Bien cordialement,

Yasmina Seddik