ポーリングモデル：巡回サービス多重待ち行列高木 英明…………‖川m＝……llll…川川m＝l州川川＝………………………………………………………＝l…………………………………l…l川l……………llll…………l…lll……………ll…………………lllll…ll………lllll…

1． はじめにメッセージ用バッファが客の待ち行列に対応する．これはポーリングモデル（polling model）とは複数の待ち行
列を1つのサーバが巡回してサービスするシステムのことである．類似め巡回的サービスである同期時分割多重方式（synchronoustimedivisionmultiplexing：STDM）
では各待ち行列でのサーバの滞在時間が客の有無にかかわらず一定であるのに対して，ポーリングモデルでは各待ち行列にサーバが来るときにそこにいる客数等に応じて動的にサービス期間が決められるのが特徴である．また通常の固定優先順位をもつ待ち行列システムと比べると，
ポーリングモデルは優先順位がサーバの位置とともに巡1970年代始め頃のポーリングモデルの応用であるが，いろいろ文献を調べると，データ通信以外の分野においても同様の待ち行列モデルが研究されていることがわかった．

現在の観点から整理すると，既に1950年代には単一
バッファモデルが

綿織物工場の巡回機械修理工の問題に使われた【44】．1960年代には，道路の交差点における交通信号制御のモデルとして【53】，またオペレーションズ

リ●

サーチの問題として【4］，2つの待ち行列から成る無限バッ
ファモデルが解析された．1960年代の終りには，データ通信の実用化とともに，全処理式とゲート式サービスシス
テムが研究された【22，23，26，32，331．1970年代には回するシステムであるといえる（図1参照）．

上述のようにポーリング方式のデータ通信の理論的モデ

ルとしてよく用いられたが，1980年代になると，ローカル
エリアネットワーク（LAN）におけるトークンリング方式のモデルとして再び脚光を浴び【16，17】，とくにその方式に合った制限式サービスモデルが解析された【29，56，66】．

さらに，トークンバスやFiber Distributed DataInter＿hce（FDDI）のモデル化では，優先順位付き時間制限式

サービスが研究された．最近のLANの標準IEEE802．12
100VG−AnyLAN（DemandPriprity）の方式も優先順位

付きポーリングモデルである．狭帯域ISDNのDチャネ
ルのアクセス競合はポーリングモデルで解析される【47ト
通信分野以外でも，交通や生産システムのモデルとして使われている［5，14ト

図1：ポーリングモデル

ポーリングモデルがこのように広い応用範囲をもつこ
もともと「ポーリング」とは，中央のコンピュータがそとは不思議ではない・なぜならば，1つの資源（サーバ）をれに接続された複数の端末機に対し順に送りたいデータ

複数の利用者（待ち行列）が協調して使うとき，資源の巡があるかどうかを問い合わせ，それに応えてデータのあ回式割り当て（ポーリングモデル）は自然で公平な方式でる端末機はデータがあれば送信を行なうというデータ通あると考えられるからである．

信の制御方式に付けられた名前である．・この場合，中央のコンピュータがサーバの役目を果たし，各端末機の送信

ポーリングモデルの解析に閲し1980年代半ばまでに種々の分野で多分独立になされていた研究結果を集め，初めて統一的に整理したのが筆者の研究書【57】と概説論文

たかぎ ひであき 筑波大学社会工学系

である【叫・解析のみならず最適化と応用を含むその後〒305茨城県つくば市天王台1−1−1の研究成果については筆者や他の研究者による解説論文

受付：1995．5．9・採択：1995．10．13
108（46）が多く出ている【8，18，21，30，41，48，59，6？，61，67］・© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

オペレーションズ・リサーチ●本解説文では，第2節で基本的な単一バッファモデルとすべての待ち行列の動作が統計的に同じであるとき，シ

無限バッファモデルの解析の結果をまとめ，第3節でそれステムは対称（symmetric）であるという・対称なシステ

らの拡張モデルを紹介する．なお，文献の引用は代表的なムに対する結果は，以下の方程式等において桝＝β／Ⅳ＝

ものに限った．

入もとし他のすべてのパラメタの添字五を省略することにより得られる．

2．基本モデル2．1 単一バッファシステム
ポーリングモデルはいくつかの基本モデル（basic
それぞれの待ち行列で一時点に高々1人の客しか収容

model）とそれらを拡張したモデルに分類することができる．本節では，基本モデルとその解析の結果を紹介する・できないシステムを単一／くッファシステム（singlebuffbr

基本モデルは，それぞれ独立な客の到着過程をもつ複数のsystem）という．このシステムでは，客の到着時に待ち行

待ち行列を1つのサーバが巡回しながらサービスを行な列が占有されていると到着した客は消失すると仮定する．
各サービス時間が定数むであり，かつ全歩行時間も定数う連続時間システムである．定常状態のみを考える．

●

すべての基本モデルに共通の条件と記号を示そう．シ

月であるような対称な単一バッファモデルについては，平ステム内の待ち行列の数をⅣとする．それらの待ち行列

均巡回時間呵C】と平均待ち時間呵呵に対して次のよに，サーバが巡回する順序に従って1，2，…，Ⅳと番号をうな閉じた式が得られている【44，50ト

付ける．待ち行列Ⅳの次には待ち行列1が訪問される．

β【C】＝月＋呵や］む

待ち行列iには客が率入iのPoisson過程（Poissonpro−
呵Ⅳト（Ⅳ一1）わー＋

cess）で到着する（1≦豆 ≦Ⅳ）・待ち行列壱における客のサービス時間（service time）の分布関数のLaplace−

ここで
﹁■■﹂
l

．っ一

■−○

︶

＋
月

ヽ∧
P−

﹇

れⅢ国

﹁■■■﹂

l

．勺J

︶

LV

e

＋
R

︑人

ト

几

扁Ⅲ国

︶

︵

Ⅳ

β＝∑朽；桝‥＝入iわi（1≦盲≦Ⅳ）（1）

︶
l

一犯

〃∑は

＋

l

一Ⅳ

Ⅳ

にかかる負荷（load）は︵Ⅳ

ぞれβ；（β），む およびわ≡2）で表す・このときシステム全体

侶∑畑

Stieltjes変換（LST），平均および2次モーメントをそれi＝1●で与えられる．サーバが待ち行列言でのサービスを終えは1回の巡回時間の間にサービスする客の平均数である．

