………………川…ll州州……川…l川州……州l川州…州…川……州州…………川州…川＝‖‖‖＝‖‖‖‖‖‖＝‖‖‖‖‖＝‖‖‖‖‖‖‖‖‖‖‖＝‖‖‖‖‖‖＝‖‖‖＝‖‖‖‖‖‖‖‖‖＝‖‖‖‖‖‖‖‖‖＝‖‖‖‖‖＝州●二∴．・‥、・十〕∴、〜∴ 一・． −・∴中iキ干二埠

宮沢 政清…………………lllill…………………………………………………………lll……l…‖‖‖＝‖‖＝‖‖＝‖‖‖‖＝‖‖＝‖‖‖‖＝‖‖＝＝‖‖‖＝‖‖＝＝‖‖‖‖‖‖＝‖‖‖‖‖‖＝‖‖‖＝‖‖＝＝‖‖＝‖‖＝‖‖‖‖‖‖＝‖‖‖‖‖‖‖＝‖‖‖‖‖‖＝‖＝‖＝＝‖‖＝州……l式ネットワークの新しい展開を見ることができた。こ盈。今なぜ横形或なのかのホットな話題を紹介したい。

待ち街列ネットワークに多少とも関心を持ったことのある読者は，本稿の表題に疑問をもたれる方も多いと思う。後に詳しく述べるが，横形式（product form）−・ニて■′・ミ∵‥1：や：−ニ1二． ∴・：−でござニ・一二J、∵・・
初めに，待ち行列ネットワークの概要と研究目的にとは結合分布が周辺分布の積となることである，またついて簡・単に説明する◎ 待ち行列ネットワークとは，そのような定常分布を持つ待ち行列ネットワークを横複数のサ叫ビスシステムをネットワークとして結合し形式ネッ距ワ榊夕と呼ぶ。Jacksonが横形式ネットワたシステムのことである。客は結合している経路に従ークの論文を発表したのが1957年，ニれを拡張し現在い，場合によっては，確率的に経路を選択し，順次サ標準モデルとしてよく使われるBCMP（Ba軸ett etーーービスを受ける。客がサービスを受ける個々のシステ

al。［且］の略）やKe盟旦yによる積形式ネットワークの発ムをノ脚絆と呼ぶ申 例えば，ノードを直列につないだ表が1970年代である。横形式はネットワークの解析を場合には，直列型といい，外部から到着した客は9 到

単一のシステムのレベルまで簡略化するため応用上使着したノ」ドから順次サービスを受け退去する合 一般いやすく，近似計算などにも広く利用されてきた。しに，外部から客が到着する待ち行列ネットワークを開かし9 且980年代以降，理論的発展は止まってしまった放型と呼ぶ。また，外部からの到着がなく一定の人数かの様に見える8 私自身も6，7年前までは横形式ネの客が常にいるモデルを閉鎖型と呼ぶ

ットワークに新しい展開があるとは考えてもいなかっこのような待ち行列ネットワークは，計算機システた㊤ むしろもっと別の方向である離散時間型ネットワ

ム，通信ネットワーク，生産システムなどの設計や運ーク（後述する）に興味を持っていた。

用のための性能評価モデルとして広く使われてきた。

そもそも9 私はネットワークの専門家ではなかった

あらゆるものがネットワーク化されつつある今日では，

し9 後述する準可逆悼（quasiTTeVerSibility）が初め

待ち行列ネットワークの寺替在的需要も大きい◎ 通常，よく理解できなかった．，しかし，少しずつ慣れ親しんこれらのモデルの解析や分析はシミュレーションによでくると，BCMPやKellyのモデル化は細かな仕様ることが多いが，モデルの一般的特性を調べるためににこだわりすぎて9 全体を見ていないことに疑問を感は理論的なモデルの解析が重要である。理論的研究のじてきた。たぶん「単一の待ち行列モデルでも解析的課題として以下のものが挙げられる。に解けるモデルは限られているので9 一般的なネットワークモデルを考えることは無理である」という認識が強かったのであろう。でも初めから問題を小さくする必要はないのではないか？ 例えば，なぜ積形式を持つかを検討するためには，横形式を持たないモデルを含む】般的なネットワークを考える必要がある血 こんな気持ちから始まった研究だが，たまたま，新しいタイプの横形式ネットワークの出現とぶつかり9 横形⑳システムを長時間稼働したときの安定性，特に定常分布の存在条件や定常状態への収束の速さ。
⑳魅力ある解析可能なモデルを見つけ，定常分布等の解析手法や数値計算法を与える。
⑳システムの最適な制御方法。

