………………l………………………………lll……………………l……………………………lllll…………lll…州…………llil……………………………………………………………………………………………………………l…‖‖‖＝‖‖淵l・∴シ・−、∵ド・−一骨豆・十r、ヰ！ 丼・J．．−・−∴

一十∴・、・‥ −て ニーーニ言…言二・→−＝‥・
高橋幸雄夕 槻木直樹…………………………‖‖‖‖＝‖‖‖‖‖州……………l…‖‖‖‖‖‖‖‖‖‖酬＝……帖‖‖‖‖＝‖‖‖＝‖‖‖‖‖‖‖‖‖‖‖‖‖‖‖‖＝‖‖＝‖‖‖＝‖‖＝＝＝‖‖‖＝‖＝‖‖‖‖‖‖＝‖‖‖＝‖‖‖‖‖‖＝‖‖＝＝‖‖‖‖‖＝＝‖‖‖‖＝‖‖‖‖‖‖‖＝‖‖＝‖‖＝‖‖帖． ィ、− 、

文［22］がその先駆けのひとつとなったのは幸運であ

待ち行列研究の流れが大きく変化した要因のひとつに，計算機の発達とそれに支えられた数値解析法の研究の進展があった。本稿では，待ち行列に対する数値解析法とそれから派生した相型分布や行列幾何形
式解などの理論的研究がどのように進んできてどこまで到達したかを紹介する。ただし数値解析法は大変
幅広く研究されており，その全容をここで紹介するのった。

これは且976年の』ORSJに掲載された論文で，いまの言葉で言えば，Aggregation／Disaggregatiom法（A／D法）を利用するとPH／PH／cモデルの定常状態
確率が効率的に数値計算できる ことを示したものであった．今坂り返ってみると，この論文の中で使った新しい考え方はつぎの3つであったように思う。

は難しい叩 ここでは9 且975年頃に始まったいわゆるa）吸収的Markov連鎖で表現できる分布（相型分布）

Neu七S流のA旦gori抽m温capproach（アルゴリズム的方b）乱mmpimg法（A／辺法）

法論）の流れを追いながら，それに関係するトピックc）系内人数分布の裾の幾何的減衰を中心に話を進めることをお許し願いたい．なお本稿

この論文を書いたとき，その後これらが現在のようなは，2フ5節を高橋がタ 3，4節を牧本が担当した。

形に発展していくとはとても想像できなかった．
この論文に最初に反応したのは，Marcel『．Neuもs

望8 マ誹』詔習連鎖すこ遮る数値解析であったっ 彼はすでにこのような考えを持っていたの

待ち行列モデルをマルコフ連鎖に帰着して解析す

か夕筆者が送ったpreprimtを読んで気がついたのかはるという方法論は，Er且angによるM／M／β？M／D／βの

定かではないが，すぐにa）のMarkov連鎖で表現でき研究以来，待ち行列研究のもっとも標準的なアプロー

る分布のクラスというのが研究の対象となりうると

チとしてずっと用いられてきた。そして「マルコフ連

考えたようで，［咽でphase−もypedistribu七ion（相型分鎖に帰着されれば，あとは数値的に定常状態確率を求布）というネーミングを与え，研究を開始した。さらめて計算すればよい＿j という考えも，M／G／且に対する隠れマルコフ法（むmbe舶e（旦Markovchaimme七hod）

や註ゐ／Eγ／βの相による方法（meもhodofphases）などに採用されていた山 しかし，これらは比較的特殊なモデルに適用が限定される方法と考えられていた勺

にc）の分布の裾にも興味を持ち，GI／M／1モデルの結果を参考にして，Maもrix−geOmeもric餌msolution（行列幾何形式解）という新しい理論体系を作った。これをまとめたのが［軋2】の著書である凸本稿では，3節で相型分布の発展とその後を，4節で行列幾何形式解にところが，応用上たいへん重要なM／G／βが従来のまつわるいろいろな研究とその後の発展を紹介する．

