Ballade chimique : projet d'optimisation combinatoire

Résumé du document

Rapport final d'un projet d'optimisation ccmbinatoire résolvant un problème d'optimisation de la durée d'une galvanisation d'une pièce de monnaie dans une entreprise chimique.

Extraits

[...] Tous les bacs ne sont pas accessibles une fois un bac utilisé, le choix d'un bac se fait donc à partir des bacs utilisés précédemment. Chaque galvanisation ayant un effet permanent sur la pièce, il faut pouvoir garder un historique des réactions précédemment faites pour éviter les réactions secondaires. La durée de déplacement du robot entre chaque bac correspondrait au poids d'un arc du graphe. Nous envisageons d'attribuer à chaque sommet un poids correspondant au temps (fixe) de trempage d'une pièce dans ce bac. [...]

[...] Il nous a donc paru intéressant de reformuler le sujet selon la perception que nous en avions. Suite à une première concertation avec d'autres membres entre le premier et le deuxième cours d'Introduction à l'Optimisation Combinatoire nous avions plusieurs idées qui se sont révélées fausses: Plusieurs pièces pouvaient être en circulation en même temps pour le même robot, donc il fallait gérer minutieusement le temps de déplacement du robot pour éviter les pièces défectueuses dues à une galvanisation trop longue. [...]

[...] Chaque bac contient au moins une solution, mais peut aussi en contenir plusieurs : le problème est donc qu'il faut utiliser un bac qui contient la solution nécessaire, mais qui ne contient pas une solution entraînant une réaction secondaire. Les réactions n'ont pas d'ordre particulier à avoir du moment où elles sont toutes réalisées, mais ceci est aussi valable pour les réactions secondaires. Il s'agit de minimiser la durée totale de la galvanisation, à savoir le temps passé dans les bacs auquel s'ajoute le temps de transport d'un bac à un autre. [...]

[...] On peut stopper le processus après un nombre maximal d'itérations, mais nous avons choisi de l'arrêter après un nombre fixé d'itérations pendant lesquelles la meilleure solution ne s'améliore pas. ALGORITHME DE RECHERCHE TABOUE Par souci de clarté, on utilise les mêmes notations que dans l'heuristique Soit S la solution obtenue par une heuristique, de coût c c meilleur coût obtenu S meilleure solution obtenue T Ø on vide la liste taboue nIter 0 ; répéter nIter++ ; {Construction du voisinage V de c'' 9999 pour toute solution S' de //élimination des voisins non solutions si S' T alors S' n'est pas taboue si f(S') [...]

[...] La contrainte exprime l'idée que le dernier bac a un unique prédécesseur et aucun successeur. Heuristiques Nous présentons ci-dessous deux heuristiques basées sur des algorithmes gloutons. A chaque itération on effectue le meilleur choix relativement à critère donné. Pour la première heuristique, on cherchera à minimiser, à partir de chaque bac exploré, la somme du temps de transport vers un bac successeur et du temps de trempage dans ce bac successeur. [...]