たあと待ち行列壱＋1に移動するのに要する時間をサー

図2にむ＝月＝1の場合の平均待ち時間即呵をβ＝バの歩行時間（walking time）という・その分布関数の八り沌に対して示す（Ⅳ＝∞は連続ポーリングモデルを

LST，平均および分散をそれぞれ月；（β），γiおよび∂デで表表す）．Ⅳが有限の場合は，p→ ∞のとき呵サ1先す．各歩行時間は独立であると仮定すれば，負荷が無いと月＋（〃−1）むとなる・

きサーバがすべての待ち行列を一巡するのに要する時間の平均と分散はそれぞれ

呵Ⅳ1
20
．Ⅳ

月＝∑γi
i＝1

．Ⅳ

△＝∑醤

（2）

i＝1

で与えられる．

17．5
15
12．5

負荷があるときにサーバがすべての待ち行列を一巡するのに要する時間を巡回時間（cycletime）という・待ち10
7．5

行列盲で測った巡回時間の分布関数のLSTと平均をそれ5

ぞれC；（β）と呵C】で表す（平均巡回時間はどの待ち行列2．5で測るかに依存しない）．待ち行列盲における任意の客の0

待ち時間（waitingtime）Wiの分布関数のLSTと平均を

−0．5

0

0．5

1．5

1

loglOβそれぞれl町（g）と呵Ⅳi】で表す・サーバの巡回時間と客の待ち時間はポーリングシステムの主要な性能指標（per−図2：対称な単」バッファポーリングモデルにおける平均

formancemeasure）である・

待ち時間利明（あ＝月＝1）・© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

1996年2 月号（47）1092

非対称な単一バッファシステムについては性能指標がやすことにより，これらの方程式の数を0（2〃）個にする

閉じた形に得られていないが，次のような方程式の解こともできる（そのかわり係数が複雑になる）【63トとして数値的に計算することが可能である． サーバ

対称モデルにおいて月とβ＝Ⅳ入あを一定値に保ちながた番目に訪れる待ち行列にとっての駐在時間（station

がらⅣ → ∝〉としたシステムを連続ポーリングモデル

time）叫を，待ち行列た−1から待ち行列たへの歩行（continiouspollingmodel）という．これは，客が円周上時間と待ち行列たでのサービス時間（もし客がいれば）のの任意の地点に等確率で到着し，サーバが円周に沿って動和と定義する． ここで番号たはすべての待ち行列につきながら出会った客をサービスするというモデルである．

いての通し番号で，サーバが1つの待ち行列を訪れる度

このモデルでは訪問時開聞隔は巡回時間に等しい．歩行速に1ずつ増えるものとする． 相次ぐⅣ個の駐在時間

度が一定の場合，平均巡回時間と平均待ち時間は昭一〃＋1，U∬−Ⅳ＋2，…ルたは互いに独立でないので，そ，1．．「， 月［．，．，，

呵C】＝÷；呵Ⅳ】＝∴＋ ￣l ■】1−β

れらの結合分布関数のLSTを

針＋．

／㌦）

￣L￣」
2（1−β）■2叫1−β）（11）

喘（β1，…，妬）：＝βトⅩp（−∑畏1U良一〃＋Jβメ）］（6）で与えられる．さらにサービス時間が一定の場合，巡回時

間と待ち時間の分布関数のLSTはで定義すると，これは関数方程式n；（輿，・‥，阜Ⅳ）＝月芸＿1（βⅣ＋入た）【1−β言（βⅣ）】×n忘＿1（0，gl＋入た，…，阜Ⅳ−1＋入た）＋月忘＿1（βⅣ）β芸（βⅣ）n忘＿1（0，β1，…，βⅣ−1）

尺C■（β）＝e￣鼠R
1−βe−＆●（12a）

1−C■（g）（7）

Ⅵ〃（β）＝

（12b）
g【ぐ】β

た＝1，2，‥．

で与えられる【20】．サービス時間が確率変数の場合も確率を満たす【叫・

積分と点過程の理論を用いて研究されている【38】．

サーバが各待ち行列を去る時刻をその待ち行列にとっそれぞれの待ち行列で一時点にいくらでも多くの客ての巡回時間の開始点と考えると，た番目に訪問される待を収容できるシステムを無限／くッファシステム（infinite

ち行列にとっての巡回時間Cたの分布関数のLSTはbufEbrsystem）という・このシステムでは客の損失は無い．無限バッファシステムの基本モデルとして，サーバ

C芸（β）＝n芸（β，…，β）（8）が各待ち行列で継続してサービスできる最大の客数に応で表される．各待ち行列をサーバが去ってから次にまたじて，4つのシステムを考える．第1の全処理式サービス

来るまでの時間をサーバの訪問時開聞隔（intervisittime）（exhaustiveservice）システムでは，サーバは待ち行列がという（「巡回時間」との違いは，訪問時間間隔は当該待空になるまでサービスを続ける．サービス期間中にその待ち行列でのサービス時間を含まないことである）．待ち行

ち行列に到着する客も同じサービス期間内にサービスさ

列たの訪問時開聞隔んの分布関数のLSではれる・第2のゲート式サービス（gatedservice）システム
では，サーバが待ち行列に来た時点でそこにいる客だけをぢ（β）＝n芸＿1（0，β，…，β）月完＿1（β）（9）

サービス期間中にサービスし，その期間内に新たに到着すで与えられる．これを使うと，た番目に訪問される待ち行

る客のサービスは一巡後のサービス期間に行なわれる．第列での客の待ち時間の分布関数のLSTと平均は3の制限式サービス（1imitedservice）システムでは，サーバが待ち行列に来たとき待ち行列が空であれば素通りし，l昭（β）＝入た［㍍（β）−ぢ（入た）】（10a）

空でなければ1人の客だけをサービスして次の待ち行列（入た−β）【1一花（入ん）】へ移動する．第4の減少式サービス（decrementingser−
現在】

1

β【Ⅳた】＝（10b）

1一花（入た）入たVice）システムでは，サーバが待ち行列に来たとき待ち行

列が空であれば素通りし，空でなければ客数が1だけ少なと書くことができる．

くなるまでサービスを続ける．

式（7）よ りC芸（β）やⅣ言（β）を 決 め る の に必要なⅣ（2Ⅳ￣1−1）個の未知数に対する同数の連立一次方程式が得られるので，原理的には数値計算により呵C］
や呵W鳥】を求めることができる・関数n紆）の引数を増
110（48）

