Efficacité et fiabilité des algorithmes génétiques pour résoudre un problème d’ordonnancement à machine unique

Abstract

Le travail réalisé dans cette thèse porte sur l’élaboration et l’évaluation des algorithmes génétiques pour résoudre un problème d’ordonnancement des tâches sur une machine unique sous contrainte de disponibilité. Ce problème est considéré comme NP-difficile, ce qui rend difficile la détermination d’un algorithme polynomial permettant de le résoudre de manière exacte pour des instances de grande taille. Dans ce contexte, nous avons étudié la performance des algorithmes génétiques afin d’obte nir des solutions approchées de bonne qualité, tout en réduisant le coût lié au temps d’exécution. Le problème étudié est noté, selon la notation adoptée : 1 | h_k | ∑(i=1 to n) w_i C_i wiCioù wi représente le poids de la tâche i et Ci sa date d’achèvement.