糊‖l州‖…刷‖帽‖‖㈹‖‖…酬‖‖‖‖州‖‖‖‖＝州‖‖…服‖榊‖‖榊‖州‖‖‖‖＝‖‖州‖‖‖‖‖＝‖‖＝‖‖‖‖‖州‖‖＝‖‖州‖＝……＝‖‖州‖＝‖州＝‖‖‖‖＝＝州‖‖‖‖‖＝‖‖＝‖＝‖‖‖‖＝‖‖＝‖‖‖‖‖‖‖‖‖＝＝‖州

蔀享≒1二、∴∵．
・−、・、 ∴・￣ヰ
石崎 文雄‖‖＝‖＝‖‖‖‖‖州‖‖‖‖脚‖…刷‖…‖‖‖‖‖‖‖‖‖‖‖刷‖…‖＝‖＝‖‖＝測‖‖‖‖‖‖‖＝‖仙……‖‖‖＝＝‖‖‖＝刑‖川‖‖‖‖＝＝‖‖‖‖測＝…‖‖‖‖‖＝‖‖‖＝‖州‖＝‖仙……‖刑‖…川＝‖‖‖‖＝＝‖‖＝＝‖‖‖＝‖‖‖‖‖‖＝仙川…川1

介する。4童では分布聞の関係を利用したオンライン鼠。 隠臆め臆

並列推定手法を紹介する。5章で本稿で紹介したオン

待ち行列システムの制御を行う際に，あるバッファライン並列推定手法の特徴を短くまとめる。

容量を持つ待ち行列システムを観測することによってその待ち行列システムとバッファ容量だけが異なる別の待ち行列システムの性能を予測したいことが良くあ

2．離散事象システムの定式化
この章では，彼の議論のための準備として離散事象る。例えば9 パケット通信網のルータにおいて垂加勺なシステムの定式化を行う。特にここでは，考える離散バッファ割当て制御を行うときに，各クラスに割当て事象システムを」−一般化セミマルコフ過程（generaトられたバッファ容量を変化させると性能がどのようにized semiuMarkov process）の枠組みを使い定式化変化するか正確に予測することが良い制御のために必する亜 スペースの制約上，本稿では一般化セミマルコ要である。このような場合には，実際に動いている待フ過程についての説明は行わない。一般化セミマルコ

ち行列システムを停止させたりサービスに影響がJhる

フ過程については［1］等の文献を参照するとよい．

ような擾乱をシステムに加えることなく，そのシステ

図1に示されているようなパラメータ∂をもつ離ムを観測することによりバッファ容量だけが異なる別散事象システムを考える血 βの取り得る値は有限集合の待ち行列システムの性能を予測しなければならない。

で，それを￠＝〈銑，軋…，鮎）と表すことにする。例

さらにこのようなシナtjオにおいては，持ち行列シスえば，待ち行列システムの例だとパラメータβはバテムへの到着過程の統計的な性質が先験的に分かってッファ容量等になる。

いないことが普通である。本稿で紹介するオンライン

本稿においては各イベントに関連する時計の寿命列

並列性能推定手法は，そのような場合に用いられる手をシステムへの人力と考える。例えば，通常のシング法である

ルサーバ待ち行列システムの場合には客の到着に関連

本稿では，離散事象システムのオンライン並列性能する時計の寿命列陥＝（陥，1，陥，2，…）と離脱に関連推定のための手法を幾つか簡単に紹介する。本稿はする時計の寿命列陥＝（佑，1，佑，2，…）が人力になる。

個々の手法の詳細な解説をそれぞれ個別に与えること

ここに陥，た，1ん，ゐはそれぞれゐ番目の客の到着，離脱

ではなく，各手法の適印可能範岡および限界が明らかに関連する時計の寿命を表す確率変数である。になるような形で手法の基本的なアイデアとそこに現またぎ 発生したイベントのタイプとその発生時刻のれる重要な概念を出来るだけ整理された形で提示し，組で構成される列をシステムからの出力と考える。すそのことにより全体的な見通しを与えることを目的となわち々二番目に発生するイベントのタイプを確率変する。個々の手法の詳細な解説については，引屈して数方々，その発狂時刻を確率変数7完で表すと，出力いる参考文献を直接参照してほしい。