これらのシステムが安定であるための必要十分条件は，それぞれ次のように与えられる．
全処理式：β＜1© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

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

●

減少式：

β 全処理式 ゲート式 制限式 減少式．00 ．5500

．5500

．5500

．05 ．6000．6053．6085 ．6031．10 ．6556．6742 ．6628．15 ．7176

．6667
．7353

．7485 ．7302（呵Ⅳ】eと呵呵タは橋田温氏と中村義作氏が導出した．20 ．7857．8125．8333 ．8070【32，33】．制限式サービスシステムの厳密な解析は野村雅．25 ．8667．9310 ．8953．30 ．9571

．9000
1．000

．35 1．062

1．115

1．179 1．119

式はFuhrmann，Watsonおよび筆者がほぼ同時期に独立．40 1．183

1．250

1．339 1．263に導いた【29，56，66】・呵Ⅳ1dは筆者による【5叶）．45 1．327

1．409

1．535 1．438．50 1．500

1．600

1．778 1．655．55 1．711

1．833
2．125

2．089 1．931

2．500
3．000

3．070 2．793

3．700
4．750
6．500

5．286 4．690の関係が成り立つことがわかる． また，負荷が低いと7．917 6．858

き呵呵g＞呵Ⅳ】dであり，負荷が高いとき呵呵g＜

10．00
20．50

100．0 50．00．60 1．975．65 2．314．70 2．767．75 3．400．80 4．350．85 5．933．90 9．100．95 18．60∂2 Ⅳ入招）（1一入γ）＋（γ＋入∂2）（Ⅳ−β）．5500

呵Ⅳh＝京＋

2【1一戸一入γ（Ⅳ一川（14d）

行・塚本克治両氏によりなされたが【46】，上の呵Ⅳ】Jの1．045 ．9980

表1にこれらの平均待ち時間の数値例を示す・式（14）の形または数値例を見ると2．500 2．294

呵Ⅳ】。＜β【Ⅳ】g＜呵Ⅳ】l
呵Ⅳ】e＜呵Ⅳ】d＜利明J

3．913 3．523

15．00 12．27

利明。である．なお，式（14）において∂2＝0とし，月＝Ⅳγとβ＝Ⅳ加を一定値に保ちながらⅣ→∞とすると，4つの式はいずれも連続ポーリングモデルに対する式（11）に一致する．

表1：対称な無限バッファポーリングモデルにおける平均待ち時間割Ⅳ】（Ⅳ＝10，γ＝0．1，∂2＝0．01，b＝

非対称な全処理式とゲート式サービスシステムについては，各待ち行列での平均待ち時間を数値的に厳密に計算

1，招）＝1）．

する方法が確立されている．全処理式サービスシステムの場合，待ち行列壱での平均待ち時間呵Ⅳi＝も訪問時開聞

ゲート式：β＜1

隔ムの平均と2次モーメントを用いて

制限式：すべての盲についてβ十人i月＜1減少式‥ すべての盲についてβ＋入i（1−βi）月＜

入 む！2） 呵（り2］

gIlり＝

＋

（15）

2（1一郎）■ 2利夫】

これらのの厳密な証明は多次元Ma∫kov過程のエルゴーと表すことができる．ここでド性にかかわり簡単ではない【54ト月（1−β；）
β【圭】＝2．2 無限バッファシステム

（16a）

1−β

」Ⅴ

4つのサービス方式を含む広範囲の無限バッファシス
榊）2】＝（叫り2＋軋1＋土手∑γ メ 桝

テムにおいて，平均巡回時間は簡単に

j＝1
（j≠i）

月
g【（−】＝（13）

1−βであり，γiJは待ち行列壱とjの駐在時間uiと叫の共分散である．全処理サービスシステムにおける待ち行列豆ので与えられる．対称な4つの基本モデルにおける平均待駐在時間は，待ち行列豆一1のサービス期間の終了から待ち時間は次のように与えられる．
全処理式：判明e＝京＋∂2

ち行列盲のサービス期間の終了までの時間であると定義
される・Ⅳ2個の未知数hゴ；盲，J＝1，2，…，Ⅳ）は次のⅣ入む伺＋γ（Ⅳ一β）（14a）
2（1−β）

ゲート式：呵呵g＝弄＋∂2

Ⅳ2個の連立1次方程式の解として数値計算で求められる【28】．

Ⅳ入あ（2）＋γ（Ⅳ＋β）
（14b）

Ⅳ

2（1−β）
βi

riゴ＝
制限式：

判明＝京＋

l−仇

ゴー1

ト1

∑γJm＋∑γゴm＋∑
m＝i＋1

m＝j

m＝1

∂2 Ⅳ入招）＋γ（Ⅳ＋β）＋Ⅳ入∂2（14c）2（1−β−Ⅳ入γ）

（17a）

メ＜壱

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

1996年2 月号（49）‖1

〃
γiブ＝
1

一郎

i−1

値的に求めることができても陽な表現式は得られていな

γブm＋∑γ両＋∑
m＝メいし，制限式および減少式サービスシステムについては数m＝1

値計算法さえ無い．しかしながら，驚くべきことに，各待ブ＞五軋1．入 む！2）β伍】 β

γii＝

＋

（17b）

」Ⅳ

ち行列の平均待ち時間の適当な重み付け平均が簡単な式∑句（17c）で表されることが知られている．待ち行列毎にサービス

ゴ＝1

方式が異なってもよいシステムについて，その式は（1−βi）2 ■（1−βi）3 ■1一郎
（j≠i）

さらに，係数ははるかに複雑であるが，同じものを計算するためのⅣ個の連立1次方程式も導か叫ている【49ト註仰】＋芸β （ト岩）珊】

ゲート式サービスシステムについても同様の解法が得ら
入イ1−桝）月

れている．

＋∑β

1一β

■i∈上）

非対称システムにおいて，高負荷の鱒ち行列と低負荷のJV待ち行列での任意の客の平均待ち時間を比べた興味深い月

β人 む52

結果が報告されている．全処理式サービスシステムでは，。2＋β＋

高負荷の待ち行列のほうが低負荷の待ち行列よりも平均2（1−β）2（1−β）（19）

