Techniques rétrospectives pour résoudre le Minimum Open Stacks Problem
Résumé
Nous présentons une étude de cas sur le MOSP (minimum number of open stacks problem). Ce problème se rencontre dans des environnements de production où la réalisation d'un ensemble de tâches n´ecessite une uti- lisation simultanée de diff´erentes ressources (les piles – stacks). `A travers ce problème, nous cherchons com- ment des raisonnements rétrospectifs assez classiques mais bas´es sur les explications peuvent ˆetre utilis´es pour ´elaguer l'espace de recherche. Les explications ont, en effet, souvent ´et´e utilis´ees pour mettre en place des m´ecanismes sophistiqu´es de retour arri`ere dans le cadre de la programmation par contraintes mais tr`es peu dans des sch´emas de type nogood recording. Ce n'est pas le cas dans la communaut´e SAT o`u la notion de clause apprise joue un grand rˆole aussi bien pour l'´elagage de l'espace de recherche que pour l'exploration elle-mˆeme. Dans cet article, nous introduisons un nogood g´en´eralis´e (bas´e sur les explications) pour le MOSP qui nous per- met d'introduire une nouvelle technique de r´esolution. Des r´esultats exp´erimentaux montrent l'int´erˆet d'une telle approche pour le MOSP et la capacit´e des explica- tions `a identifier et `a exploiter dynamiquement la struc- ture de ces probl`emes.
Loading...