複数の到着流をもつ単一サーバ待ち行列
滝根 哲哉…………………………………ll……………………lll……l………ll……ll…………………………………………………………………………………………………………………………‖‖＝‖‖‖＝‖‖＝‖‖‖＝‖＝‖‖‖＝‖‖‖＝‖‖‖‖‖‖‖‖‖州l

1 はじめにがこのようなモデルを考察するに至った経緯から，最待ち行列モデルはサーバと呼ばれる共有資源に村して多数の利用者（客）が確率的に利用要求を発生するという状況を記述するものです．昨年のOR誌の特集【2】でも紹介されているように，その応用分野は様々ですが，中でも，通信網の性能評価は最も自然な応用分野といえます．実際，電話網の設計問題を解決するための枠組として，20世紀初頭に研究が開始されており，通信網への応用を意識したとき，待ち行列理論は通信トラヒック理論とも呼ばれています．
本稿の表題である複数の到着流をもつ単一サーバ

終的に解析手法を確立するまでを，着眼点を中心に紹介したいと思います．

2 研究の動機
待ち行列モデルにおける最も基本的な客の到着過程はポワソン過程です．これは客がランダムに到着す
ると仮定することと等価です1．しかし，統合サービ
ス網に対する応用では，必ずしも伝送単位の発生がポ
ワソン過程に従うとは仮定できず，より広い範囲の到着過程を記述できるモデルが必要です【13ト筆者が非ポワソン到着流・をもつ待ち行列の研究を始めた1990

待ち行列も，やはり，通信網への応用から自然発生的に現れたモデルです．近年の通信網の高速化に伴い，年以前にも，既に幾つかの（解析的取り扱いが可能

従来，個別綱に収容されていた多様なメディア（音声，動画，データなど）を単一の通信網に収容する統合サ

れらはいずれも記法の面で（筆者にとっては）繁雑にービス網の技術開発が進められています．統合サービ
ス網に収容されるトラヒックは，メディアあるいはコンテンツによって，それぞれ固有の特徴を持っている
ため，通信網内に設置された交換機では，性質の異なるトラヒックが多重化されて伝送されることになります．これを待ち行列モデルで記述すれば，メディアあるいはコンテンツに対応する異なる性質をもつ客（伝送要求）が共有資源であるサーバ（回線あるいは交換
機内のバッファ）の利用を競い合うことになります．
このような技術動向に刺激され，複数の到着流をもつ待ち行列の研究がこの十数年来，精力的に行われてきました【131．一般に，待ち行列モデルは客の到着（発生）パターンと到着した客が要求するサービスに必要な時間の確率的性質を定めることで得られます．
本稿で紹介する複数の到着流をもつ待ち行列モデル
は（1）各到着流は異なる確率過程に従い，かつ（2）到
着流毎にサービス要求時間の確率分布が異なるようなものです．後述するように，この種の待ち行列モデ
ル，中でも最も基本的な先着順サービスモデルは，ごく最近まで極めて限られたモデル以外は解析的な扱な）非ポワソン到着過程が提案されていましたが，そ思えました．それゆえ，当時，このような非ポワソン
到着過程の枠組で，既知の結果を実質的に発展させることができるとほ必ずしも思っていませんでした．今から思えば，それは記法の繁雑さが対象となる問題の構造の見通しを悪くしていたのだと理解できます．
好運にも，筆者が研究を始めたちょうどその頃，マ
ルコフ型到着過程（MAP）［3］と呼ばれる到着過程モデルが提案されました．MAPには，独立なMAPの重畳がMAPで表現できることや，あらゆる定常単純点過程を任意の精度で近似できるなどの利点があります．後にMAPはそれ以前に提案されていた他の非ポワソン到着流と数学的には等価なことが分かるのですが，待ち行列の解析という観点から最も簡潔な表現をもつため，急速に浸透しました．筆者も，このMAPなら何か新しいことができるのではないかと思って勉強を始めました．
到着過程がMAPに従い，サービス時間が独立同一分布に従う単一サーバ待ち行列（MAP／G／1）の客数
過程はM／G／1型と呼ばれる構造を持った離散時間マ
ルコフ連鎖に帰着でき，通常，アルゴリズム的解法のいが困難なものと思われていました．以下では，筆者一種である行列解析法【4】によって解析されます．このアルゴリズム的解法は，昨年，OR誌で企画されたたきね てつや 京都大学大学院情報学研究科数理工学専攻「待ち行列研究の新しい潮流」【6，7】でも紹介されてい〒606−8501京都市左京区吉田本町
E−mail：takine＠kuamp．kyoto−u．aC．jp