積形式ネットワー¶クの研究は2番目の定常分布の解析法の1つであるQ ネットワークのように複雑なシス

みやざわ まさきよ 東京理科大学理工学部情報科学科

テムでは9 応用上魅力あるモデルを見つけることは特〒278 0022千葉県野田市山崎2641に重要である印 なお，本稿では，流体などの近似モデ

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

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

ルは考えず，直接的なモデルを対象とする．

方（乃）＝れ（乃1）×穐（乃2）×…×恥（乃Ⅳ）

先に触れたが，待ち行列ネットワークの難しさは，であり，各ノードの待ち人数は互いに独立である．

ネットワークを構成する単一システムでも限られた場

このように，結合分布が周辺分布の積となるとき，合にしか理論的解析ができないことにある．解析が簡積形式と呼ぶ．横形式は，待ち行列ネットワークの解単な例に，客の到着がポアソン過程に従い，サービス析がノードごとの解析に置き換えられることを意味し時間が互いに独立で同一の指数分布に従う場合がある．ており，定常分布を求めるうえで問題が格段に易しくこれを堀舶一型モデルと呼ぶ．この型の待ち行列には，なる．特に，Jacksonネットワークでは，各ノードの単一窓口の腑舶／1や複数窓口の畑などがある．こ待ち人数分布は，そのノードへ仮想的に平均到着率がれらのモデルの拡張が試みられてきたが，到着間隔の一致するポアソン到着を仮定したときの定常分布に等分布またはサービス時間の分布の一方を一般の分布としい．したがって，ネットワーク状態の定常分布は平する場合を除いて定常分布を解析的に求めることは困

均到着率を求める問題と閲舶一型入力を持つ待ち行列難である．ただし，数値計算的な面からは，Neutsの定常分布を求める問題に帰着する．ノードノへの平［17］による行列幾何表現があり，広い範囲の分布に対均到着率をのとすると，勒は平均退去率に等しく，トして，アルゴリズム的な解析が可能である．ただし，ラヒック方程式（traffic equation）

これも待ち行列が1つである場合にしか通用できない．
したがって，一般的なネットワークモデルの解析に」Ⅴ勒＝ん十∑αゐγ妨ノ＝1，2，…，♪J

（1）

ゑ＝1

は多くを望めないと考えるのが自然である。しかし，が成り立つ．ここに，んは外部からノードノへの客のシステムが複雑になったことから，単一システムとは到着率である．（1）を解くことにより勒が求められる．

別の角度からの研究が進められつつある．これは横形

また，〃舶一型入力モデルはすでに解かれているので，式などの定常分布の解析だけではない．例えば，本稿ネットワーク状態の定常分布が解析的に求められる．

では論じないが，客の到着やシステムの変化を流体でJacksonネットワークは外部からの到着がない閉鎖型近似する流体近似モデルを利用して，システムの安定に対しても横形式の定常分布を持つ。この場合には，性に対する必要十分条件を調べる研究が大きく注目さ系内人数は一定であるため，ノードの待ち人数の独立れている（［6］等参照）．

性は成り立たない．また，定常分布を定めるためには3．横形式と線形トラヒックモデル正規化定数の計算が必要である．
Jacksonネットワークは，定常分布が簡単であるこ

待ち行列ネットワークの定常分布の解析は，初めにとから，広く応用され，理論的にも，横形式を導く手述べたように，Jackson［12］による研究が端緒となっ法を中心に多くの研究の対象とされてきた．しかし，た．彼は，開放型ネットワークにおいて，外部から客が各ノードにポアソン到着し，単一または複数の窓口で指数分布サービスを受け，サービス完了後は次のノ●経路をあらかじめ決めて選ぶことができない．
●サービス時間の分布が指数分布に限られている．

