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

竹 田仁†

Hitoshi Takeda†
あらまし待ち行列理論は，顧客がサービスを受けるために行列を作るような混雑した現象を理論的に調べ，それに関する対策を立てて混雑を解消させる学問であり，オペレーションズ・リサーチ（OR）の中で一つの重要な研究分野である．
この理論は歴史的にも古く，電話通信における待ち行列から発達して，その後数多くの論文が発表され，理論的側面および実際問題への応用は大きく発展してきた．今回はその応用分野で特に重要なネットワークを研究する場合，既に研究されているコントロール問題の一部を紹介する．

キーワード：確率論，Kendall の記号，リトルの公式，マルコフ過程，状態平衡方程式

1. は じ め にを及ぼすのかを解析する必要がある．これらの問題を解決するにはどのようなコントロールが可能かなどを知る必要

待ち行列理論（Queuing Theory）は，OR 手法の中でがある．待ち行列ネットワークにおいても待ち行列のコンきわめて古くから研究されてきた理論で応用範囲も広範囲トロールにより系内の様子が大きく変化する．今回は， モにおよぶ．待ち行列理論の先駆者は，1909 年にデンマーク

デルによるサービス規則の違いについて平均系内滞在時間の A.K.Erlang の発表した「The Theory of Probabilitiesを示す．

and Telephone Conversations」という電話交換機の呼損率の研究から始まっている 1) ．その後，確率過程論の導入に

2. 待ち行列のコントロールについて

よって M/G/1 型，GI/G/1 型待ち行列理論の研究が進めら

待ち行列モデルで待ち時間を減少させる方法はサービスれてきたが，1966 年 Kingman の発表した On the Algebra

順序を変える事により可能である．サービス順序は以下のof Queues で一般的な複数サーバモデルの理論解析が極めて困難であることを明らかにした，その結果 M/G/s の解析で行き詰まって以来待ち行列の必要性から，今までの数4 通りがある．
(1) 先着順サービス：First-Come First-Served (FCFS)
待ち行列モデルにおいて, 到着した順にサービスを施学的解析（待ち時間分布のラプラス変換や積分方程式を求すサービス規律．最も単純なモデル，先頭から順に実める）から数値的なアルゴリズムを示す方向に研究の方向行する．長くかかる客が窓口を占有することがあるのが変更された．一方ではコンピュータの急激な性能向上にで，スループットは低くなる．同じ理由で，ターンア

よりモデルを作りシミュレーションにより簡単に結果を導ラウント時間，待ち時間，応答時間は長くなる可能性

けるようになった ．

がある．

2)

通信分野においては，1969 年 ARPANET(米国) でパケット交換ネットワーク設計問題でパケットを処理単位とし，パケットの配送処理が研究された．1974 年 Kleinrock の発(2) プロセッサ・シェアリングサービス：Processor-Sharing（PS)
システム内に n 人の客がいるとき, それぞれの客に対して窓口のもつ能力を 1/n ずつ割り当て, 同時にサー表した Queueing Systems というパケット交換ネットワービスを施すサービス規律．従来から活発に研究されてクの研究がコンピュータシステムの性能評価のバイブルといる．PS 方式の解析はジョブの到着過程がポアソン到なった．

着のときのモデル (M/G/1) に限定されているという待ち行列ネットワークでは，ボトルネックはどのノードか，あるノードの混雑が他のノードの混雑にどの様な影響問題がある．
優先権 (priority) によりサービスの順番を定める優先権待ち行列 (priority queues) には, 高い優先権の客2015 年 4 月 17 日受付† 〒 253–8550 神奈川県茅ヶ崎市行谷 1100
takeda@shonan.bunkyo.ac.jp

が低い優先権の客のサービスに割り込む割込優先権と割り込まない非割込優先権がある．系内の状態により† Graduate School of Information and Communications,
Bunkyo University

定まる内部優先権としては, 他の客のクラスとの相互

1100 Namegaya, Chigasaki, Kanagawa 253–8550, Japan

関係により定まるものや, 待ち時間や経過サービス時

文教大学大学院情報学研究科 IT News Letter Vol. 10, No. 2, pp. 7〜 8 (2015)(3) 7

間等の客の系内での状態により定まるものが考えられる. 待ち時間を減少させるには, サービス時間が最短の客からサービスする最短サービス時間順待ち行列がある.

(3) 非割り込優先権：Nonpreemptive-Priority(NP)
優先権の高い客が行列の先頭に並びサービスを受ける．

