Laboratoire de Génie Informatique et d’Automatique de l’Artois

L’optimisation combinatoire est un domaine vital ayant un impact important sur des divers domaines. Historiquement, les méthodes exactes étaient utilisées pour résoudre ces problèmes, mais elles se sont révélées limitées lorsqu’elles étaient appliquées à des problèmes complexes et à grande échelle en raison de leur temps de calcul élevé. Cela a conduit au développement de méthodes approchées telles que les heuristiques et les métaheuristiques, qui trouvent un équilibre entre la qualité de la solution et le temps de calcul. Cependant, les métaheuristiques nécessitent, souvent, des ajustements manuels lorsqu’elles sont appliquées à différents problèmes ou instances, limitant ainsi leur adaptabilité. Pour remédier à ce problème, les hyperheuristiques ont émergé comme une approche plus générique, visant à automatiser la sélection et la génération d’heuristiques avec un minimum d’intervention humaine. Leur généricité est obtenue en explorant l’espace de recherche des heuristiques plutôt que l’espace de recherche des problèmes. Cette thèse contribue au domaine des hyperheuristiques en proposant trois nouvelles méthodes dans les catégories de sélection et de génération, appliquées aux problèmes d’ordonnancement, plus particulièrement dans le domaine de la logistique hospitalière. Une hyperheuristique de sélection basée sur l’optimisation par le comportement des abeilles a été introduite comme première contribution, simulant le comportement naturel de reproduction des abeilles pour guider la sélection des heuristiques. Cette méthode a été testée sur les problèmes théoriques Max-SAT et Bin-Packing afin de vérifier son bon fonctionnement, puis appliquée au problème d’affectation des patients aux lits. La deuxième contribution a exploré une hyperheuristique de génération basée sur la programmation génétique pour les problèmes d’ordonnancement, intégrant un processus d’apprentissage pour l’application des heuristiques. Cette approche a utilisé la Recherche par Voisinage Variable et le Recuit Simulé pour affiner la génération des solutions par l’hyperheuristique. Elle a été efficacement appliquée d’abord au problème de l’affectation des patients aux lits. Ensuite, une extension a été appliquée au problème d’ordonnancement du flow shop de permutation. La troisième contribution a présenté une hyperheuristique basée sur l’algorithme du tri de non-dominance 2 "Non-Dominated Sorting Genetic Algorithm 2" (NSGA-II) pour les problèmes d’ordonnacement multi-objectifs, combinant les avantages des hyperheuristiques avec la capacité de NSGA-II de fournir des fronts de Pareto de haute qualité. Pour explorer efficacement dans les différents espaces de recherche : l’espace de recherche des problèmes associé à NSGA-II et l’espace de recherche des heuristiques associé aux hyperheuristiques, un individu de cartographie spécialisé a été mis en œuvre. Cette hyperheuristique a été appliquée au problème d’ordonnacement du flow shop de permutation et démontrée sur d’autres problèmes d’ordoannancement, montrant son efficacité à fournir des solutions robustes qui équilibrent plusieurs objectifs tout en explorant efficacement l’espace de recherche. Ces contributions sont validées en utilisant des benchmarks de la littérature et des métriques standards, démontrant leur capacité à résoudre une large gamme de problèmes d’ordonnancement tout en abordant les limitations des métaheuristiques. Leur généricité est reflétée dans la réussite de l’application des hyperheuristiques proposées à différents domaines de problèmes d’ordonnancement, soulignant leur adaptabilité et leur efficacité dans divers contextes par rapport aux méthodes de la littérature. Cela positionne les contributions comme des avancées significatives dans le domaine, montrant leur potentiel à surpasser les approches existantes