ードを確率的に選択し，最終的には退去すると仮定した．この経路選択の確率はネットワークの状態とは独などモデルの制約が強く，柔軟性に欠けている．これ立であるとし，ノードノから退去しノード々へ到着すらの点に関して，1970年代に2つの重要な拡張がなさるときれ烏と表す．これらの確率を行列のように並べれた。1つは，客をクラス（タイプともいう）に分けた（7Tjh）を経路選択行列（routingmatrix）と呼ぶ．こて，クラスごとに異なる経路選択やサービス時間分布のモデルは，今日，Jacksonネットワーク と呼ばれを設定することである．もう1つは，客やクラスごとている．N個のノードを持つJacksonネットワークのサービス時間を一般分布に従うとしたことである．

では，ノードノでの待ち人数乃ノを要素とするベクトル

これらの仮定の下でも，サービスの方法が対称型であ乃＝（乃1，乃2，…，乃〃）る場合には横形式が成り立つ．ここに，対称型サービをネットワークの状態に取ると，連続時間型のマルコス（symmetric service）というのは，それぞれの客フ連鎖（状態が可算個のマルコフ過程）となる．このに番号が付いた場所（これを位置と呼ぶ）が割り当て

マルコフ連鎖の定常分布方はノードごとの定常分布屯られ，各位置へ到着がある確率とそこで客が受けていの積となる．すなわち，るサービスの割合が比例することをいう．例えば，後1998年8月号© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

（27）443

着順割り込みサービスでは，最後に到着した客がいつγ（α）＝写γ（α′）γ（α′，α），∀α

もサービスを受けるが9 これは9 いつもユ人だけサーαビスを受け，到着客はサービスを受けている客の位置が解γを持ち，ネットワーク状態庚＝（乃1，…，鋸）の下でに割り込んで自分がサービスを受ける対称型サービスαの過去が発生する条件付き確率〆がとして記述できる。この場ノ釧こも，ノ山ドごとの分布

酢（蹄−α＋）〆（α一花）＝

は，仮想的にポアソン到着を仮定したモデルを解くこ

γ（α），α≦脂・−、ごごJ．1

これらの結果は，ほぼ同じころに，BCMP［1］と任意の非負債関数であり，その選択により各種のサーKe且呈y［H］により独立に得られた。ことに，Keユユyはビス方法を表すことができる。一方，￠ほ〆（αl凋）のα横形式を証明するために時間を逆転させた逆時間過程についての和が且になることから定まる関数である。

や局所平衡（localbalamce）を積極的に利用した。

このとき，過去直前の状態の定常分布方はまた，後述する準可逆性と呼ばれる特性が積形式のた方（開）＝屈憾（銅），（慮は正規化定数）めの十分条件となることを示した自 今日では9 このにより与えられる。この結果も横形式解と呼ぶ文献もBCMPとKe凰1yによるモデルは標準的なネットワーありややこしいが，本稿ではその立場を取らない。

クモデルとして広く償われている。なお，これらのネ

これまでに述べてきたモデルのトラヒック方程式

ットワークでは，サー∴ビス時間分布を一般化したとき，（（ユ）や（2））はすべて線形である（理論的には局所平人数ベクトルの定常確率がサービス時間分布の平均の衡と同値）。これは9 到着と退去の率（集団移動型のみで定まる申 これを定常分布の不変性（insensitivity）

時は集団の大きさの分布）が等しいことを意味し，集という（［7］など参照）。

団移動型の1つである回線保留型の呼損ネットワーク

1980年代になると別の角度からの待ち行列ネットワ（circuit switchingioss metwork）のようによく当ークの研究がなされるようになったひ 動機は，計算機てはまる例もあるが，一般にモデル化の制約となってやデジタル方式の通信への応用である。これらのシスいる。

テムでは9 時間をスロットに分けた離散時間型のモデ

4◎ 亀の客とシダテルルが重要である8 離散時間型のモデルでは，異なるノードで同時に変化が起こる。また，同一のノードでも，1991年Gelenbe［8］は，一風変わったネットワーーク退去や到着が集団で同時に起こりうる。このようなモの研究を発表した巾 このモデルは基本的には各ノード