は（（gl，71），（g2，茄），…）で表される列になる．簡単

以降本稿は以下のように構成されている。2章におのために出力を9 それがパラメータβに依存するこいては，3，4章で与えられるオンライン並列推定手法の紹介の準備として，本稿で考える離散事象システ
ムの定式化および問題の定式化を行う。3章ではサン￣‖〒4890863瀬戸市せいれい町27
瑠爵爵（24）「現押）］VIwヰ、SystemDynamics

プルパス構築に基づいたオンライン並列推定手法を柑
いしぎき J、みお 南山大学数〕哩情報学灘￣￣￣ ‥−￣− ￣ミミ囲yⅣ叫
図Ⅲ パラメータβを持つ離散事象システム© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

オペレーションズ。リサーチ

とが分かるようにβを明記して，∈（β）と書くことにム，その観測システムの情報から性能を推定するβする．また点番目のイベント発生直後のシステムのとは別のパラメータ値を持つシステムのことを推定シ

状態を確率変数晶（β）（々＝0，1，…）で表すことにする．

ステムと呼ぶことにする．観測システムの観測から得システムの初期状態，すなわち品（β）は確定的に決られる情事削こ関して以下のことを仮定しておく．

まっているものとする．システムの発生可能イベント関数（feasible eventfunction）をIl（x）で表記する．

すなわち，システムが状態Jにあるときの発生可能イベント集合（feasible event set）はIl（x）である．
一般の離散事象システムにおいてはシステムの状態遷●観測システムからの出力は直接観測することが出来る．

●観測システムへの入力は直接観測することは出来ない．
●観測システムの初其馴犬態は既知である．

移は現在の状態と発生したイベントの組により確率的

結局，本稿で考える離散事象システムに対するオンラに決まるが，本稿で考える離散事象システムは状態遷

イン並列性能推定は，特定のパラメータ値βを持つ移が現在の状態と発生したイベントの組により確定的観測システムの出力の観測から違うパラメータ値（すに決まるものに制限する．システムの状態遷移関数をなわち違う状態遷移関数）を持つ推定システムの性能／で表記することにする．すなわち，システムが状態を推定することになる．

Jにありイベントe′が発生すると，システムは新しい状態／（∬，e′）に遷移する．ここに紹丁（∬）であるZ3。サンプルパス構築による方法に関して，／（J，才）は定義されないものとする．特に本章では，前章で定式化された離散事象システムの断りの無い限り本稿で考えるシステムのパラメータβ

並列性能推定を行う手法，特に推定システムのサンプはシステムの状態遷移関数／にのみ影響を及ぼすもルパス構築によってオンライン並列性能推定を行う手のとする．

法を幾つか紹介する．この方法は観測システムの出力

以上本稿の見方によると，考えるシステムはイベンの観測から推定システムのサンプルパスを構築するもトに付随する時計の寿命列が入力されると，システムので，観測システムの出力と確率的に等価な推定シスが持っている発生可能イベント関数と状態遷移関数にテムのサンプルパスが構築できれば，その構築された従って，イベントのタイプとその発生時刻の組の列サンプルパスから推定システムの性能が推定できるこ（（gl，n），（且2，右），・・・）を出力するシステムと考えられとになる．サンプルパス構築によって並列推定を行う

る．

手法は，サンプルパスの構築の仕方により大きく二つ
本稿で考えるような状態遷移に確率的な要素を含まに分類することが出来る．一つは観測システムの出力ない離散事象システムにおいては，初期状態と出力を観測し，それを直接使って推定システムのサンプル〈（且，れ），（且2∴㍍），…）からシステムの状態を表す過程

パス構築を行う方法で，もう一つは観測システムの出を完全に決めることが出来るので，システムに関する力の観測からその入力を決定しその入力を使って推定情報の観点からは，出力とサンプルパスを同一視してシステムのサンプルパスを構築する方法である．前者

よい．以降本稿では出力とサンプルパスを同一視するの方法に基づいた手法を3．1，3．2節で，後者の方法ことにする．このとき，システムのあるサンプルパスに基づいた手法を3．3節で紹介する．