1999年3 月号

1ポワソン過程の平易な解説が［5】にあります．

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

（33）147

るように∴系内客数に対応する離散確率変数とシステて1つの到着流とみなし，それを先着順でサービスすムの状態変化を記述するために必要な情報を保持するモデルの解析結果が必要なことは明らかでした。こる補助的な離散確率変数の組からなる2変数離散状
態マルコフ連鎖に対してタその構造を利用して定常解れが今回紹介する研究の動機となりました岬を求める数値アルゴリズムと見ることができます。．詳認 対象恕なる菟デルと複数の到着流の記述

最初に少以下で対象となるモデルの最も単純な例を

細は膵明を膚灘して下さい。

当時，既に行列解析法の基本的枠組は確立されて−いましたので，筆者は，統合サービス網への応用という示しますか

例 2つの到着流を収容する単wサⅦバ待ち行列

観点から基本的なモデルであり，かつ，従来の行列解

到着流1は到着間隔がÅJlのポワソン到乱サー

析法では解析できないをデルとして，到着流間に非割

ビス時間分布関数机（E）をもつ。一方，到着流2は込み優先権がある得ち行列モデルを研究の対象に据到着間隔が平均Å；1の2ステ←ジアーラン分布3に従えました。優先権がある場合，系内客数の挙動を表現

い野サレビス時間分布関数ゐ2（可をもつ。客は先着順するためには，各到着流毎の客数を保持する必要があ

サ・叫ビス規律に従ってサービスされ，得ち部屋の容量

ります＼ぞ・の結果夕 客数に対応する無限個の状態をもは十分に大きく，到着した客は全てシステム内に入る

つ確率変数が到着流の数だけ必要となり∴鯉限個の状

こ．とができる。

態をもつ確率変数を1つしか許さない従来の行列解

この件ち行列における到着過程を図で表現すると以下のようになります。

析法の枠組では解析できないわけです心各到潜流がMA鮮 に従う非割込み優先権付き待ちÅ1っ叫∬） Å1誹′1（憲）

行列の蔵も単純なをデルは，全ての客のサービス時間が独立岡山分布に従う場合です。筆者は，まず，このモデルの研究から始めまLた。簡単な考察の後，このをデルは，2つのMÅP到着流をもつ非割込み優先権付き待ち行列の結果を用いれば解析できること，また少 この2つの到着流をもつモデ虹吼全ての到着流を且つにまとめた到着流をもつ先着順をデルの結果
を用いれば解析可能なことが分かりました∴全ての客のサー伸ば−ス時間が独立同一分布に従う場合，全ての到着流を1、【別にまと抽た到着流せもつ慄涌順モデルは通常のMÅP／鰐ノ1モデルになり，これは従来の行列解析法で解析でき針恥 結果として，サービス時間が図乱ニポワソン到着と2ステ山ジアーラン到着の重畳
一一般に ，先着順サ仙tビス単一サーバ待ち行列において，γ＆番目の客の離脱直後の客数を吼，m番目の客のサーゼス時間内に到着する客数をAmとすると
軌＋且＝m弧（軌一皿，0）＋現車が成立します。叫∬）＝‰（￡）の場合，Q・柁の値とサービスの終了時点でアーラン分布がいずれのステー

独立同山分備に従う場合の非割込み優先権モデルはジにあるかを表す確率変数ぶれ の値が与えられると既知の結果を応用すれば解析できたわけですE呵由遡mの分布が定まります。言い替えますと確率変数のこの研究結果は理論的には余り面白いところはありませんがp 固定魔の伝送単位をもつA甘か浦網2に直接応用できる利点があります∴暫時∴筆者は米国に滞在しておりタ 帰国前に米国タ カナダの大学√研究所を回ってこの結果ならびに離散時間をデルに関する同様組（吼丹‰）はマルコフ連鎖になります。特にこのマルコフ連鎖はM／G／1型と呼ばれる構造をもっており，

前述の行列解析法で解析できます。
しかし，‰（諾）≠れ2（￡）ならば，客の到着とサービ
ス時間分布の間に相関が生じるため，給客数軌 との結果（m講演をじてV−ました8Å甘＆甘迅eJL孔研究所でのぶれの組はマルコフ連鎖を構成しません凸 実際，客数