デルは9Jacksom，BCMP，Kellyなどによる連続時が窓口lつのJacksonネットワークであるが，通常間モテナルでは表すことができない。の経路選択の他に，ノードノを退去した客が確率γ義で離散時間モデルについては，Ⅵ7alrand［21］が初め同時に別のノード点の客を退去させる曲 この変化は，て一般的なネットワ、・叫クに関する結果を得た￠ 5∵型

確率γ義でノードノから飢こ来た客が到着ノードの客を待ち行列と呼ばれる連続時間での準可逆性に相当する減らすとみなすこともできる。Gelenbeは，このよう特徴を持つノ山ドをマルコフ型の経路選択行列で結合な客を亀の客（megative customer）と呼んだ。ただすると，ポアソン分布に従う互いに独立な集団到着がし，ノード削こ客がいないときにはノード引こ変化はあったときに9 ネットワークの人数ベクトルの定常分ない。このモデルの定常分布は，やはり横形式を持つ。

布が横形式となることを示した。ただし，集団退去ししかし，これまでのモデルと異なるのは9 ノードノのた客は個別に経路を選ぶとする。この結果は9 大沢

サービス率を鮎 そこへの外部からの負の客の到着率［18］により到着人数分布の一般化が検討されたが，こを打とすると9 非線形なトラヒッ夕方程式

れとは独立に，Henderson＆Taybr［10］はより山の＝ん十鼻話般化し9 ベクトルα＝（恥恥…，伽）で表される各ノー

α々γ如

打＝頼仇γ㌫

ドからの退去がα′＝（α昌，α呈タ…タαわで表される到着に確率γ（α，α′）で変わるとしたQ ここに，0は外部を表し9α。とα昌は，それぞれ9 ネットワークへの過去および到着人数を表している。彼らは，この経路選択に対する均鯛（28）（3）で与えられるとした。ここに，α＋＝（恥…，伽），許はとにより求められる☆

トラヒック方程式（2）を持つことである。この方程式で，α烏の前につく石は9総過去の中での客の過去の割合を表している（釘＝0のとき（り）に一致することに注意）。
© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

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

Brouwerの不動点定理からこの方程式が解を持つこという機能を持つ部品であるとする．ノードノ（部品）とが証明できる．また，求めたのを平均到着率にもつの状態がエから∬′へ変わるとする．この推移を，（a）

ポアソン過程に従う客の到着をノードノへの到着とみの変化では条件付き確率ガ（エ，J′），（b）の変化では，なしてノードノの周辺分布を決めることができる．こ率すプ（∬，∬′），（c）の変化では，率仔ヂ（ズ，J′）で表す．これは瑚1待ち行列であるから，定常分布屯は，の＜の記述はノードをネットワークから切り離したときの拘の時にのみ存在し，次式により与えられる．

もので，到着過程については何も規定しない。各ノー

屯（乃ノ）＝（ト若）（苦）乃ブ，乃ノ＝0，1，…

ドへの到着はすべてのノードをネットワークへ戻した

この結果は，［5，9，19］などにより，負の客が集団退去を引き起こしたり，負の客が連鎖的に異なるノードの退去を引き起こすモデルへ拡張された．ただし，ときに他のノードからの退去より生成される。なお，
このモデルでは外部もノードとみなし，ノード0と表す．したがって，ネットワークの状態はベクトル∬＝（勃，∬1，．．．，ヱⅣ）

客のいないノードに到着したときにはそれ以降の動作である．このモデル化の重要な点は，到着や退去といは取りやめとなる．一般に，このように連鎖的にノーう用語を使っているが，それらによって引き起こされドに到着し変化を引き起こす・客のことをシグナルる状態変化に制限がないことである．これから，たと（signal）と呼ぶ．シグナルは，えば，負の客を取り込むことが可能となる．また，外部も状態を持つので，位相型到着などポアソン以外の●集団退去や複数のノードからの同時退去，到着過程も記述できる．