での性能（サンプル性能）は出力ぎ（β）によって決ま3．1サンプルパス構築可能性ることになる．出力とサンプル性能を対応づけるサン

本節では，観測システムの出力を観測し，それを直プル性能関数をエと表記することにすると，システ接使って推定システムのサンプルパス構築を行う方法

ムの性能評価指標は結局ノ（β）＝且［上（ぎ（β））］と表されについての考察を行う．この方法では，観測システムることになる．の出力（すなわち発生したイベントのタイプとその発さて上の定式化のもとで，オンライン並列性能推定

生時刻の≠阻の列）をそのまま使って推定システムの状とはある特定のβのもとで動いている離散事象シス態遷移関数を駆動してやることにより推定システムのテムを観測し，その観測結果から違うパラメータ値をサンプルパスを構築する．

持ったシステムの性能／（仇），′（β1），…，J（鮎）を推定す

このようにして推定システムのサンプルパスを構築ることである．以降簡単のために，ある特定のパラメする方法は直接的な方法ではあるが，どのようなシスータ値βで観測されたシステムのことを観測システテムに対しても適用出来るわけではない．この方法が2001年4月号© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

（25）189

適用できるためには，原理から明らかなように，観測システムからの出力を川いて （a）観測システムの観測されたサンプルパスと確率的に等価な（b）推定シス

テムの状態遷移関数に従った推定システムのサンプルddd

観測システム（K＝3）

パス を構築できないといけない。そのような推定システムのサンプルパスを構築出来ることを保証する条件をCassandras and Strickland［3］はサンプルパス構築可能性条件（Sample pathcomstructability conN

aad

拡大システムd推定システム（だ＝2）

図2 状態遷移図

朗tiom）と命名し研究している。サンプルパス構築可能性条件は，2つの条件を合わせた形で述べられておさらにその状態から過渡的な状態を取り除いた新しいり，その各々がそれぞれゝⅧ二記の （a）観測システムの観システムを考えるのが便利である。このシステムのこ測されたサンプルパスと確率的に等価な99 と （b）推定とをCassandras and Strickland［4］は拡大システム

システムの状態遷移関数に従った推定システムのサン（Augmented system）と名付けた。図に示された拡プルパス に対応している。以Fにおいて，サンプル大システムの左側の部分では，2つのシステムは同じパス構築吋能性条件を説明する。

状態にとどまっている。2つのシステムの状態の違い

サンプルパス構築可能性条件の最初の条件は（b）に関は，あるゐに関してプ㍍（3）＝方々（2）＝2でイベントα連した条件で，可観測性条件（Observability condi−が起こったときに限り発生する。そのときに，

tion）と呼ばれる。この条件は，任意時点で観測シス

晶十1（3）＝3となるが9 先＋l（2）＝2である。これ以降2テムと推定システム間の状態の違いに起岡する発生吋

つのシステムの状態はプ㍍（3）＝＆（2）＋1となり，こ能イベント集合√（ご‰（β）），r（脆（βm））の違いのための関係は状態が（1，0）になるまで続き，状態が（1，0）に推定システムのサンプルパスが構築出来なくなるこでイベントdが発／二王三すると状態は（0，0）に戻る。

とがないことを保証する。言い換えると，推定システ

拡大システムの状態遷移図を調べることにより，ムの状態遷移関数が定義されないような状態とイベンプ㌫（3）ニプ㍍（2）となる3つの状態に関して可観測性条

トの組▲合せが推定システムの状態遷移関数に人力され件が満たされていることが直ちにわかる。また同様にることがないことを′保証する。

状態（3，2），（2，1）に関しても，すべての∬＞0で（可観測性条件）ぎ（のをβのもとでのサンプルパ

Jl（J）＝（α，d）なので可観測性条件が満たされている

スとし，（脆（β））吉≡。を対応する状態列とする㊥ β椚≠β

