文教大学大学院 ■ 情報学研究科■ IT News Letter ■待ち行列理論文教大学大学院情報学研究科 教授

竹田仁†

Hitoshi Takeda†
あらまし待ち行列理論は，行列を作るような混雑した現象を理論的に調べ，それに関する対策を立てて混雑を解消させる学問であり，オペレーションズ・リサーチ（OR）の中で一つの重要な研究分野である．この理論は歴史的にも古く，電話通信における待ち行列から発達して，その後，数多くの論文が発表され，理論的側面および実際問題への応用は，大きく発展してきた．その応用の一部を紹介する．
キーワード：確率論，Kendall の記号，リトルの公式，マルコフ過程，状態平衡方程式

トワーク系となる．ネットワーク系は異なる窓口で 2 回以

1. は じ め に上のサービスを受ける．ネットワーク系の中でも生産管理

待ち行列理論（queueing theory）は，ＯＲ手法の中できや交通問題で特に重要な直列型（タンデム型）がある．直わめて古くから研究されてきた理論で応用範囲も広範囲に列型で最も単純な２段の場合でも第一段の窓口に到着して，およぶ．待ち行列理論の先駆者は，1909 年にデンマークのサービスを終了した客が第二段の窓口に入って，サービスA.K.Erlang の発表した The Theory of Probabilities andTelephone Conversations という電話交換機の呼損率の研を受け，そのサービスが終わり退去するまでを問題とする．

1)

第二段の窓口の前に待ちを許す事を認めても，損失系にし究から始まっている ．その後，確率過程論の導入によっなければ第二段の待ちがいっぱいになってしまったとき，第て M/G/1 型，GI/G/1 型待ち行列理論の研究が進められ一段の窓口でサービスが終了した客の行き先がないので，第てきたが，1966 年 Kingman の発表した On the Algebra

二段の待ちが空くまで第一段で待つことになり，第一段窓of Queues で一般的な複数サーバモデルの理論解析が極めて困難であることを明らかにした．その結果 M/G/s の解口のサービスに影響を及ぼす．このような点が，直列型の難点の一つとなっている．また，直列型で M/G/1(N) の析で行き詰まって以来待ち行列の必要性から，今までの数出力分布が入力と同じ M になるのは G ≡ M かつ N ＝∞学的解析（待ち時間分布のラプラス変換や積分方程式を求のときに限り，幅広い現実の問題に対して有効となる直列める）から数値的なアルゴリズムを示す方向に研究の方向型待ち行列システムの理論的解析は少ない．これも待ち行が変更された．一方ではコンピュータの急激な性能向上に列の困難性によるものである．しかし，直列型待ち行列シよりモデルを作りシミュレーションにより簡単に結果を導

ステムは情報通信，生産システム，コンピュータ・ネットけるようになった．

ワークにおいて特に重要なタイプの１つである．

通信分野においては，1969 年 ARPANET(米国) でパケッ

直列型待ち行列システムで問題になるのは，各段への客ト交換ネットワーク設計問題でパケットを処理単位とし，パの到着分布である．上記に示したように第一段への到着が2)ケットの配送処理が研究された ．1974 年 Kleinrock の発

ポアソン分布で，各段でのサービス時間が指数分布に従い，表した Queueing Systems というパケット交換ネットワー

各段の待ちに制限がない場合は，各段の客の到着はポアソ

クの研究がコンピュータシステムの性能評価のバイブルとン分布になるので各段を切り離し各段で解析できるので都なった．

合がよいが，ポアソン到着，指数サービスでないと，その2. 待ち行列について 3)4)5)
待ち行列モデルを大きく分類すると単一ノード系とネッ段からの出力が解析できなくなる．ネットワークが複雑になるとポアソン到着，指数サービスの場合でも平衡方程式で解けることになるが簡単な場合しか解かれていない．計算機システムの場合，処理に優先権を付けたり，割込みを2011 年 8 月 5 日受付† 〒 253–8550 神奈川県茅ヶ崎市行谷 1100

許したり，フィードバックなどを許すと非常に難しくなる．

takeda@shonan.bunkyo.ac.jp

実際のモデルではバッファがいっぱいになればバッファが† Graduate School of Infomation and Communication,
Bunkyo University

空くまで待つことになりこのような条件を考慮した場合はより難しくなる．

文教大学大学院情報学研究科 IT News Letter Vol. 7, No. 1, pp. 1〜2 (2011)(1) 1