このネットワークからノードノ を切り離し，率のの●集団到着や複数のノードへの同時到着，ポアソン過程で到着を入力として加えたとき，状態のやそれらの組み合わせなどを表すことができる．ただ定常分布和が存在したとする．準可逆性とは，このとし，到着に関してはモデルの変更が必要となる（9節

きの過去過程が退去直後の状態と独立なポアソン過程で述べる）．なお，シグナルの通過はすべて到着と過となることであり，条件去に数えトラヒッタ方程式に反映される，しかし，シグナルの通過はその都度，到着又は退去のいずれか一方の効果しかないので，トラヒック方程式は一般に非∑笹（∬′）すヂ（∬′，∬）＝＆屯（∬），∀∬ エ′（5）により表すことができる．この式とトラヒック方程式線形となる．

．Ⅳ勒＝ん＋∑β烏γ姑 ∀ノ（6）烏＝15．準可逆性と横形式を満たす勒，＆が存在するならば，ネットワークの状

これまで負の客やシグナルをもつネットワークの定態の分布加ま笹の積となる．

常分布は，ほとんどが定常方程式を直接確かめること

この結果は客にクラスのある場合も拡張される．たにより求められてきた．そのような方法は，モデルのだし，カ品，￠見，り ，軌のα，鮎∠などのように，箱と扇を仮定が複雑になるにつれ，見通しが悪くなり，効率的除いて，ノがノ〟等に変わる．さらに，［3］では，シグナとはいえない．実は既に述べたが，Kelly［11］は準可ルがある場合へ準可逆性の定義を拡張し，横形式が得逆性が横形式のための十分条件であることを示した．

られている．

これは一般的な方法であるが，これまでは，線形なト準可逆性を持つネットワークを解析する際の1つのラヒック方程式を持つモデルに対してのみ適用されて大きな課題は，トラヒック方程式（6）を解くことであきた．Chao＆Miyazawa［2］では，ネットワークモる．一般に，＆は勒の非線形な関数であり，（6）は非デルの記述を抽象化するとともに，この方法を非線形線形方程式となる．これは不動点を求める問題でもあなトラヒッタ方程式の場合に通用した．このモデル化るが，（6）の右辺は必ずしも有界ではないので，不動においては，各ノードは点定理を使えない場合が多い．一般の場合の解の存在証明は今後の課題として残されている．

（a）到着に反応し状態を変える，（b）内部的な変化が起こり状態を変える，

6．準可逆性は必要条件か（c）退去を生成し状態を変える

準可逆性は横形式のための十分条件であるが，必要

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

（29）445

条件か？既知の横形式のネットワークはすべて準可逆ア◎ 横形式から状態依存型へ性を満たしている。例えば負の客やシグナルを持つネットワークなどについてこれを確かめることができる。

準可逆性は横形式の必要条件でないことはわかった

そこで，準可逆性は必要条件であるとの予想があり，が，準可逆性からは横形式以外の結果，たとえば，平部分的には確かめられてもいた（［13］）① しかし，

衡方程式を細分化した局所平衡方程式が導かれる。たTakada＆Miyazawa［20］（より一般的な結果は［4］だし，非線形トラヒックの場合には，通常の局所平衡にある）は，シグナルがない場合について，この予想は成立せず9 偏各メのある局所平衡（biasedloca呈bal−を否定する形で問題を以下のように解決した。

amce）となる￠ これを簡単に述べると，∑先。告＝0とネットワークの状態分布打が横形式（外部を表すノなる告があり9Jをネットワーク状態とするとき，ード0も含める）となるための必要かつ十分な条件は，（状態が∬でありノからの過去がある率）十告方（∬）

ある勘，＆があって9 方の周辺分布範が推移率＝（ノへの到着により状態が∬となる率）（8）

射（∬ノ，∬；）＝動力プ（∬J，∬；）＋材ヂ（み，∬ニ）＋￠プ（諾ノ，∬ニ）である。（8）と横形式から準可逆性が得られるが9 もを持つマルコフ連鎖の定常分布であり9（6）および次