待ち時間が短い．それは，サーバが高負荷の待ち行列に長月∑β… 月∑β 入ぎあ王2）く滞在しがちであるので，そこに到着する多くの客ほそのサービス期間のうちにサービスされるからであると説明

i∈C，⊥

i∈β

1−β

2（1−β）

されている【2叶 ゲート式および制限式サービスシステ

で与えられる．ここで，β，G，エおよびβはそれぞれ全ムにおいては，逆の傾向が観測される．すなわち，高負荷処理式，ゲート式，制限式および減少式サービス方式をもの待ち行列に到着する多くの客は，少なくともサーバが一つ待ち行列の番号の集合を表す【9】．この式は擬保存則巡するのを待たなければならないので，平均待ち時間が長（pseudoconservationlaw）とよばれる．その理由は，もしくなる【34】．

歩行時間がすべて0なら，客がいる限りサーバは必ずサー
ビスを行なうという仕事量保存（work conserving）シス

制限式と減少式サービスシステムに対する同様の厳密な解析は今までのところ成功していない．最も簡単な2テムに対するKleinrockの保存則（KleinfOCk sconser−

つの待ち行列から成る制限式または減少式サービスシス

Vationlaw）に帰着するかうである・擬保存則から，対称

テムに対して，待ち行列長の結合確率分布の母関数の方程システムにおける平均待ち時間（14）が直ちに得られる．

式を複素平面上の境界値問題に帰着させる厳密解法が知3． 拡張モデルられているだけである［10】・制限式サービスシステムは応用上よく現れるので，そこでの待ち時間を評価するために

前節で述べた基本モデルの条件を様々に変形・拡張し多くの近似解法が提案されている．代表的なものは，条件たモデルの解析が多くの研究者によってなされている．そ付き巡回時間の考えを用いる数値計算法【39】と，下記の擬れらの変形・拡張モデルには，現実のシステムの特徴をよ

保存則を満たすように調整して作られる陽公式である．後り忠実に採り入れようとする試みがある一方で，単に数学者の1つの例は的練習問題のようなものも多い．

g【In】記1一戸＋釣以下では，いくつかの本質的な拡張モデルについて最近

1−β」Ⅴ

1−β一入i月の研究成果をまとめる．

（トp）β＋∑誹

3．1 客の動き方に関する拡張

勅富＋勅）・［㌫姜去姜基本モデルでは，客はそれぞれの待ち行列に独立なPoisson過程で到着し，サービス終了後直ちにシステムか（18）

ら退去すると仮定された．到着過程を集団Poisson到着である【13】．この式はLANの階層モデルにおけるトークに拡張するとき，各待ち行列において独立な集団Poisson

ンリング部分のサブモデルに使われた【4叶到着がある場合と，システム全体に対して集団Poisson到

非対称な基本モデルにおける各待ち行列の厳密な平均
待ち時間は，全処理式とゲート式サービスシステムでは数112（50）

着があり客は確率的に各待ち行列に振り分けられる場合とが考えられるが，どちらの場合も基本モデルと同様の解© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

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

析が可能であるt7，42ト マルチメディアトラヒックをモ

chronousoverrun）のように，そのサービスだけは最後まデル化するといわれるMarkov変調Poisson到着過程をで続ける場合が考えられる．このような拡張された制限式もつポーリングモデルの厳密解Iま得られていない．再生サービスシステムは近似的に解析されているt25ト

過程や流体型の到着過程をもつポーリングモデルはいく

数学的な拡張の1つは，Bernoulliスケジューリング
（Bernoullischeduling）とよばるもので，サーバがある待

つかの近似解が提案されている．

バッファの大きさが1と無限大の中間の有限値である

ち行列において1人の客のサービスを終えたときにまだ（到着時にバッファが一杯であれば受け入れられない）シ

他の客が同じ待ち行列にいる場合，確率pで再びその待ち

ステムや，客の母集団が有限である（サービスが終わると行列でサービスを行ない，確率1一夕で次の待ち行列に移母集団に帰る）システムは，状態空間が有限であるので，動する（0≦p≦1・p＝0が基本モデル．の制限式に，複雑ではあるが厳密解が可能である．後者は，通信ネット

p＝1が全処理式に対応する）．非対称なBernoulliスケ

ワークにおける洗量制御（且ow control）のためのウィン

ジューリングシステムについて，各待ち行列での平均待ちドウ制御（window control）および等数制御（isarithmic

時間はもちろん得られていないが，擬保存則は得られておcontTOl）方式のモデルとして使うことができる・

り，したがって対称システムにおける平均待ち時間も得ら

1つの待ち行列でのサービスを終了した客が確率Jでもとの待ち行列にもどり，確率1一打でシステムから退れる［64】．
客にサービスの優先順位のクラスがあるシステムにつ去する（0 ≦J＜1）というBernoulliフィード／くッいては，優先順位に基づく処理が各待ち行列内部で行なわ

ク（Bernou11ifeedback）は，サービスのやり直し（たとれる場合は簡単に厳密解が得られる（バケーションを取る

えば伝送エラーによる再送信）や分割サービス（たとえばサーバをもつ優先処理待ち行列システムの解を使う）【叫

大きなファイルをブロック化して送る）のモデルとなるが，トークンリングやFDDIの仕様に近いシステム全体【62，63ト さらに，サービスを終えた客が他の待ち行列にに渡っての優先順位に基づく処理をするモデルは近似解移動する可能性も考慮に入れると，待ち行列網（networkのみが提案されている．

Ofqueues）を1つのサーバが巡回的にサービスするとい

ゲート式サービスの変形として，大局的ゲート式とうモデルが得られる．全処理式およびゲート式サービス

CRMAを紹介する．大域的ゲート式サービス（global1yをもつ待ち行列網は厳密解が可能である【52】・

gatedservice）では，システム内に「主待ち行列」とよばれる特定の待ち行列が1つあり，待ち行列盲でのサービス

3．2 サービス方式の拡張

はサーバが最後に主待ち行列を訪問したときに既に待ち基本モデルでは，システムのすべての待ち行列におい

行列盲にいた客についてのみ行なわれ，その後に到着したて，全処理式，ゲート式，制限式またはゲート式のうちど

客は次回まで待たされる．このシステムに対しては平均

れか1つのサービス方式が採用されると仮定した．それ

