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

Question

Je cherchai par ici comme je pouvais et que j'ai trouvé quelques questions pertinentes, je ne pense pas qu'ils couvraient la question à:

Supposons une seule ressource et une liste connue des demandes de planifier une tâche. Chaque demande comprend un start_after, start_by, expected_duration et action.

L'objectif est de planifier les tâches d'exécution le plus rapidement possible tout en gardant chaque tâche planifiée entre start_after et start_by.

Je codé un exemple simple Prolog que je « pensais » devrait fonctionner mais j'ai malheureusement obtiens des erreurs lors de l'exécution: « > = / 2: Les arguments ne sont pas suffisamment instanciées ».

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: conflits objectif n'a pas été tout à fait raison: nécessaire T> clause T1 supplémentaire

.

Edit: Apparemment, mon objectif de programme fonctionne si je demande l'offre valide, paires dans le temps ... mais je suis coincé en essayant de forcer Prolog à trouver des valeurs valides pour T1..3 quand donné R1..3?

Answer 1

Il y a quelques problèmes avec la mise en œuvre originale. Il pourrait fonctionner OK (avec des modifications mineures) dans un système de programmation logique de contrainte, mais pas en Prolog droite. En Prolog, l'ordre des objectifs est cruciale. 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).

I ajouté l'utilisation de l'entre / 3-jacente (a défini BuiltIn dans certaines mises en œuvre Prolog). Il génère des nombres entiers compris entre deux points d'extrémité donné.

I ajouté vérifie l'inégalité en annexe / 6 pour forcer R1, R2 et R3 soit différent de valeurs.

Enfin, je réorganisés les objectifs dans le calendrier / 6 pour assurer que le can_run / 2-jacente a été évaluée pour une paire de variables Ri / Ti avant ces variables ont été vérifiées par des conflits / 3.

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

?-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.