An iterated local search approach to the job scheduling and tool switching problem

Details

Supervisors

Catanzaro, Daniele

Faculty

Louvain School of Management

Degree label

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

Abstract

Le problème d’ordonnancement de tâches, chacune nécessitant un ensemble spécifique d’outils, fait partie des enjeux courants des industries. Posséder un algorithme capable de déterminer l’ordonnancement optimal d’une série de tâches et l’ordre de chargement des outils sur une machine flexible peut entrainer des gains conséquents. Un tel ordonnancement optimal permettrait en effet d’avoir un nombre minimal de changements d’outils à effectuer entre les différentes tâches. Ces changements d’outils requièrent non seulement du temps mais ont également un certain coût. Dans un premier temps, le Job Sequencing and Tool Switching Problem sera présenté. Ensuite, les méthodes de résolution exactes existantes dans la littérature seront exposées. Cette partie plus théorique se terminera par une présentation des principales métaheuristiques en mettant particulièrement en avant la recherche locale itérative. Dans un second temps, un algorithme de recherche locale itérative sera proposé. Les tests réalisés sur un ensemble d’instances montrent que la métaheuristique implémentée permet d’obtenir des solutions de qualité satisfaisante.