3

ここでできる限り検索しましたが、関連する質問がいくつか見つかりましたが、目前の質問をカバーしているとは思いません。

1 つのリソースと、タスクをスケジュールするための既知の要求リストがあるとします。各リクエストには、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 句が必要でした。

編集: 有効な Request,Time ペアを指定すると、スケジュールの目標が機能するようですが、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 実装で定義されているビルトイン) の使用を追加しました。指定された 2 つのエンドポイント間の整数を生成します。

schedule/6 に不等式チェックを追加して、R1、R2、および R3 を強制的に異なる値にしました。

最後に、schedule/6 のゴールの順序を変更して、競合/3 によって変数がチェックされる前に、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

この問題には、はるかに効率的な実装があります。

于 2010-03-27T12:48:14.247 に答える