ジョブスケジューリングアルゴリズムでリソース使用率を最大化しますか？

Question

私は、ジョブスケジューリングの問題に対する動的プログラミングアルゴリズムを作成しようとしています。私はnジョブのセットを持っており、それぞれのジョブは、開始時刻がs(i)、終了時刻がf(i)のiです。開始は常に終了前であり、同時に2つのジョブを持つことができます。リソースがビジー状態になっている時間を最大限に活用するためのアルゴリズムを作成するにはどうすればよいですか？

Answer 1

各ポイントでどのような状態を追跡するかを決める必要があります。 1つのオプションは、現在実行中のジョブの終了時刻を追跡することです。この場合、可能な最大ビジー時間は、おおよそ次のように計算できます。

これまでの終了時刻からビジー時刻までのマップを作成します。

1. は、新しいマップを作成し、持っている古い マップからそこにすべてのエントリを挿入します。開始時間の昇順に各ジョブの場合> 0

   - {nullをセット}にそれを初期化します両方の終了時刻は現在の開始よりも大きい 時間。

2. 古いマップの残りの各エントリについて、 のセットから削除すると、現在のジョブの開始時刻（ ）以下のものを終了します。新しいマップに終了時刻のセット のエントリがない場合、または 旧マップのエントリに関連付けられた値が、そのセットの新しいマップの値より大きい場合は、 結果エントリを新しい地図。現在のジョブの終了時刻を の終了時刻に挿入し、新しいジョブで取得した時刻 を値に追加します。新しいマップに完了時刻の のエントリが含まれていない場合、または計算された値より低い値の がある場合は、そのセットのエントリと新しいマップに値 を追加します。
3. 新しいマップは、マップ内の最大値は、可能な限り最大の忙しい時期で終わりに古いマップ

になります。あなたが言及していないバックトラッキング情報を保持している場合は、どのようなジョブの選択であったかを調べるためにトレースすることができます。