ことがわかる。残りの状態（1，0）についても，に関して，∈（βm）をβにおける出力ど（のによって生r（プ㍍（2））＝r（0）＝（α）⊂〈α，d〉＝Jl（1）＝デ（羞（3））であ成されるサンプルパスとする。このとき，すべての々るので可観測性条件が満たされている。したがって，＝0，1，…に関して，㌃（羞（β∽））⊆r（プ㍍（の）。

ぞ（2）はど（3）に対して吋観測になっている。

この条件が満たされているとき∈（β椚）はぎ（のに対して可観測（observat）1e）であるといわれる。
例3．且：G佃／且相持ち行列システムに関する可観

次に，観測システムと推定システムの役割を入れ替えて，可観測性を考えてみる。すなわち，厨＝2のシステムを観測システム，茸＝3のシステムを推定システムとし，ど（3）のぎ（2）に対する可観測性を考える。

測性条件［且］

G／G／1／K待ち行列システムの例を考えてみる。バ

このときは，状態（1，0）について，r（＆（3））＝r（1）＝

ッファ容量．打をパラメータとし，∬＝3のシステム（α，の￠（α）＝J「（0）＝r（＆（2））となり，状態＆（2）＝0を観測システム，肯＝2のシステムを推定システムとで状態ガ云（3）＝1で必要とされる発生可能イベントdする。このときど（2）のど（3）に対する可観測性を考えが観測できないことになる。したがって，∈（3）はてみる。

ぎ（2）に対して吋観測とならない。

これらの2つのシステムの状態遷移図を図2に示す。

さて講を元に戻して，残りの （a）観測システムの観ここにイベントの集合はE＝（α，d）で9 吼dはそれぞ測されたサンプルパスと確率的に等価な の部分に関れ客の到着，離脱を表す。推定システムのサンプルパわる条件についての考察を行う。ある時点において観スは観測システムの出力をそのまま使って構築される測システムで発生叶能イベントであるにも関わらず，ので9 2つのシステムの結合待ち行列長を状態とし，推定システムで発年ミ可能イベントでか−イベントが存

瑠9◎（26）© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

オペレーションズ。リサーチ在するかもしれないことに注意する（可観測性条件がに等しくなっていないといけないことが分かる．この満たされている場合は，ある時点で観測システムで発ことを以下にまとめる．

生可能イベントでないイベントであるにも関わらず，あるイベント才の観測された年齢をzとしたときの推定システムで発生可能イベントであるようなイベン

そのイベントの残余寿命の分布をガォ（f，Z）で表すことトは存在しない）．このために，観測システムと推定にする．すなわち，システム間でその入力であるイベントに関する時計の月i（f，Z）＝P（杭＜z＋fl析＞2）寿命列が異なることになる場合がある．このことを，である．イベントの年齢はパラメータβに依存する

先ほどのG／G／1／K待ち行列システムを例にとって考ことに注意して，βのもとでの点番目のイベント発えてみる．斤＝3のシステムを観測システム，斤＝2

生直後のイベントZの年齢をzz，烏（β）で表す．また一のシステムを推定システムとし，観測システムの出力般的には残余寿命の分布〟ォ（f，Z）もパラメータβにに従って推定システムのサンプルパスを図3のように依存する・ので〃ブ（′，Z；のと表記することにする．

構築したとする．このとき，ゐで発生したイベントdを引き起こした時計の寿命は観測システムにおいては（イベントに関連する時計の残余寿命分布に関する条件）すべてのダ∈r（羞（β∽）），点＝0，1，…に関して，ぁ】Jl，推定システムにおいてはね−ねとなり異なっ〃亨（′，Z∠，烏（β∽）；βm）＝荘（J，Zブ，ゐ（β）；の．

た値を取ったことになっていることに注意．時刻fl

上記のイベントに関連する時計の残余寿命分布に関すにおいてイベントdは観測システムにおいては発生る条件が満たされれば，推定システムのサンプルパス可能イベントであるにも関わらず推定システムにおいは観測システムのそれと確率的に等価になることが保ては発生可能イベントではなかった．その後，時刻ね証される．

で発生した状態遷移によりイベントdは推定システ

以上の可観測性条件とイベントに関連する時計の残ムにおいても発生可能イベントとなった．このために，余寿命分布に関する条件を合わせたものをサンプルパ

