Extensions du "Hoist scheduling problem" cyclique : résolution basée sur un traitement des contraintes disjonctives en programmation en logique avec contraintes

Abstract

Cette these presente la resolution de deux extensions d'un probleme connu dans la litterature sous le nom de «Hoist Scheduling Problem» cyclique. Ce probleme est lie au pilotage des chaines automatisees de galvanoplastie dans lesquelles un ou plusieurs robots doivent assurer la manutention de tous les produits presents sur la ligne. Apres une analyse de l'etat de la recherche concernant ce probleme particulier, le deuxieme chapitre est consacre a une etude de l'adequation des outils de Programmation en Logique avec Contraintes pour la resolution des problemes d'ordonnancement et plus particulierement du «Hoist Scheduling Problem» cyclique. La troisieme partie de la these s'articule autour de l'etude des solveurs de contraintes et du probleme lie a la resolution de contraintes lineaires mutuellement exclusives. Une methode d'arbitrage de ces disjonctions est presentee. L'approche proposee vise a reduire la taille de l'arbre de recherche d'une solution, par une elimination de nombreux points de choix et par une detection des echecs au plut tot. Une application de cette procedure de resolution est realisee pour deux extensions du «Hoist Scheduling Problem» cyclique. La premiere porte sur les changements de gammes operatoires pour les productions, dites par campagne, ou des lots de pieces identiques se succedent sur la ligne. Un ordonnancement cyclique des mouvements des robots assure la production de chaque lot individuellement. L'approche proposee, dans ce memoire, permet la recherche d'ordonnancements transitoires admissibles pour le passage d'une production cyclique mono-produit a une autre. Enfin, une etude de l'implantation physique des cuves d'une ligne simple a un seul robot est developpee. Un algorithme permettant de trouver simultanement l'ordonnancement cyclique des mouvements du robot et l'implantation de la ligne est propose