Supervision : Philippe CHRÉTIENNE

Co-supervision : SOURD Francis

Problèmes d'ordonnancement avance-retard avec et sans préemption

Les problèmes d'ordonnancement juste-à-temps sur une machine modélisent des problèmes rencontrés dans beaucoup de domaines différents comme la fabrication industrielle ou les processus informatiques. Comme la problématique de ces problèmes est fortement inspirée des besoins de l'industrie, nous proposons des extensions qui permettent de prendre encore mieux en compte les caractéristiques spécifiques de certains problèmes. Plus précisément, dans un premier temps, nous examinons les problèmes dans lesquels les interruptions des tâches sont permises et ensuite, nous introduisons la notion de livraison. Comme les problèmes que nous considérons sont NP-difficiles, nous proposons des algorithmes exacts et des heuristiques. Pour les problèmes préemptifs, la fonction objectif non-préemptif ne peut pas être appliquée. Dans ce contexte, nous étudions un modèle préemptif existant et proposons une borne inférieure, une heuristique ainsi qu'un algorithme exact. Le cas particulier du problème ordonnancement préemptif autour d'une date d'échéance commune est examiné séparément. Nous présentons également un nouveau modèle préemptif avec dates d'échéance distinctes pour lequel un nouvel algorithme de timing et un algorithme de recherche locale permettent de calculer des solutions pour des instances de grande taille plus rapidement. Finalement, nous considérons une extension qui consiste à introduire la notion de dates de livraison. Pour ce nouveau modèle, nous présentons deux bornes inférieures et un algorithme de recherche locale.

2006-2009 Publications

• 2009
  • N. Runge, F. Sourd : “A new model for the preemptive earliness - tardiness scheduling problem”, Computers and Operations Research, vol. 36 (7), pp. 2242-2249, (Elsevier) (2009)
  • Y. Hendel, N. Runge, F. Sourd : “The one-machine just-in-time scheduling problem with preemption”, Discrete Optimization, vol. 6 (1), pp. 10-22, (Elsevier) (2009)
• 2008
  • N. Runge : “Problèmes d’ordonnancement avance-retard avec et sans préemption”, thesis, phd defence 09/22/2008, supervision Chrétienne, Philippe, co-supervision : Sourd, Francis (2008)
• 2007
  • N. Runge, F. Sourd : “Problème d’ordonnancement avance-retard autour d’une date d’échéance commune avec préemptions”, Conférence scientifique conjointe en Recherche Opérationnelle et Aide à la Décision FRANCORO V / ROADEF 2007, Grenoble, France, pp. 229-239, (Presses Universitaires de Grenoble) (2007)
• 2006
  • N. Runge, F. Sourd, Y. Hendel : “Une borne inférieure pour l’ordonnancement préemptif Juste-à-Temps sur une machine”, 7^e Congrès de la Société Française de Recherche Opérationnelle et d'Aide à la Décision (ROADEF 2006), Lille, France (2006)