っと重要なことは，過去率粛（み，∬ニ）をネットワークの式が成り立つことであるの全体の状態に依存するある形に変更できることである㊤
この変更は9 線形なトラヒックモデルに対しては既知（すヂ（五巨βJ）竹丘（靡芸（諾ゐ）Ⅶ1）＋（百g（∬ゐ）−βゐ）γ揖（卵（み）−1）＝0（7）ここに9】〆＝0．1，…に対して9であるが，Miyazawa＆Chao［15］は非線形トラヒックモデルに対しても同様な変更ができることを示した。

紬）＝羞浦鵡）諷需湖）

これを9 客を減らす負のシグナルがある準可逆性を持つネットワ山クについて説明する。簡単のために，

卵h）＝羞浦鵡）頭ム亮）

各ノードでサ山ビスを受ける客の種類は1つ，サービとする心 条件（7）は相殺平衡（counter balance）とス時間はすべて指数分布に従うとする。また9 シグナ

呼ばれ9 ある種のバランスを表している￠ すぐわかる

ノじは外部から到着し，経路選択確率に従って連続的にように，準可逆性（5）が成り立つならば，（7）が満たさ経路を選ぶが，空のノードに到着，または，外部に退れる。しかし，準可逆性が成立しないが（7）を満たす

去したときには停止するか 客をc，シグナルをsで表ネットワークがある，すなわち，準可逆性は必要条件

すと，到着9 過去9 シグナル通過の推移は，ではない。これらの結果は客にクラスがあるときに容蕗（裾，裾十1）＝且，易に拡張される￠J鴫（乃」−1，裾）＝1，カ品（0，0）＝1

先に述べたように，外部も1つのノードであり，例付点（卵，卵一1）＝拘1（乃≧1），えば，位相型の到着に対しても横形式かどうかの判定

ふ，ぶ（鋼ク視【1）＝1（現≧1）ができるQ 特に9 外部からの到着がポアソン過程に従と表せる。ここに，〃Jはノードノのサービス率であり，うときには，仔♂（∬。）＝β。が成り立つので，外部との経1（0）はぃ）が正しければ1，そうでなければ0であり，路があるノードとノード0のペアについては，条件んざ（乃，乃′）はシグナルの到着により状態が乃から乃′へ変（7）は自動的に満たされる。この場合には9 状態ベク化したとき，シグナルが転送きれる確率である。このトルからノード0の状態を除くことができる中ネットワー血クの定常分布方は幾何分布の積であり，そ条件（7）を使うと9 準可逆性が必要となる各種の条件を与えることができる。たとえば，外部からポアソのパラメーターは（6）と同様な非線形トラヒック方程式を解くことによって決められる。

ン到着があるモデルにおいて，ノードが空の状態を0

このネットワ山クの到着，退去の推移をネットワーとし9 0では内部推移は起こらない，0では過去はな

ク全体の状態用に依存する形で次のように変更する。

い9 到着後に0とならないとする。また，過去が外部卵≠柁′に対して9へのみ行くノードを端末ノードと呼ぶ。このとき，トラヒック方程式が線形ならば，非端末ノードはすべて準可逆である① これは［13］の結果に一致する。

屋島（殉，銅′）＝1（㈹′＝閃−1乳）カ笈（乃ノ，乃；）許（紺−eノ）す見（殉，銅′）＝1（悶′＝殉一密ノ）露（犯ノ，乃；）許（殉−eノ）町巨l；J＝∴）© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

穏砲6（30）オペレーションズ。リサーチここに，￠はノー番目の要素のみ1である単位ベクトル，

F（〈乃，α〉）
αd（αl乃）＝町（乃）は乃の任意の非負債非減少関数，￠は任意の正値

桝Jl）ヮ（乃，α）（12）関数である．なお，シグナルの到着効果を現すカ鳥も（iii）時間を逆転したときに同じ条件付き退去率を持変更されていることに注意されたい．（8）から，変更

つネットワークになる（経路選択行列γは一般されたネットワークの定常分布寿がに異なる）．

斤（乃）＝茸￠（乃）方（乃）（∬は正規化定数）（9）

また，これらのいずれかが成り立つならば，ネットとなることを証明できる．この結果は内部推移がある
場合，客にクラスがある場合，客の数を増やす正のシ

