Dates
on the November 30, 2017
10h00
Location
salle Lovelace, Polytech Tours, 64 av. J. Portalis, 37200 Tours
Exact algorithms with worst-case guarantee for scheduling: from theory to practice
Résumé :
L’objectif de cette thèse est de proposer des algorithmes exacts qui ont une meilleure complexité, temporelle ou spatiale, dans le pire des cas pour des problèmes d’ordonnancement qui sont NP-difficiles. En plus, on s’intéresse aussi à évaluer leurs performances en pratique. Trois contributions principales sont rapportées.
La première concerne un algorithme du type Dynamic Programming qui résout le problème F3||Cmax. L’algorithme est généralisé facilement à d’autres problèmes du type Flowshop et aux problèmes d’ordonnancement à une seule machine.
La seconde contribution porte sur l’élaboration d’une méthode arborescente appelée Branch & Merge pour résoudre le problème 1||sumTi. Le travail se base sur l’observation que de nombreux sous-problèmes identiques apparaissent répétitivement pendant la résolution du problème global. A partir de ça, une opération appelée merge est proposée, qui fusionne les sous-problèmes (les noeuds dans l’arbre de recherche) identiques autant que possible. Cette méthode doit pouvoir être généralisée à d’autres problèmes.
Le but de la troisième contribution est d’améliorer les performances en pratique des algorithmes exacts procédant par parcours d’un arbre de recherche. D’abord nous avons aperçu qu’une meilleure façon d’implémenter l’idée de Branch & Merge est d’utiliser une technique appelée Memorization. Avec la découverte d’un nouveau paradoxe et la mis en place d’une stratégie de nettoyage de mémoire, notre algorithme a résolu les instances qui ont 300 tâches de plus par rapport à l’algorithme de référence pour le problème 1||sumTi. Avec ce succès, nous avons testé Memorization sur trois autres problèmes d’ordonnancement. Les résultats finaux des quatre problèmes ont montré la puissance de Memorization appliquée aux problèmes d’ordonnancement. Nous nommons ce paradigme Branch & Memorize afin de promouvoir la considération systématique de l’intégration de Memorization dans les algorithmes de branchement comme Branch & Bound, en tant qu’un composant essentiel. La méthode peut aussi être généralisée pour résoudre d’autres problèmes qui ne sont pas forcément des problèmes d’ordonnancement.
Mots clés : Algorithmes exponentiels, ordonnancement, branch and reduce, branch and merge, mémorisation, branch and memorize, programmation dynamique, flowshop, somme de retards
L’objectif de cette thèse est de proposer des algorithmes exacts qui ont une meilleure complexité, temporelle ou spatiale, dans le pire des cas pour des problèmes d’ordonnancement qui sont NP-difficiles. En plus, on s’intéresse aussi à évaluer leurs performances en pratique. Trois contributions principales sont rapportées.
La première concerne un algorithme du type Dynamic Programming qui résout le problème F3||Cmax. L’algorithme est généralisé facilement à d’autres problèmes du type Flowshop et aux problèmes d’ordonnancement à une seule machine.
La seconde contribution porte sur l’élaboration d’une méthode arborescente appelée Branch & Merge pour résoudre le problème 1||sumTi. Le travail se base sur l’observation que de nombreux sous-problèmes identiques apparaissent répétitivement pendant la résolution du problème global. A partir de ça, une opération appelée merge est proposée, qui fusionne les sous-problèmes (les noeuds dans l’arbre de recherche) identiques autant que possible. Cette méthode doit pouvoir être généralisée à d’autres problèmes.
Le but de la troisième contribution est d’améliorer les performances en pratique des algorithmes exacts procédant par parcours d’un arbre de recherche. D’abord nous avons aperçu qu’une meilleure façon d’implémenter l’idée de Branch & Merge est d’utiliser une technique appelée Memorization. Avec la découverte d’un nouveau paradoxe et la mis en place d’une stratégie de nettoyage de mémoire, notre algorithme a résolu les instances qui ont 300 tâches de plus par rapport à l’algorithme de référence pour le problème 1||sumTi. Avec ce succès, nous avons testé Memorization sur trois autres problèmes d’ordonnancement. Les résultats finaux des quatre problèmes ont montré la puissance de Memorization appliquée aux problèmes d’ordonnancement. Nous nommons ce paradigme Branch & Memorize afin de promouvoir la considération systématique de l’intégration de Memorization dans les algorithmes de branchement comme Branch & Bound, en tant qu’un composant essentiel. La méthode peut aussi être généralisée pour résoudre d’autres problèmes qui ne sont pas forcément des problèmes d’ordonnancement.
Mots clés : Algorithmes exponentiels, ordonnancement, branch and reduce, branch and merge, mémorisation, branch and memorize, programmation dynamique, flowshop, somme de retards
