待ち行列研究の新しい潮流（1）

待ち行列研究の変遷
高橋 幸雄
l州l…‖‖‖川‖‖‖‖‖‖‖‖‖‖‖‖‖‖‖‖‖‖‖‖‖‖‖‖‖‖‖‖‖‖‖‖‖‖‖‖＝‖‖‖‖‖‖‖‖‖＝‖‖‖‖‖‖‖‖‖‖‖‖‖‖‖‖‖‖‖‖‖‖‖‖‖‖‖‖‖‖‖‖‖‖州…lll…州l川Ill川Ill川Ill川…l川…ll……l川…川Il川…川…m

1． はじめに

2．2 第1期黄金時代

A．K．Erlangによって待ち行列の研究が始まってからErlangの研究以来，数学が実際の問題に役に立つ面白90年以上が経った．この間，この分野における研究はい研究分野だということで，待ち行列は多くの著名な研幾度となく壁にぶっかってはつぎっぎと新しい概念や理究者の関心を集め，とくに1950年代にはその後の待ち論を持ち込んで，今なお理論体系の拡大・精緻化と新し行列理論において重要な役割を果たす基本的概念が多数い応用分野の開拓が続けられている．このたび講座『や出されている．年表には書ききれなかったが，C．Palm，さしい待ち行列』［4］の続編を本誌に書かせていただく

J．W．Cohen，J．Keilson，J．Gani，N．U．Prabhuなど機会が与えられたので，今回は待ち行列研究部会のメン

いったビッグネーム達が活躍を始めたのもこの時期であバー数人によって，研究の最前線がどのようになっている．また応用の面でも，電話に限らず，生産システム，るかを『待ち行列研究の新しい潮流』と題して5回シ流通システム，交通システム，サービスシステムなど，リーズで書かせていただくことにした．

いろいろな分野に待ち行列が積極的に応用された時期で本稿では，新しい潮流を説明する前提として，筆者のもあった．これが待ち行列研究における第1期黄金時代

個人的な待ち行列研究史観を紹介させていただきたい．

である．我が国で待ち行列の研究が開始されたのもちょ

これは，研究の歴史を眺めることによって，現在進みつうどこの頃で，資料［2］によると，河田龍夫先生や本間

つある最先端の研究の意味が多少ともわかりやすくな鶴千代先生による論文が1955年に出版されている．

ることを期待してのことである．添付の年表は参考のた

この第1期黄金時代の成功に刺激されて，それ以後，め作製したもので，網羅的でもまた必ずしも公平でもな発表される論文の数も鰻登りに増加していったが，やがい．本文を含め論文の取り上げ方に不満な方が大勢居らて大きな壁に突き当たった．応用上もっとも基本的なモれると思うが，個人的な見解ということでその点は平にデルであるM／G／βの解析が行き詰まったのである・多ご容赦願いたい2くの研究者がこの解析にチャレンジし敗れ去った．これに引導を渡したのが1966年に書かれたJ，F．C．Kingmanの代数的解析の論文であった．これは従来の研究方法の2。待ち行列研究の流れ延長線上ではM／G／βの解析は無理であることをはっき

2．1 待ち行列研究の始まりりと示したものであった4．それでも待ち行列研究はひ

待ち行列の研究は，デンマークの電話会社技師A．K．

るんだわけではなかった．

Erlangによる1907−1920年の研究に始まるとされる．

これはちょうど電話の交換機が開発され，電話の需要見込みに対してどのくらいの交換機を設置したらよいかという問題が契機であった・待ち行列研究はOR（オペレーションズ・リサーチ）という言葉が生まれる20年以上も早く始まっており，これがOR史の実質的なスタートでもある3．

1この研究は一部，科学研究費補助金基盤研究（A）（1）課題番号08308025の補助を受けている．
2この稿を執筆するにあたり，森村英典の資料［2］，R．Syskiのサーベイ論文［3］などを参考にした．

3p．M．S．BlackettらによるORのはじまりが1937年，J．von
Ne11mannと0・Morgensternによるゲームの理論が1944
年，G・B・Dantzigによるシンプレックス接が1948年，C．E．
Shannonによる情報理論が1949年，R．Bellmanによる動的計画法が1952年である．

たかはしゆきお東京工業大学大学院情報理工学研究科〒152−8552目黒区大岡山2−12−2
1998年9 月号

4筆者は大学院の授業で森村先生からこの解説を聞かされ，博士論文の研究テーマを待ち行列からマルコフ連鎖に変えた．こ
うした研究者が多数いたものと思われる．

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