ワークの状態の定常分布方はグナルがある場合などに拡張できる．

方（乃）＝∬￠（〝）（∬は正規化定数）（13）により与えられる．

8．状態に依存する経路選択

この結果は3節で述べた［10］の結果を含むとともに，複数のノードからの同時退去と経路選択ががネット

状態依存型の経路選択モデルなどに広く応用できる．

ワーク全体の状態に依存する一般的なネットワークをただし，応用に際しては，モデルにうまく適合する町考えてみよう．このモデルは，［10］のモデルをさらにと￠を見つけることが必要である（［14］に例がある）．

一般化したものであり，解析は困難である．しかし，

9．エピローグ

モデルの抽象化により準可逆性が再検討されたように，そのような一般化により，解析可能なモデルの範囲を

前節の結果は，状態に対応するミクロレベルにトラ明確にすることができる．

ヒッタを分けたときにトラヒッタ方程式が線形になる［10］と同様な集団移動を考えるが，時間は連続とすならば，モデルの解析が可能であることを示している．

る．ネットワーク状態が〝のときαが退去したという

しかし，この線形性の制約は強く，到着と過去に対す条件の下で，α′が到着して状態が〝′に変わる確率をる対称性が必要である．これに対し，横形式ネットワγ（（〝，α），（〝′，α′））とする．なお，αとα′の絶入数は等しークの線形トラヒック条件はマクロレベルであり，必く，状態変化はずしも強い条件ではないが，集団退去や複数のノード〝′＝〝−α＋十（α′）十（10）である．γの中に乃′は必要ないが，対称性を保つためでの同時変化がある時には，トラヒック方程式が非線形となってしまう．に入れておく．定常状態が存在すると仮定し，ネット

この非線形性のもたらす複雑さは，集団移動型の線ワーク状態が乃のとき，ベクトルαで表される集団の形トラヒック条件をゆるめ，到着と過去の対称性を取平均到着率をγ（乃，α），ベクトルαで表される集団の平り除くための代償といえる．ただし，同時到着に関し均退去率をγ＊（乃，α）とすると，トラヒック方程式ては，準可逆性を保持するためにノードが空の時に余分な到着を追加する必要がある．したがって，横形式

γ（乃，α）＝写′γ＊（〃′，α′）γ（（〃′，α′），（乃，α））（11）〝，αを持つのは元のモデルの上限を与えるモデルである．

が成り立つ．特に，γ＝＝γ＊ならば線形である．退去とこのようなモデルは［3，16，22］で論じられている．

到着の紙数が等しいことと（10）から，γを推移確率とこの上限がどの程度よいかなど今後検討すべき課題はするマルコフ連鎖の状態空間は有限個の状態からなる多い．また，横形式ネットワークがカバーする範囲が規約な集合（γの推移で移ることができる状態の集ま広がったので，実際の問題への応用も期待される．

り）に分割することができる．この集合を代表する元

このように横形式については研究課題が多く残されを〈乃，α〉と表す．有限マルコフ連鎖に関する結果より，ているが，その限界もまた事実である．例えば，流体γの定常分布が常に存在する．1つではないので，適のネットワークでは，各ノードでの蓄積量が独立にな当に1つ選び甲と表す。

ることは考えがたい．したがって，相関の入った次の以上の仮定の下で，次の条件は同値である（［14］）．

標準分布形が望まれる．残念ながらこの方向の研究は（i）線形なトラヒック方程式を持つ．

あまり成功していない．式（9）はその1つの可能性であるが，特殊な状況である．現状では，次の標準型を（ii）ある非負債関数町と正値関数￠があって，条件付き退去率すdが次の式で表される．
1998年8 月号

探すよりは，分布の裾の減少率などの漸近的な量に注目する，時間軸や状態空間をスケール変換し確率過程© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

（31）447

としての漸近的振る舞いを調べる（極限は流体近似やarrivals and batch services，Queueing Systems6，拡散近似になる）など，漸近的または近似的なアプロ

71−88．

ーチの方が可能性が高い㌔ ただし，これらの方法も多［u］F。P椚Kelly（1979）厨♂〃e和才∂才物α乃♂SわcゐαSオブc
JVgg紺0祓s，Wiley．

