Techniques rétrospectives pour résoudre le Minimum Open Stacks Problem - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2006

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.
Fichier principal
Vignette du fichier
10.pdf (261.92 Ko) Télécharger le fichier
Loading...

Dates et versions

inria-00085778 , version 1 (14-07-2006)

Identifiants

  • HAL Id : inria-00085778 , version 1

Citer

Hadrien Cambazard, Narendra Jussien. Techniques rétrospectives pour résoudre le Minimum Open Stacks Problem. Deuxièmes Journées Francophones de Programmation par Contraintes (JFPC06), 2006, Nîmes - Ecole des Mines d'Alès / France. ⟨inria-00085778⟩
215 Consultations
83 Téléchargements

Partager

Gmail Facebook X LinkedIn More