■ IT News Letter ■文教大学大学院 ■ 情報学研究科

待ち行列理論とその応用
文教大学大学院情報学研究科 教授

竹田 仁†

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

1. は じ め に

2. 待ち行列について

待ち行列理論（queuing theory）は，OR 手法の中でき待ち行列理論の研究の目的は，行列を作るような混雑しわめて古くから研究されてきた理論で応用範囲も広範囲にた現象を理論的に調べ，それに関する対策を立てて混雑をおよぶ．その名が示すように，あるサ−ビスにおける待ち解消させることにある．待ち行列の現象は我々の日常生活の理論的解析を行う学問である．

でもごく普通なことである．

待 ち 行 列 理 論 の 先 駆 者 は ，1909 年 に デ ン マ ー ク のA.K.Erlang の発表した The Theory of Probabilities andTelephone Conversations という電話交換機の待ち合わ

しば行列に並ぶことがある．もし，この行列をなくそうとせの研究から始まっている．その後，待ち行列理論は電話らわれわれはシステムを設計する必要がある．

病院の受付や，高速道路の出口での渋滞のように，しばすると，巨額な費用がかかり，費用と待ち時間を較べなが交換の問題として研究が進められてきたが，確率過程論のこのようにして，電話システムばかりでなく，道路・鉄導入によって飛躍的な発展をとげた．アメリカのベル電話

道の輸送システム，機械の保守，工場の生産ロットの加工試験所でも種々の成果が得られた．現在でも，待ち行列の待ちや機械の修理待ち，コンピュータのバッファの待ちと理論の用語に，電話に関する用語がしばしば使用されてい至るところに待ち行列は存在し，サービスのシステムなどるのも，この経過から当然の事である．また，1947 年にはのモデルを構築されている．とくに近年めざましい発展をスウェーデンのパーム（C.Palm）が機械管理の問題においとげている情報処理システムの中には，数多くのタイプのて，機械の故障修理に待ち行列の考え方を取り入れた論文

待ち行列を見うけることができる．サービス処理方法の違を発表している．これは，今までの電話に関する待ち行列

いによる優先順位のある待ち行列，情報の流れによって起の研究から，他の分野での待ち行列の理論の研究として名こるネットワーク上の待ち行列など，コンピュータの情報高いものである．

処理は，待ち行列の問題を多種多様にわたって提供していこの様に待ち行列理論は単に電話交換の問題だけでなくる．現在この分野で多数の研究がなされている．

道路，鉄道といった輸送システム，機械などの保守や点検，また，ネットワークを構築するには新しい構築論が必要

在庫，生産，販売などの分野にもまたがっている．最近でになり，リソースを適正に算出し配備するにも待ち行列理はコンピュータのシステム設計や性能評価，オンラインシ論が大きく貢献している．

ステムのバッファの待ちに至るまで多くの分野で利用されている．

待ち行列の問題は，サービスを提供する施設（サービス窓口）が多すぎるとサービスを提供する施設や人員の遊休が発生してしまい，逆にサービスをする施設が少なすぎると，サービスを受ける側の待ち行列が長くなり待ちによる2006 年 5 月 10 日受付† 〒 253–8550 神奈川県茅ヶ崎市行谷 1100
takeda@shonan.bunkyo.ac.jp† Graduate School of Information and Communication,
Bunkyo University
1100 Namegaya, Chigasaki, Kanagawa 253–8550, Japan

文教大学大学院情報学研究科 IT News Letter Vol. 2, No. 2, pp. 9〜10 (2006)

損失が発生する．このように待ち行列の問題では，サービスを提供する側とサービスを受ける側との相対立する費用の均衡を図り，最適なサービス窓口の数などを決定することになる．この様な問題を扱うための確率的モデルが待ち(1) 9行列理論である．

を取り込んで「解析のアルゴリズムを与えることで，解析待ち行列理論では，一般に次のようなことが解析できる．

したことにする」という態度である．これによって相型分布（ 1 ） システムの中にｎ人の客がいる確率（システム内に客がいない時には待たずにすぐサービスを受けら(PH) という概念が生まれ，Aggregation/Disaggregation法を用いたものなど，PH/PH/c モデルの解析法が確立され，客が 1 人以上いる時には待たなければならない．

れた．相型分布のクラスは非負の確率分布のクラスの中でこのようにシステム内に客がいない確率，1 人の客

