nジョブでn番目のジョブが実行されるマシンを見つけるにはmマシンジョブスケジューリング

Question

mマシンにスケジュールされるジョブはn個あり、各マシンはジョブに対して異なる時刻t_iをとります。マシンは無料であれば第1マシンに優先順位を付けて注文します。

n番目のジョブが実行されるマシンを効率的に計算するアルゴリズムをC++でコーディングする必要があります。

はこれまでのところ、私の擬似コードは次のようになります。

initialise rem_time[m] to 0 // Remaining time for m machines 
for each element(i) in job array 
    machine(j)= find_min(rem_time[]) //Find the lowest rem_time among all machines 
    append joblist[j] with element_i 
    rem_time[j] += t_j 

私はさらにfind_min n回を使用してソリューションを最適化するために、ここで使用できる他のソリューションを探していて、スケジュールされているすべてのジョブを格納していますすべてのマシンでは無駄に思える。

ありがとうございます！

Answer 1

アルゴリズムを改善する1つの方法は、バイナリヒープ：https://en.wikipedia.org/wiki/Binary_heapを使用することです（エントリを読むことをお勧めします）。
n < mの場合、あなたの即時回答は明らかにマシン[n]です。
n> mの場合は、マシンの最小ヒープを作成します。ヒープ内の各ノードには、現在割り当てられているジョブの時間と、それを実行しているマシンのインデックスが格納されます。時間はヒープのキーです。
ヒープを作成するにはO（m）が必要です。ヒープを最初のm個のジョブで初期化すると、ノードはkey = joblist [1] machine = 1〜key = joblist [m]、machine = mになります。
結果の各ジョブに対してループを開始します。 ヒープ内のジョブを最小時間で見つけて、O（ログm）を取るヒープから削除します（マシンのインデックスを保存している間）。そのジョブ時間は次のジョブの時間であり、ヒープから削除したばかりのマシンインデックスの新しいノードです。これはまた、O（log m）によって覆われた。
jを必要とするジョブに到達すると、ヒープに挿入しようとする前に削除したマシンのインデックスを取得するだけです。これが答えです。 j = nの場合、このプロセスがO（n log m）によって制限されていることは容易に分かります。 私は実装をあなたに任せていますが、Wikipediaのエントリを使用するのは難しくありません。
さらにヘルプが必要な場合は、お気軽にお問い合わせください。