待ち時間が陽に得られている【12】．この方式を拡張して，ぞれの方式の拡張がいくつも提案されているが，応用上重システム内の待ち行列がれ個の主待ち行列とそれぞれの要な拡張は，トークンリングLANの動作で各ノードから主待ち行列に従属する待ち行列に分割されている方式をの継続送信に最大値が設定されていることに対応する，個同期ゲート式サービス（synchronousgatedservice）とい

数制限式と時間制限式サービスである．個数制限式サーう（れ＝Ⅳの場合が基本モデルのゲート式であり，弗＝1

ビス（number−1imited service）では，各待ち行列で継続の場合が大局的ゲート式である）【36トまた，巡回式予約多しセサービスされる客数の最大値がたで与えられる．（理重アクセス（cyclicreservationmultiplea．ccess：CRMA）

論上，たの値は待ち行列毎に異なってもよい．このた個とよばれる方式では，ちょうど郵便集配車が各地のポストにサービス期間中に新たに到着する客を含めるか否かにを享わって郵便物を集め郵便局で処理をするように，サー

よって，「全処理型た一制限式」と「ゲート型た一制限式」

バがシステム内を一巡して客を集めてから1人ずつサーが区別される．これらは，た＝1の場合が基本モデルのビスするもので，一方向回線で接続された高速通信ネット

制限式になり，た＝00の場合がそれぞれ全処理式とゲー

ワークのプロトコルのモデルとして提案されたt12】．

ト式になる．）時間制限式サービス（time−1imitedservice）

では，各待ち行列においてサービス期間の長さが制限される．客のサービスの途中で制限時間に達したとき，サービスを打ち切る場合と，FDDIの非同期オーバーラン（舶yn−

3．3 サーバの動き方
寒本モデルでは，サーバはすべての待ち行列を番号順に巡回すると仮定された．解析されている非巡回サービス© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

1996年2 月号（51）113

システムを次のように分類することができる．（1一）固定

また，閉じた待ち行列網を1つのサーバがサービスする的（deterministic）な動き．たとえば，エレベータや磁気ときには，サービス中の待ち行列においてのみシステム

ディスクのアームのようにサーバが往復する方式をとくの状態が変化するので，どのようにサーバを動かすかとにSCANという・（2）確率的（probabilistic）な動き．待いう問題は複数の腕をもつスロットマシンの問題（multi−

ち行列盲の次に確率拘で待ち行列jが訪問される方式をarmedbanditproblem）として定式化されるf65】．

Markov的経路選択（Markovian routing）という．および（3）状態依存的（state−dependent）な動き．たとえ

3．4 その他のシステム

ば，最も長い待ち行列に移動するサーバや，最も近くの客

最後にその他の代表的なモデルの研究状況を紹介する．

のサービスに向かう貴欲（greedy）なサーバ【31】，あるい

歴史的には，歩行時間の無い全処理式およびゲート式

はシステム内に客がいなくなると基地に帰るとか最後に

サービスモデルが既に1960年代に解析されている【4，22，

サービスした待ち行列のところに止まるサーバ【27】等が2叫第去節で見たように，歩行時間が有るモデルの解析考えられる．SCANシステムで大局的ゲート式サービス

では，サーバの1巡回時間に渡ってシステムの変数を評価を用いると，すべての待ち行列の平均待ち時間が同じになする方法が取られる．ところが，歩行時間が零のモデルでるという特異な結果が報告されている【3】．

は，システム内に客がいなくなる（安定なシステムではそもしサーバの動きを制御することができれば，適当な目のようなことが確率1で無限回起こる）と，サーバは有限的関数を設定してそれを最適化するようにサーバを動か

時間に無限回の巡回を行なうので平均巡回時間が零となすことが考えられる・このような最適化には，静的，半動

り，巡回時間に基づく解析ができない．このような理由に的および動的の3通りがある．たとえば，平均巡回時間やより，歩行時間が無いモデルと有るモデルは別々に取り扱

任意時刻におけるシステム内の全客数あるいは全負荷がわれてきたが，最近になり2つのモデルにおける平均待ち

目的関数とされる．

時間が関連付けられるようになった【19，24ト

静的最適化（static optimization）では，システムの稼システムの時間軸がスロット（slot）とよばれる一定の働前にサーバの最適な動き方を決め，そのとおりにサーバ

間隔で区切られ，システムの動作はスロットの境界のみでを動かす．サーバが訪れる待ち行列の番号順はポーリング

起こると仮定する離散時間（discretetime）モデルも早く

順序表（pollingordertable）で表される．全処理式またはから解析された【37］．離散時間ポーリングモデルは本質ゲート式サービスシステムに対し，∑芝1両叩瑚を最小にするように，ポーリング順序表の大きさと待ち行列番号

的に客の集団到着がある連続時間モデルと同様に扱うこの頻度と順序を最適化する方法が提案されている【11J．

半動的最適化（semidynamicoptimiza・tion）では，各巡とができるので，対応する結果が得られている．

通信システムやその他の現実のシステムにおいては効率向上のため複数のサーバをよく用いるが，複数のサー回前にその時点での・システムの状態に応じて巡回順序をバをもつポーリングモデルの解析や最適化は数値計算に決める．たとえば，歩行時間の無い全処理式およびゲー

よってのみ可能である・一般化確率Petriネット（gen−ト式システムにおいては，各巡回直前の待ち行列豆の客数

eralizedstochaBticPetrinets）を用いた研究【1，2］によをエiとすると，エi／入iの昇順にまわるとき平均巡回時間

れば，サービス率の総和が与えられているとき，（高速都市が最小になることが知られている【15】．

型通信ネットワークに典型的である）長い歩行時間と高負動的最適化（dynamicoptimization）では，1人の客の荷をもつシステムは，複数のサーバを使うことによって平サービスを終了する度にサーバの最適な動きを決める．た均待ち時間を大きく減らすことができる．また，1つの待とえば，対称なシステム内の全客数を任意の時刻において

ち行列だけが高負荷であるシステムを2つのサーバが巡最小にするためには，（i）1つずつの待ち行列で空になる

回サービスを行うと，高負荷の待ち行列が1つのサーバをまでサービスを続ける，（ii）その待ち行列が空になれば，独占し，他のすべての待ち行列が他方のサーバを共同使用

システム内で最も客数の多い待ち行列へ移動する，そしするという傾向が発見されている．さらに，多くの待ちて（iii）システム全体が空になれば，最後にサービスした行列をもつシステムを少数のサーバでサービスするとき，待ち行列のところに止まっている，というのが最適である

