任务调度使用Prolog的单个资源

Question

我寻遍这里尽我所能，虽然我发现了一些相关的问题，我不认为他们所涉及的问题在眼前：

假设一个单一的资源和请求来调度任务的已知列表。每个请求包括start_after，start_by，expected_duration，并采取行动。

我们的目标是尽可能快调度执行的任务的同时保持每个任务start_after和start_by之间的调度。

我编写了一个简单的例子序言，我“认为”应该工作，但我一直在运行时被不幸收到错误信息：“> = / 2：参数是不够实例化。”

任何帮助或建议将不胜感激

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

编辑： 冲突的目标是不完全正确：需要额外的T> T1子句

编辑： 很显然，如果我提供有效的请求，时间对我的日程表目标工作......但我被困在试图给予R1..3时强制序言找到有效的值T1..3？

Answer 1

有几个与原来的执行问题。它可能工作在约束逻辑编程系统OK（稍作修改），但不是在直序言。在Prolog，目标的顺序是至关重要的。我已修改代码，以便它可以工作：

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

我添加使用之间/ 3谓词（在一些实现方式中的Prolog限定内置）的。它生成两个给定端点之间的整数。

我添加在时间表/ 6不等式检查强制R1，R2，和R3是不同的值。

最后，我重新排序在时间表/ 6的目标，以确保前这些变量是由冲突/ 3。

检查到can_run / 2谓词是为一对RI /钛变量的评价

查询时间表（R1，T1，R2，T2，R3，T3）运行几个分钟，最后生产：

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

有更高效的实现对于这个问题。