 |
NP-complétude du problème du flowshop à deux machines avec des opérations couplées
1 : Université Abderrahmane Mira Béjaia
2 : LORIA - UMR 7503, Université de Lorraine, Campus Scientifique - BP 239, 54506 Vandoeuvre-les-Nancy Cedex, France
Laboratoire LORIA
3 : Laboratoire RECITS, Faculté de Mathématiques,USTHB, BP 32, Bab-Ezzouar, El-Alia 16111, Alger, Algérie
Dans ce travail, Nous considérons le problème du flowshop à deux machines avec des opérations couplées.
Chaque tâche est composée de deux opérations couplées sur la première machine séparées par un délai exact et d'une seule opération sur la deuxième machine. L'objectif est de minimiser le makespan. Nous étudions la complexité d'un sous problème et nous montrons qu'il est NP-difficile. Pour la résolution du problème général, nous proposons des heuristiques avec des expérimentations numériques et nous présentons des sous problèmes polynomiaux.