方法では解析できないことが且966年にKimgmamに

もうひとり，この論文に興味を示したのがPall且』。

よって明らかにされた。これは待ち行列研究における最大のピンチであった。この間題の解決にマルコフ連鎖の数値的方法を利用することを考えたのは，恐らく筆者ばかりではなかったであろう。それでも筆者の論

S血weitze㌻であった†彼もb）の数値計算法とほとんど同じアイディアを持っていたようであるが9 たいへんフェアな態度で筆者の業績を認めてくれた。彼はその後もこの数値計算法を紹介する論文を書いたり，さらに他のmimea訂mO（且e且sへの拡張なども行っている小5節

たかはしゆきお 東京工業大学大学院情報理工学研究科

では，このA／D法とそれに関連する数値解析法の話〒且52m8552 東京都目黒区大岡山2¶12−1

題をいくつか紹介する。

まきもとなおき 筑波大学大学院経営政策科学研究科〒1且2−0の且2 東京都文京区大塚3・一29一且

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

オペレーⅦションズ。リサーチ3．相型分布とMAP

またヱ，Jはそれぞれ到着間隔とサービス時間の相の3．1 相型分布と構造的マルコフ連鎖

ルれ，￡れ＝（（れ，豆，ブ）；宜∈ヱ，j∈J）とし，推移速度行を相型分布（phase−typedistribution）と呼ぶ3・

（1）

Al⁝

マルコフ連鎖の吸収時間分布として定まる確率分布

AO

まる非負確率変数となる．このように，有限次元吸収0るまでの時間は，初期分布と推移速度行列によって定0期分布に従ってスタートしてから吸収状態に吸収され

O A︒Alん⁝

空間上を推移する連続時間マルコフ連鎖を考える．初仇Alん0

列をレベル間の推移で分割して表すと

仇筏0 0⁝

1つの吸収状態と有限個の一時的状態からなる状態集合を表す．また，系内数がmである状態集合をレベ

相型分布は，アーラン分布や超指数分布などいわゆというブロック3重対角構造をもつ5．このようなマる相によって表現される分布を一般化した分布族で，ルコフ連鎖に帰着される待ち行列はPH／PH／1に限ら

待ち行列モデルのAlgorithmic approcahにおいて中ず，複数サーバモデルPH／PH／cや中間バッファが心的な役割を担っている．その主な理由は，

限の直列型待ち行列など広範囲に渡っている．また，

1．［0，∞）上のどのような分布も理論的には任意の精度で相型分布による近似が可能である．

有マルコフ連鎖が持っこのような構造は，4節の行列解
析法や5節の数値計算法を研究する上で大きな役割を果たしている．

2．到着間隔分布やサービス時間分布が相型分布で3．2 相関を持つ入力過程与えられる相型待ち行列は，一般に構造を持った

相型待ち行列モデルの研究が進む一方で，1980年

マルコフ連鎖として定式化できる．

の2つであろう・これらの性質により，M／G／βのように従来の方法では解析できないモデルに対しても，一般分布を相型分布で表現（あるいは近似）して構造的
マルコフ連鎖を構成し4，後述する行列解析法や数値計算法を適用する，というアプローチが可能となる．
到着間隔分布やサービス時間分布が一般分布に従頃から到着間隔が独立でない入力過程や，そのような入力を持つ待ち行列モデルの研究も進められた．例えば，有限状態空間上を推移する連続時間マルコフ連鎖
を考え，連鎖の状態が盲の間は率入壱 のポアソン過程に従ってパケットが到着するモデルが提案されている．このような入力過程はマルコフ変調ポアソン過程

