ordonnancement des tâches à une seule ressource en utilisant Prolog

Je recherche par ici comme je pouvais et que j'ai trouvé quelques questions pertinentes, je ne pense pas qu'ils couvraient la question à:ordonnancement des tâches à une seule ressource en utilisant Prolog

On suppose une seule ressource et liste connue des demandes pour planifier une tâche. Chaque requête comprend un start_after, start_by, expected_duration et une action.

L'objectif est de planifier les tâches à exécuter dès que possible tout en gardant chaque tâche planifiée entre start_after et start_by.

J'ai codé un simple exemple Prolog que je "pensais" devrait fonctionner mais j'ai malheureusement eu des erreurs pendant l'exécution: "> =/2: Les arguments ne sont pas suffisamment instanciés".

Toute aide ou des conseils seraient grandement appréciés

startAfter(1,0). 
startAfter(2,0). 
startAfter(3,0). 

startBy(1,100). 
startBy(2,500). 
startBy(3,300). 

duration(1,199). 
duration(2,199). 
duration(3,199). 

action(1,'noop1'). 
action(2,'noop2'). 
action(3,'noop3'). 

can_run(R,T) :- startAfter(R,TA),startBy(R,TB),T>=TA,T=<TB. 
conflicts(T,R1,T1) :- duration(R1,D1),T=<D1+T1,T>T1. 
schedule(R1,T1,R2,T2,R3,T3) :- 
      can_run(R1,T1),\+conflicts(T1,R2,T2),\+conflicts(T1,R3,T3), 
      can_run(R2,T2),\+conflicts(T2,R1,T1),\+conflicts(T2,R3,T3), 
      can_run(R3,T3),\+conflicts(T3,R1,T1),\+conflicts(T3,R2,T2). 

% when traced I *should* see T1=0, T2=400, T3=200

Edit: but n'a pas été de conflits tout à fait raison: clause T> T1 supplémentaire nécessaire. Apparemment, mon objectif de planification fonctionne si je fournis une requête valide, des paires de temps ... mais je suis bloqué en essayant de forcer Prolog à trouver des valeurs valides pour T1..3 quand on me donne R1..3?

Source

2010-01-27 Reed Debaets

Une autre question que j'ai posée a la dernière instanciation de ce problème: http://stackoverflow.com/questions/2156581/extending-a-prolog-goal-through-recursion –

Vous trouverez des solutions pour des problèmes similaires marqués avec [ tag: clpfd]. Par exemple, dans SICStus Prolog, consultez 'serialized/2', disponible dans' library (clpfd) '. C'est un prédicat dédié qui décrit ce type de contrainte. – mat

L'implémentation d'origine présente quelques problèmes. Cela peut fonctionner correctement (avec des modifications mineures) dans un système de programmation à logique contrainte, mais pas dans Prolog direct. En Prolog, l'ordre des buts est crucial. Je l'ai modifié le code afin qu'il fonctionne:

can_run(R, T) :- 
    startAfter(R,TA), 
    startBy(R,TB), 
    between(TA,TB,T). 

conflicts(T,R1,T1) :- 
    duration(R1,D1), 
    T=<D1+T1, 
    T>=T1. 

schedule(R1,T1,R2,T2,R3,T3) :- 
    can_run(R1,T1), 
    can_run(R2,T2), 
    R1 \= R2, 
    \+ conflicts(T1,R2,T2), 
    can_run(R3,T3), 
    R3 \= R1, 
    R3 \= R2, 
    \+ conflicts(T1,R3,T3), 
    \+ conflicts(T2,R1,T1), 
    \+ conflicts(T2,R3,T3), 
    \+ conflicts(T3,R1,T1), 
    \+ conflicts(T3,R2,T2). 

between(Low, High, Between) :- 
    Between is Low 
    ; 
    Low < High, 
    Next is Low + 1, 
    between(Next, High, Between).

J'ai ajouté l'utilisation du entre/3 prédicat (un BuiltIn défini dans certaines implémentations Prolog). Il génère les entiers entre deux extrémités.

J'ai ajouté des contrôles d'inégalité dans la planification/6 pour forcer R1, R2 et R3 à être des valeurs différentes. Finalement, j'ai réordonné les objectifs dans le programme/6 pour m'assurer que le prédicat can_run/2 a été évalué pour une paire de variables Ri/Ti avant que ces variables aient été vérifiées par les conflits/3.

Le calendrier de requête (R1, T1, R2, T2, R3, T3) court pendant plusieurs minutes et produit enfin:


?-schedule(R1,T1,R2,T2,R3,T3) 
R1 = 1 
T1 = 0 
R2 = 2 
T2 = 400 
R3 = 3 
T3 = 200

Il existe des implémentations beaucoup plus efficaces pour ce problème.

Source

2010-03-27 12:48:14

ordonnancement des tâches à une seule ressource en utilisant Prolog

Répondre

Questions connexes