Une approche pour l'ordonnancement dynamique d'un atelier de traitement de surface

摘要

Cette these presente une approche dynamique pour la resolution d'un probleme d'ordonnancement connu dans la litterature sous le terme de Hoist Scheduling Problem. Il traduit le probleme de pilotage de chaines automatisees de traitement de surface, ou des robots doivent assurer la manutention de porteurs entre des cuves tout en assurant le respect de contraintes chimiques (aucun stock en cours de traitement, durees operatoires fournies avec tolerance). L'approche adoptee consiste a resoudre une succession de problemes, dits locaux, correspondant chacun a l'introduction d'un porteur ; l'objectif rescherche est la maximisation de la production apres une serie d'introductions de porteurs. Pour tendre vers cet objectif, un critere est optimise dans chaque probleme local a l'aide d'une Procedure de Separation et d'Evaluation Progressive. Mais, pour accelerer la resolution en dynamique, des informations d'inconsistance entre contraintes (Nogoods) detectes lors de resolutions de problemes locaux precedents sont reutilises. Un algorithme de retour arriere, appele dynamic backtracking est utilise a cet effet. Un procedure dynamique heuristique est aussi introduite : elle consiste a reutiliser des informations, non plus dues uniquement a des inconsistances entre contraintes, mais aussi dues au depassement du critere dans un probleme local precedent. Elle permet de maitriser l'espace de recherche envisage dans chaque probleme local et realise ainsi un compromis entre le temps de calcul et la qualite de l'ordonnancement obtenu. Developpee en premier lieu dans un cadre simple avec un seul robot, des cuves de capacite unitaire, cette approche dynamique est finalement etendue pour considerer les chaines comportant plusieurs robots, des cuves de capacite multiple et des chariots de transfert de porteurs entre deux lignes, dans un atelier sans panne. Enfin, des etudes comparatives avec des heuristiques deja existantes permettent de valider l'approche dynamique.