推定システムではイベント♂に関連する時計のためス構築可能性条件と呼ぶ．このサンプルパス構築可能に新しい寿命（すなわち年齢が0のときの残余寿命）性条件が満たされているとき，観測システムの出力にを必要とする．しかしながら，使っている情報は年齢

従って推定システムの状態を推定システムの状態遷移がぁーJlのときの残余寿命で，その残余寿命を新しい関数によって駆動してやると観測システムのサンプル寿命の代用品として使い推定システムのサンプルパスパスと確率的に等価な推定システムのサンプルパスがを構築していることになっている．したがって一般的構築できることになる．には，このようにして構築された推定システムのサン3．2 イベントマッチングアルゴリズム

プルパスは観測システムのそれと確率的に等価になら

3．1節で考えた推定システムのサンプルパスの構築ない．上の観察から構築された推定システムのサンプ

方法は，観測システムの出力をすべて使って推定シスルパスが観測システムのそれと確率的に等価になるたテムのサンプルパスを構築する方法であった．本節でめには，観測システムにおいて発生可能で推定システ

は，観測システムのサンプルパスをカットアンドペー

ムにおいて発生可能でなかったイベントが発生可能とスト（cut−andqpaste）して，言い換えると観測シスなる点での時計の残余寿命分布がもともとの寿命分布

テムの出力の全てを使わずその一部を使うことによって推定システムのサンプルパスを構築する方法を考える．そうすることにより，ある時点での観測システムと推定システム間の状態の違いに起因する発生可能イベント集合r（晶（の），r（羞（β∽））の違いのために推定システムのサンプルパスが構築出来なくなることを回避し，可観測性条件を満足することが出来るようになる．
d

可観測性条件が満たされていない観測システムと推aO

壬1定システムを考える．このとき，以下のようにして推わ定システムのサンプルパスを構築することを考える．
図3 観測システムと推定システムの時計寿命

2001年4月号

r（羞（β∽））⊆r（＆（β））である間は，前節のやり方と© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

（27）191同じように観測システムの出力に従って推定システムとが出来る。またイベントに関連する時計の残余寿命のサンプルパスを構築する匂 r（斉（βm））⊃r（ガ（の）で分布に関する条件については，イベントαに関するあるような状態の組合せ（斉（β），ガ（∂椚））にシステム

時計の寿命は指数分布にしたがうので，その無記憶性が達したとき推定システムのサンプルパスの構築を一により条件を満たす。イベントdに関する時計の寿時休止し，観測システムの新しい状態斉′（のが命はm一般に無記憶ではないが，サンプルパスの構築がr（X（β椚））⊆r（∬′（β））を満たす状態になったときに推相関されるおで，必ず観測システムと推定システムの定システムのサンプルパスの構築を掴関する。ここで両方で新たな寿命（すなわち年齢が0の残余寿命）が可観測性条件充足のためには，推定システムのサンプ設定されるので，時計の寿命の分布は観測システムとルパスの構築の再開を芽′（β）＝ガ（βm）という状態マ推定システムで日計一のものとなる。したがって，イベッチングではなく9 もう少し弱いイベントマッチング

ントに関連する時計の残余＃命分布に関する条件も満爪牙（β椚））⊆√（斉′（の）で行えば十分であることに注息たされることになる。結果として，イベントマッチン

このようにイベントマッチングにより観測システムのグアルゴリズムはM／GI／1／K待ち行列システムに適サンプルパスのカットアンドペーストを行い推定シス川可能である。

テムのサンプルパスの構築を行う手法をイベントマッ

3．3 タイムワwビングアルゴリズム

チングアルゴリズム（Event Matching Aigorithm）

今までに説明したサンプルパス構築の方法は，観測［5］と呼ぶ。

システムの脚力の全部あるいは一部を使って推定シス

次に，イベントに関連する時計の残余寿命分布に関テムのサンプルパスを構築するものであった。それにする条件の観点からイベントマッチングアルゴリズム射しタイムワーピングアルゴリズム（TimeWarpingを考察する。この条件が満たされるためには，サンプ

