Programmation Logique avec Contraintes et Ordonnancement
Contents
1. ce langage de se distinguer sur des probl mes du type analyse synth se de circuits lectriques analogiques dans lesquels interviennent effectivement de nombreuses contraintes lin aires et non lin aires Il pr sente d autre part des fonctionnalit s de m ta programmation il permet en particulier de traiter symboliquement les termes et les contraintes arithm tiques gr ce une forme cod e traitement qu il n est pas possible de r aliser l gamment en CHIP ou PrologII 4 Les langages de PLC Pour effectuer un bilan sur l ensemble des possibilit s offertes par ces langages nous nous restreindrons aux trois langages qui nous semblent les plus repr sentatifs de la PLC CHIP DIN 88 PrologII COL 90 et CLP R JAF 87 4 1 Le fonctionnement de base des machines Prolog avec contraintes L tat de la machine abstraite ProloglIl peut tre repr sent par un triplet V B C o V est l ensemble des variables auxquelles on s int resse Best la liste des buts r soudre B bo b1 bn C est le syst me de contraintes courant L utilisation d une r gle du type SQ gt S1 S2 Sm o c d signe les contraintes attach es l utilisation de la r gle engendre le nouvel tat V B C tel que B s S2 Smb1 bn et C C U c U bo s0 Les contraintes propres une clause sont plac es la suite des litt raux logiques Le langage se charge de l ordre dans lequel elles doivent2. ventuellement minimisation de la date de fin de l ensemble des t ches minval Sprojet minval S domain_info S Min _ _ S Min 15 Pour des probl mes dont les t ches ont des dur es connues le programme pr c dent permet de trouver les fen tres temporelles associ es aux dates de d but des t ches sur l ensemble des solutions admissibles En revanche lorsque les dur es ne sont pas connues cette caract risation est incompl te car les contraintes font intervenir 3 variables d but dur e fin et la consistance globale n est plus assur e par les m canismes de propagation sur les domaines finis La seule alternative est d adopter une mod lisation en nombres rationnels L exemple ci dessous permet de mod liser un graphe de contraintes temporelles dont les sommets sont les dates de d but et les dates de fin d un ensemble de t ches et dont les arcs correspondent une contrainte de distance entre deux dates Un tel graphe muni d un sommet origine des temps permet de d terminer de mani re compl te les valeurs minimales des distances entre tout couple de dates Exemple PrologI Le graphe initial d clar par la clause grapheO GO est mod lis par une liste d arcs du type lt origine extr mit valuation gt Chaque noeud origine ou extr mit est de l un des trois types 1 lt org 0 gt 2 lt deb i x gt o x est la variable date de d but d une t che i 3 lt fin i y gt
3. Max Sn Dn lt Max pose_precede S1 S2IS D1 D2ID Max S2 0 Max S1 D1 lt S2 pose_precede S21S D2ID Max 5 1 2 Contraintes de disjonction Les probl mes d ordonnancement ressources non partageables d finissent les probl mes d ordonnancement disjonctifs Une mod lisation par graphe non conjonctif ERS 79 BAR 88 est alors possible mais il n existe pas d algorithmes de complexit acceptable permettant comme dans le cas pr c dent de caract riser de mani re n cessaire et suffisante l ensemble des solutions On ne peut donc attendre de la PLC qu une gestion passive de ces contraintes au sens o les domaines des variables ne peuvent tre r duits a priori par les contraintes Une contrainte disjonctive entre deux t ches t1 et t2 peut s exprimer sous la forme d une disjonction d in galit s du type S2 F1 0 v S1 F2 20 o v repr sente la disjonction logique Elle traduit le fait que l une des deux t ches doit pr c der l autre Dans le cas o les dur es sont connues la contrainte s exprime S2 S1 D1 v S1 S2 D2 5 1 2 1 Mod lisation par un point de choix C est la solution la plus directe mais aussi la plus inefficace pour traduire une telle contrainte la disjonction en Prolog tant naturellement repr sent e par l existence de 2 clauses d finissant la m me relation Exemple CHIP disjonction S1 S2 D1 D2 S2 gt S1 D1 disjonctionl1 S1 2
4. Techniques et Science Informatiques 2 4 1983 COL 90 COLMERAUER A An introduction to PrologIII Communications of ACM 33 7 pp 69 90 1990 COS 93 CosyTEC Reference Manual COSY REF 001 1993 DEC 91 DECHTER R MEIRI I PEARL J Temporal Constraints Networks Artificial Intelligence 49 pp 61 95 1991 DEC 92 DECHTER R From local to global consistency Artificial Intelligence 55 1992 DIB 70 DIBON M Ordonnancement et potentiels M thode M P M Hermann 1970 DIN 87 DincBAs M SIMONIS H Van HENTENRYCK P Extending equation solving and constraint handling in logic programs Proc Colloquium on Resolution of Equations in Algebraic Structures MCC Austin Texas USA 1987 29 DIN 88 DINCBAS M Van HENTENRYCK P SIMONIS H AGGOUN A GRAF T BERTHIER F The Constraint Logic Programming Language CHIP Proc International Conference on Fifth Generation Computer Systems FGCS 88 pp 693 702 Tokyo Japan 1988 DIN 90 DincBAs M SIMONIS H Van HENTENRYCK P Solving large combinatorial problems in logic programming Journal of Logic Programming 8 pp 75 93 1990 ELM 77 ELMAGHRABY S E Activity networks John Wiley amp Sons 1977 ELM 92 ELMAGHRABY S E KAMBUROWSKI J The analysis of activity networks under generalized precedence relations GPRs Management Science 38 pp 1245 1263 1992 ERS 76 ERSCHLER J Analyse sous contraintes et aide a la d cision pour certains probl mes d
5. ce qui permettrait d aborder des probl mes dont la mod lisation n cessite plusieurs types de variables Au contraire certains langages se sp cialisent dans la r solution de probl mes tr s sp cifiques privil giant le point de vue de l optimisation au d triment de la caract risation de la consistance des solutions et de la standardisation de la PLC standardisation dont l absence a longtemps nuit et nuit encore au langage Prolog lui m me Le but est clair concurrencer les outils sp cialis s ce qui entre en contradiction avec les buts originaux de la PLC qui taient la formalisation et l int gration de m canismes g n raux de propagation de contraintes De plus le fonctionnement des primitives les plus volu es n est pas clairement expliqu 24 concurrence oblige et leur utilisation passe par une syntaxe relativement contraignante ce qui ne facilite pas leur appropriation par les programmeurs 7 Bibliographie ACM 92 Communications of ACM Special section on Logic Programming 35 3 1992 AGG 92 AGGOUN A BELDICEANU N Extending CHIP in order to solve complex scheduling and placement problems Actes des Journ es Francophones de Programmation Logique pp 51 66 1992 BAR 88 BARTUSCH M MOHRING R H RADERMACHER F J Scheduling project networks with resource constraints and time windows Annals of Operations Research 16 pp 201 240 1988 BAP 92 P Baptiste B Legeard C Varnier Hoist scheduling
6. quates Exemple CHIP boucle d instanciation d une liste de variables domaine fini labeling1 labeling1 XIY delete Var XIY Rest 0 most_constrained indomain Var labeling1 Rest Le pr dicat indomain X de CHIP est un g n rateur de valeurs qui vite au programmeur de sp cifier explicitement le domaine de la variable domaine qu il n est pas certain de conna tre au moment de l instanciation tant donn les restrictions qu ont pu op rer les contraintes De m me le pr dicat enum X de PrologIII num re toutes les constantes enti res n telles que le syst me courant de contraintes augment de la contrainte X n soit globalement satisfait 4 2 2 Optimisation Les langages de PLC incluent des primitives permettant de trouver une solution optimale un probl me de satisfaction de contraintes Dans le cas de probl mes variables rationnelles ou r elles l algorithme du Simplexe permet de r pondre au probl me d optimisation la condition que le crit re soit lin aire gr ce aux primitives du type minimize X PrologIIl ou rmin X CHIP Pour les variables domaines finis la primitive min_max de CHIP permet de rechercher toutes les solutions et conserve celle de plus petit co t Lorsqu il existe un tr s grand nombre de solutions la recherche peut tre r duite selon quatre crit res dont le r glage ne peut tre qu exp rimental 1 une limite d
7. tre interpr t es compte tenu des contraintes d unification En CHIP et en CLP R au contraire les contraintes ne sont pas diff renci es des litt raux classiques 4 2 G n ration de solutions 4 2 1 Sch ma g n ral de r solution La r solution d un probl me dont les variables sont soumises des contraintes ob it au sch ma suivant 1 Cr ation des variables du probl me et ou pose des contraintes de domaine 2 Pose des contraintes binaires ou n aires 3 Instanciation des variables 4 Arr t sur la premi re solution ou retour sur les points de choix laiss s en 3 ventuellement en 2 dans le cas de points de choix sur la pose de contraintes L ordre des tapes 2 et 3 est primordial dans l optique d une utilisation active des contraintes Bien que l instanciation des variables soit non d terministe on peut n anmoins agir sur l ordre d instanciation deux niveaux 1 strat gie de choix des variables instancier 2 strat gie de choix des valeurs pour une variable donn e Les primitives de choix des variables permettent d appliquer le first fail principle HAR 80 Ce principe dit qu il vaut mieux chouer le plus t t possible dans l exploration de l espace de recherche En pratique il faut s lectionner en priorit les variables ayant le plus petit domaine et pr sentes dans le plus grand nombre de contraintes Cette s lection peut tre assur e par le langage lui m me moyennant des primitives ad
8. o y est la variable date de fin de i On pose la contrainte y x z d d tant une constante positive ou n gative Le graphe courant G reprend la m me structure que GO la diff rence que chaque valuation est une variable dont on cherche la valeur minimale apr s avoir pos et propag les contraintes de GO Le programme principal top consiste a lire le graphe initial lancer la propagation et retourner les valeurs minimales des arcs top gt grapheO GO propa_graphe GO G affiche G grapheO arc1 arc2 gt propa_graphe gt propa_graphe lt lt n_i i gt lt n_j j gt d0 gt 1 GO lt lt n_i i gt lt n_j j gt d gt GJ gt propa_graphe GO G minimum i d j i gt d0 affiche gt affiche A_rc Liste_d_arcs gt outl A_rc affiche Liste_d_arcs L exemple suivant permet de poser les contraintes de gamme dans un probl me de job shop Un ensemble de travaux doivent tre ex cut s sur un ensemble de 16 machines Chaque travail est constitu d un ensemble de t ches ordonn es et r alis es sur des machines diff rentes On consid re chaque travail successivement Pour chaque t che d un travail on cr e une variable domaine de d but et on pose les contraintes qui constituent la s quence de t ches au sein du travail Exemple CHIP travail S11S D11ID Max S1 0 Max pose_precede S11S D1ID Max pose_precede Sn Dn
9. ordonnancement Th se de Doctorat d tat Univ Paul Sabatier Toulouse 1976 ERS 79 ERSCHLER J FONTAN G ROUBELLAT F Potentiels sur un graphe non conjonctif et analyse d un probl me d ordonnancement moyens limit s RAIRO RO 13 1979 ESQ 87 ESQUIROL P R gles et processus d inf rence pour l aide l ordonnancement de t ches en pr sence de contraintes Th se de Doctorat Univ Paul Sabatier 1987 ESQ 93a ESQUIROL P LOPEZ P BOY G BRADSHAW J HAUDOT L SICARD M SCOOP Syst me COop ratif pour Ordonnancement de Production rapport LAAS 94171 1994 ESQ 93b ESQUIROL P LOPEZ P HUGUET M J Modelling and managing disjunctions in scheduling problems Journal of Intelligent Manufacturing 6 1995 to appear FRE 78 FREUDER E C Synthesizing constraint expressions Communications of ACM 21 11 1978 FRE 82 FREUDER E C A sufficient condition for backtrack free search Journal of ACM 29 1 1982 GAR 79 GAREY M R JOHNSON D S Computers and Intractability W H Freeman and Company New York 1979 GOT 93 GOTHA Les probl mes d ordonnancement RAJRO RO 27 1 pp 77 150 1993 HAN 88 HAN C LEE C Comments on Mohr and Henderson s path consistency algorithm Artificial Intelligence 36 1988 HAR 80 HARALICK R M ELLIOT G L Increasing search efficiency for Constraint Satisfaction Problems Artificial Intelligence 14 1980 HEN 89 Van HENTENRYCK P Constraint satis
10. principe de r solution PR ROB 65 qui permet travers une d monstration par r futation d obtenir les valeurs des variables ventuellement pr sentes dans la question pos e L ex cution d un programme logique correspond l exploration d un arbre de d rivation dont la racine constitue la n gation de la clause d montrer et dont les feuilles sont des clauses vides cf figure 1 Chaque branche est r gie par un algorithme d unification qui g n re l ensemble minimal des substitutions n cessaires l application du PR Le choix des clauses devant tre mises en relation lors des diff rentes inf rences est contr l par une strat gie d exploration en profondeur d abord avec retour arri re chronologique Par d faut tous les points de choix sont m moris s ainsi que leur contexte listes des variables locales et des substitutions pour assurer l exhaustivit de la recherche Pour aborder la r solution de probl mes avec contraintes la PL est un outil int ressant Le caract re non d terministe de la PL et sa s mantique d clarative permettent de s parer la repr sentation d un probl me de sa r solution De plus lorsqu ils sont r versibles les programmes gagnent en g n ralit et en r utilisabilit La proximit conceptuelle de la strat gie de r solution et des techniques de recherche arborescente dans les probl mes combinatoires facilitent galement la conception des programmes Toutefois ces caract r
11. une dur e gale la distance temporelle minimale positive ou n gative entre ces bornes Ces contraintes temporelles peuvent se repr senter sous la forme d un graphe potentiels t ches ou potentiels tapes DIB 70 ROY 70 ELM 77 ELM 92 ou d un graphe potentiels bornes ESQ 93b permettant de prendre en compte des dur es variables et des contraintes sur ces dur es Les contraintes de localisation absolue peuvent galement se traduire par des in galit s du m me type condition d instancier une des deux bornes par un instant de r f rence Bi By B 0 B Bi lt Bit 0 Bi Bit Traditionnellement l application d algorithmes de recherche des plus longs chemins entre deux sommets permet de caract riser de mani re n cessaire et suffisante l ensemble des solutions Cette caract risation est de complexit acceptable O n3 si n est le nombre de t ches PAP 82 DEC 91 Elle est directement r alisable par un langage de PLC tel que CHIP et l exemple du traitement d un probl me PERT est souvent utilis par les concepteurs DIN 90 Le squelette d un programme CHIP permettant de calculer les fen tres temporelles d ex cution d un ensemble de taches avec contraintes de localisation absolue ou relative des taches est le suivant trouver_fenetres Liste_des_dates_de_debut_Si pose des contraintes de localisation absolue Si Smin Smax pose des contraintes de localisation relative Sj gt Si Di
12. D1 D2 S1 gt S2 D2 L inconv nient majeur de cette solution est de cr er pour n t ches en conflit un espace de recherche de taille exponentielle en n Les feuilles de l arbre g n r par la 17 pose de l ensemble des contraintes disjonctives repr sentent une solution s quentielle du probl me et il est possible d obtenir les marges temporelles associ es une s quence donn e avant toute instanciation des dates de d but La figure 4 repr sente les r ductions ventuelles de domaine temporel d une t che fen tre apr s passage par un point de choix i E i C C E i EE jj i pr c de j j pr c de i i E SSSR i a j JE Figure 4 R duction des fen tres apr s un point de choix li une disjonction L ordre de pose des contraintes propos dans les exemples est en g n ral statique et impos par une boucle d num ration des couples possibles L efficacit peut tre augment e en rempla ant cet ordre statique par un ordre plus dynamique qui forme en priorit les couples de t ches dont les fen tres temporelles se chevauchent le moins principe du first fail La complexit d une telle proc dure ne garantit pas au bout du compte une am lioration tr s nette de l efficacit tant donn e les nombreux tests de comparaison qu exige le reclassement dynamique des t ches avant chaque pose de contrainte disjonctive 5 1 2 2 Mod lisation par propagation conditionnelle L utilisation de la primitive d
13. Programmation Logique avec Contraintes et Ordonnancement Patrick ESQUIROL Pierre LOPEZ Laboratoire d Analyse et d Architecture des Syst mes du C NRS 7 avenue du Colonel Roche 31077 Toulouse Cedex T N S A de Toulouse Complexe Scientifique de Rangueil 31077 Toulouse Cedex R SUM Les probl mes combinatoires tels que les probl mes d ordonnancement ont fait l objet de nombreux travaux en Recherche Op rationnelle et ont donn lieu l utilisation de m thodes de recherche arborescente dont l efficacit d pend notamment de l exploitation intelligente des contraintes d finissant les solutions admissibles Malgr la puissance et l l gance qu offre la programmation logique au niveau de la repr sentation les langages imp ratifs lui ont souvent t pr f r s pour des raisons d efficacit A l heure actuelle on constate un int r t grandissant pour la programmation logique avec contraintes dotant la programmation logique de m canismes puissants d interpr tation de contraintes arithm tiques et symboliques Apr s avoir rappel les fondements th oriques de ces m canismes dont certains sont issus de travaux en Intelligence Artificielle nous essayons de cerner les avantages r els de l application de cette nouvelle technologie aux probl mes d ordonnancement ABSTRACT Combinatorial problems such as scheduling have been the target of many works in the field of Operations Research and led to develop tree se
14. ables sous forme d expressions bool ennes b ties sur la relation de pr c dence entre deux t ches On peut trouver de telles contraintes dans la formulation initiale des probl mes on peut galement rechercher certaines formes de contraintes partir d une analyse sous contraintes en particulier celles qui 23 autorisent une actualisation des fen tres d ex cution des t ches dans le but de caract riser les solutions admissibles ERS 76 Une pr caution doit cependant tre prise lors du traitement symbolique de ces contraintes la transitivit de la relation de pr c dence doit tre pos e explicitement pour tout triplet de variables bool ennes ce qui alourdit de mani re non n gligeable le syst me de contraintes 5 3 Discussion Dans le cas disjonctif la caract risation des solutions admissibles d un probl me d ordonnancement peut faire intervenir la fois des contraintes num riques temporelles et symboliques de s quencement Pour chacun de ces cas on a montr l ad quation d un mod le variables enti res ou variables bool ennes A l heure actuelle cependant il n existe pas de moyen l gant de lier les inf rences r alis es sur le domaine des variables enti res et les variables bool ennes du fait de l impossibilit de construire des expressions m langeant ces deux types de variables dans les langages de PLC cf 4 5 Si la propagation de contraintes peut s effectuer depuis le syst me de d
15. aleurs une par variable tel que pour chaque contrainte Ck les valeurs associ es aux variables var Cx assurent le respect de Cx Sur ce mod le on peut d cliner plusieurs types de probl mes de complexit quivalente NP complets GAR 791 le probl me de la satisfaction d un ensemble de contraintes sur des variables domaine fini pouvant se ramener celui de la coloration d un graphe e d montrer l existence de solutions trouver une toutes les solution s e d montrer qu une instanciation partielle des variables caract rise au moins une toutes les solution s e d terminer toutes les valeurs possibles d une variable sur l ensemble des solutions e trouver une toutes les solution s optimale s 3 2 Notion de consistance dans les PSC et propagation de contraintes La consistance FRE 78 FRE 82 DEC 92 TSA 93 est une propri t tablie par comparaison entre les valeurs d une ou plusieurs variables et les valeurs autoris es par les contraintes Le retrait filtrage de valeurs ou de n uplets de valeurs inconsistants constitue un renforcement de coh rence ou propagation de contraintes Un filtrage complet permet en th orie d obtenir une repr sentation explicite de l ensemble des solutions L absence de solution ou inconsistance globale est d tect e a l issue d un filtrage s il existe une variable Vj telle que Di Les algorithmes de filtrage NAD 89 ont pour objet de transformer un CSP en un nou
16. arch methods whose efficiency strongly depends on an intelligent processing of the constraints that define the feasibility of the solutions Although logic programming is a powerfull and elegant support for the representation of such problems classic imperative languages have been preferred for efficiency considerations Today constraint logic programming seems more attractive since it extends logic programming with efficient mechanisms managing symbolic and numeric constraints Once presented the theoretical bases of such mechanisms this paper attempts to delimit the real advantages of applying this new technology for the solving of scheduling problems MOTS CL S probl mes de satisfaction de contraintes programmation logique avec contraintes ordonnancement KEY WORDS Constraint Satisfaction Problems Constraint Logic Programming Scheduling 1 Introduction Un grand nombre de probl mes pratiques abord s d abord en Recherche Op rationnelle puis en Intelligence Artificielle LAU 76 DIN 90 e g ordonnancement affectation de ressources d coupe de surfaces v rification de circuits logiques sont des probl mes combinatoires dont la r solution revient explorer un espace de recherche discret pour trouver un point satisfaisant un ensemble de contraintes Pour la plupart de ces probl mes il n existe pas d algorithme la fois g n ral et efficace pour les r soudre Il sont donc souvent abord s l aide de techni
17. ates vers le syst me bool en gr ce une propagation conditionnelle on ne peut en revanche associer de d mons aux variables bool ennes dans le but d effectuer la propagation dans l autre sens 6 Conclusion La PL offre un cadre la fois rigoureux et souple pour la repr sentation des probl mes combinatoires dont la r solution n cessite le parcours non d terministe d un espace de recherche Par sa s mantique d clarative et la puissance de la logique du premier ordre elle procure lisibilit concision et flexibilit aux programmes Par contre la strat gie de r solution s av re tr s inefficace tant donn la faiblesse des contraintes d unification comme seul m canisme de propagation de contraintes compar s aux r gles sp cifiques existant sur les variables typ es comme les domaines finis entiers r els ou encore rationnels D autre part le retour arri re chronologique en cas d chec refl te une utilisation passive des contraintes Augment e de r gles d inf rence sp cifiques au traitement de contraintes sur des variables typ es la PLC devient beaucoup plus int ressante pour la repr sentation et la r solution de ces m mes probl mes notamment les probl mes d ordonnancement Cependant les diff rents paradigmes de r solution sont encore relativement cloisonn s et il n existe pas encore de langage complet capable de faire interagir les m canismes de propagation de contraintes sur des domaines diff rents
18. bles En l absence d hypoth ses particuli res e g contraintes num riques binaires conjonctives il n existe pas d algorithme polynomial pour v rifier la consistance globale d un r seau de contraintes quelconques Il n est donc pas possible d implanter un m canisme g n ral efficace dans un langage de PLC 3 3 Les algorithmes d instanciation progressive et de propagation 8 prog Lorsqu aucune d duction ne permet de restreindre un domaine la strat gie d instanciation consiste en une simple num ration des valeurs des variables celles ci tant consid r es dans un ordre arbitraire L application des r gles de filtrage donn es ci dessous doit tre envisag e dans un contexte dynamique partir d un tat courant o certaines variables du probl me ont d j t instanci es d autres pas Le forward checking FC est une technique de renforcement de coh rence par domaine consistance L id e est d exploiter plus efficacement les contraintes en particulier lorsqu en cours de g n ration de solution il ne subsiste dans une contrainte qu une seule variable non instanci e toute valeur du domaine non consistante avec les valeurs des variables d j instanci es est alors retir e du domaine Deux cas particuliers sont importants l issue d un filtrage de ce type e si le domaine devient vide la r solution n cessite un retour arri re e si le domaine se r duit une seule valeur la variable prend automat
19. che nerg tique RAIRO APII 26 5 6 1992 LOP 95 Lopez P HAUDOT L SICARD M ESQUIROL P Constraint based approach to design a DSS for scheduling Proc 3rd International Conference on the Practical Application of Prolog PAP 95 Paris 1995 MAC 77 MACKWORTH A K Consistency in networks of relations Artificial Intelligence 8 1 1977 MOH 86 MoHR R HENDERSON T C Arc and path consistency revisited Artificial Intelligence 28 1986 MON 74 MONTANARI U Networks of Constraints fundamental properties and applications to picture processing Information Sciences 7 1974 NAD 89 NADEL B A Constraint Satisfaction Algorithms Journal of Computers Intelligence 5 1989 PAP 82 PAPADIMITRIOU C H STEIGLITZ K Combinatorial optimization Algorithms and Complexity Prentice Hall Englewood Cliffs NJ 1982 ROB 65 ROBINSON J A A machine oriented logic based on the resolution principle Journal of ACM 12 1 1965 ROY 70 Roy B Alg bre moderne et th orie des graphes tome II Dunod 1970 RUD 74 RUDEANU S Boolean Functions and Equations North Holland Amsterdam London 1974 THI 93 THIERRY C BEL G ESQUIROL P A Constraint Based Model For MultiSite Scheduling Proc IFAC 93 Sidney Australia 1993 TSA 93 TSANG E Foundations of constraint satisfaction Computation in Cognitive Science Series Academic Press 1993 WAL 72 WALTZ D L Generating semantic descriptions from drawings of sc
20. command es et la disponibilit limit e des ressources sur chaque p riode Une mod lisation par flots est souvent propos e pour r soudre ce type de probl mes et les quations de conservation de la mati re sont lin aires THI 93 D autres exemples d application de la PLC certains probl mes de gestion du temps et des ressources peuvent tre avantageusement consult s dans BAP 92 BOI 95 LEG 92 WAL 94 Glossaire Si date de d but de i Fi date de fin de i Di dur e de i Pour une t che i Bi borne temporelle de i Sj ou Fj By borne inf rieure de Bj 14 Bit borne sup rieure de Bj Xij variable bool enne vraie si i pr c de j 5 1 Probl mes de dates C est le cas des probl mes de gestion de projets ou d ordonnancement d atelier La d composition du travail en t ches s y exprime travers des contraintes de localisation temporelle relative entre deux t ches D autre part la d finition de dates limites d ex cution e g fin d un projet d lais d approvisionnement de livraison impose des contraintes de localisation temporelle absolue des t ches 5 1 1 Contraintes de localisation temporelle relative et absolue La majorit des contraintes de localisation temporelle relative peut s exprimer travers une ou plusieurs in galit s entre des dates du type Bj Bj ajj o Bi et Bj repr sentent des bornes temporelles caract ristiques des t ches i et j dates de d but et ou de fin et ajj
21. contraintes n aires n 3 du fait du caract re local du FC cf 3 3 Dans le cas de contraintes lin aires la compl tude passe par une mod lisation en variables rationnelles dans ce domaine CHIP et PrologIII sont quivalents Mais ce jugement doit tre relativis En effet la mod lisation d un probl me concret fait souvent intervenir des contraintes li es 4 des variables de types diff rents mod les variables mixtes S il existe plusieurs paradigmes de r solution de contraintes au sein d un m me langage la propagation de contraintes entre diff rents mod les est relativement limit e Certaines faiblesses actuelles seront donn es en conclusion cf 4 5 4 4 Retardement de contraintes Toutes les contraintes n ont pas un effet imm diat d s leur pose certaines n cessitent une instanciation partielle des variables pour devenir actives Pour pouvoir poser des contraintes sans qu elles soient imm diatement valu es on peut utiliser un m canisme de retardement de buts Ceci correspond une programmation dirig e par les donn es et ne remet pas en cause pour autant le sch ma g n ral pr sent au 4 2 1 Les litt raux retard s sont r veill s et plac s dans la liste des buts courants d s que les conditions d interpr tation sont r unies Exemple 1 CLP R e Z X Y est retard e jusqu ce que l une au moins des 2 variables droite de l galit soit instanci e e Z pow X Y est re
22. de variables et de contraintes Mais les contraintes qu elles repr sentent sont alors utilis es de mani re passive Signalons des travaux r cents BOC 93 sur le traitement de contraintes pseudo bool ennes D autre part la relation qui lie un rationnel son entier imm diatement inf rieur ne peut pas tre une contrainte Une telle contrainte permettrait de propager implicitement toute actualisation des bornes d un domaine d une variable sur le domaine de l autre Pour r soudre ce probl me le co routining n est m me pas utilisable en CHIP on peut en effet propager l actualisation du domaine d un entier vers un rationnel touched 4 mais pas le contraire On ne peut donc pas faire de propagation de contraintes d un syst me de contraintes un autre ce qui diminue les possibilit s d une repr sentation naturelle 13 Ainsi pour un probl me donn il est pr f rable de s orienter vers le langage le plus adapt au domaine de variables du probl me consid r m me s il couvre moins de domaines que le langage concurrent 5 Application aux probl mes d ordonnancement L organisation du travail dans un syst me de production ou dans un grand projet n cessite une d composition du travail relativement aux ressources disponibles pour son ex cution Le produit de cette d composition conduit d finir un ensemble de t ches chaque t che repr sentant une unit de travail l mentaire caract ris e par une
23. dur e et un ensemble de ressources n cessaires son ex cution Le probl me d ordonnancement na t de cette d composition tant donn un ensemble de t ches l mentaires et un ensemble de ressources dont la disponibilit est limit e il est n cessaire d organiser l ex cution des t ches dans le temps en respectant des contraintes vari es telles que e les contraintes de coh rence technologique gammes contraintes logiques d enchainement e les contraintes de ressources elles expriment une disponibilit limit e des ressources en nombre en intensit ou en nergie LOP 92 e les contraintes de localisation temporelle elles r sultent de l existence d objectifs globaux de r alisation tels que des dates limites de d but au plus t t ou de fin au plus tard ou tels qu une dur e totale limit e Compte tenu des diff rents paradigmes de r solution utilis s dans les langages de PLC nous nous sommes limit s 4 deux grandes classes de probl mes pour lesquels une approche par la PLC peut apporter une aide les probl mes pour lesquels il s agit de d terminer des dates d ex cution g n ralement les dates de d but les probl mes pour lesquels il s agit de trouver un s quencement des taches sur chaque ressource Remarque Un autre classe de probl me concerne la planification de quantit s a produire sur un horizon discr tis en p riodes de dur e connue en respectant les d lais et quantit s
24. e propagation conditionnelle de CHIP pr sent e au 4 4 permet de s affranchir de la pose d un point de choix en retardant l activation des contraintes disjonctives tant que les domaines des variables ne permettent pas de trancher pour l une des deux configurations La mod lisation est la suivante disjonction2 S1 2 D1 D2 if S1 lt S2 D2 then S2 gt S1 D1 if S2 lt S1 D1 then S1 gt S2 D2 5 1 2 3 Autre type d inf rence La prise en compte de contraintes disjonctives que ce soit par pose de points de choix ou par propagation conditionnelle ne r duit que les bornes extr mes des domaines des variables 2B consistance LHO 93 FAR 94 Il existe cependant des cas o les contraintes de disjonction pourraient op rer des r ductions de domaine a priori Sans pose de point de choix et sans attendre qu une des deux alternatives de s quencement soit impossible comme l illustre la figure 5 18 Domaine que i ne peut enti rement recouvrir sans chevaucher j i Domaine que j ne peut enti rement recouvrir sans chevaucher i Figure 5 R duction interne de domaines L interdiction de valeurs au sein d un domaine am ne 4a cr er des trous dans les domaines information plus riche que la seule actualisation des bornes En CHIP ce type d inf rence peut tre r alis e grace l utilisation de la primitive cumulative que nous d taillons plus loin 5 1 4 ou directement par une propos
25. e temps machine 2 une borne sup rieure et 3 inf rieure du co t 4 un pourcentage d am lioration 4 2 3 R solution incr mentale Afin de conserver la flexibilit et la souplesse de la PL on ne peut faire l hypoth se que toutes les contraintes sont connues l avance et pos es en bloc Au contraire la possibilit de d clarer les contraintes de mani re modulaire de les int grer progressivement voire de les retirer gr ce la pose de points de choix permet de mettre au point des strat gies de r solution plus volu es 10 Exemple Le programme partiel suivant en CHIP correspond une strat gie de r solution d un probl me dans lequel il existe 2 niveaux de contraintes C1 C2 et 2 crit res diff rents f1 f2 On d sire utiliser le crit re f2 si l ensemble C1UC2 est satisfiable et le crit re f1 si seulement C1 l est resoudre V creer_variables V poser_C1 V suite_resoudre V suite_resoudre V poser_C2 V minimiser_f2 V suite_resoudre V minimiser_f1 V Le caract re incr mental de la r solution et la m morisation automatique du contexte r sultant de la prise en compte de C1 vite une reprise de la r solution depuis le d but lorsque C2 n est pas satisfiable On peut imaginer d autres types de strat gies comme par exemple la pose conditionnelle de contraintes de plus en plus restrictives a partir d une observation de l effet de ces contraintes sur le domaine des variab
26. enes with shadows MAC AI TR 271 MIT 1972 WAL 94 WALLACE M Applying constraints for scheduling Constraint Programming B Mayoh E Tyugu and J Penjaam eds NATO Advanced Science Institute Series Springer Verlag 1994 27 Biographies Patrick ESQUIROL a obtenu sa th se de Doctorat de l Universit Paul Sabatier en 1987 Il a ensuite rejoint une soci t de services en informatique industrielle pour d velopper plusieurs projets dans les domaines de l ordonnancement et des syst mes base de connaissances Depuis 1989 il est ma tre de conf rences au D partement de G nie Electrique de l Institut National des Sciences Appliqu es de Toulouse o il enseigne l algorithmique la programmation et l intelligence artificielle Il effectue sa recherche dans le groupe Syst mes de Production du Laboratoire d Analyse et d Architecture des Syst mes du C N R S Toulouse Ses travaux portent sur l tude des m canismes d analyse et de propagation de contraintes et la conception de logiciels coop ratifs pour les probl mes de gestion du temps et des ressources Email esquirol laas fr Pierre LOPEZ a obtenu sa th se de Doctorat de l Universit Paul Sabatier en 1991 Depuis 1992 il est charg de recherche au CNRS dans le groupe Syst mes de Production du Laboratoire d Analyse et d Architecture des Syst mes du C N R S Toulouse Charg de cours au D partement de G nie Electrique de l Institut National des Sc
27. et plusieurs solutions Par contre il donne bien toutes les variables fig es par la prise en compte des contraintes Nous donnerons au 5 2 un exemple d application en ordonnancement 3 5 Les contraintes sur les rationnels Pour la satisfaction d un ensemble de contraintes lin aires sur des variables continues l algorithme repris en PLC est celui du Simplexe Initialement orient sur la recherche d une solution optimale cet algorithme a subi certaines adaptations autorisant le caract re incr mental de la r solution et la caract risation symbolique d un ensemble de solutions La r solution donne lieu deux types de r ponses soit l chec lorsque le syst me de contraintes n est pas satisfiable soit une repr sentation symbolique de l ensemble des solutions e g y 6x 4z 8 z gt 0 Dans le cas d une solution unique variables fig es la solution est une liste d quations du type Variable1 valeurl Variable2 valeur2 ProloglII et CHIP utilisent une arithm tique sur les rationnels qui peuvent tre repr sent s de mani re exacte en machine pr cision infinie alors que la repr sentation des r els en nombres flottants entra ne des erreurs d arrondi CLP R utilise quant lui une arithm tique sur les r els en notation flottante Un ensemble tr s complet de primitives permettant de poser des contraintes non lin aires e g Y X Z Y log X de constantes et de fonctions math matiques a permis
28. eur 3 ensemble non intercalable entre deux t ches i et j on ne peut pas ins rer simultan ment toutes les t ches d un ensemble donn 22 4 couplage entre 2 relations de succession la contrainte i pr c de j ou k pr c de peut se r crire Xij v Xk Exemple Figure 6 Trois t ches en disjonction Sur cet exemple une recherche d ensembles non ant rieurs et non post rieurs fournit les r sultats suivants A B est non post rieur de C on ne peut pas placer C avant A et B B C est non ant rieur de A on ne peut pas placer A apr s B et C Exprim es l aide de variables bool ennes ces relations conduisent a Xi V Xg A Xi V XA c B c X A X V Xz soit en CHIP en rajoutant la relation de transitivit Xac Xbc amp Xab Xac amp Xab amp Xbc gt Xac amp 1 Xac Ce traitement r v le une relation de pr c dence entre A et C nouvelle contrainte qui peut am liorer l efficacit d une proc dure de r solution Pour mettre en place ce type d inf rence symbolique il faut associer 4 chaque couple de t ches une variable bool enne e g en modifiant disjonction2 cf 5 1 2 2 disjonction3 S 1 D1 S2 D2 X12 if S1 lt S2 D2 then precede S1 S2 D1 X12 if S2 lt S1 D1 then precede S2 S1 D2 X21 X21 amp not X 12 precede Si Sj Di 1 Sj gt Si Di Les contraintes ci dessus sont des cas particuliers de contraintes plus g n rales exprim
29. faction in logic programming Logic Programming Series E Shapiro ed MIT Press 1989 HUG 94 HUGUET M J Approche par contraintes pour l aide la d cision et la coop ration en gestion de production Th se de Doctorat INSA Toulouse 1994 JAF 87 JAFFAR J MICHAYLOV S Methodology and Implementation of a CLP System Proc 4th International Conference on Logic Programming Melbourne Australia 1987 JAF 94 JAFFAR J MAHER M J Constraint Logic Programming A survey Journal of Logic Programming 19 20 pp 503 581 1994 LAU 76 LAURIERE J L Un langage et un programme pour noncer et r soudre des probl mes combinatoires Th se de Doctorat Univ Pierre et Marie Curie Paris 1976 LEG 92 LEGEARD B BAPTISTEP Solving some problems in the CIM area perspectives of the constraint logic programming approach Proc International Conference on Data and Knowledge Systems for Manufacturing and Engineering DKSM 92 Lyon 1992 LEV 94 Levy M L Lopez P PRADIN B Characterization of feasible schedules for the Flow shop problem A decomposition approach Proc European Workshop on Integrated Manufacturing Systems Engineering IMSE 94 pp 307 315 Grenoble 1994 LHO 93 LHOMME O Consistency techniques for numeric CSPs Proc 13th Joint Conference on Artificial Intelligence IJCAI 93 Chamb ry 1993 26 LOP 92 Lopez P ERSCHLER J ESQUIROL P Ordonnancement de t ches sous contraintes une appro
30. i me t che alors que des dates interdites sont conserv es dans le domaine de la premi re incompletude_cumulative T1 T2 T3 T1 0 3 T2 0 6 T3 0 cumulative T1 T2 T3 6 3 11 1 1 1 unused unused 2 unused unused incompletude_cumulative L L T1 in 0 3 T2 in 0 6 0 On s aper oit m me que le domaine de T1 peut tre modifi si la dur e de T3 change ce qui ne devrait avoir aucune sorte d influence sur les autres t ches 5 2 Probl mes de s quencement Dans ce qui pr c de le s quencement de taches est traduit implicitement par des contraintes d in galit s entre dates de d but des t ches Un autre mod le utilisant une variable bool enne par couple de t ches en disjonction permet de traiter symboliquement les probl mes a contraintes disjonctives Soit O un ensemble de t ches tels que toute paire de t che soit n cessairement ordonn e On peut mod liser le probl me du s quencement absolu des t ches par un ensemble de n n 1 2 variables bool ennes une par couple de t ches ordonn es lexicographiquement VG j O i lt j Xij 1 vrai si i pr c de j Xij 0 faux si j pr c de i L int r t d un tel mod le est d abord la repr sentation de contraintes bas es sur la relation symbolique de succession du type 1 ensemble non ant rieur e g l expression X12 v X13 v X14 impose la t che T1 d tre situ e avant T2 ou T3 ou T4 2 ensemble non post ri
31. iences Appliqu es de Toulouse il enseigne la th orie des graphes l ordonnancement et la simulation des syst mes v nements discrets Ses travaux de recherche concernent l analyse et la propagation de contraintes en particulier les contraintes nerg tiques les techniques de d composition des probl mes d ordonnancement et la conception de syst mes coop ratifs pour les probl mes de gestion du temps et des ressources Email lopez laas fr 28
32. in Q Surflnt S 1 4 6 F Fin 9 Q 5 6 9 3 SurfInt 1 Dans AGG 92 les auteurs pr sentent certaines applications de la contrainte cumulative des probl mes de placement d ordonnancement de projet ou encore de job shop Pour ce dernier cas ils utilisent une proc dure du type labeling1 un pr dicat semblable pose_precede et la contrainte cumulative dans laquelle la consommation de ressource des t ches est quivalente une liste de 1 Des r sultats exp rimentaux en particulier sur le fameux probl me 10x10x10 montrent qu il est 21 possible d obtenir des r sultats int ressants une solution 1088 en 1 s la solution optimale en 25 mn sur SPARC IPC 12MB et ceci par une programmation simple mettant en jeu la contrainte cumulative On constate toutefois voir exemple 3 qu en l absence de toute g n ration les d ductions engendr es par la pose de la contrainte cumulative de CHIP d pendent de l ordre dans lequel les variables sont pass es en arguments sans qu aucune indication visant tirer parti de cet ordre ne soit fournie dans le manuel d utilisation Exemple 3 Trois t ches requi rent chacune une unit d une ressource disponible en deux exemplaires La troisi me t che est bloqu e dans sa fen tre temporelle le probl me devrait donc se r duire un probl me disjonctif sur les deux premi res t ches Le r sultat fournit bien toute l information sur le d but de la deux
33. iquement cette valeur variable fig e Le look ahead LA est la k consistance ce que le FC est la domaine consistance L id e est de v rifier que toute valeur du domaine d une variable encore libre demeure consistante avec au moins une instanciation possible des variables encore libres Toute valeur telle qu il est impossible de trouver une instanciation consistante des variables encore libres est cart e du domaine Comme pr c demment les m mes actions sont r alis es dans le cas d un domaine devenant vide ou se r duisant une seule valeur L int gration des m canismes type FC ou LA peut am liorer consid rablement l efficacit globale d une r solution par exploration et retour arri re chronologique en limitant le nombre d checs et la profondeur laquelle ils sont d couverts Cependant un compromis doit tre trouv entre le gain obtenu par la diminution de l espace de recherche et l effort en temps et en m moire consenti l analyse Par exemple l utilisation syst matique du LA meilleur que le FC en ce qui concerne l lagage de l espace de recherche n est pas r aliste au contraire elle doit tre contr l e en valuant la complexit partir du nombre moyen de variables mises en jeu la taille moyenne des domaines et l interd pendance des contraintes 3 4 Les contraintes bool ennes De nombreux probl mes combinatoires donnent lieu des mod les variables bool ennes analyse synth
34. istiques g n rales ne sauraient rel guer au second plan le souci de l efficacit des programmes Dans la suite nous expliquons pourquoi il est n cessaire d tendre la PL lorsqu on envisage de traiter des probl mes dont la r solution est soumise un grand nombre de contraintes num riques et symboliques 3 La programmation logique avec contraintes PLC Lors d une exploration arborescente le nombre d checs et la profondeur laquelle ils sont d tect s d terminent fortement l efficacit globale A titre d exemple le programme et l arbre ci dessous correspondent au probl me de la recherche de tous les couples de chiffres x y parmi 1 2 3 tels que x lt y Les branches menant aux solutions figurent en gras sur l arbre chiffre x chiffre y x lt y x x 3 chiffre y x lt y chiffre y x lt y chiffre y x lt y y 3 y 3 yal y 3 x lt y x lt y x lt y x lt y FX lt Y x lt y x lt y 7 X lt Y 7 X lt Y chec x l x 1 chec chec x 2 chec chec chec y 2 y 3 y 3 Figure 1 Arbre de d rivation Prolog Sur 9 branches terminales l arbre de recherche comporte 6 checs alors que ceux ci auraient pu tre anticip s vitant ainsi une exploration inutile En effet les domaines initiaux respectifs de x et de y comportent certaines valeurs incompatibles avec l in galit stricte x lt y par exemple les valeurs x 3 ou y 1 La mise en place d un tel rai
35. ition pr sent e et d montr e dans LOP 95 dont la programmation est donn e ci dessous Celle ci utilise le pr dicat notin 3 qui permet de supprimer des valeurs au sein du domaine d une variable D autre part ce programme n engendre qu une manipulation passive des contraintes il sera donc int ressant de poser un m canisme de d mon afin de le rendre dynamique arc_consistance S1 S2 D1 D2 D is D1 D2 if S2 lt S2 D then trou S1 S2 D1 D2 if S1 lt S1 D then trou S2 S1 D2 D1 trou S1 S2 D1 D2 domain_info S2 S2min S2max _ Min is S2max D1 1 Max is S2min D2 1 notin S1 Min Max 5 1 3 Ensembles non post rieurs non ant rieurs La contrainte de disjonction peut d duire des conclusions fortes pour le s quencement global En pratique cependant cette r gle peut ne pas tre tr s active lorsque les dur es op ratoires sont petites par rapport aux fen tres temporelles Il peut alors tre plus int ressant d tudier les positions extr mes d une t che par rapport un groupe de t ches ESQ 87 CAR 88 On examine ainsi si une t che peut tre ex cut e avant ou apr s un sous ensemble donn de t ches Par exemple si ne peut pas tre plac e avant B et C elle doit tre plac e au moins apr s B ou C Le sous ensemble B C est un ensemble non post rieur A Le programme ci dessous impl ment en CHIP permet de d terminer les ensembles non post rieurs e
36. le de probl mes d ordonnancement contraintes cumulatives ESQ 93a CHA 941 Le langage CHIP est le premier langage de PLC ayant t dot d une primitive d di e au traitement des contraintes cumulatives Cette primitive r alise une interpr tation active mais limit e des contraintes de ce type L utilisation de cette contrainte n est pas facile tant donn le nombre impressionnant d options qui sont propos es cumulative 8 Toutefois en dehors de toute approche d optimisation elle permet de resserrer les domaines des dates de d but en cr ant ventuellement des trous dans les domaines Les diff rents arguments qui composent la contrainte cumulative sont respectivement des listes S de dates de d but des t ches D de dur es des t ches R de quantit s de ressource consomm e F de dates de fin des t ches E de surfaces des t ches Q une capacit de ressource Fin une dur e totale d ordonnancement une valeur interm diaire La plupart des arguments peuvent prendre des valeurs enti res ou s inscrire dans des domaines finis Une caract ristique originale de cette primitive concerne l argument repr sentant les surfaces des t ches Cette surface ou nergie est une grandeur agr g e qui permet de raisonner simultan ment sur le temps et les ressources Son calcul est issu du produit de la quantit de ressource requise par une t che par sa dur e Elle permet d asseoir certains raisonneme
37. les au fur et 4 mesure de leur pose De telles strat gies sont int ressantes lorsque les contraintes peuvent tre hi rarchis es En effet la pose de contraintes s arr te d s que l ensemble courant n est plus satisfiable et le syst me restaure le dernier tat pr c dant l chec La solution repr sente alors un tat dans lequel les contraintes les plus importantes ont t prises en compte les contraintes responsables de l chec moins importantes ont le plus de raisons d tre remises en cause notamment dans l optique d une r solution interactive des probl mes ESQ 93a HUG 94 4 3 Types de contraintes g r es par les langages de PLC Les types de contraintes sont r sum s dans le tableau suivant Arbres Chaines Domaines Bool ens Rationnels Flottants Entiers Are Pere et PrologIII EF a Bae Ea ee Bal CHIP finis CLP R finis gestion active des contraintes sur ces types de variables types de variables autoris s types de variables non autoris s Figure 3 Contraintes couvertes par les langages de PLC Le langage CHIP appara t comme celui qui couvre le plus de types de contraintes Il est capable de propager activement des contraintes sur des variables 11 domaine fini notamment les entiers avec la possibilit de g rer des ensembles discontinus e g X 1 2 3 7 8 9 Cette propagation est n anmoins incompl te pour des
38. n r le de guide pour un choix ordonn des variables et ou de leurs valeurs On peut aussi avoir recours des m thodes plus exp rimentales utilisant des connaissances sp cifiques au domaine consid r On trouve souvent des strat gies tr s efficaces dans les m thodes heuristiques CAR 93 mais cette sp cificit rend les mod les peu r utilisables notamment dans la perspective de la conception d un langage de programmation Sur le plan pratique on trouve deux classes d outils Les outils g n raux e g la programmation lin aire en nombres entiers proposent une nonciation standard moyennant une r criture qui a tendance augmenter substantiellement la taille de l espace de recherche augmentation du nombre de variables et ou du nombre de contraintes et qui abandonne certaines caract ristiques importantes du domaine existence d heuristiques de sym tries Les outils d di s crits l aide de langages proc duraux procurent une efficacit r elle mais posent essentiellement le probl me de leur r utilisabilit Il existe donc un besoin r el mais difficile satisfaire disposer d un langage suffisamment riche pour noncer sans les d former une classe large de probl mes combinatoires et suffisamment ouvert de mani re y int grer des connaissances sp cifiques pouvant am liorer consid rablement l efficacit 2 La programmation logique standard PL En PL CLO 81 COL 83 ACM 92 l ex cu
39. nts un niveau plus lev d abstraction lorsqu on ne conna t pas de mani re pr cise les caract ristiques de r alisation e g la dur e des t ches Cette notion sert de base une m thode de propagation de contraintes mettant en jeu des bilans nerg tiques LOP 92 Les exemples suivants COS 93 illustrent l utilisation de la contrainte cumulative Dans le premier exemple les dur es des t ches sont connues et on cherche minimiser la dur e totale de l ordonnancement Dans le second les dur es 20 ne sont pas connues et on cherche minimiser la surface au dessus d une valeur moyenne d utilisation de ressource fix e 2 Pr dicats communs aux 2 exemples definition S F R Fin Q Surflnt S S1 S2 S3 F F1 F2 F3 R 1 2 2 S 1 10 F 1 10 Q 1 3 Fin SurfInt 1 10 labeling2 labeling2 XIL indomain X labeling2 L Exemple 1 dur es connues minimisation de la dur e de l ordonnancement top S F Fin Q Surflnt definition S F R Fin Q Surflnt D 4 2 3 cumulative S D R F unused Q Fin 2 SurflInt min_max labeling2 S Fin top S F Fin Q Surflnt S 1 1 3 F Fin 6 Q 5 3 6 3 SurfInt 4 Exemple 2 dur es non connues minimisation de la surface interm diaire top S F Fin Q SurfInt definition S F R Fin Q Surfint D D1 D2 D3 E 4 4 6 D 1 10 cumulative S D R F E Q Fin 2 SurflInt min_max labeling2 S SurfInt top S F F
40. problem An approach based on Constraint Logic Programming Proc IEEE International Conference on Robotics and Automation pp 1139 1144 Nice 1992 BEN 93 BENHAMOU F COLMERAUER A Constraint Logic Programming selected research Logic Programming Series E Shapiro ed MIT Press 1993 BOC 93 BOCKMAYR A Logic Programming with Pseudo Boolean Constraints Constraint Logic Programming selected research Logic Programming Series F Benhamou amp A Colmerauer eds MIT Press 1993 BOI 94 BoIZUMAULT P DELON Y PERIDY L Constraint Logic Programming for Examination Timetabling Journal of Logic Programming 1995 to appear BUT 87 BUTTNER W SIMONIS H Embedding Boolean expressions into Logic Programming Journal of Symbolic Computation 4 1987 CAR 88 CARLIER J PINSON E An algorithm for solving the Job shop problem Management Science 35 2 pp 164 176 1988 CAR 93 Mc CARTHY B L Liu J Addressing the gap in scheduling research A review of optimization and heuristic methods in production scheduling JPR 31 pp 59 79 1993 CHA 94 CHAMARD A FISHLER A MADE a workshop scheduler system written in CHIP Proc 2nd International Conference on the Practical Application of Prolog PAP 94 London UK 1994 CLO 81 CLOocKSIN W F MELLISH C S Programming in Prolog Springer Verlag New York 1981 COL 83 COLMERAUER A KANOUI H Van CANEGHEM M Prolog Bases th oriques et d veloppements actuels
41. ques de recherche arborescente qui reposent sur une strat gie par tentatives et retour arri re La principale difficult provient de la s mantique des contraintes Celles ci expriment des connaissances de nature d clarative non ant davantage des relations que des d pendances fonctionnelles ce qui ne facilite pas la conception d algorithmes en langage imp ratif L instanciation des variables intervenant dans une contrainte n ob it donc pas un ordre connu a priori De plus les contraintes ne peuvent tre consid r es ind pendamment de mani re s quentielle de par le fort couplage entre contraintes travers les variables qu elles partagent Enfin la nature disjonctive de certaines notamment en ordonnancement GOT 93 engendre des discontinuit s de l espace des solutions rendant difficile sa formulation synth tique L num ration exhaustive des valeurs permet de tester toutes les contraintes mais ceci n est envisageable que pour des probl mes de tr s petite taille et dans le cas de domaines finis Face cette combinatoire la d composabilit d un probl me peut tre une propri t rechercher car elle permet de r soudre un probl me de grande taille travers une suite de r solutions de probl mes de taille r duite LEV 94 En outre il peut exister plusieurs solutions admissibles qui ne sont g n ralement pas totalement quivalentes Les crit res utilis s dans les approches d optimisation jouent alors u
42. se de circuits logiques probl mes de s quencement d affectation Si le probl me g n ral de la r solution d quations bool ennes est lui aussi NP complet il existe n anmoins diff rentes techniques de r criture et d interpr tation exploitables pour une meilleure gestion des contraintes bool ennes en PLC Le traitement de contraintes bool ennes pose d abord le probl me de l unification d expressions bool ennes RUD 74 COL 86 DIN 87 Il faut d finir le langage des expressions constantes variables op rateurs et l interpr tation de l galit entre 2 expressions bool ennes En ProloglIl l nonc de contraintes bool ennes est d fini par un langage utilisant l ensemble des op rateurs classiques Les r ponses sont fournies sous la forme d un syst me d quations canonique dont la forme peut d pendre de l ordre dans lequel les contraintes ont t consid r es La strat gie de r solution est la SL r solution saine et compl te Le langage CHIP est bas sur une strat gie diff rente la r criture des expressions d une alg bre de Boole dans l anneau bool en muni des op rateurs logiques ou exclusif et et L int r t est d assurer l existence d un plus grand unificateur unique dont la d termination peut tre r alis e par un algorithme d unification bool enne efficace DIN 87 BUT 87 Contrairement PrologIII CHIP ne retourne pas un syst me d quations bool ennes lorsque le probl me adm
43. sonnement au sein m me du langage et non par programmation implique qu il puisse implicitement exploiter la contrainte x lt y avant toute instanciation des variables Le probl me vient donc du fait que la relation x lt y n est pas interpr t e comme une contrainte num rique mais comme un simple test sur des variables n cessairement instanci es au pr alable Les tests num riques ne sont d ailleurs pas des primitives logiques et leur existence a permis de ne pas cantonner Prolog au seul calcul symbolique mais d en faire un v ritable langage de programmation Si la r duction initiale des domaines pr sente un caract re utile et n cessaire elle n est pas suffisante une contrainte peut ne devenir active qu partir d une certaine tape d instanciation c est le cas de la branche x 2 D s que x est fix 2 la contrainte x lt y peut r duire le domaine de y la valeur 3 ce qui permet d viter l exploration inutile des branches y 1 et y 2 Ce type d inf rence n est pas produit en PL car il exigerait de faire la diff rence entre les variables non typ es prenant comme valeur un terme et les variables num riques enti res rationnelles ou r elles Le manque d efficacit de la PL standard pour la r solution des probl mes comportant des contraintes num riques provient donc d une utilisation passive des contraintes les valeurs incompatibles avec les contraintes ne sont limin es que lors du retour arri re cons c
44. t non ant rieurs maximaux d une t che et d actualiser le domaine de la date de d but de cette t che Il utilise le m canisme de propagation conditionnelle et les pr dicats minimum 2 et maximum 2 qui permettent de calculer les extr mit s temporelles d un ensemble de t ches 19 non_posterieur Si Di T non_anterieur Si Di T duree_T T Sigma duree_T T Sigma liste_fins T L_fins liste_debuts T L_debuts minimum Fin_min L_fins minimum Debut_min L_debuts maximum Fin_max L_fins maximum Debut_max L_debuts D is Di Sigma if Si lt Debut_min Sigma if Fin_max lt Si D then Si Di lt Debut_max then Si gt Fin_min 5 1 4 Contraintes cumulatives Les limitations sur la disponibilit des ressources induit des contraintes cumulatives Ces contraintes interdisent l ex cution simultan e d un nombre de t ches tel que l intensit totale d utilisation de la ressource d passe l intensit maximale de la ressource Il s en suit un s quencement partiel des t ches moins fort que le s quencement total impos par les contraintes disjonctives A titre d exemple un probl me de 4 t ches n cessitant toutes une ressource disponible en deux exemplaires est un probl me contraintes cumulatives tout sous ensemble de trois t ches doit contenir au moins deux t ches ordonn es Les probl mes de d coupe de pi ces sur un format de taille limit e repr sentent galement une version spatia
45. tard e jusqu ce que X et Y soient instanci es gt Z est valuable ou X et Z soient instanci es gt Y est valuable ou X 1 gt Z 1 ou Y 0 gt Z 1 ou Y 1 gt Z X Le principe est mis en uvre par un m canisme de co routining DIN 88 HEN 89 De ce fait il peut y avoir une incoh rence dans le syst me de contraintes une tape donn e celle ci n tant d tect e que lors du r veil des contraintes retard es ce qui pr sente un inconv nient certain sur le plan de l efficacit utilisation passive des contraintes L exemple suivant montre que le retardement de contraintes est un m canisme d licat et qu il est tr s important de ma triser les sp cificit s du langage dans ce domaine Exemple 2 ProloglII gt U N 0 lt N lt l y La d finition incoh rente d un arbre U de taille N comprise entre O et 1 n est pas d tect e car la variable N est libre au moment de la pose de ces contraintes 12 Il existe deux modes de retardement de contraintes implicite et explicite Le premier correspond au cas o le langage prend en charge le retardement apr s avoir d tect l impossibilit d exploiter imm diatement la contrainte cf exemple 1 Le deuxi me met en uvre des primitives d di es comme e freeze x but A1 A2 An PrologIll but n est valu que lorsque x est instanci e delay but A1 A2 An CHIP but n est valu que lorsque les argumen
46. tion d un programme correspond au d roulement d un raisonnement logique contr l par un d monstrateur automatique En PL contrairement la programmation imp rative une distinction est faite entre repr sentation le programme et traitement l ex cution Le programmeur mod lise le probl me l aide d un ensemble de relations de la logique des pr dicats du premier ordre puis construit un ensemble d nonc s sous la forme de clauses de Horn Dans le cas d un graphe orient une relation arc x y symbolise l arc orient qui lie le sommet x au sommet y et une relation chemin x y c permet de relier deux n uds x origine et y extr mit par un chemin c liste des n uds travers s pour aller de x en y x et y compris La d finition r cursive d un chemin donne lieu deux clauses chemin x y x y arc x y chemin x z xIL arc x y chemin y z L Le m me programme peut servir 1 d terminer tous les chemins entre deux n uds donn s 2 construire tous les chemins partant d un n ud donn ou 3 arrivant en un n ud donn 4 g n rer l ensemble des chemins du graphe 5 donner tous les chemins de longueur donn e passant par un n ud particulier On qualifie de r versibles les programmes d finissant des relations telles que la relation chemin x y c pour lesquels le r le d entr e sortie des arguments n est pas fig Pour r pondre une question donn e le langage applique le
47. ts A1 A2 An v rifient certaines conditions d instanciation compl te ou partielle e touched but X Info Type_ev CHIP L apparition d un v nement modifiant le domaine fini de X augmentation diminution de la borne minimum maximum retrait d une valeur interne engendre l ex cution imm diate de but X Info e une primitive de propagation conditionnelle CHIP if lt condition gt then lt but1 gt else lt but2 gt dont le fonctionnement est le suivant si lt condition gt est satisfiable pour toutes les valeurs des variables alors lt but1 gt est pos si lt condition gt n est pas satisfiable pour toutes les valeurs des variables alors lt but2 gt est pos sinon lt condition gt est syst matiquement r valu chaque modification du domaine des variables impliqu es dans lt condition gt 45 Conclusion Les langages de PLC ne permettent pas l heure actuelle de mod liser directement un probl me faisant intervenir des contraintes m langeant plusieurs types de variables ce qui cr e un certain cloisonnement entre les diff rents syst mes de traitement de contraintes Par exemple une expression h t rog ne comme B x lt y qui associe un bool en B l valuation d une in galit arithm tique n est pas autoris e En r gle g n rale l int gration de telles expressions oblige programmer explicitement des relations de passage entre les diff rents syst mes
48. utif un chec g n re et teste et non a priori teste et g n re Dans la suite nous nous int ressons aux m canismes d inf rence qui ont t int gr s la PL pour aboutir la PLC Nous pr senterons un certain nombre de d finitions et de r sultats th oriques importants obtenus dans le domaine des probl mes de satisfaction de contraintes PSC et leur int gration dans la PLC travers le traitement des contraintes sur les variables domaines finis Des r sultats sp cifiques sont galement utilisables pour le traitement des contraintes sur les bool ens pseudo bool ens rationnels r els listes arbres ou cha nes de caract res que nous ne pourrons que r sumer dans cet article Nous renvoyons le lecteur BEN 93 JAF 94 pour un tour d horizon des recherches actuelles en PLC et TSA 93 pour une synth se d taill e des PSC 3 1 Les PSC sur les domaines finis Un PSC peut tre d fini WAL 72 MON 74 MAC 77 par un 3 uplet V D C tel que e V est un ensemble de variables V V1 V2 Vn 3 Dest un ensemble de domaines finis D D1 D2 Dn o chaque domaine D est l ensemble des valeurs de Vj e C est un ensemble conjonctif de contraintes C C1 C2 Cm o chaque contrainte Cj est d finie par un sous ensemble de variables var Cj Vip Viz Vin une relation rel Cj rel Vi Vi Vipp Dj xDj9x xDin Une solution est un n uplet v1 v2 Vj de v
49. veau CSP tel qu un certain type de consistance soit v rifi Ils se distinguent selon l arit des contraintes consid r es contraintes unaires Un CSP est domaine consistant si le domaine de chaque variable est coh rent avec l ensemble des contraintes unaires qui p sent sur elle contraintes binaires e Un CSP est arc consistant si le domaine de chaque variable est coh rent avec l ensemble des contraintes binaires qui p sent sur elle L algorithme AC4 propos dans MOH 86 est de complexit O mxd2 avec m nombre de contraintes et d taille maximale des domaines e Un CSP est chemin consistant si tout couple de valeurs autoris par une contrainte liant 2 variables l est aussi par tous le aem de contraintes liant ces variables L algorithme PC4 est en O n3 d3 avec n nombre de variables HAN 88 La chemin consistance est une condition plus forte que l arc consistance mais ne constitue pas une condition suffisante de consistance globale comme le montre le probl me de coloration de graphes de la figure 2 ou il existe bien des triplets de valeurs consistants alors que le probl me de coloration d un graphe complet de 4 sommets en 3 couleurs n admet aucune solution Figure 2 Un PSC arc consistant mais non chemin consistant contraintes n aires Un CSP est k consistant si toute instanciation localement consistante de k 1 variables peut tre tendue toute instanciation localement consistante de k varia
Download Pdf Manuals
Related Search