講演の後，開削二束てくれた火の中位もうやることがなくなったと言っていた人がいると聞き野 園分が選の挙動を表すマルコフ連鎖を構築しようとすれば，サ山ビス中ならびに待っている個々の客がそれぞれ，どんだ研究の方向が間遠っていなかったと胸を撫で下ろ

ちらの到着流から来たかという情報を全て保持するしたことが思い出されます。

必要があります4レ

さて，サービス時間分布が到着流毎に異なる場合はどうすれば庇いのでしょうか。サービス時間が独立同

この例からも分かるように，サービス時間分布の異なる複数の非ポワソン到着流を収容する単一サーバ

一分布に従う場合椚考儲から，全ての到着流をまとめ
3平均（陀Å）鵬1の独立な指数分布の閃個の和が従う分布を平2Å甘M網では，倍速される全ての情報はセルと呼ばれる固定長の刃、さな伝送単位（ヘッダ5バイト，情報部48バイト）に分割されり 通信網へ送り出されますレ

瑠樋脇（34）

均A」の陀ステージア血ラン分布といいます。
4サービス時間が最も扱いやすい（平均の異なる）指数分布に従う場合でも同様です小© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

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

待ち行列では，客数の挙動を表現するマルコフ連鎖は

ルイ五の要素数と同じ次元の単位行列です．特にβを構

極めて複雑な構造をもつため，そのような定式化によ成している2つの要素はそれぞれの到着流からの到る解析は極めて困難です．最初に少し触れましたが，着を表現していることに注意して下さい．例えば前述

待ち行列モデルの解析において，モデルに内在する確のポワソン到着と2ステージアーラン到着の重畳は率過程（本稿の場合，到着流）をどのような記法で表現するかは，モデルの構造の見通しを良くする上で極めて重要です．簡潔な記法を用いれば，一見，複雑に見えるモデルに村しても何か糸口を得られる可能性

c十1J2入2＿入デ空2入2），β＝（先王）で記述されます．

上記の例では，重畳された到着流を1つの到着流とがあります．

して見ていますが，複数の到着流を明示的に記述する

具体的に話を進めるため，ここで前述のMAPの定義を与えます．MAPは有限状態をもつ連続時間マ
ルコフ連鎖を考え，状態遷移が起こったとき，予め決められた確率で客が到着するというものです．具体的ためにマーク付きMAPが提案されています【1】・これは，到着を伴う遷移率を表現する行列かを各到着
一般に，マー
流毎に個別に用意するというものです．
ク付きMAPを用いてP個の到着流を記述する際，には以下のように定義されます【3ト まず，状態集合

MAPにならって（C，か1，＝・，かp）で表現されます．

ルⅠ＝（1，…，〟）をもつ既約な有限状態連続時間マル

ここでβた（た＝1，．．．，P）の（壱，J）要素は，た番目

コフ連鎖‡g（り）を考えます．各状態壱∈ルイでの滞在の到着流からの客がMAPの相のまからプへの遷移

時間は平均りJlの指数分布に従います．状態宜での滞に伴って到着する率を与えています．行列Cの定義

在終了後，確率裾（J∈〟，ブ≠壱）で到着を伴わず状はMAPの場合と同じです．例えば2つのMAPの重態ブへ遷移します．また，確率鋸（J∈〟）で1人の畳の場合，か1＝β1⑳∫2，刀2＝∫1⑳か2となります．

客の到着を伴って状態jへ遷移します．ただし

また，上述の例において，ポワソン流を到着流1，2∑裾＋∑鋸＝1

ステージアーラン流を到着流2としたとき，以下のよJ∈人イ

うに記述されます．

ブ∈人′lりβの（壱，メ）要素は到着を伴う状態宜から状態Jへの遷移率を表し，Cの非対角（壱，j）要素は到着を伴わない状態壱から状態Jへの遷移率を表します．
例えば率入1のポワソン過程は到着間隔が平均入「1の指数分布に従うのでC＝一入1，β＝入1となります．また，平均入；1の2ステージアーラン分布は
︶
0 0

2

上）＝

三）・

0 1∧

て■￣ヲ， ー2入

2

︵

C＝

マーク付き MAPの表現はサービス時間に関する情報を含みません．前述の例で示したような，各到着過程を表現（C，β）をもつMAPといいます．定義よ20で与えられる〟×且オ行列C，βを用いて，この到着

β1＝（‡ヱ），β2＝（2：2C壱，J＝り胡，ブ（ノ≠壱），〔㍉＝一鞘，」玖，プ＝り雄，プ

0