3. 有限待ち行列と直列待ち行列について待ち行列理論は条件が付加されるとシステム内の状況が大きく変わる．今回は有限バッファシステムと無限バッファシステムとの比較，直列二段型待ち行列システムにおいて一段目と二段目の窓口間でバッファがない（一段目の窓口サービスが終了した客は二段目の窓口が塞がっていれば一段目の窓口を退去できない）ブロッキングが生じるモデルについて考察する．

3. 1 有限バッファシステムと無限バッファシステムとの比較

B ：平均ブロッキング時間
客が到着してから退去するまでの平均系内時間は Wq +S1 + B + S2 となるが Wq + B を求めるのは特別の場合を除いて困難である．しかし， Wq + B の推定値はS1 , S2 が独立かつ同一到着過程では (RSQ：reduced single
server queueing systems) 客の平均待ち時間 Wq∗ とすると，∗∗
Wq + B >= Wq ,Wq + B ≃ Wq が証明されている．よって， Wq + B の値は Wq∗ を用いて推定が可能であり，Wq∗の値は GI/G/1 の結果が使用できる．以上の結果よりコンピュータシステムのタンデムシステムとデプレックスシステム（図１との比較だと M/M/2）の比較が可能である．

6)

システムの性能評価のために M/M/1(N) 待ち行列システムでモデル化した場合 M/M/1 とバッファサイズが4. お わ り に有限な M/M/1(5) レベルでは棄却率は容易に求められる

これまでの待ち行列理論の研究は人間のメンタル面を考が，モデルが複雑になれば困難になる場合多い．今回は慮せず解析がなされた. しかし，生産システム，情報通信

λ = 1.5, µ = 2.0（ρ = 0.75 ）について比較する．

分野においても 平衡状態 という概念を破る必要性がある．通信トラヒック理論（待ち行列とは確たる境界がない）

表 1 M/M/1, M/M/1(5) 比較
バッファ数 M/M/1 の確率 M/M/1(5) の確率00.25000
0.3041310.18750
0.2281020.14063
0.1710730.10547
0.12830
40.07910
0.0962350.05933
0.0721760.04450
70.03337
80.02503

表 2 M/M/1, M/M/1(5) 比較
M/M/1 M/M/1(5)
システム内バッファ数 3.00000
1.70092
待ちバッファ数2.25000
1.00505

表 1，表 2 の結果からもバッファサイズを有限にした場
合，システム内の状況を比較できる．この結果，システムの性能評価では有限バッファはシステムに大きな変化をもたらす．

3. 2 直列二段型待ち行列システム

ではシステムの性能評価を過度状態でシミュレーションする必要性も出ている．また，平均値だけで議論していくとラッシュ以外のときには，低いトラフィック密度で運用されているので実感と合わない事が発生すると考えられる．
〔文献〕

1）Fell,W.:An Introduction of Probability Theory and Its Applications, John Willey, 1950
2）Kleinrock,L.:Queueing Systems vol.1 ,Wiley and Sone,1975
3）森村英典，大前義次：待ち行列の理論と実際，日科技連，1962
4）本間鶴千代：待ち行列の理論，理工学社，1966
5）鈴木武次：待ち行列，裳華房，1972
6）守谷栄一，竹田仁：経営数学，日本理工出版会，1992

たけ だ竹田ひとし仁 1947 年生．1977 年 3 月工学院大学
大学院工学研究科博士課程満期退学．工学博士．1988
年文教大学情報学部専任講師に着任．1992 年同助教授，1996 年同教授に就任．2005 年 4 月より大学院情報学研究科情報学専攻教授を兼ねる．2009 年より 2011 年まで，大学院情報学研究科研究科長．現在，情報学部学部長．横浜国立大学工学部非常勤講師．主な著書は，情報科学とコンピュータ (日本理工出版会), 経済・経営のための基礎数学（実教出版）, 産業社会と情報化 (日本理工出版会), 経営数学 (日本理工出版会), 図解エレクトロニ
クス用語辞典 (日刊工業新聞社) など 22 冊．文教大学
大学院情報学研究科では「シミュレーション特論」および「シミュレーション演習」を担当．

モデルを図１に示す．一段目，二段目のサービスをそれぞれ S1 , S2 とし S1 , S2 の間での待ちは認めない．

図 1 モデルの概略図

記号を以下のようにする．

Wq ：平均待ち時間
S1 ：一段目のサービス時間
S2 ：二段目のサービス時間
2 (2)文教大学大学院情報学研究科 IT News Letter Vol. 7, No. 1 (2011)