Le Flow shop stochastique à 2-machines

Abstract

Nous considérons le problème d'ordonnancement de type flowshop stochastique à 2-machines afin de minimiser l'espérance mathématique de la longueur d’ordonnancement appelée makespan et notée E (Cmax). Les règles de Johnson [01] et Talwar [02] établissent que dans un ordonnancement optimal, une tâche i précédé une tâche j si E( min( Ai , Bj ) ) ≤ E (min ( Aj , Bi ) ), où Ai , Bi et « E » représentent respectivement des variables aléatoires associées aux temps d’exécution de la tâche i sur la première machine, sur la seconde machine et leurs espérances mathématiques. De notre recherche bibliographique, les principaux résultats établis dans la littérature sont présentés. Nous reprenons, dans leur grande ligne et leurs principales originalités, les travaux qui, selon nous, marquent des jalons importants dans la résolution du flowshop stochastique à 2-machines par les ordres stochastiques. Pour évaluer E (Cmax), une heuristique a été étudiée, implémentée et testée sur un nombre de données élevé des temps d’exécution de tâches supposés aléatoires de distribution exponentielle. Nous avons vérifié expérimentalement qu’elle est asymptotiquement convergente vers la solution optimale. Son évaluation constituera une borne inférieure pour notre objectif.