です・このとき，（壱，ゴ）要素q．ブ，β五，ブがそれぞれ︶j≠豆となります．以下ではMAPを支配しているマルコフ

マーク付きMAPを拡張し，（Cフか1（∬），…，かp（霊））という形の表現を導入します．ここでかた（ヱ）（た＝1，…，P）の（盲，j）要素は，サービス時間がヱ以下であるようなた番目の到着流からの客が，MAPの相の哀からメへの遷移に伴って到着する率を与えています．

行列Cの定義はマーク付きMAPの場合と同じです．
例えば図1の到着流は以下のように表現されます．

ります．すなわち

列の解析を考えます．まず，この待ち行列におけるC＝Cl⑳∫2＋∫1⑳C2，か＝刀1⑳∫2＋∫1⑳か2としたとき，重畳された到着過程は表現（C，β）をもつMAPとなります．ここで⑳はクロネッカ積，∫壱は1999年3 月号

本章以降は，表現（C，β1（諾），t．．，かp（芯））をもつ到着流を収容する先着順サービス単一サーバ待ち行

MAPの相の定常確率分布訂は次式で決定されます．

訂仇＝0，訂e＝1

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

（35）149︶

とる状態集合ルlはこれらの直積集合ル11×ルイ2とな

ハU︶∬

ルーl，ルイ2とすると，重畳後の到着過程において相がハU

4 系内仕事量分布と待ち時間︵を考えます．それぞれのMAPの相がとる状態集合を

1∧

かた＝かた（∞）（た＝1，…，P）に注意して下さい．

つ一

うに記述できるでしょうか・例として，表現（Cl，β1）
ならびに（C2，β2）をもつ独立な2つのMAPの重畳

毎坤）＝（入1㌔（ミ1ご（∬，），瑚＝（

2

さて，複数の独立なMAPを重畳したとき，どのよれらを明示的に表し，かつ，簡潔な（例えば図1と等価なものを表現する）記法が必要となります．そこで

0

連鎖の状態を相と呼びます．

流がそれぞれ異なるサービス時間分布をもつ場合，そここでeは全ての要素が1の列ベクトルです。さらに〃（鳶，諾一封）肋（封）＋0（離）＋ん兄∴肝を用いて，この得ち行列の利用率〝は
β＝＝筋

−ヽ、−

が成立しが これより
トご・∴・

鉢車釦帖叫叫脛（￡ゥ瑚嘲

で与えられます。ただし戯（∬）＝戯1（可＋…＋期中）です山 以下でほβ＜胤を仮定します5。

を得ます小 これほⅧak孟csの樽分微分方程式と呼ばれ（1）ています心 特に，定常状態における系内仕事量Ⅴの分布関数申）＝m（Ⅴ≦芯）は∂可窓，∬）／飢＝のより

前述したように∴客数の解析は簡単そうではありません幽 では，待ち時間はどうでしょうか鞠 先着順サー
ビスの場合の得ち時間は，客が到着した時点における系内仕事量で与えられます。この系内仕事量とは，その客の到着時点以降，到着がないと仮定したとき，シ鉦困帖礁（∬一潮汐）となり∴両辺のラプラス巾ステイルチェス変換（msT）

を取ることにより，系内仕事量分布のmSTが（β）は㌦（β）（βwA十Aぬ⊃ト（β））＝′U（の）βステムが空になるまでの時間で与えられる量です。
系内仕事量は以下−のようなものを想像すれば理解を滴たすことがわかります（㍍（β）はぬ（可のmST）。

しやすいかもしれません。待ち行列では通常，客が行

未知数即（0）は系内仕事量が0，すなわちシステムが列を作ってサービスを待つと捉えられますが，客が待つ代わりに，客はシステムに仕事を運んで来ると考え空である確率であり，これは平均サービス時間をねとすると即（0）＝胤…肋で与えられますuてみます∴例えば，客が到着した時，その客は書類のそこで，この議論を表現（灯，脳1（憲），…，戯p（諾））を束をサ山バの前に積み止げるとします。サーバは書類

もつ到着流7を収容する先着順サービス単一サーバ待がある限り，一定のペースで書類を処理していくとしち行列の場合に拡張します酢時刻￡におけるMAPます。すなわち，客が持ち込んだ書類を処理するのにの相を動で儀し，j番目の要素が厨γ（隋≦∬，銑＝ブ）

必要な時間がサービス時間に対応します小 また，先着で与えられる行ペグー、ル即（藍，∬）を考えると∴叫鳩／且

