我尽力在这里进行搜索,尽管我发现了一些相关的问题,但我认为它们并不能解决当前的问题:
假设有一个资源和一个已知的请求列表来计划任务。每个请求都包含一个start_after,start_by,expect_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子句。
编辑:
显然,如果我提供有效的Request,Time对,那么我的计划目标就可以工作……但是当我给定R1..3时,我被迫试图迫使Prolog为T1..3查找有效值吗?
最佳答案
原始实现存在两个问题。在约束逻辑编程系统中,它可能行得通(稍作修改),但在直接的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中对目标进行了重新排序,以确保在对冲突变量Ri / Ti进行检查之前,对一对Ri / Ti变量评估了can_run / 2谓词。
查询计划(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
有更有效的解决方案来解决此问题。
关于prolog - 使用Prolog将任务计划到单个资源,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/2148567/