Algorithmes approchés et exacts pour la minimisation de la somme pondérée des retards de tâches sur machine unique

Résumé

Cette thèse étudie les approches avancées pour résoudre les problèmes d'ordonnancement, en se concentrant spécifiquement sur la minimisation de la somme pondérée des retards sur une seule machine. L'ordonnancement, un domaine important de l'optimisation est essentiel pour la gestion de la production. La première partie de notre travail présente les notions fondamentales de l'ordonnancement, en détaillant les ressources, les contraintes et les objectifs spécifiques, tels que la réduction de la somme pondérée des retards. En plus des définitions classiques, nous abordons des questions liées à la complexité algorithmique, ce qui montre que beaucoup de ces problèmes d'ordonnancement, en commençant par le problème étudié, sont NP-difficiles. La nature combinatoire de ces problèmes appelle à utiliser des méthodes heuristiques et métaheuristiques afin d'obtenir des solutions dans des temps raisonnables. La deuxième section de la thèse fournit une revue des méthodes d'optimisation combinatoire appliquées à l'ordonnancement avec le problème de minimiser la durée maximale sur deux machines (P2||Cmax). Ce chapitre présente des méthodes exactes, telles que l'algorithme de Branch and Bound et la programmation dynamique, ainsi que des méthodes approchées et métaheuristiques telles que les algorithmes génétiques. Une analyse des contributions et des limites précédentes est également présentée, afin de créer une base solide pour les développements des expériences à venir. L'une des principales contributions de notre travail réside dans la conception d'algorithmes hybrides pour le problème de minimisation de la somme des retards pondérés sur une seule machine. Trois algorithmes, nommés GA-SA (Genetic Algorithm with Simulated Annealing), GAKANG (Genetic Algorithm with Kangaroo Jump) et GALS (Genetic Algorithm with Local Search) sont proposés. Ces méthodes combinent des approches génétiques avec des techniques d'optimisation telles que le recuit simulé et la recherche locale afin d'améliorer la qualité des solutions, en particulier pour les instances de grande taille. Parmi ces algorithmes, GAKANG se distingue par sa fiabilité et son efficacité par rapport à certaines méthodes de référence dans la littérature. La thèse présente ensuite la méthode de Branch and Bound pour minimiser le retard pondéré sur une seule machine lorsque les poids des tâches correspondent à leurs durées opératoires. Cette méthode incorpore plusieurs heuristiques classiques telles que SPT, EDD, MinSlack, et MinCost. Des bornes inférieures basées sur la relaxation lagrangienne et les problèmes d'affectation sont également utilisées pour améliorer la qualité de la solution. Les résultats expérimentaux montrent que cette approche est efficace pour des instances ayant jusqu'à 50 tâches et nous proposons le développement futur des bornes inférieures supplémentaires et des méthodes hybrides. Enfin, nous avons intégré l'apprentissage automatique pour identifier la meilleure méthode à appliquer pour résoudre notre problème à partir des paramètres des tâches. Nous avons également combiné l'apprentissage supervisé et non supervisé sur des instances de petite et moyenne tailles qui sont simples à résoudre. Les résultats expérimentaux de ce chapitre offrent des perspectives pour améliorer la sélection des méthodes en fonction des spécificités des données. En conclusion, cette thèse présente une combinaison de contributions théoriques et expérimentales pour améliorer la résolution de notre problème complexe. Nous combinons différentes méthodes exactes, heuristiques et métaheuristiques, en développant des algorithmes hybrides et en intégrant l'apprentissage automatique afin d'évaluer et de prédire les stratégies de résolution les plus appropriées.

Citer ce document

Accès au document

Ce document est hébergé sur son dépôt institutionnel d'origine.

Auteur(s)

Statistiques

Consultations : 2

Téléchargements : 0