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.

Abstract

This thesis focuses on the Linear Ordering Problem (LOP) and the equivalent Feedback Arc Set Problem (FASP). Both NP-hard problems differ mainly by the type of instances they handle and they each have several practical applications in various fields. While the LOP is much studied in the literature, very few heuristics are proposed for the FASP. The most efficient heuristics proposed to tackle these problems, such as memetic algorithm and iterated local search, are hybrid heuristics and use local search repeatedly in a hill climbing (HC) operator. The implementation of a HC operator is critical to the performance of these heuristics. The objective of this work is to implement local search heuristics efficiently for the LOP and the FASP. In this work we describe the heuristics applied to the LOP in the literature and focus on existing techniques to perform local search. The most efficient methods are then implemented and several improvements are proposed to speed up the execution for large or sparse instances. Thereafter, we present an extensive experimental study of the different variants of the HC operator by comparing their running times to reach a local optimum on a large set of randomly generated problem instances which have various sizes and densities. In addition, a simple model is used to decompose the running time into several factors to analyze in detail the impact of the implementation of an operator and the search policy. We observe that the proposed variants of the HC operator are very efficient in different situations and can improve existing methods. We then present recommendations to select an appropriate HC operator according to the type of problem instances to tackle. We also provide some advice for its implementation. Notably, we present the best HC operator to solve FASP instances. This issue has not been addressed before. The various HC operators described can then be incorporated into an hybrid heuristic to speed up its execution.