ジョブ 割当 アルゴリズム
以下の問題が分からなくて困っています。
n個のマシンM1,M2,...,Mnにジョブ1,2,...,kを分配する問題を考える。各マシンには重みciが、各ジョブには長さpiが決められている。各マシンの実行するジョブの長さ*重みの総和にばらつきが無いようにジョブを分配したい。
問1.n=2のときの競合比を求めよ。
問2.n個のマシンにジョブを分配するときの競合比を求めよ。
例:
入力
n=2
c1=3,c2=5
k=4
p1=2,p2=6,p3=7,p4=9
入力に対するオンラインアルゴリズムの実行例
M1に割り振られた仕事:p1,p3,p4 総和=3*2+3*7+3*9=54
M2に割り振られた仕事:p2 総和=5*6=30
入力に対するオフラインアルゴリズムの実行例
M1に割り振られた仕事:p2,p3 総和=3*6+3*9=45
M2に割り振られた仕事:p1,p4 総和=5*2+5*7=45
入力に対する競合比=54/45=6/5
まず問1で詰まっているのですが、オンライン(greedy)アルゴリズムな場合を考えたときは、 2つの
マシーンに割当てられたジョブ(k-1番目までのジョブ)に対する両方の総和(X)を2で割ったもの(Xとおく)にk番目のジョブ(Y)をマシーン1かマシーン2に割当てた内の小さい方が、コストとなると思います。
X/2 + c1*Y or X/2 + c2*Y の内小さい方
しかし、オフラインの時の考え方をどうすればいいのかよく分かりません。(正直、オンラインの場合も自信がないです。)分かる方、ご教授ください。
よろしくお願いします。