う待ち行列モデルをマルコフ連鎖として定式化する（MarkovModulatedPoissonProcess；MMPP）と呼ばためには，システム内客数に加えて残余到着間隔や残れ，一般に再生過程とはならない・また，Neuts［11］余サービス時間を補助変数として状態に取り込む必は，到着の発生がマルコフ連鎖の状態推移にも依存す要がある（シリーズ第2回を参照）．しかし，このようにして得られるマルコフ連鎖は連続状態空間をるように拡張することで，N−p・rOCeSSと呼ばれる広い

クラスの入力過程を提案している．
このように再生過程ではない入力過程が提案されもつため，計算機による数値解析には不向きである．
一方，到着間隔分布やサービス時間分布が相型分布のた背景には，（i）独立な再生過程の重ね合わせは一般

場合は，系内数と到着間隔分布やサービス時間分布のに再生過程とはならない，（ii）入力が再生過程であっ相の組がマルコフ連鎖をなし，その状態空間は離散的ても退去は一般に再生過程にならない，という基本的である・例えば，PH／PH／1待ち行列の時点fにおけな事実がある．そのため，複数の情報源からのデータ

る系内数Ⅳ（り，到着間隔の相∫拉），サービス時間の相J（りの粗方（り＝（Ⅳ（f），∫拉），J（f））は〟×ヱ×J
上のマルコフ連鎖となる・ここで，〟＝（0，1，2，…），を多重化して送信するシステムや，ネットワークモデ
ルの性能評価においては，非再生型の入力過程を導入する必要が生じる．また，1980年代後半から ATM
ノードの性能評価が問題になると，入力過程が持っ3離散時間マルコフ連鎖を基にすれば，同様にして離散相型分布を考えることができる．
4与えられた相型分布を表す吸収マルコフ連鎖は一意ではな
いため，なるべく状態数が少なく単純な表現を求めるための手続きやデータからパラメータを推定する方法などが研究されているが，未解決の問題も多い［9］・

1998年11月号

バースト性のモデル化に適しているという理由も加わり，上に挙げたような入力過程が注目を集めるよう
5quasトbirth−and−deathprocess（準出生死滅過程）と呼ばれる．

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

（31）619

になった。

兇m＝（Ⅳれ，∬れ）を2次元状態空間〟×紅，紀＝これらの入力過程の中で，現在最も広く使われてい（且，…，∬）上の離散時間マルコフ連鎖としよう．鶴るのほ9 マルコフ型入力過程（MarkovianÅr『ival『ro愉の値によって状態空間をレベル￡

CeSS；MAP）であろう凪咽・MAPでは，有限状態空監）（閃＝の，且，…）によって分割し，レベル間の推移

間止のエルゴード的マルコフ連鎖を考え，状態推移がを部分行列で表したときに，推移確率行列が

′．

：

3

4

なる。実際，どのような単純定常点過程もMAPの極・．川3を含む広い範囲の到着過程を表現することが可能と

（3）

2

腰

の発生を状態推移と連動させることにより，MMpP

∴

1

腰

り山

マルコフ連鎖の状態のみが変化するヰ このように到着

・・∴ ′．．・．

O

腰

腰 滅 通 過 ⁚︻腰で到着が発生し，それ以外の確率では到着は起こらず

1Hふ

起きたときに，その推移に対して予め付与された確率

れ ＝（（町牒）沌 ∈で与えられるものとする。待ち行列モデルにおいて，限として記述することができる酢

梱型分布と同様に9 MÅ貯入力を持っ待ち行列モデ

到着直前の系内数を勒1，サービス時間や到着の相をルもMÅ炉の相を状態として取り込むことにより構造∬mとする隠れマルコフ連鎖は，通常このような構造的マルコフ連鎖に帰着されるため，種々の解析法や数を持つ6口 このマルコフ連鎖の定常状態確率を訂（叫）

値計算法が適用可能である♭ また，独立なMApの重とし，レベルれに対応する定常状態確率ベクトルをね合わせはMÅPとなる，MAPからのランダムな抜滞れ＝（Ⅳ（花，ゐ）雄∈監）で表す血すると，公比行列と呼取りはMA㌘となる，などMApは入力過程に対する

