Agendamento de tarefas para um único recurso usando Prolog

Question

Pesquisei aqui o melhor que pude e, embora tenha encontrado algumas questões relevantes, não acho que elas tenham abordado a questão em questão:

Suponha um único recurso e uma lista conhecida de solicitações para agendar uma tarefa.Cada solicitação inclui start_after, start_by, Expected_duration e ação.

O objetivo é agendar as tarefas para execução o mais rápido possível, mantendo cada tarefa agendada entre start_after e start_by.

Codifiquei um exemplo simples do Prolog que "pensei" que deveria funcionar, mas infelizmente tenho recebido erros durante o tempo de execução:">=/2:Os argumentos não são suficientemente instanciados”.

Qualquer ajuda ou conselho seria muito apreciado

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

Editar:o objetivo dos conflitos não estava certo:precisava de cláusula extra T>T1.

Editar:Aparentemente, minha meta de cronograma funciona se eu fornecer pares de solicitação e horário válidos ...mas estou tentando forçar o Prolog a encontrar valores válidos para T1..3 quando recebe R1..3?

Answer 1

Existem alguns problemas com a implementação original.Pode funcionar bem (com pequenas modificações) em um sistema de programação de lógica de restrição, mas não em Prolog direto.No Prolog, a ordem dos objetivos é crucial.Modifiquei o código para que funcione:

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

Eu adicionei o uso do predicado entre/3 (um embutido definido em algumas implementações do Prolog).Ele gera os números inteiros entre dois pontos de extremidade determinados.

Adicionei verificações de desigualdade no cronograma/6 para forçar R1, R2 e R3 a terem valores diferentes.

Por fim, reordenei as metas em cronograma/6 para garantir que o predicado can_run/2 fosse avaliado para um par de variáveis ​​Ri/Ti antes que essas variáveis ​​fossem verificadas por conflitos/3.

O agendamento de consulta(R1,T1,R2,T2,R3,T3) é executado por vários minutos e finalmente produz:

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

Existem implementações muito mais eficientes para este problema.