順でサービスされる場合，ある到着客が持ち込んだ書と同様の議論により次式が成立します。

類の処理が始まるまでの時間（待ち時間に対応）は，

即（窓＋∂￡9芯）＝（g＋C離）即（￡ヮ芯＋離）

到着時点において少サーバの前に積まれている未処理J即（￡，∬】封）放紗（y）∂藍＋0（舶）の書類を全て処理し終えるまでの時間で与えられます。この未処理の書類を全て処理し終えるまでの時間．′ ∠ご

ここでgほ単位行列です￠これよりを系内仕事量といルーます爪音類の例からも明らかなように，もし，到着した客がサービス終了まで退去することがなく，かつ仕事が

孟即（￡フ∬）＝孟即（藍り巾（湘＋距和一即）d戯（封）ある限りサーバは稼働し続けるとすると少系内仕事量MÅ㌘の相をぶとしたとき，メ番目の要素がPr（Ⅴ≦はサ山ビスの順序とは無関係な量となります6。この諾，ぶ＝j）で与えられる行ベクトル即（∬）はような待ち行列を仕事量保存型といいます。さらに仕事量保存型の場合，時刻再における系内仕事量Ⅵはを得ますゆ 特に，定常状態における系内仕事量をy，

−

一 一

− −1

明＞0のとき率孔で減少し，客の到着があると，そのを満たし，両辺のmSTを取ることにより，系内仕事

客のサ山ビス時間分だけ上にジャンプします。

量分布のベクトルmSTが（β）はさて，この系内仕事量に関しては少 率Åのポワソ
ン到着，分布関数呵可に従う独立同一なサービス時

即＊（β）（βg＋び十戯＊（β））＝即（0）β間をもつ通常の叫膵困の場合，時間依存分布関数

を満たします（戯＊（5）は戯（￡）のmS甘）。よってゴ番

坤フ∬）＝P『（閑≦∬）に対して，次のような結果が古目の要素がPr（y＝0，ぶ＝ブ）で与えられる衆知ベク

くから知られていました［軋 まず，徴榊寺間∂苦でのトル即（0）を求めれば良いことが分かります。これは遷移を考えることにより以下のように導出されます。

即（詰＋∂恐，芯）＝（1血Å離）坤，諾＋如）

時刻0で系内仕事量がぶであり，かつ，MÅPの相が壱であるという条件の下で，これ以降初めてシステ

5これにより定常状態の存在が保証されます。
6どの仕事から手をつけても，全て処理するまでに必要な時間は同じなので，優先権がある場合でも先着順でサービスされる場合でも系内仕事量の分布は同じです叩

周5紛（36）（2）

ムが空になった時点でのMÅpの相がブである確率
7系内仕事量を考える際には，表現（α，戯（諾））をもつ到着流と等価です（（胤）参照）。

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

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

Pr（Ⅳ鳥≦諾，g芸＝j）であるベクトルwた（∬）はを（壱，力要素にもつ行列P（￡）を考えます・定義より
0（∂可の項を無視すると項）＝

p（両）＝P（ヰ＋C机上∞叫y）ぬク旬）］（5）で与えられます．また，定常状態におけるクラスたの客の系内滞在時間を．見たとしたとき，ブ番目の要素がが成立し，これよりPr（見た≦諾，∫芸＝J）であるベクトルγた（∬）は
孟p（諾）＝P（ヰ＋上∞d瑚）p（y）］
血（y）かた（∬−y）

を得ます．ここでγた（諾）＝

汀上）たe

Q＝C＋

．J

aD（諾）exp（Q諾）

で与えられます．

とおくとdP（諾）／ゐ＝タ（￡）q，すなわちP（∬）＝

5 待ち行列長分布と不変式

exp（Q諾）を得ます．行列Qはシステムが空である時

系内仕事量の解析が終った後，暫く筆者は非割込み

間区間のみに注目した場合のMAPの相の遷移率行列
このQを用いてむ（0）を求めることができます・シ

優先権付き待ち行列に関する研究【11，15】や系内仕事量と同様の性質をもつ連続時間マルコフ連鎖に関すステムが空である確率は1−Pですのでγ（0）e＝1−βる研究【12］などを行っていました．待ち行列長分布となります．よってKQ＝0かつKe＝1を満たす行をどう攻めるか，ずっと心に残っていたものの，手つベクトルKを用いてu（0）＝（1−β）Kとなります．以

かずの状態でした．しかし，昨年，後で述べるある思

上の考察より，最終的な結果

いつきがきっかけとなり攻略できたのです．