ばれる非負正方行列腰が存在して基本換作に関して閉じており，その意味でも扱いやす・・−、‥‥・、■∫1−

い入力過程であると言える。
が成り立っことが示される［咽・（4）は，幾何分布

なお9 これまで述べた流れとは独立に，相型分布を（2）のベクトル一行列版に相当し，行列幾何形式解

複数の吸収状態に拡張して得られる位相型マルコフ（maもri）rgeOmeもァic雷ormsoiⅦもiom）と呼ばれる。風は再生過程が町原氏によって提案されている軋 また，

非線形行列方程式

集団到着に関してはタ位相型マルコフ再生過程に集団0〈〇到着を加えた複合位相型マルコフ再生過程，MAPに＿∫ ．￣− ∴・・ノ・．

集団到着を加えた迅MÅP 佃aも血MarkoviamÅrriva且

（5）

乃＝＝0

㌘ごOCeSS），最初に述べたⅣ−prOCeSSはいずれも等価なを満たす非負最小解として特徴付けられ，原理的には確率過程である防且町

魔（0）＝のからスタートして逐次代入0く）−・き∴ご−き・・．、1・、●‥漣ミぜ：．．÷・・嗅京∴こ・≡・腰（ゐ＋叫＝∑腰m（た）A氾，ゐ＝畔… （6）乃＝0…∴ ● ∴仁′／≡ 二・ニ●：・∴一ニー溝拭こ∴‥∴て●・．・二貨・洋 ∴ゾ・の極限として求めることができる，また，状態確率ベ

或解クトル罪。，肝1は平衡方程式と正規化条件から（⊃く）

よく知られているように，M／M／且やG亙／M／1待ち

常0腰1十方i∑戯れ軌＋2＝恥

行列の定常分布は幾何分布となる。すなわち9到着直

n．二n
（）く）

前のシステム内客数が開である定常状態確率灯mは，

野0腰0＋厨1∑腐れ過小1＝肝1，
Iトニ0

肝れ＝（1鵬叩）叩mフ れ＝0，且，…

（2）

で与えられる□ 叩∈（り，且）は，到着間隔分布とサ山ビス率から定まる定数で，M／叫且ではトラヒック密度に山致する。これに対して，相型待ち行列に対応する

肝0乳十肝1（す一腰）−1且＝且を解いて得ることができる7．
これらの結果は，M／M／且やα丑／M／且で観察される定常分布の単純な構造が，一般的な待ち行列モデル

ある種の構造的マルコフ連鎖では，ベクトル形式の幾何分布とでも呼ぶべき形の定常分布が存在することが知られている。

6（3）はGりM／1待ち行列の隠れマルコフ連鎖の拡張になっているためG瓦／M／1型と呼ばれる・

7胤は単位列ベクトル，gは単位行列を表す．
© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

6望昏（32）

オペレーションズ0リサーチ（7）

確率行列Gが重要な役割を果たす．Gは方程式に拡張できることを示すと同時に，無限次元の定常状
態確率ベクトルが，線形方程式系（7）と公比行列R○く）

G＝∑んGれという有限次元の要素によって決定されることを明ら

（9）

れ＝＝0

かにしている点で重要である．元来，Algorithmicap−の非負最′J、解として与えられ，原理的には逐次代入にproachの狙いはこの点にあったと考えられる・つま

よって計算することができる

り，（5）を基にRを効率的に求めることができれば，

態確率ベクトル汀。はGの左固有ベクトルとして求定常分布は（4），（7）から容易に計算することが可能と

まり，さらに定常状態確率ベクトルの母関数ベクトル

なる・そのため，（6）の逐次代入も含めて公比行列属

汀（z）＝∑≡。Zれ汀mはに対する種々のアルゴリズムがこれまでに提案されて．また，レベル0の状

汀（z）［z∫−A（z）］＝汀0［zβ（z）−A（z）】

