Analyse d'heuristiques de recherche locale pour l'ordonnancement linéaire

Ce mémoire porte sur le problème d'ordonnancement linéaire (LOP -- Linear Ordering Problem) et le problème équivalent de Feedback Arc Set (FASP). Ces deux problèmes NP-difficiles se distinguent surtout par le type d'exemplaires traités et ont chacun plusieurs applications pratiques dans divers domaines. Alors que le LOP est bien étudié dans la littérature, très peu d'heuristiques sont proposées pour le FASP. Les heuristiques les plus efficaces pour traiter ces problèmes, comme l'algorithme mémétique et la recherche locale itérée, sont des heuristiques hybrides et utilisent à répétition la recherche locale sous forme de descentes. L'implémentation d'un opérateur de recherche est donc critique à la performance de ces heuristiques. L'objectif de ce travail est donc d'implémenter des heuristiques de recherche locale de façon efficace pour le LOP et pour le FASP. Dans ce travail, nous décrivons les heuristiques appliquées au LOP dans la littérature et particulièrement les techniques existantes pour effectuer la recherche locale. Les méthodes les plus efficaces sont alors implémentées et plusieurs améliorations sont proposées pour accélérer le traitement des exemplaires de grande taille ou de faible densité. Par la suite, nous présentons une étude expérimentale des divers opérateurs de recherche en comparant leurs temps d'exécutions pour effectuer une descente sur des exemplaires générés aléatoirement de taille et densité variables. De plus, un modèle simple est utilisé pour décomposer le temps d'exécution en plusieurs facteurs afin d'analyser en détail l'impact de l'implémentation d'un opérateur et de la politique de recherche appliquée. Nous observons que les opérateurs de recherche développés sont très efficaces dans différentes situations et permettent d'améliorer les méthodes existantes. Nous proposons alors des recommandations pour sélectionner l'opérateur approprié selon le type d'exemplaire du problème à traiter en plus de donner des conseils pour son implémentation. En particulier, nous présentons le meilleur opérateur à utiliser pour des exemplaires FASP alors que ce sujet n'a pas été abordé auparavant. Les divers opérateurs de recherche décrits pourront alors être incorporés dans une heuristique hybride afin d'accélérer son exécution.