を表しています．

が（β）［β∫＋C＋が（β）】＝（1−β）βK

まず，従来とは視点を変え，客が先着順でサービス（3）

されるという仮定の下で，待ち行列長分布を系内仕事を得ました．この両辺を微分することにより系内仕事

量分布，あるいは待ち時間分布と関連つけることを考量の積率を計算することができます．特にサービス時

えました．そのために，系内経過時間（attainedwait−

間分布が独立同一な分布関数ん（∬）（LST㍍（β））をも

ingtime）を定義します．これはもしシステムが空でつMAP／G／1の場合，あるなら0であり，サービス中の客がいる場合は，こγ＊（β）［β∫＋C＋ん＊（β）呵＝（1−β）乱K （4）となります．（2），（3），（4）が極めて似た形になっての客の到着時点から現在までの時間で定義されます（図2参照）．

いることに注意して下さい．この意味で，表現（C，

離脱

系内滞在時間刀1（諾），…，βp（ご））をもつ到着流を収容する単一サーヰ

バ待ち行列はポワソン到着をもつM／G／1の自然な拡系内経過時間張になっていることが分かります．

この結果は，元々，非割込み優先権付きMAP／G／1
待ち時間

待ち行列モデルの解析のために考察したものです．しかし，思いもかけず，非常にきれいな結果が出てきたことで著者自身，非常に驚いた覚えがあります．
次に，この系内仕事量分布を用いて各到着流から来る客の実待ち時間を考えます．最初に述べたように，

時間
現時点

到着

図2：系内経過時間

客の待ち時間は到着時点における系内仕事量に等しくなります．しかし，客は MAP に従って到着する

もし系内仕事量が0であるならば，客はシステム

ため，MAPの相によって到着する頻度が異なります．

内にいません．一方，もし客がサービス中であるなら

よって定常状態において客が到着時に見る系内仕事量ば，サービスは先着順で行われるため，サービスを待は，MAPの各相における到着率と相の出現頻度の積っている客はサービス中の客が到着してから現時点まの比で重み付けられたものとなります．以下ではた番

での間に到着したことになります．すなわち，ある時目の到着流から来た客をクラスたの客と呼びます．

点で待っている客は，その時点での系内経過時間の間定常状態におけるクラスたの客の待ち時間をⅣたに到着した客になります．このような考え方に「基づいとし，定常状態においてクラスたの客の到着直後のて待ち行列長分布が満たす式を導出したのですが，そMAPの相をg芸とします．このときブ番目の要素がの結果は，より一般的な状況でも成立する不変式の特1999年3 月号© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

（37）151別な場合であることが分かりました。ここでほ，まず到着した客です。よって（6）より次式を得ます8。

この不変式を紹介したいと思います山∬＊（＋（zん−1）

雄雛鵜か脛轍）e埴＋垂勅』（8）

風ん（若）を時刻藍におけるクラスたの系内客数とし，餓（芭），♂ゐ（￡）をそれぞれ，時間間隔（0，￡jの間のクラス

勉の到着客数ならびに離脱客数とします中 このとき∴・‥・ −≡、．、．・．、∴1

さて，（8）からどのようにして系内容数分布を計算＋（j帆（￡），…鞄（故））仙（♂1（細…錠（窓））すれば良いのでしょうか。上記の系内経過時間に着田するアイデアはかなり以前からあったのですが∴数値が成立し，（Ⅳ1（諾），…鞄（￠））が表現（灯∋戯1，…ヲ戯タ）

計算ができる形に処理できるとは当時思えませんでをもつ定常なマ加ク付きMÅPに支配されていると仮したひ 話は逸れますが，昨年の春，集団到着を許す

定します￠ ここで，クラスゐの系内客数軋頼）の定常

MÅp／α／1の客数分布の新しい計算アルゴリズムを状態における値を瓜勉，諾＝（紬…山ワZp）とし，

思いつきました脚朴これは，時間平均の客数分布が，∴軋直接は関係なさそうなM／G／1型マルコフ連鎖

瞞巨利や…杵柄示の解と同じ分布を持つという点に涯潤したものです血をゴ番田の要素にもつ結合母関数ベクトルをg（z）とこれを思いついた直後，ひょっとすると同じようなします。ここで乱（x）は事象Ⅹの指示関数でサdまた，構造が隠れているのでほないかと思い，山気に計算を定常状態において，クラス鬼の客の離脱直後におけ進めたところ，憲ゴ（れ1，…，れp）＝炉㌃（∬1＝開1，…，るクラス陀の系内客数鳳m（￠）の値を軌（た）とし，∬㌘ニ陀ダ，ぶニブ）をゴ番目の要素にもつ定常状態における待ち客数の結合確率ベクトル評（ml，…，閃㌘）を

