Scheduling in Semi-parallel Flowshop with a Final Synchronizing Operation

Ordonnancement dans un atelier de type flowshop semi-parallèle avec opération de synchronisation Cette étude est une variante du problème flow shop motivée par une situation pratique. Dans ce contexte, il y a une ligne d’assemblage composée de deux demi-lignes parallèles avec des activités indépendantes. Les demi-lignes ont q1 et q2 nombres de machines. A la fin des demi-lignes il y a une machine responsable par l’union des produits des deux demi-lignes. Chaque demi-ligne est dédiée à différentes tâches, en raison chaque travail nécessite des opérations dans chacune des machines des demi-lignes avec temps de transformation différents. Les tâches d’une demi-ligne ne dépendent pas de la réalisation d’une autre tâche dans autre demi-ligne, de sorte qu’une tâche est traitée en parallèle dans chaque demi-ligne. La séquence des travaux dans chaque demi-ligne parallèle devrait être la même, bien qu’une tâche n’ait pas de besoin de commencer en même temps dans demi-ligne. La dernière opération de synchronisation ne peut pas être démarrée que lorsque les opérations dans les deux demi-lignes aient ont été complétées. La solution à ce problème est de déterminer une séquence de travail pour optimiser le makespan. En ce sens, l’objectif de cette étude est de modéliser ce problème et le résoudre avec des algorithmes spécialisés. Premièrement, nous avons défini un modelé de programmation linéaire et au vu des la complexité du problème, il été résolu par la règle Johnson, heuristique NEH et la recherche locale, Recuit Simule et GRASP. Enfin, une importante campagne de tests a été menée et le méthode qui utilise le GRASP a démontré supériorité par rapport autres méthodes proposées