おり，またそれらの比較も行われている［4，5］・

から決定される8・Neuts［13］には，これらも含めて数値計算法の開発の一方で，行列幾何形式解から派当時までに得られたM／G／1型マルコフ連鎖に関する生した行列解析法（matrix−analyticmethod）は理論結果が網羅的に述べられている．さらに，MAPの登的にも大きく発展し，現在では待ち行列解析の1つの場によって重要性が増したこともあり，M／G／1型マ理論体系を成している．例えば，2節で述べた系内人数分布の裾の幾何的減衰は行列幾何形式解によって説

ルコフ連鎖に関する研究はその後も適用範囲を広げ，明することができる（この問題に関する解説がこのシあるいは精微化されながら続けられている．

リーズの第5回に予定されている）．また，ネットワー

5．Aggregation法

クモデルでは，各レベルが可算無限の状態からなるママルコフ連鎖を用いて待ち行列モデルを解析しよ

ルコフ連鎖が現れるが，そのような連鎖に対する行列

うとしたとき，モデルが複雑になるにつれて解かなけ

幾何形式の体系も徐々に整いつつある．さらに，系内ればならないマルコフ連鎖の状態数が急速に増大す

数分布の行列幾何形式解に対応して，連続量である

る9．これがマルコフ連鎖による数値解析の最大の欠待ち時間分布の行列指数形式解（matrix−eXpOnential点である．これを解消するために，マルコフ連鎖の状

brmsolution）などの研究も行われている［17］・

態をまとめて状態数を少なくすることが考えられる．

4・2 M／G／1型マルコフ連鎖

5．1Aggregation法の原理

GI／M／1と逆に，待ち行列モデルにおいて退去直後

状態空間∫上の定常なマルコフ連鎖（ズm）を考え，の状態で隠れマルコフ連鎖を構成すると

β

A

A

3

2

ルを汀＝（汀ま）とする・gの分割を（β1，・‥，∫m），g〝∩

乱＝￠，〃≠レ，∪鎧1g〝＝g，とし，

3

A

A

つ−

β

（8）

軋壱＝打電／∑勺，恥＝ ∑二 恥動（10）

2

J∈5〃

0

i∈g〝，J∈5レ

とおく・すると行列Q＝（‰〝）は

1

⁚．

A．⁚

A

1

0⁝

玖AI A︒0⁝仇A︒0

その推移確率行列をP＝（p宣J），定常状態確率ベクトという構造を持っマルコフ連鎖が現れる（M／G／1型㌦＝〃，ifズm∈5〝（11）と呼ばれる）・例えば，MAP／G／1待ち行列の退去直によって定義される確率過程（㍑）の推移確率行列と後の系内数と到着の相の組は，系内数でレベル分けをなっている・（㍑）はマルコフ性を満たさずマルコフすれば（8）の形のマルコフ連鎖となる・（8）と（3）の連鎖にはならないが，定常過程でありその定常状態確構造から 2つのマルコフ連鎖の間にはいくつかの双率ベクトルα＝（αFL）はaggregatedequation

対的な関係があるがr2］，（8）の定常分布は行列幾何形

α＝αQ

（12）

式解にはならず，陽表現を求めることは難しい．にも関わらず，構造をうまく利用することで効率的な数値計算法や多くの理論的結果が得られている．
M／G／1型マルコフ連鎖では，あるレベルから1つ下のレベルに初めて到達したときの相の推移を表す

8A（z）＝∑≡。ZれAれ，β（z）＝∑≡。Zれβれ・
9通常，マルコフ連鎖の状態数は無限大であるが，有限のところで打ち切ってもある精度で計算することができる
かしモデルが複雑になると，精度を保つのに必要な状態数が増大してしまう．

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

1998年11月号（33）621．しを満たす。つまりi㍑）の定常状態確率は，あたかの形で公刊しただけで雑誌には投稿せず，【22】で引用も‡㍑‡が推移確率行列唾をもつマルコフ連鎖であしただけであった。このことがネーミングを含め後々

