6

ノードがさまざまな種類のワークロードであり、エッジがワークロード間の依存関係であるグラフがあるとします。（循環依存関係が存在してはならないため、これはDAGです。）

また、作業を実行できる複数のエージェントのセットがあります。

一部のワークロードの種類は任意のエージェントに与えることができ、他の種類は特定のエージェントに与える必要があり、他の種類は特定のエージェントグループの1つのエージェントに与える必要があります。

次のようなワークロードを割り当てるにはどうすればよいですか。

  • すべてのブロッキングワークロードが完了するまで、エージェントにワークロードは与えられません

  • 総ワークロードグラフを完成させるには、可能な限り最短の時間が必要です。（エージェントのアイドル時間を最小限に抑えることは一般的には良いことですが、基本的な要件ではないことに注意してください。特定のエージェントが長時間アイドル状態になるシナリオがありますが、すべてのエージェントのすべてのジョブを完了するための合計時間は最小です。）

ワークロードには期間の見積もりがありますが、簡単にするために、すべてのワークロードの計算に同じ時間がかかると想定しています。（すべてのワークロードが実質的に一定時間の操作になるまで、各ワークロードを複数のシリアル依存のワークロードに分割するだけです。）

トポロジカルDAGソートを認識していますが、これにより、ノードの単一のシリアル順序が生成されます。複数のエージェントが並行して動作しており、タスクの非自明な並べ替えによって、潜在的に大規模なタイミング最適化を実行できるような関係になっています。

この結果は、全体の最小期間のガントチャートとして最適にレンダリングされます。実際、この問題を、マイルストーンをできるだけ早く完了することを目的として、チーム内のエンジニアにマイルストーンでバグチケットを割り当てることと考えると、そのアイデアが得られます。（いいえ...グラフをMS Projectにインポートしてからエクスポートするように言わないでください:)-その背後にあるアルゴリズムに興味があります！）

よく知られているアルゴリズム、ソフトウェアライブラリ、または一般的な問題と原則へのポインタは大歓迎です！

4

2 に答える 2

4

タスクのすべての先行タスクが完了するとすぐに互換性のあるエージェントを使用できるようにエージェントの数が無限にない限り、これは NP 困難な問題です。

＜ハレンチプラグ＞

私の著書「 Algorithms For Interviews」には、非常によく似た問題があります。

< /ハレンチプラグ >

本からの問題と解決策は次のとおりです。

M 教室で N 講義をスケジュールする必要があります。これらの講義の中には、他の講義の前提条件となるものもあります。できるだけ早くすべての講義を終了するために、いつ、どこで講義を行うかをどのように選択しますか?

解決策: N 単位時間の講義と M 教室のセットが与えられます。講義は、2 つの講義が同じ教室で同時に行われる必要がなく、すべての優先順位の制約が満たされている限り、同時に開催できます。これらの講義を完了するまでの時間を最小限に抑えるようにスケジューリングする問題は、NP 完全であることが知られています。この問題は、グラフを使用して自然にモデル化されます。u が v の前提条件である場合、頂点 u から頂点 v へのエッジを使用して、講義を頂点としてモデル化します。優先順位の制約が満たされるためには、グラフが非循環でなければならないことは明らかです。講義室が 1 つしかない場合は、単純に講義を位相順に開催し、N 時間で N 回の講義を完了することができます (各講義が単位時間であると仮定します)。次のことを観察することで、ヒューリスティックを開発できます。優先度制約が満たされたレクチャーのセットがあります。このセットが M より小さい場合、それらすべてをスケジュールできます。それ以外の場合は、スケジュールするサブセットを選択する必要があります。サブセットの選択は、いくつかのメトリックに基づくことができます。

  • レクチャーは、開始時の最長の依存関係チェーンの長さに基づいてランク付けされます。
  • 直近の前提条件であるレクチャーの数に基づいてレクチャーをランク付けします。
  • 直接的または間接的な前提条件であるレクチャーの総数に基づいてレクチャーをランク付けします。

これらの基準の組み合わせを使用して、現在スケジュール可能な講義を注文することもできます。たとえば、各頂点について、臨界点をそこからシンクまでの最長パスの長さと定義します。頂点をトポロジー順に処理して講義をスケジュールします。アルゴリズムの任意の時点で、一連の候補レクチャーがあります。これらは、前提条件が既にスケジュールされているレクチャーです。候補セットがサイズ M 未満の場合、すべての講義をスケジュールします。それ以外の場合は、M の最も重要な講義を選択し、それらをスケジュールします。これは、より長い依存関係チェーンの開始点にあるため、より早くスケジュールする必要があるという考えです。基準はヒューリスティックであり、最適なスケジュールにつながらない可能性があります。問題が NP 完全であるため、これは予想されることです。他のヒューリスティックを使用することもできます。

于 2010-10-23T03:25:23.327 に答える
2

PERTに関するウィキペディアの記事は、出発点として役立つかもしれません。

于 2010-10-20T07:06:07.907 に答える