(4) 割り込み断続優先権：Preemptive-Resume(PR)低い優先権の客のサービス中に高い優先権の客が到着した場合，低い優先権の客のサービスを一時的に中断

表 1 サービス規則による平均系内滞在時間

λ1 : λ2 = 2 : 1 µ1 : µ2 = 2 : 1
ρ
0.1
0.5
0.9
FCFS 0.038 0.354 3.326
PS0.037 0.333 2.990

NP0.037 0.333 2.501

PR0.037 0.306 2.378

し優先権の高い客のサービスを行う．再び一時的に中λ1 : λ2 = 2 : 1 µ1 : µ2 = 5 : 1
ρ0.1
0.50.9

断された客のサービスを行うときは中断された残りのFCFS 0.039 0.442 4.749

サービスを受ける．

PS0.037 0.333 2.991

NP0.039 0.381 2.696

PR0.036 0.302 2.400

3. 待ち行列の規律について到着する客の並び方やサービスをする場合の客の選定方
法を待ち行列の規律という．今回は最も簡単な M/M/1 モ
デルつまり 2 種類の異なった客はパラメータ λ1 , λ2 のポアソン過程に従って到着し，それぞれ平均 1/µ1 , 1/µ2 の指数

λ1 : λ2 = 2 : 1 µ1 : µ2 = 1 : 10ρ
0.1
0.50.9FCFS 0.041 0.521 6.006
PS0.037 0.333 2.985

比により，その客に対するサービス規則の違いについて平NP

0.041 0.424 2.987

均系内滞在時間を比較する．

PR0.037 0.311 2.590

M/M/1 モデルによるサービス規則の違いについて平均系内滞在時間を表 1 に示す．表中の記号は ρ = ρ1 + ρ2 ，
ρ1 = λ1 /µ1 ，ρ2 = λ2 /µ2 とし，表の数値は単位時間で示

λ1 : λ2 = 2 : 1 µ1 : µ2 = 1 : 5
ρ
0.1
0.5
0.9

分布に従う時間サービスを受ける．λ1 , λ2 の比，µ1 , µ2 のした．また表の数値は待ち行列理論のサービス規律と平均系内滞在時間の公式を適用した 6) ．
表 1 のうち，µ1 : µ2 = 1 : 5 の場合は，µ2 > µ1 となったサービス時間の最長順にサービスを行ったため，NP, PRFCFS 0.038 0.377 3.721
PS0.037 0.333 3.005

NP0.038 0.424 7.830

PR0.038 0.434 7.928の値が大きくなる結果となった．
サービス規則には，上記の 4 種類のほか，ランダムサービス，逆順サービス，動的優先権サービスなどが知られている．

4. お わ り に待ち行列理論において，待ち時間を小さくする方法の一つにサービス順序を変える方法がある．今回の話題は，サービス順序の変更（サービス規律）による，2 種類の客の平た け だ

竹田

ひとし

仁 1947 年生，1977 年 3 月工学院大学
大学院工学研究科博士課程満期退学．工学博士．1988 年
文教大学情報学部専任講師に着任．現在情報学研究科教授．情報学研究科において，「シミュレーション特論」を担当．日本機械学会, 日本オペレーションズ・リサーチ学会, 日本経営数学会, 電子情報通信学会，各会員．主な著書として，情報科学とコンピュータ (日本理工出版会),
経済・経営のための基礎数学（実教出版）, 産業社会と情報化 (日本理工出版会), 経営数学 (日本理工出版会), 図解エレクトロニクス用語辞典 (日刊工業新聞社) など
22 冊がある．

均系内滞在時間についての比較を示した．
〔文献〕

1）Feller., W.:“An Introduction of Probability Theory and Its Applications”, John Willey, 1950.
2）Kleinrock, L.:“Queueing Systems vol.1”,Wiley and Sone, 1975.
3）本間鶴千代:「待ち行列の理論」, 理工学社, 1966.
4）鈴木武次：「待ち行列」, 裳華房, 1972.
5）守谷栄一, 竹田仁：
「経営数学」, 日本理工出版会, 1992.
6）高橋幸雄：「やさしい待ち行列 (4)」, オペレーションズ・リサーチ: 経
営の科学 41(2), 1996, pp.100-105.

8 (4)文教大学大学院情報学研究科 IT News Letter Vol. 10, No. 2 (2015)