Métaheuristique à base de colonies d’abeilles pour l'ordonnancement des ateliers de type Job shop

Abstract

Dans cette thèse, nos investigations sont orientées vers le développement d’une méthode efficace pour la résolution du problème d’ordonnancement des ateliers du type Job shop (JSP: Job shop Scheduling Problem). Il s'agit d'un problème pratique très important dans le domaine de la gestion de production et de l'optimisation combinatoire. En effet, en raison de sa grande applicabilité et de son inhérente difficulté, le JSP est considéré comme l’un des problèmes les plus courants mais aussi les plus complexes. De ce fait, pour résoudre le JSP qui est classé comme étant un problème NP-difficile au sens fort, on a forcément besoin d’avoir recours aux métaheuristiques. Nous avons choisi la métaheuristique des colonies d’abeilles qui s’inspire du comportement intelligent des abeilles butineuses dans la recherche d’une source de nourriture de bonne qualité. Cette méthode a été récemment introduite et formulée par l’algorithme ABC (Artificial Bee Colony) pour résoudre des problèmes d’optimisation difficile mais de nature continue. Ainsi, pour résoudre le JSP qui est de nature combinatoire, notre première contribution dans cette thèse fut d’adapter la version continue de l’algorithme ABC au problème combinatoire du Job shop. L’algorithme proposé est noté : « CABC : Combinatorial Artificial Bee Colony ». Il s’articule sur trois phases : la phase des abeilles actives et la phase des abeilles spectatrices qui assurent l'exploitation, et la phase des abeilles scoutes qui assure une bonne exploration et permet d’échapper aux optima locaux. En deuxième lieu, afin d’améliorer encore le côté exploitation de l'algorithme CABC, une hybridation séquentielle avec une nouvelle procédure de recherche locale a été introduite. La procédure proposée est appelée "Simple Iterated Local Search (SILS)". C’est une métaheuristique simple qui applique la recherche locale de manière itérative pour affiner la meilleure solution de l'itération actuelle de l'algorithme CABC. La procédure de recherche locale s’appuie sur la notion de voisinage généré par un opérateur d’insertion. La version hybride est notée « CABC_SILS ». Les approches proposées sont testées sur de nombreux benchmarks de Job shop extraits de la bibliothèque de recherche opérationnelle (OR-Library). Les simulations montrent que les deux algorithmes proposés donnent des résultats très satisfaisants dans la plupart des cas étudiés. De plus, on a noté que la version hybride CABC_SILS améliore efficacement l'exploitation de l'algorithme combinatoire proposé, car elle offre de meilleurs résultats en termes de qualité de la solution évaluée par le Makespan et en termes de vitesse de convergence.