次元になると克服すべき課題が多い￠

最後に，ネットワークについての共同研究でお散話になった方々と，本稿について貴重なコメントをいた
だいた東北大学の山下英明氏に心から感謝したい。

［12］J。R．．Iacksom（1957）Networks of waiting
limes，Opms，Res叶 5，518−−521．

［13］Y＼Ⅴ■H Malimkovsky（1990）A criterion for
POimtwiseimdependence of states of unitsin am
OPen Stationary Markov queueing network with

参考文献

One Class ofcustomers，Theory of Pro虹 Appi．
［1］F．Baskett，K。M。Chamdy，R．R。Mumtz amd35，797一802．
F．G申 Palacios（1975）Open，Closed and mixed
metworks of queues with different classes of cus−
tomers，J．ACM22，2舶−260。

［2］Ⅹ．Chao amd M。Miyazawa（1996a）On quasiu
reversibility amdlocaibalance：Am alternative der一主vatiom of the product−form results，tO appearin
Opns山 Res。

［14］M．Miyazawa（1997）StructureMreVerSibilityand

departurefunctionsofqueueingnetworkswithbatch
movememts and state dependent routimg，Queueing
Systems25，45−75凸［15］M申MiyazawaamdX．Chao（1998）Generatinga
queueing metworkwith signals amd state dependent
localtramsitions from a quas卜reversible network，［3］Ⅹ巾 Chao and M。Miyazawa（1996b）Queueingpreprimt。

networks withinstantaneous movements；a cou−

［16］M．MiyazawaandP．G．Taylor（1997）Ageomet−

pling approach by quas亘一reVerSibility，preprimt。

ricproduct−formdistributionforaqueueingnetwork［4］Ⅹ。Chao，M。Miyazawa，R．Serfozo and H．

Withnonstandardbatch arrivalsandbatchtransfers，Takada（1998）Markov network processes withAdv−Appl。Prob。29，523−5掴，

product form statiomary distributions，tO aPpearin
Queueing Systems。
［5］ⅩJChao and M．Pimedo（1993）On generalized
netwo『ks of queues with positive and negativearrivais，PEIS7，301334．

［㍑］M。『爪 N飢ItS（1981）肋わ嘉一Ggo∽gf露c50g紺如犯S∴Jヾ／川九J∫／／■（∴1∫F川／〔1／∫∴一1ノブ．−1な（げ〃ん川／（∴−り）／り川J（九′r！1ビJohms班opkinsUmiversity Press。

［略＝軋8sawa（1994）Quasi¶reVerSibilityofadiscrete
time queue amd related models，Queueing Systems［6］J，G。Dai（1995）On positive Harris recurrence

Of multiclass queueing networks：a unified
approach via fluidlimit modeis，Ann。Appi．

18，133¶148，［19］R．F．Serfozo amd B。■Vang（1996），Markovmetwork pI−ocesseswithstringtransitions，Preprint．

Prob。5，4977。

［20］H．T北adaandMv Miyazawa（1997），Necessary［7］Pu Franken，D．K6mig，U．ArndtandV．Schmidt and sufficiemt conditions for product−form queueing
・：：、、 ′ ．．・∴ ●．・∴・∵∴・‥・．、、． ＼＼‥、、

networ］ks，Preprimt．

［8］E。Geienbe（1991）ProductfoTm queueimg net−

［21］れWairand（1983）Adiscrete¶timequeueingnetp

WOrkswithnegativeandpositivecustomers，J。Appl。

WOrk，∬．Appl．Prob．20，903−909。

Proわ。28，656−663。

［22］軋 Yamashita and M＼二Miyazawa（1998），［9］E．Gelenbe（1993）G山netWOrkswith signals andbatch㌻emOVal，PEIS7，335−342．

［10］Ⅵr。Henderson and P。G．Taylor（1990）Prod−

Geomet−ric Product Form Queueing Networkswith
ConMCurrentBatchMovements，tOappearinAdv．Ap−pl。Pro虹uct formin networks of queues with batch© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.
趨穏＄（32）

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