サーバの最適な動き方は巡回サービスであることが確認【43ト 半動的および動的最適化問題はMarkov決定過程

されている．複数サーバのポーリングモデルに適用できる（Markovdecisionprocess）として解かれる．

別の数値計算法として，システムの状態変数と方程式をす
べてβのべき級数に展開し，その係数に対する簡単化され114（52）© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

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

【5】Bertsimas，D・J・，and Van Ryzin，G・，StochaB−た方程式を数値的に解くというべき級数法（power−SeriesticanddynamicvehicleroutingintheE11Clidean

dgoTitbm）が提案されている【6】・

planewith multiplecapacitated vehicles・Opera−

4． おわりにtionsResearch，Vol．41，No．1，pp．60−76，Jan11ary−
February1993．

1968年のぶcねm坤c Amer通れ誌に掲載された非専門家向けの記事【40】で「興味深い重要な待ち行列モデル」【6］Blanc，J・P・C・，Performanceevaluationofpollingとして紹介されたポーリングモデルは，30年間に渡り，

systemsbymeanSOfthepower−Seriesalgorithm・

解析・最適化・応用について多くの人々により研究されA乃乃αJβ〆OpeTⅦf盲0陀β鮎ざeα化九，Vbl．35，No・1−4，てきた．筆者が個人的に集めた約760篇（平成7年10

pp．155−186，Apri11992・月現在）の参考文献のリストはインターネットのワールド【7】Boxma，0・J・，Wbrkloads and waiting times

ワイドウェブ（WWW）でhttp：／／www・Sk・tSukuba・aC・jp

in slngle−Server SyStemS With multiple customer／￣takagi／polling・htmlを開くと見ることができる・ポー

Classes．QueueingSystems，Vol．5，No．1−3，pp・185−

リングモデルの解析において，日本での研究が早い時期か

214，November1989．

らインパクトのある貢献をしたことは特筆に値する．今後の課題は，マルチメディアトラヒックの到着過程をもつシ【8］Boxma，0・J・，Analysis and optimization of

ステムや複数のサーバをもつシステムの研究であると思

po11ingsystems．In：Queueing，Performanceand

われる．

ControLinATM〝TC−1V，J・W・CohenandC・D・Pack（editors），pp・173−183，EIsevierSciencePub−

謝辞

1ishersB．Ⅴ．（North−Eolland），Amsterdam，1991・

本論文の研究は（財）電気通信普及財団の平成7年度助【9］Boxma，0・J・，andGroenendijk，W・P・，Pseudo−

成を受けています．また，査読者の方々の有益なコメント

conservationlawsincyclic−SerVicesystems・Jour一に感謝します．

花αJげAp〆盲edf，rohむ壷J軸，Ⅵ）1・24，No・4，pp・949−
964，December1987．

参考文献【10］Boxma，0・J・，and Groenendijk，W・P・，Two【1］AjmoneMarsan，M・，Donatelli，S・，andNeri，F・，

queues with alternating service and switching

GSPN models of Markovian multiserver multi−
q11eueSyStemS．Perhm

times．In：Queueing meoryandnsAppLications

nCeEvatuation，Vol・11，

一上iむerAm壷corllmJbrJ．Ⅳ．Coんeγl，0・J・Boxma

No．4，pp．227−240，November1990・

a．ndR．Syski（editors），pp・261，282，EIsevierSci−【2】AjmoneMarsan，M・，Donatelli，S・，Neri，F・，and

dam，1988．

Rubino，U．，Good and bad dynamic po11ing or−dersinsymmetricsinglebufEbrMarkovianmulti−
servermultiqueuesystems．IEEE冊OCOM

ence Publishers B．V．（North−Holland），Amster−【11】Boxma，0・J・，Levy，H・，andWeststrate，J・A・，

93，

E瓜cient visit ordersfor po11ing systems．Per−

pp．176−185，SanFrancisco，California，March3O−

わm肌Ce助αJむα如m，Wl．18，No．2，pp・103−123，

Aprill，1993．

September1993．

【3］Altman，E・，Khamisy，A■，andYechiali，U・，Onel− ［12］Boxma，0・J・，Levy，H・，チnd Yechiali，U・，
evatorpollingwithglobal1ygatedregime・Queue一

Cyclicreservationschemesfore伍cient operation

壷叩勒ざfemβ，Vol．11，No．1−2，pp．85−90，July1992・

ofmultiple−queueSingle−SerVerSyStemS．jlnnaLsqf
OpeγⅦfわnβ月eざeα作九，Vol．35，No・ト4，pp・187−208，【4】Avi−Itzhak，B・，Maxwe11，W・L・，andMiller，L・W・，

April1992・

Q11eueing withalternating priorities・qPerations【13］Boxma，0・J・，and Meister，B・，Waiting−timeReseaTTh，Vol．13，No．2，pp．306−318，March−April，
1965．

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

1996年2 月号（53）115

Switchovertimes・P？rjbrmanceEvatuation，Vol．7，【23］Cooper，R．B．，andMurr叩，G．，Queuesservedin

CyClicorder・T7LeBettSystem7もchnicaLJoum叫No．4，pP．299−308，November1987．

Vol．48，No．3，pp．675−689，March1969．

【14】Bozer，Y．A．，andSrinivasan，M．M．，Tandemcon−【24】Cooper，R．B．，Niu，S．−C．，andSrinivasan，M．
figurationsforautomatedguidedvehiclesystems
andtheanalysisofsinglevehicleloops．IIE7hns−

Adecompositiontheoremforpollingmodels：the
Switchovertimes aree飴ctivelyadditive．Operu−αC如托β，Vol．23，No．1，pp．72−82，March1991．

fわ乃β月eβeαⅣ九に掲載予定．

【15】BTOWne，S・，andYechiali，U・，Dynamicpriority

ru1esforcyclic−typeq11eueS・AdvancesinApptied【25］de Souza e Silva，E．，Gai1，H．R．，and Muntz，

R．R．，Polling systems with server timeout．

Probabitity，Vol・21，No．2，pp．432−450，June1989．

叩C財乃肌βαC如乃β0几Ⅳe亡びOrた如に掲載予定．

【16］Bux，W・，Local−areaSubnetworks：Aperformance
COmparison．IEEE nYmSaCtions on Communica−【26］Eisenberg，M．，Queueswithperiodicserviceandtions，Vbl・COM−29，No．10，pp．1465−1473，Octo， Changeover times・Operations Research，Vol．20，