るかのように考えて求めることができる廿 この（㍑）までいろいろ波紋を投げかける原因となった，きちんを（（∬m｝の分割‡軌7…，ぶm）に対する）agg陀gaもedと雑誌に発表しておくべきであったと反省している。

chaimと呼ぶ。

このÅ／m法にはいくつかのバリニに∴山一ションが考案

式（Ⅲ）の条件付き確率分布動二織元），脚＝1，2，

されている［均一Schwei七zer［咽では，数学的基礎…，m，が求まってしまえば，（12）を解いてαをそしの解説と反復が必ず停止するための変更（厨仰が幾何て郡を簡単に計算することができる小 間題は，如何的に収束することを利用する）がなされている．See一にして動を求めるか，ということである⊂

息em［咽は勘働法が効率的なのはAg騨ega七五omフェ一山

特殊な問題では9 この軋がうまく定まり9比較的ズであると主張してサ Åggrega七ionと加速法を利用し簡単に定常状態確率が求められる［23，叫虚しかし9一て実際に多数の待ち行列モデルを数値解析している．

般にはそう簡単には行かないα

またS㍑m血＆隠ei舶rs［16］は，Disaggregaもiomフェー

ズの計算を改良する方法を提案している小 これはマル5。認 ∝⑬Ⅶ訂能の畳sめ討ⅢM

コフ連鎖に特定の構造がみられないときにはかなり

CoⅥr七Ois［3］は，このような分割の結果，Qの非対有効である付 この方法に関する研究はまだ進行中で，角項が対角項に比べて無視できるほど小さくなる場

軋995年に米国のNo止h C鋸01imaで行われた国際会議

合（ⅣDM，mea損y decomposab且e Maどkov血a通）につでも9超並列計算機を利用する場合の方法論［叫ないて考察した山 このとき軋は，対応する靡の対角

ど，数編の論文が発表されている小ブロックを推移確率行列と見なして，その定常分布から近似することができる。

筆者らの経験によると，このA／D法で解けるマル
コフ連鎖の大きさ（状態数）は主としてメモリのサイ5。認 Ågg訂ega庖五￠m／D畳sagg訂ega奄温⑬m法

ズに制約され，通常のワークステーションなどを用いたときは状態数10万程度，超並列計算機などでは，計動を求めるのに別のag酢egatedchaimを利用するのが，Åggreg血0可Ⅲisaggregaもiom法（A／Ⅲ法）である□ ここでは，各〝に対して，β〃の外の状態すべて
をひとつの状態‡0〝‡にまとめたぶ〝∪（0〃）を状態空

算機にもよるが℡1000万程度が限度のように思える。
−・ ●・：・ノミ：、ミ∴・二さ．：・二‥、：∴：王Åggregation法の原理を使って待ち行列ネットワー

間とするaggregate（且c払aimを考えるc このとき重みとクを近似解析しよう，という試みも筆者の近辺で行わして使う条件付き確率は，他の軋，〝≠絢とαかれているDこのcrossaggregatiom法には近似の精度に

ら求められる。この喝即egated c宜1aimの定常状態確応じていくつかのレベルがあるが，そのうちレベル2率からβ担が簡単に計算できる。この手続きをdisag−と呼ばれているものの原理は次のようである［2叶

gre紳iomという。αフ‡動，揮＝且，…）m）を変数としネットワー■血 クの中で隣接するノードペアの集合をて9 ひとつのaggregaもiomフェーズとm個のdisag一

Ⅳ2＝ま（ゐ，九））とする一 ペア（ゐ，ゐ）∈ノ鞄に対して，

節e卵七宜onフェーズを組み合わせた反復法を構成する

それらの状態だけを考慮し他のノードの状態を無視と，これらの変数が反復とともに真の値に収束していしてaggrega七edchainを作る・するとその定常状態確くことが期待されるく・これがÅ／D法の原理である血率ベクトル∬抽＝（鞘正症偏））は（12）と同様のag−