Algorithm）［2］は観測システムの人力すなわち各イベルパスの構築が二醇開される点で，推定システムのすべントの時計寿命列を使って推定システムのサンプルパての発隼可能イベントに付随する時計の残余寿命分布スを構築する。タイムワービングアルゴリズムを一言が観測システムの対応するそれと等しくなっている必で説明すると以骨のようになる。観測により観測シス要がある8 これは一般には満たされないが，イベントテムの侶力からその人力であるイベントの時計寿命列に関連する時計の寿命分布がすべて指数分布のシステを順次決定していく。現時点までに得られた時計寿命ムや指数分布に従わない時計がサンプルパスの構築が列を使うことにより，推定システムのサンプルパスを楯岡される点で観測システムと推定システムの両方で現時一点までで柿築できる最大時一点まで構築していく。

必ず新たにセットされるようなシステムにおいてはこ

タイムワービングアルゴリズムは，前節までに紹介の条件は満たされることになる。後者のシステムの例

したサンプルパス構築アルゴリズムに比べるとより原としてM／GI／1／K待ち行列システムがある。

始的でそれゆえに適用範囲も広い。しかしながら，す

例3．2≡M／Gヨ／且／K待ち行列システムヘのイベント

でに観測されたにも関わらずまだ推定システムのサンプルパスの構築のために使われていないイベントの時マッチングアルガヨjズムの適用

例3。1と同様のシステム，ただし到着αに関する計寿命の部分列を記憶しておくことが必要となる。ス

時計の寿命が独嘉溝針一の指数分私 離脱dに関するペースの制約仁，タイムワービングアルゴリズムのこ時計の寿命が独立同一の】−〃一般分布に従う待ち行列シスれ以上の説明と定式化は省略する。タイムワービング

テムを考える。観測システムのバッファ容量を仔＝29

アルゴリズムついての詳しい説明は［2，1］を参照して推定システムのバッファ容量を∬＝3とする。このとほしい。

き，かソトアンドペーストを行わず観測システムの出力をすべて依って推定システムのサンプルパスを梼築

4。分布聞に成立する関係を利用する方法

しようとすると，例3。1で見たように可観測件条件が3章では推定システムのサンプルパスを構築するこ満たされない。しかしながら，状態の組合せが斉（のとによって推定システムの性能推定を行う手法を紹介＝0，斉（βm）＝1になった時点で推定システムのサンプした。本試では，観測システムと推定システムの状態ルパスの構築を休止し，観測システムに到着がありの分布Ⅰ陽に戌1ンニする関係を利川して，観測システムの方（β）＝1になった時点でサンプルパスの構築を再開

汁一力の観測から推定システムの性能推定を行う手法をすることにすると9 可観測性条件をうまく満足するこ紹介する。

瑠盟2（28）© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

オペレーションズ。リサーチバッファ容量の異なるM／GI／1／K待ち行列システ

うに思える．しかしながら，最近になってIshizaki

ムの定常待ち行列長分布間で簡単な比例関係が成立す

etal．［9］は，サンプルパス構築による方法が容易に通ることがよく知られている．その関係は例えば以下の用出来ない応用上重要と思われる離散時間待ち行列シように表現される［10］．晶＞凡，ノ＝0，…，凡−1に関ステムに分布間に成立する比例関係を利用する手法をして，適用し，その手法の可能性と意義を再提示している．
P（方（凡）＝ノ）＝P（芽（瓜）＝ノ）1−PP（凡≦方（」私）≦瓜−1）

P（芽（凡）＝凡）＝1−

サンプルパス構築による手法の通用が難しいが分布間に成立する関係を利用する手法が容易に通用できる
待ち行列システムの例として，図4に示されるようなP（方（晶）≦凡−1）
1−PP（」軋≦ズ（晶）≦晶−1）