ber1981．

No・2，pp．440−451，March−Apri11972．

【17］Bux，W．，Tbken−ringlocal−areanetWOrksandtheir【27］Eisenberg，M・，Thepollingsystemwitha．stop−
ping server・QueueingSystems，Vol．18，Nos．3，4，

performance■ Proceedings qf the mE昂Vol．77，

Pp．387−431，November1994．

No・2，pp．238−256，February1989．

【28］Fer占uson，M．］．，andAminetzah，Y．J．，Exactre−【18】Campbell，G・M・，CyclicqueueingsysteITfs．Eu一

SultsfornonsymmetrictokenrlngSyStemS．

叩e肌JoむmdJ可qpe相加乃αJ月eざeαγC九，Vol．51，

7ねmβαC如几β0−1Commu乃icαfio耶，Vol．COM−33，

No．2，pp．155−167，March1991．

No・3，pp・223−231，March1985．訂正：Cho11dhury，

G．L．，andTakagi，H．，Commentson【19］Choudhury，G．L．，Po11ingwithagenera．1service
Ordertable：Gatedservice．LEEEINFOCOM，90，

Exact re−SultsfornonsymmetrictokenrlngSyStemS・nmEE
升也れβαC如乃ざ・0γlComm視れ血如几β，Vol．38，No．8，

pp・268−276，San Francisco，California，June3−7，

pp・1125−1127，August1990．

1990．

【29］Fuhrmann，S．W．，Symmetric queues servedin【20］Connan，E．G．Jr．，and Gilbert，E．N．，A
CyClicorder・QpeTYZtionsResea7ThLetlers，Vbl．4，

COntinuous polling system with constant service

No．3，pp．139−144，October1985．

times・mnYmSaCtionson坤rmationmeory，
Vol・IT−33，No・4，pp．584−591，July19弼．

【30］Grillo，D．，Pollingmechanismmodelsincommu−
nicationsystems−Someapplicationexamples．In：【21】Conti，M・，Gregori，E．，andLenzini，L．，Metropoli−

βfocんαβねcAmαJyβiβ可Comp祝fer鍋dComm鮎乃壷cα−tan area networks（MANs）：PrOtOCOIs，mOdel−tionSystems，II・Takagi（editor），Pp．659−698，El−

ingandperformanceevaluation．In：Perhrmance

SeVierSciencePublishersB・V・（North−Ⅱo11and），

助dJむα如乃扉Comp祝fer肌dComm肌壷cα如乃勒ざ−Amsterdam，1990．

femg，Joinfねfo膏αJp叩erβ可Peγわmα乃Ce，タタ【31】Harel，A・，and Stulman，A．，Polling，greedy
andSi9metrics，93，L．Donatie1loand R．Nelsonand horizon servers on a circle．Operations（editors），pP・81−120，LectureNotesinComputer
Research，Vol・43，No・1，pp．177−186，January−

Science729，Springer−Verlag，Berlin，1993．

February1995．

【22】Cooper，R．B．，Queues servedin cyclic order： 【32】Hashida，0・，Analysisofmultiqueue．Reviewqflhe
Waitingtimes．ne BelLSystem二陀chnicalJour−βJecfわcαJComm一班壷cαfio†l血血椚血血路 Vol．20，

nal，Vbl．49，No．3，pp．399−413，March1970．

No・3−4，pP．189−199，March−April，1972．

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

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

【33】橋田温，中村義作：複数待ち行列の解析・経営科学，第by one operative when walkingtime and repalr

13巻第1号pp．30−47，1969年10月．

times areconstantS．JournalqftheRoyaLStatis−
ticalSociety，Series B，Vbl・19，No・1，Pp・166−172，【34】Ibe，0・C・，and Cheng，Ⅹ・，Approximate anal−

1957．

ysIS Of asymmetric slngle−Service token−paSSlng
systems．mEE7ねnsactionsonCommunications，［45］Mura・ta，M・，and Takngi，II・，Two−layer model−

Wl．37，No．6，pp．572−577，June1989・

ingforlocalareanetworks．IEEE升αnSaCtionson
Comm祝乃壷cα如那，Vol．COM−36，No．9，pp．1022−【35］Ibe，0・C・，andCheng，Ⅹ・，Performanceanalysisof

1034，September1988．

asymmetricsingle−bufEbrpo11ingsystems・Perfbr−

manceEvatuation，Vol．10，No．1，pp．l−14，October【46】野村雅行，塚本克治：ポーリングシステムのトラ

1989．

ヒック解析．電子通信学会論文誌，Vbl．J61−B，No．7，【36］Khamisy，A・，Altman，E・，and Sidi，M・，Polling pp．600−607，1978年7月．
systemswithsynchroni2；ationconstraints・Annals
イOperαfio那月eざeα陀九，Vol．35，No・1−4，pp・231−【47】Oza・Wa，T．1990・，Analysisofamultiqueuemodel

foranISDNaccessinterface．PerfbrmanceEvatu−

267，April1992．

ation，Vol．15，No．2，pp．65−76，June1992．
【37］Konheim，A・G・，andMeister，B・，Waitinglines

and timesin a system with polling．JoumaE qf【48】Rubin，Ⅰ・，and Baker，J・E・，Mediaaccess con−

銑eAβgOCidfio乃わrCompⅦ血タ〟αC九豆乃ery，Vol．21，

trolfor high−Speedlocalarea and mQtrOpOlitan

No．3，pp．470−490，July1974・

areacommunicationnetworks．Proceedin9Sqfthe
lEEE，Vol．78，No．1，pp．168−203，January1990．

［38］Kroese，D・P・，and Schmidt，V・，A continuous

pollingsystemwithgeneralservicetimes・meAn− 【49］Sarkar，D．，and Zangwill，W・Ⅰ・，Expected wait−nαJざイAp〆iedP和あα如J慮fy，Vol・2，No・4，pp・906−

ing timefor nonsymmetric cyclic queuelng SyS−

927，1992．

tems−Exact results and applications．Mana9e−

ment Science，Vol．35，No．12，pp．1463−1474，De−【39］Kuehn，P・J・，Multiqueue systems with nonex−

cember1989．

haustivecyclicservice．meBeLISystem7tchnical