この方法を用いると，PH／PH／cなど広い範囲の待gregated eqⅦatiomを満たすが，そこにでてくる重み

ち行列モデルに対して比較的少ない計算量でその定係数β（彪，帰は3つの隣接した状態の同時定常状態確

常状態確率を計算することができる。とくに（1）の執 たとえば諾抽γ（豆ん，豆九，戌γ）のようなもの，を含んで形の推移確率（速度）行列をもつ場合に効果的である。

いる。これを

この反復法で，各変数ベクトルの値が収束すればそれが真の値に一致することは簡単に示せるが，この反復法自身の収束性はまだ証明されていない。
この数値計算法は，筆者がmumpimg法という名で提案したものであるが9 元の論文は隠esea．rch隠eport
62望（34）

ミ．．・J− ∴，・．．＼こ‥諾抽（転偏）諾九γ（症ふ）
（13）
￡九（転）

などのように近似すると，職に含まれるノードペア
における定常状態確率のみを変数とする反復法を構成することができる。

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

オペレーションズ。リサーチこのcrossaggregation法によってどの程度の近似精度が得られるかについて，最近，筆者のところの大学［12】Ne−1tS，M・F■（1981）〟α什血−Geomefr盲c5■og祝f宜0れぶ慮れ∫わc九αβ亡豆c〟0（geJβご AれAgタ0γ抽m盲c ApproαC九，JollnS

院生がかなりきちんとした数値実験を行った［25，26】・［13】Ne11tS，M・F・（1989）∫血cね陀d∫わc九αβ王宮c〟αfr盲ceβ扉

HopkinsUniversityPress，Baltimore．

・／H2／2／4というようなノードが50個ほどいろいろ〟／G／1Tbeand77｝eirApplications，Marce且Dekker，な形に繋がった非循環型の（循環するルートがない）

New York．

［14】Schweitzer，J・P・（1984） Aggregation methodsfor
large Markovchains， inIazeolla，G・，Cour七ois，P・J・
andHordijk，A．（eds．）MathematicalComputerPer−
hrmanceandReliability，NortIl−Holland，Amsterdam，

ネットワークで試したところ，スループットは，通常，

誤差1％以下，特に悪いものでも数％の誤差で近似することができた．誤差の生じる主たる原因はボトル

275¶286．

ネックノードが川上に向かって及ぼす影響で，この影【15］Schweitzer，J・P．（1991） A survey of aggregation〜
disaggregationinlarge Markov chains， in Stewart，

響が大きいネットワークでは誤差も大きくなる傾向に

W・J．（ed．）Ⅳ祝mer壱cαJgog餌f五州毎〟αrたou仇α盲那，Mar−ある．

CelDekker，NewYork，Amsterdam，63−88・

この方法はかなりの潜在的可能性を持っていると筆［16］Seelen，L・P・（1986） An algorithm for Ph／Ph／c

者は考えている．もう少し研究を続ければ，実用的な

qlleueS， β視γ0・J・Op乃乱Reβ・，23，118−127・【17］Sengupta，B・（1989） Markovprocesseswhosesteadystatedistrib11tionismatrix−eXpOnentialwithanappli−
CationtotheGI／PH／1q11eue， Adv・Appl・Prob・，21，

近似法として広く利用可能となると思われる．
参考文献［1】Asumussen，S・andKoole，G・（1993） Markedponit
processesasalimitofMarkovianarrivalstreams，

J・

Appg・Proみ・，30，365−372・［2】Asumussen，S・and Ramaswami，V・（1990） Proba−bilistic interpretation of some duality results for thematrixparadigmsinqueuelngtheory， Stoch・Models，
6，715【733・［31Courtois，P・J・（1977）βecompoβαむ豆g和ご Q視e祝eβαれdCompuiersystemApplications，AcademicPress，New