翫，メ（g）＝腰［g㌘皿（ゐ）…諸招）1｛瑚］

計算する数値アルゴリズムを得ることができました咄
以下にその概略を紹介します阻 まず定義より，

をブ番目の要素にもつ結合母関数ベクトルを鮎（z）○（〉としますけ このとき呵可と鮎（．冨）の間には次式が成・・1立します仁噂。

0く）∴・i・

・：・・・・．、i

ml＝＝0陀ヂ＝￠です。また（5），（7）より値鞘（ヱ）＝即（∬）戯ゐ／Åたです。

−−‥∵．＿ −・．・

よって批Ⅷ闇雄みlで与えられるβを用いて（8）を変形すると9

ここで購クラス到着率ですやが（十＝（zたml咽た（7）（6）はサービス時間分布の構造，サービス規律あるいはサーバ数などに依存せず，非常に広い範囲のモデル
で成立します。また，単一の到着流の場合の結果仁14】痺重瑚垂…∑…∑z㌃1…

と書くことができます。ただしの拡張になっています。

e一禦許坤）

即（m）（♂）ニ（6）を用いれば待ち行列長分布が満たす式を簡単に得ることが出来ます。以下では、待ち部屋をシステムと捉え，待ち客数を考えますり 定常状態において，クラス ゐの待ち客数を g克 とし，定常状態におけるMÅPの相をぶとしたとき，メ番目の要素工芸（g）が榊）＝薙ぎ1…Z芳Pl｛副Z簑P厨m（柁1，…，陀p）（9）γ乙1≧0 れP＞O
ml＋・汀 ＋関戸≦m＿∠∴ ∴ ● ∴ ・一丁．り：・ト・‥・
ml≧0 れP＞0
れ1十…一打岬≦m

神津離郷＋です。（9）の両辺のz㌘1…Z芸pの係数を比較するこで与えられるような結合母関数ベクトルが（z）を定とにより 諾（㍑1，…，れァ）に対する再帰式を即（m）（￡）

義します。これは（6）のg（z）に対応します。一方と厨m（れ且，…う穐β）を用いて構築することができます。

轡ぬ（g）に対応するのは，クラスぁの客が待ち部屋から出たとき（サービスの開始時点）に待ち部屋に残っている客数です。客は先着順でサービスされるので，これらの客は待ち部屋から出た客の待ち時間の間に

笥5認（38）8（8）の右辺にある積分はクラスゐの待ち時間の間に到着する客数を表現しています．
9この操作は連続時間マルコフ連鎖を雄散時間マルコフ連鎖に変換する一棟化手法として知られていますb© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

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

すなわち，アm（ml，…，↑−p）とγ（m）（β）が計算できれ最後になりましたが，本稿の草稿に対して貴重な御意見を頂いた東北大学の山下英明氏に深謝敦します．

ば諾（托1，…，れP）が計算できるわけです．

ダm（れ1，…，れP）は，P＝1のときの数値計算アルゴリズムが既に知られており，P≧2への拡張は容易

参考文献

です．問題はu（m）（β）の数値計算アルゴリズムでした［1］Q・−M・He： Q11eueS With marked customers， Ad・u・
Ap〆Proあ．，28，567−587，1996・

が，このγ（m）（β）は必ずしも自明でない構造を含んで［2］紀一誠（編）：特集「待ち行列理論の最近の応用」オペ

おり，これを利用することで解決できました．

レーションズ・リサーチ，43（5），258−288，1998．
［3］Dt M・L11CantOniK，S・MeierqHel且stern and Mr F・
Neuts：A single−SerVer que11e With server vacations
and a class of non−reneWalarrivalprocesses， Adv．
Ap〆Prob．22，676叫705，1990．
［4］M．F・Neuts：∫れcわげedgわc九αβf壱c〟￣α±r盲ceβ0′〟／G／才物pe and Their Applications，MarcelDekker，New
York，1989．

