Techniques rétrospectives pour résoudre le Minimum Open Stacks Problem

Hadrien Cambazard 1 Narendra Jussien 2
2 TASC - Theory, Algorithms and Systems for Constraints
Inria Rennes – Bretagne Atlantique , Département informatique - EMN, LINA - Laboratoire d'Informatique de Nantes Atlantique
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.
Type de document :
Communication dans un congrès
Deuxièmes Journées Francophones de Programmation par Contraintes (JFPC06), 2006, Nîmes - Ecole des Mines d'Alès / France, 2006
Liste complète des métadonnées

Littérature citée [12 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00085778
Contributeur : Laurent Henocque <>
Soumis le : vendredi 14 juillet 2006 - 09:57:46
Dernière modification le : vendredi 22 juin 2018 - 09:32:23
Document(s) archivé(s) le : mardi 6 avril 2010 - 00:08:17

Fichier

Identifiants

  • HAL Id : inria-00085778, version 1

Citation

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, 2006. 〈inria-00085778〉

Partager

Métriques

Consultations de la notice

290

Téléchargements de fichiers

120