稠密なので，これによって標準的待ち行列モデルの解析はがいる確率，2 人の客がいる確率，，n 人の客がいある意味で解決できたとも考えられる．さらに，このようる確率が求められる）．

な思い切りから Matrixgeometric form solution という理

（ 2 ） システムの中にいる平均客数．

論も出現し，マルコフ連鎖や待ち行列の理論のある部分が（ 3 ） 行列待ちの平均の長さ．

たいへんみとうしがよくなった．

（ 4 ） 到着した客がシステムの中で滞在する平均時間．

個別モデル（ 5 ） 到着した客がサービスを受けるまでの平均待ち標準的モデルの他にも多数のモデルや概念が提案され，解時間．

析された．たとえば到着客のコントロールとサービスの方法によるコントロー• 待ち合い室有限の（呼損のある）待ち行列モデル• 優先権のある待ち行列モデル• 有限呼源待ち行列モデル• タイムシェアリング待ち行列モデル• バァケーションのある待ち行列モデル• ゲートのある待ち行列モデル• 集団到着のあるモデル• 集団サービスのあるモデル

ルに分けることができる．入力のコントロールは，到着客

これらはコンピュータや通信ネットワークの性能評価を受け入れによる利益と待ち時間による損失を較べながら到行うための部分モデルとして考えられたものである．たと着客を受理するか否なのコントロールであり，サービスのえば待ち合い室の無いモデルは古い型の電話交換機をモデ方法によるコントロールは，システムの状態から費用のかル化したものだし，優先権のあるモデルは計算機の中で緊からないようにサービス方法を動的に決定することである．

急性や計算時間の異なるジョブを最適にコントロールする

オペレーションズ・リサーチは，根源的にも， 決定 の要素を含んでいるその中で，待ち行列における 決定 とは，例えば，高速道路の料金所のゲート数の決定であれば，モデルを作り，理論計算，または，シミュレーション等を通して，設計段階の決定であった．近年，決定を含んだ動的に制御された待ち行列（controlled queue）が研究されてきた．コントロールの方法を大別すると，入力すなわちこのような 2 種類のコントロールを同時に扱うモデルに対して最適政策の単調性を求めた．この問題をセミマルコフ決定過程で定式化し，状態の推移を作用素を用いて表現ために利用された．

3. お わ り にすると，簡単になるだけでなく，従来，個別に行われてき待ち行列モデルが適用される問題は拡がっている．それた到着客のコントロールとサービス方法のコントロールのに伴って解析すべき状況も複雑なものになり，解析手法も単調性を導くための凸性が，同時に取り扱うこの問題に対高度なものになっている．

しても，負の項に注目することによって，統一的に解析す〔文ることができる．
この様に，あらゆる分野で数え切れないほど多くの研究が多数の研究者によってなされてきたが，その多くがコンピュータと通信の分野の課題に関するものであった．この意味で，待ち行列理論はこれらの分野の新技術とともに発献〕

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.

展してきたと言ってよい．この流れの中で初期の中心的な話題は D.G.Kendall による記号で表現される標準的な待ち行列モデルを確率過程論を用いて解析することである．
利用率ρが１に近づくと待ち時間が急速に大きくなる．
これを避けるには窓口の数を増すなど，ρの値を小さくすればよい．また，指数分布を一定分布にするなど，変動係数（ランダムネス）を減らすことも，待ち時間を減少する効果がある．

たけ だ

竹田

ひとし

仁 1947 年生．1977 年 3 月工学院大学
大学院工学研究科博士課程満期退学．工学博士．1988
年文教大学情報学部専任講師に着任．1992 年同助教授，1996 年同教授に就任．2005 年 4 月より大学院情報学研究科情報学専攻教授を兼ねる．現在，情報学部学部長．横浜国立大学工学部非常勤講師．主な所属学会は，日本機械学会，日本オペレーションズ・リサーチ学会，日本経営工学会，日本経営数学会，電子情報通信学会．文教大
学大学院情報学研究科では「シミュレーション特論」および「シミュレーション演習」を担当．

最も基本的なモデルである M/G/s モデルの解析は不首尾に終わり，これが待ち行列理論研究の方向を大きく変えることになった．そのひとつの帰結が，コンピュータの進歩
10 ( 2 )文教大学大学院情報学研究科 IT News Letter Vol. 2, No. 2 (2006)