2

私は Prolog でタスク スケジューラ/プランナーをプログラミングしており、そのために(SWIPL で) CLPFD ライブラリを使用する予定です。スケジューリングの問題を解決するために有限領域を使用することの威力と、それを使用した場合の CPU 負荷への影響について考えていました。

スケジューリングの問題は、この論文の 10 ページに記載されているアサーションに基づいています: 「制約ベースのスケジューリング」。実際、私のタスク/アクティビティは非常に異種であり (プリエンプション可能なものもプリエンプト可能でないものもあります)、アクティビティ リソースの容量は異なります。現在、私は単純なケース (非プリエンプティブル、選言的スケジューリング) に取り組んでおり、次のような結果になりました。

/* 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. */

それは機能し、非常に高速です（実際には瞬間的です）。しかし、これは 3 つのアクティビティがある単純なケースにすぎません。最終的なプログラムでは何百ものアクティビティがあり、スケジューリングの問題はこれよりもはるかに複雑になります。

アドバイスありがとうございます！

4

1 に答える 1

3

一般に、CLP(FD) は、この種の問題を解決するのに適した確立された方法です。ただし、 内でも問題をモデル化するにはさまざまな方法があることに注意してください。library(clpfd)たとえば、グローバル制約を使用しserialized/2たり、それcumulative/1を表現したりできます。他の Prolog システムは、多くの場合、SWI-Prolog よりもはるかに優れたパフォーマンスを提供しますが、問題をモデル化してソリューションを検索する方法は、通常、特定の実装の最適化よりもはるかにパフォーマンスに影響します。

于 2013-06-11T10:45:08.403 に答える