Scribd
Importer
3 vues1 page

Travaux Dirigés Série Numéro 5: CSP Continus Exercice 1

Le document présente des travaux dirigés pour le module 'Programmation Par Contraintes' dans le cadre du Master 2 en Systèmes Informatiques Intelligents. Il inclut des exercices sur le problème d'ordonnancement de type job shop, la modélisation de problèmes à l'aide de TCSP, et l'analyse de la complexité de l'algorithme de consistance de chemin PC2. Les exercices abordent également la détection d'inconsistances dans des CSP qualitatifs liés à des directions cardinales.

Transféré par

Maria Lmn
Copyright
© All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd
3 vues1 page

Travaux Dirigés Série Numéro 5: CSP Continus Exercice 1

Le document présente des travaux dirigés pour le module 'Programmation Par Contraintes' dans le cadre du Master 2 en Systèmes Informatiques Intelligents. Il inclut des exercices sur le problème d'ordonnancement de type job shop, la modélisation de problèmes à l'aide de TCSP, et l'analyse de la complexité de l'algorithme de consistance de chemin PC2. Les exercices abordent également la détection d'inconsistances dans des CSP qualitatifs liés à des directions cardinales.

Transféré par

Maria Lmn
Copyright
© All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd

USTHB, Faculté d’Informatique

LMD Master 2 ‘‘Systèmes Informatiques Intelligents’’ 2024/2025

Module ‘‘Programmation Par Contraintes’’

Travaux Dirigés

Série numéro 5 : CSP continus

Exercice 1 : On considère le problème d’ordonnancement de type job shop donné par la table
ci-dessous, qui consiste en deux jobs J1 et J2 devant passer chacun par deux machines M1 et
M2 :

1ère tâche : <machine, durée> 2ème tâche : <machine, durée>


Job J1 <M1,2> <M2,2>
Job J2 <M2,3> <M1,1>

 Toutes les tâches sont non-préemptives


 La date de début au plus tôt est td=1 et la date de fin au plus tard est tf=10

On s’intéresse à la recherche d’une solution réalisable, c’est-à-dire satisfaisant toutes les


contraintes mais ne donnant pas forcément l’optimum du problème.

1. Modéliser le problème à l’aide d’un TCSP P=(X,C)


2. Donner la représentation matricielle de P
3. Comment peut-on adapter l’algorithme Look_Ahead avec wbdAC-3 comme procédure de
filtrage durant la recherche, de telle sorte qu’il fournisse, pour un TCSP modélisant un
problème d’ordonnancement de type job shop, une solution réalisant l’optimum ?

Exercice 2 : Calculer la complexité du pire cas de l’algorithme de consistance de chemin PC2


appliqué à un CSP qualitatif de directions cardinales.

Exercice 3 : Montrer que l’algorithme de consistance de chemin PC2 détecte l’inconsistance du


CSP qualitatif de directions cardinales suivant :

 Béjaia est à l’est d’Alger


 Oran est à l’ouest d’Alger
 Le bâteau est au nord-ouest d’Alger
o satellite 1 à l’instant t
 Le bâteau est au nord-est de Béjaia
o satellite 2 au même instant t

Vous aimerez peut-être aussi