ここに芽（踪）（オ＝0，1）はM／GI／1／踪待ち行列シス
テムの定常状態での待ち行列長を表す確率変数，Pはトラヒック強度である．これと同様な比例関係式は他の待ち行列システム，例えばレベル依存な休暇時間をもつM／GI／1／K待ち行列システム［6，13］等において待ち行列システムを考える．このシステムは単一サーバとバッファで構成される離散時間待ち行列システム
で，到着過程は二種類のストリームから構成される．
各ストリームから客は集団で到着し，客のサービス時間は同じ幾何分布にしたがうものとする．一番目のストリームは，相関のある到着過程，ただし到着のないスロットにおいて再生する到着過程である．二番目のも成立することが知られている．
待ち行列システムの多くの（定常）性能評価指標は，定常待ち行列長分布から計算することができる．そこで以下のように，観測システムと推定システムの定常待ち行列長分布間に成立する比例関係を利用して，観測システムを観測することによって得られた情報から推定システムの種々の性能を推定することができる．
1．観測システムを観測することにより観測システムの定常待ち行列長分布を推定する．
2．その推定された観測システムの定常待ち行列長分布から比例関係を使って推定システムの定常ストリームは，前のスロットでの待ち行列長に依存して次のスロットでの到着数が決まるレベル依存の到着過程である．このストリームは待ち行列長に基づいたフィードバック制御が行われているような到着過程であると見ることができるので，文献［9］においてはこのような到着過程を持つ待ち行列システムのことを

feedbackcontro11edqueueingsystemと呼んでいる．
このような待ち行列システムに関して，観測システムのバッファ容量を晶，推定システムのバッファ容量を凡とし，晶＞凡を仮定してオンライン並列性能推定を行う．この待ち行列システムにおいても，観測シス待ち行列長分布を推定する．
3．その推定された定常待ち行列長分布から推定シテムと推定システムの定常待ち行列長分布間にある比例関係が成立することが示される［14，8］．この分布間ステムの性能を推定する．
この並列推定に分布間に成立する比例関係を利用するというアイデアそのもの自体は文献［7］まで遡ることが出来るものと思われる．そこにおいてGong andGongはM／GI／1／Kにそのアイデアを適用しバッファ容量をパラメータとした並列性能推定を研究していに成立する関係を利用して，観測システムの出力の観測から推定システムの性能を推定することが出来る．
上記のシステムでは，システムへの入力がシステムの状態によってフィードバック制御される．それゆえ，パラメータの値が状態遷移関数のみならず，入力にも影響を及ぼすことになる．このことは，観測システムる。
分布間に成立する関係を利用する並列性能推定手法

への入力と全く同じ列が推定システムへ入力されてもは，観測システムと推定システムの状態分布間に何らかの単純な関係が成立しているようなシステムにしか適用できず，このことがこの手法の通用可能範囲を本質的に制限する．この制限とサンプルパス構築による手法も適用出来るM／GI／1／K待ち行列システムへの適用のような適用例しか示されてこなかったために，分布間に成立する比例関係を利用する手法はGong
and Gongの研究以後あまり注目されて来なかったよ

Feedback control

図4 Feedbackcontrolledqueueingsystem
2001年4月号© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

（29）193それら二つの入力は確率的に等価とは限らないことを［3］C．G．CassandrasandS．G．Strickland，Samplepath意味する．このために，サンプルパス構築による方法

PrOperties of timed discrete event systems，Proc．〆

によってオンライン並列性能推定をすることは難しい。

〟zβm，Vol。77pp．59w71，1989．

例えば，3．1，3．2節で紹介した手法を通用するにも，そもそも＿付記のシステムはイベントに関連する時計の残余寿命分布に関する条件を満たしていない。また
3。3節で紹介した手法を適用してサンプルパスを構築すると推定システムには観測システムの入力と同じ列が入力されることになるが，上述のようにそれらは確率的に等価とはならないので，そのようにして構築さ［4］CuG．CassandrasandS．G．Strickiand，On−1inesemsi−
tivityamalysisofMarkovchains，1EEE77uns．Autom．
Co邦吉γ．，Vol．34，pp．7686，1989．

［5］C．G．Cassandras and S．G．Strickland，Observable

augmemtedsystemsforsensitivityanalysisofMarkov
and semトMarkov processes，1N 77uns．Autom，C〃据わ′．，Voi．34，pp．10261037，1989．

［6］P．Gはsserman and W：B．Gong，Time−Changing

れた推定システムのサンプルパスは観測システムのサand truncating K−CaPaCity queues from one K to

