5

タスクのスケジューリングにこの問題があります。各タスクには推奨開始時刻 T ([T-10, T+10] に開始する必要があります) があり、完了までに L 分かかり、多数のリソース [R1, R2,...] を使用します。リソースが使用されている場合、他のタスクはそれを使用できません。開始時間のみが柔軟であることを考えると、私の目標は、タスクをスケジュールして、必要なリソースにアクセスしたり、解決が必要なすべての競合を指摘したりできるようにすることです。

この目的のためにどのアルゴリズムを使用できますか? ありがとうございました。

4

3 に答える 3

4

これを としてタグ付けしたので、制約ロジック プログラミング(CLP) で実装し、CLP 実装に組み込まれたアルゴリズムを使用するprologことをお勧めします。部分的な例:

:- use_module(library(clpfd)).

on_time([]).
on_time([Task|Tasks]) :-
    Task = task(TSuggested,TActual,L,Rs),
    TActual #>= TSuggested - 10,
    TActual #=< TSuggested + 10,
    on_time(Tasks).

別の述語は、2 つのタスクが同じリソースを同時に使用しないことを確認します。

nonoverlap(R,Task1,Task2) :-
    Task1 = task(_,T1,L1,Rs2),
    Task2 = task(_,T2,L2,Rs2),
    ((member(R,Rs1), member(R,Rs2)) ->
        T2 #> T1+L1     % start Task2 after Task1 has finished
        #\/             % OR
        T1 #> T2+L2     % start Task1 after Task2 has finished
    ;
        true            % non-conflicting, do nothing
    ).

最後に、labelingすべての制約付き変数を呼び出して、それらに一貫した値を与えます。これは、整数時間単位で機能するCLP(fd)を使用します。CLP(R)は実数値の時間に対して同じことを行いますが、少し複雑です。リンクは SWI-Prolog 用ですが、SICStus とECLiPSeにも同様のライブラリがあります。

于 2010-11-02T11:40:09.323 に答える
2

このようなスケジューリングの問題は、多くの場合、制約プログラミング CP または混合整数プログラミング (MIP) を使用して対処するのが最適です。どちらも宣言型のアプローチであるため、問題の特性だけに注目し、特殊なエンジンに基礎となるアルゴリズムを処理させるだけで済みます。詳細については、ウィキペディアを参照してください。

http://en.wikipedia.org/wiki/Constraint_programming

http://en.wikipedia.org/wiki/Linear_programming

于 2010-11-01T23:26:27.340 に答える
1

制約がある場合、または問題のドメインがスケールアウトする場合は、次のような不完全なアルゴリズムも確認する必要があります。

于 2010-12-20T10:02:29.530 に答える