次のジョブ/リソース スケジューリングの問題を実装したいと考えています。
- エッジが優先関係をエンコードするジョブの DAG。
- 優先関係のないジョブは並列実行可能
- 複数のリソース プール。各プールには 1 つ以上の同様のリソースが含まれます。
- ジョブは、1 つまたは複数のプールの 1 つまたは複数のリソースに依存する場合があります。つまり、ジョブ J1 は、「プール P1 から 2 つのリソースが必要で、プール P2 から 7 つのリソースが必要です」のようなことを言います。
- ジョブは、直前の先行ジョブの 1 つとまったく同じリソースが必要であることを表明する場合があります。つまり、ジョブ J2 は、「プール P1 から 1 つのリソースが必要ですが、それはジョブ J1 が割り当てられたリソースの 1 つでなければなりません」と言うかもしれません。簡単にするために、この種の制約では、ジョブ J2 が J1 の直接の後継者でなければならないと仮定します。
- リソースの依存関係は、読み取りまたは書き込み、またはその両方、または「ドントケア」のいずれかです。
- ジョブ J1 がプール P1 からリソースに書き込み、その後のジョブ J2 が「J1 が P1 から取得したのと同じリソース」に読み取り依存関係がある場合。その間、リソースはステートフルであるため、他のジョブで書き込みを行うことはできません。
- 各ジョブの実行時間は事前にわかりません。また、ジョブには優先順位や締め切りの要件もありません。
を探しています：
- この問題を正式なドメインで表現する方法、
- 指定された要件と制約でジョブ グラフを実行できるかどうかという質問に答えるオフライン スケジューリング可能性テスト。
- オンライン スケジューリング アルゴリズムの提案
リソース プールがなく、各タイプのリソースが 1 つしかない場合、問題はおそらくはるかに単純になります。グラフ理論と単純なデータフロー分析アルゴリズムの基礎に精通しています。