Résumé: <resume>Les problèmes d’ordonnancement d’atelier occupent une place omniprésente dans la production industrielle. On définit un problème d’ordonnancement comme étant un ensemble de tâches devant être exécutées sur une ou plusieurs ressources partagées. Le lien avec la production industrielle est par conséquent très évident, alors qu’on peut imaginer la production des différents produits comme étant les tâches et la machinerie dont dispose l’entreprise comme étant la ressource partagée. Dans les récentes années, la programmation par contraintes s’est avérée très efficace pour la résolution de ces problèmes d’ordonnancement. Ce paradigme de programmation emploie des algorithmes de filtrage pour réduire l’espace de solution et par le fait même accélérer l’acquisition d’une solution dans celui-ci. Plusieurs règles et algorithmes de filtrage ont été proposés dans la littérature au cours des récentes années pour les contraintes d’ordonnancement. Le filtrage complet des valeurs incohérentes des domaines des variables ne peut être réalisé en temps raisonnable vu la NP-Complétude du problème général d’ordonnancement. Ces algorithmes reposent donc sur une relaxation du problème faisant référence à l’élasticité des tâches. Dans le cadre de ce séminaire, je présenterai une généralisation de deux de ces règles de filtrage basée sur une fonction estimant de façon optimiste le temps de fin le plus tôt d’un ensemble de tâches. Je présenterai également deux algorithmes permettant d’appliquer ces règles généralisées en utilisant une relaxation énergétique plus réaliste que celle utilisée dans la littérature, et permettant donc un meilleur filtrage. Les résultats expérimentaux démontrent les bienfaits de cette généralisation alors que le temps d’exécution du solveur, ainsi que le nombre de retours-arrières effectués par celui-ci, sont réduits lorsque la méthode proposée est utilisée.</resume>
<resume>http://www2.ift.ulaval.ca/~quimper/Seminaires/</resume>