JournaL，Vol．58，No．3，pp．671−698，March1979．
［50］Scholl，M．，and Poti占ー，D・，Finite andinfinite
source modelsfor communication systemsundert40］Leibowitz，M・A・，Queues・Scientific American，

pblling．IRIARapportdeRecherche，No．308，In−

Vol．219，No．2，pp．96−103，August1968・

Stitut de Rescherche enInforma．tique et en Au−【41】Levy，H・，and Sidi，M・，Polling systems：ap−

tomatique，LeChesnay，France，1978．

plications，mOdeling，and optimization・mEE
升αれβdC−われβ0れComm肌icαf壷0Tlβ，Vol．38，No．10，【51］Shimogawa，S．，andTakahashi，Y・，Anoteonthe

pse11do−COnSerVationlawfor a multi−queue With

pp．1750−1760，October1990・

localpriority．Queuein9Systems，Vol．11，No・ト2，【42】Levy，II・，andSidi，M・，Pollingsystemswithsimulq

pp．145−151，J111y1992．

taneous arrivals．IEEE升ansactions on Commu一
乃よcα如乃ちⅥ）1．39，No．6，pp．823−827，Jume1991・【52】Sidi，M・，Levy，II・，and Fuhrmann，S・W・，A【43］Liu，Z・，Nain，P・，andTbwsley，D・，On optimal
po11ingpolicies．QueueingSystems，Vol・11，No・ト2，pp．59−83，J111y1992．

queuelng netWOrk with a single cyclically rov−

ing server．Queuein9Systems，Vol．11，No．1−2，
pp．12ト144，July1992．訂正：Correctiontoeq11a−
tion・（5・6）inthepaper：Aque11eihgnetworkwitha［44】Mack，C・，Murphy，T・，andWebb，N・L・，Theef−

ficiencyofNmachinesllni−directionallypatrolled

Singlecyclical1yrovingserver．Queuein9Systems，
Vol．16，No．1−2，p．193，April1994．

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

1996年2 月号（55）11丁【53］Stidham，S．，Jr．，Optimalcontrolofasignalized【61】Takagi，II・，Queueinganalysisofpollingmodels：intersection，PartI：Introduction：StruCtureOfin−progressin1990−1994．In：伽nliersinQueuein9：

tersectionmodels，PartII：Determlnlngtheopti−

ModeLs，Methods andProbtems，一．H．Dshalalow

malswitchingpolicies，and PartIII：Descriptive（editor），CRCPress，1995（出版予jf）．

StOChasticmodels．TechnicalReports No・94，95

and96，DepartmentofOperationsResearch，Cor−［62】Takine，T．，Takagi，H．，and Hasegawa，T．，So−

JOurntimesinvacationandpollingsystemswith

nellUniversity，Ithaca，NewYbrk，1969．

Bernou11ifeedback．JournalqfAppEiedProbabitity，【54】Szpankowski，W．，Towards computable stabil−

ity criteria for some multidimensional stochastic
processes．In：Stochastic＾naLysis qf Computer

Vol．28，No．2，pP・422−432，June1991．
【631T乱kine，T．，Takahashi，Y．，andⅡasegawa．，T．

Average messagedelayofan asymmetricsingle−

andCommunicationSystems，H．Takagi（editor），

bu鮎rpollingsystemwithro11nd−rObinscheduling

pp．13l−172，EIsevier Science Publishers B．Ⅴ．

Ofservices．In：Modellin9二陀chniques and noLs

（North−Holland），Amsterdam，1990・

わrComp加ゎrf，e†わmα乃CeβγαJ祝α如乃，D．Potier【55］Takagi，H・，Mean message waiting timein a

Symmetric pollingsystem．In：PerfoTmanCeandR・P11i鼠janer（editors），pp・179−187，Plenum

84，

E・Gelenbe（editor），pp・293−302，EIsevier Sci−
ence Publishers B・Ⅴ・（North−IIolland），Amster−

PublishingCorporation，NewYork，1989．
【641Tedijanto，Exact res111tsfor the cyclic−Service

queue with a Bernoullischedule．PerfbmlanCe

dam，1985．

Evaluation，Vol・11，No・2，pp．107−115，July1990．

【56］Takagi，H．，Meanmessagewaitingtimesinsym−【65］Walrand，J．，Queueingnetworks．In：Handbooks
metric multi−queue SyStemS With cyclic service．
五和qPe相加那月eざeα代ゎαれd〟α氾叩e〝l印fβci印Ce，

Pe†中門Ⅵd几Ce動′αJ視α如乃，Vol．5，No．4，pp．271−277，

Vbtume2：StochasticModets，D．P．IIeymanandNovember1985．

M・J・Sobel（editors），pP・519−603，EIsevier Sci−
ence Publishers B・V・（North−Ⅱolland），Amster−【57］Takagi，H．，＾naLysisqfPotLin9Systems．TheMIT

dam，1990．

Press，Cambridge，Massaclmsetts，1986．
【58］Takagi，H．，Queuing analysis ofpolling models・【66］Watson，K・S．，Per払rmanceeval11ationofcyclic

AC肘Comp祝fi乃〃βurueyβ，Vbl．20，No．1，pp．5−28，

SerVice gtrategies−A survey・In：Pe7わrmance

March1988．

，84，E．Gelenbe（editor），Pp．52ト533，EIsevierSci−
ence Publishers B・V．（North−Holland），Amster−t59］Takagi，H．，Queueing analysis of polling mod−dam，1985．

els：Anupdate．In：StochasticAnatysisqfCom−p視ねrα柁d Comml 几icα如乃gyβfe†那，H．T乱kagi【67】Yechiali，U・，Analysisandcontrolofpollingsys−（editor），pp・267−318，EIsevierSciencePublishers

tems．In：Peゆrmance EvaLuation qf Computer

B・V・（North−Holland），Amsterdam，1990・

α循d Commtlれ壷c（lfio乃軸βねmg，Jo壷乃‡ねわ膏αJpα一【601Takagi，H．，Applicationofpollingmodelstocom−

puter networks．Computer Networks andSystems，Vol．22，No．3，Pp．193−211，October1991・

118（56）夕eγβ扉アeγわmα乃Ce βタα乃dβiタmefわcβ タβ，L・Donatiello and R・Nelson（editors），pp・630−650，

LectureNotesinComputerScience729，Springer−
Verlag，Berlin，1993．

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

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