まずが（β）の定義と（10）より
0〇∑り（m）（β）zm＝U＊（β一叫m＝0であることがわかります・よって（3）より00∑γ（m）（β）zm桝1一之）∫＋C＋が（∂一叫］［5］高橋幸雄： やさしい待ち行列（2）一等間隔運転は待ちを減らす，，，オペレーションズ・リサーチ，40（12），716−m＝0＝β（1一之）（1−β）Kを得ます．この両辺の zm の係数を比較することによりu（m）（β）の満たす無限個の連立方程式が得られます．この連立方程式を良く調べると，U（m）（β）は，M／G／1型とよばれる構造をもった，あるマルコフ連鎖の定常解と同一であることが分かりました．すなわ

721，1995．

［6］高橋幸雄： 待ち行列研究の新しい潮流（1）一得ち行
列研究の変遷， オペレーションズ・リサーチ，43（9），495−499，1998．
［7］高橋幸雄，牧本直樹： 待ち行列研究の新しい潮流（3）一相型分布と行列解析法， オペレーションズ・リサー
チ，43（11），618−623，1998．
［8］L・Tak乙cs＝ Investigation ofwaiting time problems

ち，通常のM／G／1型マルコフ連鎖に対する行列解析

byreductiontoMarkovprocesses，

法を適用することでγ（m）（∂）が計算できることが明ら

gc壱．ガ肌タ．，6，10ト129，1955．

かになったわけです10．

AciaMath．Acad・【9】T・Takine and T・Hasegawa： The workloadin the
MAP／G／1q11eue With state−dlependent services：Itsapplicationtoaq11e11eWithpreemptiveres11mePrlOr−

6 ぁわりにity， ∫わcん．〟odリ10，183−204，1994．

サービス時間分布が到着流毎に異なる複数の到着流をもつ単一サーバ待ち行列に関する筆者の研究成［10］T・Takineetal・，＝

果を紹介しました．待ち行列理論は，その名が示すと【11］T・Takine： A nonpreemptive p訂iority MAP／G／1
q11euewithtwoclassesofc11StOmerS， JORSJ，39，266−

おり待ち行列長を中心とした議論が多く，通常，待ち行列長を元に待ち時間分布を導出するという手順を経ます．しかし，サービス時間分布が到着流毎に異なる場合，客数の挙動を直接解析することは極めて困難です．一方，系内仕事量，あるいは待ち時間分布を最初に解析し，それを利用して客数分布の解析へと向かうアプローチを取れば，従来，解析が困難と見られていたクラスの問題も解決できる可能性があることが本稿では触れることができませんでしたが，この種の研究では，実際に数値計算するための数値的に安定したアルゴリズムを示すことが極めて重要です．今まで各種の問題に村して様々なアルゴリズムが提案されていますが，大規模な問題に対しては，まだ，十分とは言えません．今後，解析が困難と思われているモデルに対して挑戦していくとともに．より効率の良いア
ルゴリズムの開発を進め，将来，それらを一つのソフ
トウェアパッケージにまとめたいと思っています．
10サービス中の客も含めた系内客数の結合分布も同様に計算1999年3 月号

290，1996．

［12］T・Takine： Acontin11011S VerSionofma七rixTanalytic
methodswiththeskip−freetotheleftproperty，Stoch．

〟od．，12，673−682，1996．
f13］滝根哲哉，村田正幸： 通信網における待ち行列一理論の応用と課題−， オペレーションズ・
リサーチ，43（5），264−271，1998．

［14］T．TakineandY．Takahashi： OIltherelationshipbe−
tweenq11e11elengthsatarandominstan七andatade−
Partureinthestationaryque11ewitllBMAParrivals，
gfocん．〟od．，14，601−610，1998．

分かります．

できます．

Meanwaitingtimesinnonpreemp−tivepriorityqueues withMarkovianarrivalandi．i．d．
SerViceprocesses， Perjbr．Eval．，20，13ト149，1994．

［15］T・Takine： Thenonpreemptive priority・MAP／G／1
queue，

toappeal・in Opns．Res．，1999．

［16］T・Takine：
Anewrecursion tocomp11tetheq11eue
lengthinthestationaryBMAP／GI／1queue， Bubmit−
tedforp11blication．
［17］T．Takine： Queuelength distrib11tionin a FIFO
Slngle−SeVerq11e11eWithmultiple arrivalstreamshav−ingdi鮎rentservicetimedistrib11tions，publication．
【18］T・Takine：

s11bmittedfor

Jointq11e一ユelengthdistributioninasta−tionaryqueuewithmultiplearrivalstreamsgoverned
byaMarkovchain，

submittedforp11blication．

【19］滝根哲哉： 構造化されたマルコフ連鎖と待ち行札 シ

ステム／制御／情報，43（3），且999．

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

（39）153