performance - Prolog 对有限域库性能的 CLP

Question

我正在 Prolog 中编写任务调度程序/计划程序，为此我打算使用 CLPFD library (在 SWIPL 上)。我想知道使用有限域来解决调度问题有多么强大，以及如果我使用它会对 CPU 负载产生什么影响。

调度问题将基于本文第 10 页中所述的断言:“Constraint-Based Scheduling”。事实上，我的任务/事件将是非常异构的(有些是可抢占的，而另一些则不是)，并且事件资源将具有不同的容量。现在，我只是在处理一个简单的案例(不可抢占的、分离的调度)，我遇到了这样的事情:

/* Non-preemptive, disjunctive scheduling. *******************************/
planner :- 
    /* 'S' stands for start point. 
       'E' stands for end point. */
    set(a1,S1,E1),
    set(a2,S2,E2),
    set(a3,S3,E3),
    interval(intersection,[S1,E1],[S2,E2],[]), % Tests whether activities 
    interval(intersection,[S2,E2],[S3,E3],[]), % intersect. If they do,  
    interval(intersection,[S3,E3],[S1,E1],[]), % backtracking occurs and 
    (...).                                     % an alternative solution
                                               % will be looked for.

/* A set of times in which activity A executes (non-preemptive) */
set(A,[S],[E]) :-
    /* 'A' is the activity.
       'R' is release point and 'D' deadline point. 
       'Lst' stands for Latest Start Point.
       'Eet' stands for Earliest End Point. */
    preemptable(A,no),
    rd(A,R,D),
    p(A,P),
    Lst is D-P,
    Eet is R+P,

    S in R..D,
    E in R..D,

    S #=< Lst,
    E #>= Eet,
    S #< E,
    P #= E-S,
    indomain(S),
    indomain(E).
set(A,[],[]). /* When the activity can't be scheduled. */

它确实有效，而且速度非常快(实际上是瞬时的)。但这只是一个包含三个事件的简单案例，当在我的最终程序中我将有数百个事件时，调度问题将比这复杂得多。

谢谢你的建议!

Answer 1

一般来说，CLP(FD) 是解决此类问题的合适且行之有效的方法。但是请注意，即使在 library(clpfd) 中，也有许多不同的方法可以对您的问题进行建模。 :例如，您可以使用全局约束 serialized/2或 cumulative/1来表达它。其他 Prolog 系统通常会为您提供比 SWI-Prolog 更好的性能，但是您对问题建模和搜索解决方案的方式通常比任何特定实现的优化对性能的影响要大得多。