Résolution heuristique du problème périodique

Résolution heuristique du problème périodique

 Parmi les problèmes d’optimisation combinatoire les plus complexes réside la classe des problèmes NP-difficile [Garey et Johnson, 1990]. Etant donné que l’espace des solutions croît exponentiellement avec la taille du problème, il est souvent infaisable en pratique d’en énumérer toutes les solutions pour en sélectionner la meilleure. La résolution de ces problèmes demande un temps de calcul qui augmente plus rapidement que toutes puissances de la taille du problème.

L’étude de ces problèmes a amené à l’élaboration de méthodes de résolution approximative appelées des heuristiques [Reeves, 1995; Rayward-Smith et al., 1996; Glover et Kochenberger, 2003]. L’objectif de ces heuristiques est de trouver des solutions de qualité acceptable en un temps raisonnable.

L’efficacité d’une heuristique réside dans sa capacité de s’adapter aux instances générales du problème, d’éviter le piège des minimums locaux et d’exploiter certaines propriétés du problème (telles que des symétries ou des règles de dominances). Ainsi dans le chapitre précédent nous avons établi un modèle linéaire de notre problème,

ce modèle fournit une solution optimale cependant lorsque la taille du problème augmente les temps de résolution deviennent irréalistes. Nous avons dû élaborer une approche heuristique plus rapide pour obtenir sur des instances de plus grande taille des solutions de qualité acceptables, mais pas nécessairement optimales. 

Présentation générale de la méthode

Tout d’abord nous allons décrire la terminologie employée : Définition 5.1 (Espace des solutions). L’espace des solutions est l’ensemble des instances réalisables du problème (instances qui vérifient un ensemble de contraintes liées au problème considéré). On dit aussi qu’une instance réalisable est une solution admissible. Définition 5.2 (Fonction objectif, espace des critères et ordre de comparaison).

La qualité d’une instance est évaluée par une fonction objectif f qui associe à chaque instance x un élément y de l’ensemble des critères. Cet ensemble est pourvu d’un ordre partiel ≺ appelé ordre de comparaison. Notons que cet ordre de comparaison s’étend naturellement à l’ensemble des solutions via la fonction objectif f. Un problème d’optimisation consiste à chercher dans l’espace des solutions les meilleures ins tances relatives à l’ordre de comparaison

Résolution heuristique du problème périodique

Définition 5.3 (Espace des configurations, fonction de codage). L’espace des configurations est un ensemble abstrait où est associé à chaque élément une instance de l’espace des solutions. La fonction correspondante est appelée fonction de codage. Lorsque cette fonction est sur jective sur l’ensemble des solutions, on dit que le codage est complet, sinon on dit que le codage est incomplet.

Le rôle de la fonction de codage est de simplifier la représentation des solutions du problème en vue de les traiter. Pour ce faire, le codage doit si possible respecter des propriétés de régularité par rapport à l’ordre de comparaison. Ces propriétés facilitent alors la recherche d’une solution de bonne qualité.

Pour notre problème, nous proposons un codage complet d’une solution qui consiste en une permutation des tâches, laquelle définit un ordre entre tâches, et un vecteur de booléens, un booléen par tâche, il indique quand la tâche est calée sur sa date de disponibilité ou non. Ce codage des motifs est complet, on pourra alors lui associer un diagramme de Gantt