Un algorithme basé sur l'Inclusion-Exclusion pour la résolution du flowshop de permutation avec précédences entre travaux
Olivier Ploton  1@  , Vincent T'kindt  2@  
1 : Laboratoire d'Informatique Fondamentale et Appliquée de Tours
Université de Tours : EA6300, LIFAT EA 6300, CNRS, ROOT ERL CNRS 7002
2 : Laboratoire d'Informatique Fondamentale et Appliquée de Tours
Université de Tours : EA6300, LIFAT EA 6300, CNRS, ROOT ERL CNRS 7002

Nous proposons un algorithme pour résoudre le problème du flowshop de permutation avec précédences entre travaux. Cet algorithme combine les techniques d'Inclusion-Exclusion et de programmation dynamique pour dénombrer les ordonnancements admissibles dont l'objectif est suffisamment petit, ce qui permet d'en déduire une solution optimale du problème. Comparé à l'algorithme classique basé sur la programmation dynamique sur les sous-ensembles de travaux, cet algorithme réduit la complexité spatiale d'un facteur exponentiel sans dégrader la complexité temporelle.


Personnes connectées : 2 Vie privée
Chargement...