（33）495

2血3 第2期黄金時代

表1：待ち行列分野の主要な研究

このKimgmanの論文以後，新しい待ち行列研究の方事

項向を巡って多くの研究者が模索を開始した。その模索の待ち行列の最初の論文（臥Ⅸ．E舶ng）

結果が出だしたのが且970年代の半ばから80年代へか

M／M／β／β，M／の／βフM／M／βの解析

けて，とくに乱975年からの数年間である巾 これが第2（臥儲・Er且ang）の黄金時代であろう。

鱒／G／1の平均待ち時間（A・Ya馳im七chine）

年表をみると，1975年前後，計算機の飛躍的な発達出生死滅過程（W．馳iler）に刺激されて，計算機や通信システムに対する新しいモケンドし−ルの記号（D。G・Ⅸemぬ且り

デルの提案やモデルの整備，待ち行列ネットワークへのG耳／G／温の研究（の・Ⅴ−mind且ey）

関心の高まり，アルゴリズム的方法論の台頭など，その隠れマルコフ法（Ⅲ・G．Ⅸenぬ11）成果が一気に吹き出してきたのがわかる．

G瓦／G／βの平衡状態の存在（』．Kiefbr＆♂．
Ⅵ70肋wi七z）

待ち行列の解析というと従来は数学的な解析がほとんどであり，待ち時間分布のラプラス変換や積分方程式を求めるなどといったことが目標であった。しかし
蹴imgmamの論文でその道が（少なくともM／G／βに対しては）閉ざされてしまった。そこで待ち行列を解析するということの意味を変え，数値的な計算方法（アルゴリズム）を示すことによって解析したことにする，とい

補助変数法（Ⅲ▲Cox）

仮待ち時間過程（m・Takacs）
日本での論文第且号（T・Kawata）

M／M／βの出力過程（P。』．Burke）
待ち行列ネットワーク（飢民∴摘ckson）
M／G／且の待ち時間分布岬。C・R．Pollaczek）
M／α／c平均待ち時間の近似式（A．MLmeeう「解く」という概念の変更，大げさにいえばパラダ＆P・A。軋omg七Om）

イムの変革9 が行われたのである。この変化を示す象

リトルの公式（』。D・C．Li七も1e）

徴的な研究成果が相型分布と行列幾何形式解，およびM／α／βの代数的取り扱い（解析の難しさのBCM炉型待ち行列ネットワークの積形式解とそれに対するMVÅ（平均値解析法）などの数値解法である。
相型分布5は，ある種のG‡／G／βモデル（後にいう㌘H／P猥／c）をme七hodofstages（相の方法）で数値計算しようと9 ネ】ミングなしで導入されたのが最初であった。それをみたNe㍑七sが相型分布（phaseぺypedistriMbution）と命名して，広く使われるようになった℡ 正の値のみをとるどんな分布も相型分布を用いて任意の精度で近似できるので，この相型分布を持ち込むことによってM／G／βモデルの問題は，実質上解決されたわけであるd さらにPH／P親／cの数値計算法の研究は，行列幾指摘）（本）（』且C。Kingman）

流体モデル（本）（G且Newell）
漸増入力モデル（0−Hashida＆M．勒舶）㌘H／P掴／cの数値解析（Y．Takahashi＆Y．
甘akamり，相型分布（M．F∴Nel止S）

BCMP型待ち行列ネットワーク，積形式解岬・Basket七他）9 たたみ込み法（M．Reiser
鮎HⅥKobayashi）

計算機システムへの応用（本）（m．Kleinrock）
可逆性と積形式解（本）（『．P。Kelly）

MVA（平均値解析法）（M・Reiser＆S鼠mavemberg）
待ち行列ネットワークの近似解析（Y．

何形式解という新しい理論的枠組みを生み出すきっかけ

甘akahas払拭・Miyaha柑＆T・Hasegawa）にもなった。これに連なる研究は，現在でも活発に行わ

行列幾何形式解（本）（M。『．Neuts）

れている。

点過程アプローチ（本）（P・Br昌maud，P．

一方，待ち行列ネッ虹り軸クの研究は応用分野から鮒amkem，D中K6nig，U・Arnd七＆Ⅴ・Schmidも）の要請が研究を引っ張った．コンピュータなどへの応用

pAS甘Å則（R・W・Ⅵわ1ff）を強く意図したK且eimrockの本にみられるように，コ率保存則（M・Miyazawa）

