Le Flowshop hybride à 2-étages

Abstract

Dans un environnement informatique composé d’un « serveur » et de « Mmachines parallèles identiques appelées processeurs, « N » tâches sont à exécuter sans interruption. Avant son exécution, une tâche i (i = 1,..., n) doit être chargée sur une des machines parallèles. Ce chargement ou setup est réalisé par une autre machine particulière appelée serveur. Ayant terminé un chargement, le serveur est libre d'en effectuer un autre et le chargement d'une tâche doit être suivi de son exécution. Ce problème est appelé un flowshop hybride à 2-étages et est noté P2, S1 pi , si Cmax . Dans la littérature, il est prouvé NP-difficile. Dans le mémoire, un schéma rapide d’organisation et de fonctionnement d’atelier est donné. Une brève introduction, dans laquelle nous rappelons les notions de base et en présentant les problèmes d'ordonnancement est faite. Deux exemples de flowshop hybrides sont fournis. Une recherche bibliographique est menée. Nous présentons l’algorithme de Guirchoun et Martineau (2003) et deux heuristiques de Abdekhodaee et al. (2006) pour sa résolution. Des exemples illustratifs de ces algorithmes sont déroulés. Une nouvelle heuristique est proposée par nos soins. Elle s’inspire et s’influence des idées de Johnson (1954). Un exemple de son déroulement est même fourni, et une comparaison avec l’heuristique Forward de Abdekhodaee et al. (2006) est effectuée. Notre heuristique s’avère la plus efficace en fournissant des valeurs de la longueur d’ordonnancement les plus proches de l’optimum. On propose la résolution du problème étudié en comparant six algorithmes de type liste, d’une heuristique SR1 et de deux variantes AG1 et AG2 d’un algorithme génétique. Les implémentations réalisées par nos soins sont regroupées dans un logiciel pédagogique à interface conviviale.