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é]

Publications 2011-2017

• 2017
  • Ch. Dürr, Z. Hanzalek, Ch. Konrad, Y. Seddik, R. Sitters, O. Vasquez Perez, Gerhard J. Woeginger : “The triangle scheduling problem”, Journal of Scheduling, (Springer Verlag) (2017)
• 2015
  • Y. Seddik, Ch. Gonzales, S. Kedad‑Sidhoum : “Performance guarantees for a scheduling problem with common stepwise job payoffs”, Theoretical Computer Science, vol. 562, pp. 377-394, (Elsevier) (2015)
• 2013
  • Y. Seddik, Ch. Gonzales, S. Kedad‑Sidhoum : “A polynomial time OPT-1 algorithm for a scheduling problem with two delivery dates and cumulative payoffs”, 6^th Multidisciplinary International Scheduling Conference: Theory and Applications, MISTA 2013, Gent, Belgium, pp. 268-289 (2013)
  • Y. Seddik, Ch. Gonzales, S. Kedad‑Sidhoum : “An absolute approximation algorithm for a scheduling problem with cumulative payoffs”, 26^th European Conference on Operational Research, Rome, Italy (2013)
  • Y. Seddik, Ch. Gonzales, S. Kedad‑Sidhoum : “Single machine scheduling with delivery dates and cumulative payoffs”, Journal of Scheduling, vol. 16 (3), pp. 313-329, (Springer Verlag) (2013)
  • Y. Seddik, Ch. Gonzales, S. Kedad‑Sidhoum : “Un algorithme avec garantie de performance pour un problème d’ordonnancement avec dates de livraison et gains cumulatifs”, Congres de la Societe Francaise de Recherche Operationnelle et d'Aide a la Decision, ROADEF 2013, Troyes, France (2013)
• 2012
  • Y. Seddik : “Ordonnancement avec dates de livraison et gains cumulatifs”, soutenance de thèse, soutenance 07/12/2012, direction de recherche Gonzales, Christophe, co-encadrement : Kedad-sidhoum, Safia (2012)
  • Y. Seddik, Ch. Gonzales, S. Kedad‑Sidhoum : “Résolution exacte d’un problème d’ordonnancement de tâches avec dates de livraison et gains cumulatifs”, 13^e Congrès de la Société Française de Recherche Opérationnelle et d'Aide à la Décision, Angers, France, pp. 512-513 (2012)
  • Y. Seddik, Ch. Gonzales, S. Kedad‑Sidhoum : “A Branch and Bound method for a one-machine scheduling problem with cumulative payoffs”, International Symposium on Combinatorial optimisation (CO '12), Oxford, United Kingdom, pp. 86-87 (2012)
• 2011
  • Y. Seddik, Ch. Gonzales, S. Kedad‑Sidhoum : “Single machine scheduling with delivery dates and cumulative payoffs”, proceedings of the 5^th Multidisciplinary International Conference on Scheduling: Theory and Applications (MISTA'11), Phoenix, Arizona, United States, pp. 261-274 (2011)
  • Y. Seddik, Ch. Gonzales, S. Kedad‑Sidhoum : “Solving the one-machine scheduling problem with cumulative payoffs”, proceedings of the 10^th workshop on Models and Algorithms for Planning and Scheduling Problems (MAPSP'11), Nymburk, Czechia, pp. 245-247 (2011)
  • Y. Seddik, Ch. Gonzales, S. Kedad‑Sidhoum : “Ordonnancement de tâches avec contraintes de livraison et gains cumulatifs”, 12^e Congrès de la Société Française de Recherche Opérationnelle et d'Aide à la Décision (ROADEF 2011), vol. II, Saint-Etienne, France, pp. 855-856 (2011)