ンピュータシステムの性能評価が待ち行列の問題とし遊休のあるM／G／1の分解定理（S．W。てとらえられ，待ち行列ネットワークの利用が試みられ始めた。しかしサービス時間分布が指数分布に限られ5状態数有限の吸収的マルコフ連鎖における吸収時間の分布と恥rmamn＆R」臥Cooper）
ポ＼H】−−−リングシステム（本）（耽・甘akagi）

自己相似入力をもつ待ち行列（‡。Norros）
到着過程の長期依存性（J。Beran他）

して表される分布を相型分布とよぶ．
穐96（34）© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

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

るJacksonモデルでは適用範囲が狭すぎるという不満

レーション，待ち行列の制御や最適化，そして統計的取があった．

り扱いなど，単なるモデル解析から一歩踏み出した問題

これをかなりの部分解決したのがBCMP型待ち行列も種々研究されはじめ，それらは現在でもまだ研究が続ネットワークである．積形式解を持っという性質を保っけられている．

たままで，まず客のクラスという概念が導入され，クラ2．4 待ち行列研究の拡大と研究グループの分スによってネットワーク内の異なるルートを指定するこ裂とが可能となった．さらにサービス分布についても，先着順サービスでは依然として指数分布に限られるもの

このように第2期の黄金時代を迎えた待ち行列研究の，割り込み後着順（LCFS−PR）やプロセッサーシェアは，理論から応用までその幅を急速に拡大していった．

リング（PS）などのサービス規律のときにはクラスごと筆者流に分類すると，これらの研究はつぎの3つに大別に異なる相型分布6が指定できるようになった．そしてできる7．

このようなBCMP型待ち行列ネットワークの解を求め

a）新しい応用分野，とりわけ情報通信分野，からの要るためのたたみ込み法やMVA法（平均値解析法）といっ請による新しいモデル構築と理論体系の整備た数値解析法も開発された．コンピュータメーカーはこb）モデルの性能評価尺度を数値的に求めるアルゴリズ

ぞってこのBCMP型待ち行列を解析するソフトウェアを作製し，製品導入の際には必ず事前にシステムの性能評価を行うようになった．実用上もその功績はたいへん大きかったのである．

ム的方法の研究C）ある範囲のモデルに対して一般的に成立する理論の研究

上でみたように，第2期黄金期と一口にいっても，そこれらアルゴリズム的アプローチや待ち行列ネットのピークはこの3つの領域で少しずれている．これは，ワークの研究に少し遅れて，1980年代に入ってからはこれら3つの領域が独立に発展しだしてきたことを反映

いわゆる理論派の活躍の場であった．点過程，マルチンしている．別な言い方をすると，幅が広がりすぎて，待ゲール，パーム測度などの高度な数学的道具を駆使して，ち行列研究全体を把握することが難しくなり，各研究者

従来，個別のモデルに対してのみ成り立つことがわかっがそれぞれ自分の専門グループに閉じこもって研究をすていた性質を，より一般の広いクラスのモデルに適用でるようになってしまった．それに伴って各領域内での研きるよう拡張する，といったことがさかんに行われた．

究は深化していったが，画期的な斬新なアイディアが出これらの成果のひとっがPASTA（PoissonArrivalsSeeにくくなった．この意味で，待ち行列研究は再び行き詰TimeAverages）である・これは，客の到着時点でのシまったのである8．この閉塞感を打ち破ることができた

ステムの状態分布と任意時点でのシステムの状態分布のは，やはりa）の新しい応用分野であった・

が，到着過程がポアソン過程のときは等しくなることを示したもので，待ち行列理論をわかりやすくした功績は2．5 情報通信分野からの刺激
待ち行列理論は，当初から電話という情報通信分野へ大きい．

さらに率保存則などをはじめとする各種の保存則（con−の応用によって理論的な発展にドライブがかけられてきSerVationlaws）や不感性（insensitivity），積形式解の成た．この流れはほぼ1世紀近くたった現在でもなお続い

立条件，サーバ遊休（vacation）のある待ち行列におけている．表2は，情報通信・コンピュータ分野におけるる分解定理など，理論的な研究がかなり進展した．

技術革新によって，新しいモデルや解析が生み出されてこの時期，特殊な形をした待ち行列の解析も活発に行いった例をあげてみたものである．

われた．いろいろな待ち行列規律，優先権，スケジュー

このような応用が待ち行列研究に如何に沢山の研究材

