ACCUEIL

Consignes aux
auteurs et coordonnateurs
Nos règles d'éthique

APPEL À
CONTRIBUTION
Masses de données hétérogènes
En savoir plus >>
Autres revues >>

Revue d'Intelligence Artificielle

0992-499X
Revue des Sciences et Technologies de l'Information
 

 ARTICLE VOL 24/4 - 2010  - pp.485-504  - doi:10.3166/ria.24.485-504
TITRE
Réseaux de contraintes sur des chronogrammes pour la planification et l'ordonnancement

TITLE
Constraint networks on timelines for planning and scheduling

RÉSUMÉ
Au cours des dernières décennies, la connexion entre planification et programmation par contraintes a fait l'objet d'un intérêt croissant. Différentes approches ont été explorées, conduisant à différentes formes de combinaison entre les deux domaines. Dans cet article, nous présentons un cadre nouveau, dénommé CNT (Constraint Network on Timelines, Réseau de contraintes sur des chronogrammes) permettant de modéliser et de résoudre des problèmes de planification et d'ordonnancement. Basiquement, un CNT est une forme de CSP dynamique équipé de variables spéciales, appelées variables d'horizon, représentant le nombre initialement inconnu d'étapes dans le plan recherché. Nous présentons aussi un algorithme et des résultats expérimentaux montrant que l'expressivité du cadre CNT permet de construire des modèles « efficaces » et peut conduire à des gains significatifs sur des problèmes issus des compétitions de planification.


ABSTRACT
In the last decades, there has been an increasing interest in the connection between planning and constraint programming. Several approaches were explored, leading to different forms of combination between the two domains. In this paper, we present a new framework, called CNT (Constraint Network on Timelines), to model and solve planning and scheduling problems. Basically, a CNT is a kind of dynamic CSP, enhanced with special variables called horizon variables representing the initially unknown number of steps in the sought plan. We also present an algorithm and experimental results showing that the expressiveness of the CNT framework allows "efficient" models to be built and can lead to significant gains on problems taken from planning competitions.


AUTEUR(S)
Cédric PRALET, Gérard VERFAILLIE

MOTS-CLÉS
planification, ordonnancement, programmation par contraintes, chronogrammes.

KEYWORDS
planning, scheduling, constraint programming, timelines.

LANGUE DE L'ARTICLE
Français

 PRIX
• Abonné (hors accès direct) : 7.5 €
• Non abonné : 15.0 €
|
|
--> Tous les articles sont dans un format PDF protégé par tatouage 
   
ACCÉDER A L'ARTICLE COMPLET  (260 Ko)



Mot de passe oublié ?

ABONNEZ-VOUS !

CONTACTS
Comité de
rédaction
Conditions
générales de vente

 English version >> 
Lavoisier