ジョブの数が未知である確率変数列に対する最適割当て
スポンサーリンク
概要
- 論文の詳細を見る
Derman、Lieberman and Ross〔2〕によって研究されたsequential stochastic assignment problemに於ては、出現するjobの数が既知である場合が扱われている。しかし現実には、jobの数が予め既知である場合は少なく、またjobの数も高々有限であると考えられる。この為に、ここでは出現するjobの数は未知であり、jobが出現する毎にjobの数が一つづつ減少する場合のsequential stochastic assignment Problemを考える。現在、出現し得るjobの数は確率変数Nであらわされ、Nに関する事前知識をqとする。取り得る決定の集合を{p_1、…、P_n}とし、各決定は1回しか用いることは出来ないとする。また、各jobは他のjobとは独立にrateλのPoisson到着により出現するものとする。従って各jobのinterarrival timeにより残りのjobの数に対する知識を改善してゆくものとする。ここではjobが出現した時点でのみ決定を取る事が出来るから、事前知識qもまたjobが出現した時点でのみ改善し、途中の時点では改善しないものと考える。よって、今までのうち最後のjobの出現時刻から現在までの経過時間t、その最後のjobの出現時刻における残り計画期間Tとあわせて(P_1、…、P_n;T、t、q)をこの問題の状態と考える。従って事前知識qはjobとjobの問ではtとは独立となる。一方、各jobの大きさは、i。i。d。確率変数の値としてあらわされると考える。ここでの問題は、出現したjobの大きさを知り取り得る決定{P_1、…、P_n}の中から1つを選択して総期待利得を最大にする事を目的とする。ここでは、この問題を動的計画法により定式化し、最適政策及びその下での総期待利得を求める。
- 社団法人日本オペレーションズ・リサーチ学会の論文