リン久 タイムシェアリン久バッファーシステム，窓口料を提供し，大きな影響を及ぼしてきたかわかるであろの数が変わるモデル，溢れ過程，出力過程，など，様々う．第2期黄金時代に種を撒かれた研究が深化し，斬新なモデルが提案され研究された．また数値計算やシミュ
6原論文ではCox型分布でよいことが示されている．Cox型分布というのはそのラプラスーステイルチェス変換が有理関数であるような分布で，そのクラスは相型分布のクラスよりほんの少し広い．

1998年9月号

7syski［3］ではa）とc）の2つのグループに分類している．しかし筆者は自分がそのグループに属していることもあり，b）の存在が大きかったのではないかと考えている．
8誤解の無いように付け加えると，これは決して研究活動が低調になったというわけではない．相変わらず沢山の研究論文が書かれ，国際会議なども盛況を極めている．
© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

（35）49丁なアイディアが出にくくなってきてからも，この情報通信分野における応用は新しい研究材料をつぎっぎと供給し続けている。

たとえば，近い将来の主力情報通信システムと考えられているÅ甘Mネッ睦ワ恥タでは，マルチメディア
表2：情報通信申コンピュータ分野で生み出された待ちに対応したいろいろなタイプのトラヒックがこのネット行列モデルワークに流される。そのうちのひとつ，ビデオデータは，従来の待ち行列モデルで考えられていたポアソン
且．回線交換網

入力や再生過程入力などとは全くといってよいほど異電話アナログ回線，データ通信，デジタル回線⇒臥餉喝による待ち行列モデル

再呼，溢れ呼9 迂回⇒Ⅸemdふ且1による待ち行列モデルなった入力パターンを有している．統計的に解析すると
鼠omg鰍柑mge鮎pem通e弧Ce（長期依存性）という性質がみられ，この性質から平衡状態とか定常確率などといった，これまでの待ち行列解析ではもっとも基本的な概念

乱ノバケット交換網Å鼠PANET（パケット多重，パケット交換）⇒離散待ち行列，集団待ち行列，待ち行列ネットワーク

3。ネットワークプロトコルと考えられていたものさえも，その存在性を覆されてしまう可能性がある。ではどうしたらよいであろうか。これは現在，多くの待ち行列研究者が必死になって取り組んでいる大問題である．

誤り再送制御⇒個別モデルÅ甘Mがもたらした研究上の新しい考え方のもうひと

フロー制御＝＞待ち行列ネットワーク
別owComもro且）、プロトコルスタック（参照モデル、HD監C、Ⅹ。25、甘CP／‡P）、つの例として，セル損失率の評価というのがある。A甘M
では情報を一定の長さのセルと呼ばれる小さな単位に分割して高速で送信する。このセルが叫部でも欠けてしま

4．マルチアクセス

うと全体を復元することができなくなる．そのためセル

AmOHA，紺地ermet＝＞ランダムアクセス
甘okem−Ring⇒ポーリングシステム
5。ÅTMネットワークの損失確率をできるだけノ」＼さく押さえたい。実際にはたとえば且0−9などという数字が検討されている。この値はこれまで待ち行列研究で扱っていた呼損率（たとえばA甘Mの多重効果⇒流体モデル
各種の入力制御（CBR，VBR，ABR）⇒Bursもy入力モデル，長期依存性
セル廃棄率⇒流体モデル，大偏差理論

10−2のオいダー）などとくらべて圧倒的に小さい。そのためこの値を評価するのにシミュレーションは使えな
い山 いくら計算時間をかけても精度のよい評価値が得られないからである。そこでこのセル損失率の評価には，

臥移動体通信
Hand血0鱈制御＝＞複数待ち行列モデル

待ち行列モデルにおける系内客数の分布の裾が指数的に減少する，という性質を利用することが一般的である。

基地局設置政策⇒最適化問題

待ち行列への入力過程が従来のモデルのようにポアソ

7。コンピュータシステム

時分割⇒プロセッサーシェアリング規律
ページング＝〉個別モデル

ン過程と見なしてよいならば，この評価はそれほど難しくない，しかし上で述べたように入力過程そのものが今までのものとかなり異なっているとすると，セル損失率優先権＝＞優先権のあるモデルの評価方法も新たなものへ変えていかなければならな

コンピュータシステム性能評価＝〉BCMP型待ち行列ネットワーク

いq現在では且a柑edevia七iontheory（大偏差理論）など分散システムと負荷分散⇒最適化モデルを使ってこの問題へ取り組む試みなどが活発になされている。

