ジョブ 割当 アルゴリズム

以下の問題が分からなくて困っています。

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)アルゴリズムな場合を考えたときは、 ２つの
マシーンに割当てられたジョブ(k-1番目までのジョブ)に対する両方の総和（X）を2で割ったもの(Xとおく)にk番目のジョブ(Y)をマシーン1かマシーン2に割当てた内の小さい方が、コストとなると思います。

X/2 + c1*Y or X/2 + c2*Y の内小さい方

しかし、オフラインの時の考え方をどうすればいいのかよく分かりません。(正直、オンラインの場合も自信がないです。)分かる方、ご教授ください。
よろしくお願いします。

No.1 回答者： MagicianKuma 回答日時： 2012/06/01 21:23

う～ん。

今ひとつ何が知りたいのか分からない。

>問1.n=2のときの競合比を求めよ。
>問2.n個のマシンにジョブを分配するときの競合比を求めよ。
具体的なジョブストリームが与えられたときの競合比を求めよという問題なのかな？
オンラインアルゴリズムをこれこれとしたときの競合比の下限値を求めよという問題？

>コスト
説明がないけど、各マシンの実行するジョブの長さ*重みの総和＝コスト　のこと？

>オフラインの時の考え方をどうすればいいのかよく分かりません。
オフラインアルゴリズムとは最初からジョブストリームが与えられており全体を見通して最適な割り当てを求めるアルゴリズムの事だと思います。（実際にうまいアルゴリズムがあるかどうかは別にして）
対して、オンラインアルゴリズムとはジョブp1が与えられたときに割り当てを決め、その後p2が与えられたときに割り当てを決めるといったように、一個一個のジョブごとに割り当てを求めよという意味だと思います。アルゴリズムの一つに貧欲アルゴリズムがあります。

この回答への補足

すいません。説明不足でした。オンラインアルゴリズムを貪欲法とした時の、競合比を求めよ、という問題です。(下限値、上限値を定めて競合比を求める。)オンライン、オフラインアルゴリズムからの競合比を求める意味は分かるのですが。。。。。。
　オンラインアルゴリズムで最悪となりそうな入力とそのコストを考えて、それをオフラインで考えたときのコストと比較。これを競合比の下限とすればいい。と思いました。しかし、上限はどうやって出すのかが新たな疑問が出てきてしまいました。

補足日時：2012/06/01 22:43