A Metaheuristic for the Job Sequencing and Tool Switching Problem

Details

Supervisors

Catanzaro, Daniele

Faculty

Louvain School of Management

Degree label

Master [120] en ingénieur de gestion (Mons)

Abstract

Ce mémoire donne une résolution métaheuristique du problème d'ordonnancement et de changement d'outils sur une machine flexible (Job Sequencing and Tool Switching Problem). La métaheuristique utilisée est l'algorithme Ant Colony Optimization. Tout d’abord, nous nous sommes concentrés sur le problème, sa définition, sa complexité. Nous avons alors déjà pu aborder dans les chapitres suivants les méthodes exactes qui permettent derésoudre ce problème. Ensuite, nous avons défini ce qu’était une heuristique qui permet d’obtenir une solution approchée de l’optimum. Dans ce chapitre, nous nous sommes concentrés principalement sur les heuristiques qui allaient être utilisées par après dans le cadre de l’implémentation de l’algorithme Ant-Colony. Ensuite, nous avons résumé le fonctionnement d’un bon nombres de métaheuristiques afin de mettre en avant les différentes possibilités pour résoudre des problèmes combinatoires comme celui qui nous intéresse dans ce mémoire. Enfin, nous nous sommes concentrés sur l'algorithme des fourmis dont nous avons implémenté la variante Ant Colony System. Le but était d'arriver à obtenir un résultat plus satisfaisant qu'une méthode aléatoire sur un court laps de temps. Ensuite, nous avons proposé des pistes d'amélioration de l'algorithme pour obtenir des meilleurs résultats dans cette même durée.