認￠ 這甑からの待ち行列研究
現在，待ち行列研究は黄金時代の狭間にあるのか，あるいは第3期黄金時代に突入したのか，その判断は今は難しい。少なくとも新たな方法論を用いて解決しなけれ
増98（36）© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

オペレーションズ。リサーチばならない問題が待ち行列研究に突きつけられているこで，できたら比較してお読みいただきたい・また（3）でとだけは確かである．

は，計算機を利用したアルゴリズム的アプローチがどの第2期黄金時代から，上で述べたように研究者グルーような考えで研究が進められ，それによってどのようなプが割れ始めてきている．しかし，新しいモデルを開発計算が可能になったか，またその過程で開発された理論し新しい理論体系を作る上では，応用分野からの刺激が体系がどのような果実をもたらしたかを紹介する．

絶対的に必要である．画家がいつまでたっても写生や素つぎに2回にわたって，情報通信分野での応用から刺描を欠かせないのと同じである．これからも理論家とい激されたまさに現在進行形の研究を紹介する・まず（4）えども，待ち行列の実際問題への応用を，そして混雑現では，ATMネットワークなどへを念頭に，新しいタイ象に対する深い洞察を，追究していくことがますます必

プの入力過程モデルを紹介する・そして（5）では，その要となっていくであろう．

ような入力過程を持った待ち行列モデルの解析がどのよ

そして情報通信分野に偏りがちであった応用を，さらうな形で進行しているかを紹介する．に広い分野に拡大していくことも必要であろう．待ち行

これら一連の講座から，現在の待ち行列研究がどのよ

列の3大応用分野といわれる情報通信，コンピュータ，うな方向を向いて進みつつあるか，その感じだけでもく生産システムのうちの後2つの分野への応用を拡大すみ取っていただければ幸いである．そして，新しい感性ることはもちろんのこと，広く社会システムに関わる応を持った若い諸君が，新しい待ち行列研究へ向けて出発用を一歩一歩広げていくことが大切である．とくにこれするきっかけにしていただけたらと念じている．

まで待ち行列理論が比較的不得意としてきた人間の行動に関わる分野への応用を今こそ考える時期であろうかと思う．

引用文献［1］宮沢政情（1998）， 待ち行列ネットワークと積形式

待ち行列は，その名前から，人間としての客をイメー

解， オペレーションズ・リサーチ，4乱ジしてモデル化が進められてきた．しかし，そこで扱われている人間は個性を持たず，極端にいえば石ころと同［2］森村英典（1989）， 待ち行列研究事始め， シンポジじであった．だからこそ理論がここまで発展できたとい

ウム報文集「情報ネットワークのトラフィック評価えなくもない．しかし情報通信分野でも 平衡状態 とに関する基礎的研究」，pp．34−40．

いう概念を突き破る必要性がではじめた．客に個性が求められだしたのである．平衡状態の呪縛から逃れられれば，もっと個性豊かな人間を相手にした待ち行列モデル，混雑現象モデルを扱うことができるかもしれない．待ち［3］Syski，R．（1997），

theory，A personalview ofqueueing

in伽ntiersinQueuein9，ModelsandAp−pg戎cα如mβ盲乃∫c豆eγlCeαれd居れタ豆meer窟叩，Dshalalow，

JqH・（ed・），CRCPress，BocaRaton，pp・3−18・

行列研究はまだまだ夢いっぱいの世界である．
［4】高橋幸雄，他（1995−1996）， 入門講座：やさしい待4． この講座の内容

ち行列（1）〜（4），（補遺） オペレーションズ・リ

この講座のシリーズは，このような待ち行列研究の最前線がどうなっているかを紹介することを目的に，つぎサーチ，40，pp．649−654，pp．716−721，41，pP．35−40，PP．100−105，pP．106−107．のように構成することにした．まずはじめに，第2期黄金時代に始まった研究がどこまで深化したかを見ていただくために，2つの稿を用意した．
（2）では，補助変数法と呼ばれる考え方によって，一般分布を含んだ待ち行列モデルをマルコフ過程で記述することによって，その定常分布を積形式解の形で導けること，そしてそれが待ち行列ネットワークへも拡張でき，積形式解を持つための条件などが得られることなどを紹介する．このネットワークの部分は先月号の宮沢政情氏の「研究最前線」［1］と重なるところもあるが，研究者によって問題への接し方がかなり違うよい例でもあるの
1998年9月号© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

（37）499