prolog - 约束逻辑编程调度

Question

我正在尝试在序言中使用 clp 解决问题。问题如下:

基本上，一艘船载有许多容器，我们要卸下它们。容器被描述为谓词 container(I,N,D)，其中 I 是容器标识符，N 是需要卸载的人数，D 是持续时间。示例可能如下所示:

容器(a,1,1)。
容器(b，2，2)。
容器(c，2，2)。
容器(d，3，3)。

容器也可以放在另一个容器之上，例如:

在(a，c)上。
在(b，c)上。
在(c，d)上。

容器 a 在 c 之上，依此类推...

问题是最小化卸载容器的成本。成本定义为雇用的人数乘以所需的时间。在整个卸货期间雇用所有人员。

由于我不熟悉 prolog 的 clp 部分，所以我在开始时遇到了问题。有没有人对如何解决问题有任何建议，或者在哪里可以找到有关 clp prolog 如何工作的示例？

Answer 1

如果为每个作业的开始和结束声明时间变量，则 cumulative/2 可以对整个过程进行建模，serialized/2 可以模拟 on/2 约束:

...
Tasks =
    [task(SA,1,EA,1,_)
    ,task(SB,2,EB,2,_)
    ,task(SC,2,EC,2,_)
    ,task(SD,3,ED,3,_)],
cumulative(Tasks, [limit(MAX)]),

serialized([SA,SC,SD],[1,2,3]),
serialized([SB,SC,SD],[2,2,3]),
...

这已经产生了一个合理的解决方案，并且易于表达总时间的最小化。

...
labeling([min(max(EA,max(EB,max(EC,ED))))], [SA,SB,SC,SD]).

[SA,SB,SC,SD] = [0,0,2,4]

但您必须计算计划的成本，将所需的 worker 数量乘以总持续时间。实际上，这是一个复杂的计算，因为它取决于任务的重叠。我们不能简单地在重叠任务上添加 worker ，因为不同持续时间的任务可能使用同一组 worker 。

我认为有一个“技巧”适用:迭代加深限制 (MAX)，从所需的绝对最小值开始(3，对于容器 d，在这种情况下)。

编辑

抱歉，我对 serialized/2 的看法是错误的。应该用明确的比较代替，比如

EA #=< SC,
...