3

我尽我所能在这里搜索，虽然我发现了一些相关的问题，但我认为它们没有涵盖手头的问题：

假设一个资源和一个已知的请求列表来安排任务。每个请求都包含一个 start_after、start_by、expected_duration 和 action。

目标是尽快安排任务执行，同时将每个任务安排在 start_after 和 start_by 之间。

我编写了一个简单的 Prolog 示例，我“认为”应该可以工作，但不幸的是在运行时遇到错误：">=/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 时，我试图强制 Prolog 找到 T1..3 的有效值？

4

1 回答 1

1

原始实现存在几个问题。它在约束逻辑编程系统中可能工作正常（稍作修改），但不能在直接的 Prolog 中工作。在 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).

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

我在 schedule/6 中添加了不等式检查，以强制 R1、R2 和 R3 为不同的值。

最后，我对 schedule/6 中的目标进行了重新排序，以确保 can_run/2 谓词已针对一对 Ri/Ti 变量进行评估，然后再通过冲突/3 检查这些变量。

查询 schedule(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

这个问题有更有效的实现。

于 2010-03-27T12:48:14.247 回答