159−180．

【18】S−1mita，U，andRieders，M■（1990） Applicationofthe

replacement process approach hr computing the er−
godicprobabilityvectoroflargescalerow−COntinuous
Markov chains， J．qpれβ．月eβ．∫oc・J叩αm，33，279−
307．

［19］TakahasIli，Y・，Machihara，F・and Takahashi，Y・（1996）

Correlateq input queues arising out ofhighspeedcommunicationnetworks，Proceedin9S qf

貯0月∫Jタ9∂，TDll．1．

York．

［4】Latouche，G・（1993） AlgorithmsforinfiniteMarkov
Chains with repeating columns，in Meyer，C・D・［20］Takahashi，Y・（1989） Aggregate approximationfor

acyclic queueing networks with communication block‑and Plemmons，R．J．（eds．），LinearA19ebra，Markoving， inPerros，H・G・andAltiok，T・（eds−）Queuein9
Networks with Blockin9，North−Holland，Amsterdam，Cnains and Queuein9Models，Springer Verlag，New
33−46．

York，231−265．

［5】Lato11Che，G・andRamaswami，V・（1993） Alogarith−
mic red11Ction algorithmfor quasトbirth−and−death
PrOCeSSeS，

J．Appl．Prob．，30，650q674．

［6］LucantOni，D・M・，Meier−Hellstern，K・S・and Neuts，M．F・（1990） Asingle−SerVerqueueWithservervaca−［21】Takahashi，Y■and Ftdimoto，K・（1995） Aggrega−tion／disaggregationonaparallelcomp11ter， inW・J・
Stewart（ed．）Computalions wiih Markov 仇ains，
Kluwer，Boston，591−593．

［22］Takahashi，Y・and Takami，Y・（1976） A n11mericalmethodforthesteady−StateprObabilitiesofaGI／G／c
tions andnon−reneWalarrivalprocesses， Adv．Appl．
queuelngSySteminageneralclass， J．Opns・Res．Soc・P欠沌．，26，676−705．
［7］Lucantoni，D・M．（1991） New results on the single
J叩αm，19，147−157．
［23］Tanaka，A・andKino，Ⅰ・（1998） LumpabilityinLRU
ServerqueueWithabatchMarkovianarrivalprocess，∫わc／も．凡才odegβ，7，ト46．
StaCkwithMarkovianpagereferences， J．Opns．Res・［8］Machihara，F・（1988） Completiontimeofserviceunit
goc・J叩αm，41，9ト117．
interruPted by PH7eneWalcustomers andits appli−［24】Yamashita，H，Ohtani，H．andSuzuki，S・（1998） An
Cations， Proceed慮れタβOJJg兢加古er乃αf豆omαg7七gef叫伊cexact aggregation fbrinventory distribution▼in an
Con9reSS，North−Ho11and，Amsterdam，1508−1514．

【9］Maier，R．S・andO Cinneide，C．A．（1992） Aclosure
Characterizationofphase−typedistrib11tions，

J．Appl．

J叩αれ，41（toappeaけ［25］梅原元（19粥） 大規模待ち行列ネットワークに対するCrossAggregationMethodの近似精度の検証， 修士

P叩あ・，29，92−103．

【10］Neuts，M．F・（1975） Probabilitydistributionsofphase
type，

automatic warehousing system， J・Opns・Res・Soc・

in LiberAmicorumPrqF Emeritus H．Florin，

論文、東京工業大学数理■計算科学専攻．

［26】平井力（1996） SomePropertiesoftheCrossAggre−

Department of Mathematics，University ofLouvain，

gation methodfor Approximately Analyzlng Acyclic

Belgium，173−206．

QuelleingNetworks， 修士論文，東京工業大学数理・計算科学専攻．

［11】Ne11tS，M・F・（1979） AversatileMarkovianpointpro−
CeSS， J．Appg．Pγ0ゐ，16，764−779．

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

（35）623