Supervision : Philippe CHRÉTIENNE

Co-supervision : SOURD Francis

Contributions à l'ordonnancement juste-à-temps

Les politiques de production juste-à-temps visent à minimiser aussi bien les retards de production que d'éventuels coûts d'avance qui peuvent être liés au stockage, à la détérioration des produits. Dans cette thèse, on s'intéresse à la résolution de problèmes d'ordonnancement avec pénalités d'avance-retard, principalement quand on dispose d'une unique machine pour effectuer les tâches. De manière générale, la difficulté des problèmes d'ordonnancement réside dans la recherche d'un bon ordre d'exécution des tâches sur les machines (problème du séquencement). Pour les critères irréguliers tel que l'avance-retard, déterminer les dates d'exécution des tâches une fois cette séquence connue est un problème non trivial (problème du placement ou ``timing''). Dans ces travaux de thèse, on propose un nouvel algorithme polynomial de placement pour le problème à une machine. Dans le cadre de la résolution générale du problème à une machine, on propose un algorithme qui calcule des voisinages (plus) efficacement en combinant la recherche de la séquence et du placement des tâches. On propose aussi une nouvelle modélisation du problème à une machine dans un contexte préemptif (c'est-à-dire quand l'exécution d'une tâche peut être interrompue puis reprise plus tard); le problème de placement afférent est résolu en temps polynomial. Enfin, on résout différents cas particuliers de problèmes d'atelier: des problèmes de Flow Shop en étendant des algorithmes de placement et de Job Shop à deux tâches par une approche géométrique.

2003-2009 Publications

• 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
  • Y. Hendel, F. Sourd : “Job-shop with two jobs and irregular criteria”, International Journal of Operations Research, vol. 5 (1), pp. 61-67, (Operations Research Society of Taiwan (ORSTW)) (2008)
• 2007
  • Y. Hendel, F. Sourd : “An improved earliness-tardiness timing algorithm”, Computers and Operations Research, vol. 34 (10), pp. 2931-2938, (Elsevier) (2007)
• 2006
  • Y. Hendel, F. Sourd : “Efficient neighborhood search for the one-machine earliness-tardiness scheduling problem”, European Journal of Operational Research, vol. 173 (1), pp. 108-119, (Elsevier) (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)
• 2005
  • Y. Hendel : “Contributions à l’ordonnancement juste-à-temps”, thesis, phd defence 11/17/2005, supervision Chrétienne, Philippe, co-supervision : Sourd, Francis (2005)
  • Y. Hendel, F. Sourd : “The single machine just-in-time scheduling problem with preemptions”, Multidisciplinary International Conference on Scheduling: Theory and Applications, New York, United States, pp. 140-148 (2005)
• 2004
  • Y. Hendel : “Minimum time-dependent cost path”, PMS 2004 - 9^th International Workshop on Project Management and Scheduling, Nancy, France, pp. 151-153 (2004)
• 2003
  • Y. Hendel, F. Sourd : “Job-Shop à deux tâches avec critères irréguliers”, Ecole d'Automne de Recherche Opérationnelle, Tours, France, pp. 70-73 (2003)
  • Y. Hendel, F. Sourd : “Calcul de voisinages pour l’ordonnancement avec critères irréguliers”, MOSIM 2003 - conférence Francophone de Modélisation et Simulation, Toulouse, France, pp. 21-25, (SCS-European Publishing House) (2003)