ンプルパスと確率的に等価ではなくなる。結果として，

another，♪フ肴∠γ卯αJ〆月」坤J．戸川∂、Vol．28，Pp．647−655，

上記のシステムに対してサンプルパス構築による方法

1991．

［7］W．B。Gong and K．Gong，On1ine estimation ofを適用するのは難しい。
文献［ll］で得られた結果は，その後Ishizaki［8］に

bu仔ersizeeffectin M／G／1／K queue anditsapplica−

より優先権を含むような離散時間待ち行列システムに

ti川1．けr」∴．そ′ ／ん∴二）、ヾ抽〔㍉ノ高リt〃（、t、り〃J）（−（−／■高りJ（イ仙ノ

拡張されている。さらに，Miyoshiandヱshizaki［14］C〃邦′γOg，pp．1087¶1092，1989．

は，より−一般的な設定で文献［8，9，11，12］において得られていたバッファ容量の異なる待ち行列間の定常待ち行列分布の比例関係を含むより一般的な結米を統一的なアプローチで証明している。

［8］F．Ishizaki，On皿Iineconcurrentestimationofprior−

ity queueing systems with feedback controlled andnonreneWalinput streams，Proc．〆the39thlEEだC〃列痢プ℃犯CgO裾ガecねわ犯α裾dCo犯′和乙j坤．406411，2000．

［9］F．Ishizaki，Exactrelationbetweenlossprobability

and quellelengthin an ATM multiplexer with cor−・・ ∵こ．− ∴．

related arrivais and peri（）dic vacations，P7VC．qf the
本稿では，オンライン並列性能推定手法を幾つか簡単に紹介した。本稿で紹介した性能推定手法は，⑳到着過程に関する先馬鋸勺な完全な知識を必要とし／／仙／ノノ／．川 ／／／り招／／し り／（／こ＝ハ＝り／／Jl′iり川′J／／tり／．＼ tノ／＝り▲−
ゐ才祁g（JCOmトプ4），pp．1A−3．11A−3．8，2000・［10］F．亙shizaki，Comparison ofestimatorsfor on−1ine

concurrent performance estimation of queuelng SyS−

ない
⑳到着過程の統計的性質の変化に追随することがで

tems，tO be presented atIASTEDInternationalCon−
ferenceModeliing，Ident拍cation and Control（MIC）

きる⑳作動中の実システムに擾乱を加えることなく，別のパラメータ値でのシステムの性能を推定できるという特徴を持つため，オンラインで動的な制御を行う場合に特に有益である。これらの性能推定手法を使った離散事象システムの動的な制御に関する研究が今後より盛んに行われることを期待したい。

2001．

［11］F．Ishizaki，G．C．LinandT．Suda，On−1inesensitiv−

ityanalysis offeedback controlledqueueingsystems
with respect to buffer capacity，P7u．〆 the38th
什阜、ノ丁了（1りノ町汀／汗 ・．り／／）（、（ふ／■り〃−イ仙／し り〃／′り／，l−L）・」いう11、
1999．

［12］F．Eshizakiand T．Takine，Loss probabilityin afinitediscrete山timequeueintermsofthesteadystate

参考文献

distribution of aninfinite queue，6？ueueing SγStemS，［1］C．G．Cassandras amd S。Lafortune，hdroduction10

dtscrete euent即StemS，Kluwer academic publishers，Vol．317pp．317326，1999．
［13］J，KeilsonandI，．D．Servi，Blockingprobabilityfor
M／G／1vacationsystemswith occupancyleveldepenT

1999．

［2］C．G4CassandrasandC．G．Panayiotou，Concurrentdentschedules，（カer．Res．Vol．37，pp．134140，1989・

samplepathanalysisofdiscreteeventsystems，jour−［14］N．MiyoshiandF．Ishizaki，AuniBedapproachto
・′・．′、∴・・∴ ∫・∴● ′い−・・ご・‥・ヽ・、・●‥ 、・・ト・こ−：小the proportionalrelation for discretetime single−

171195，1999，

serverqueues，Submitted，2000．

瑠9僅（30）© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

オペレーションズ。リサーチ