待ち行列理論（queueing theory）
要求が到着する速さと処理する速さから、待ち時間や待ち行列の長さを求める理論。
もう少し詳しい説明
待ち行列理論は、行列がどれくらい伸びるかを計算する方法です。
コンビニに1台だけ置いてあるATMを思い浮かべてください。待ち時間を決めているのは2つの数字です。どれくらいの間隔で人が来るか、そして1人あたり何分かかるか。この2つが分かれば、平均で何分待つことになるかが計算できます。
試験に出るのは M/M/1 という一番単純な形です。M/M/1 とは「人の来かたもばらばら、かかる時間もばらばら、窓口は1つ」という意味で、まさにこのATMの状況です。
まず利用率から
一番大事な数字が利用率（記号は ρ・ロー）で、これはATMがふさがっている時間の割合です。
数えれば出ます。 1時間に12人来て、1人あたり3分かかるとします。
12人 × 3分 ＝ 36分 … 1時間のうち、ATMがふさがっている時間 36分 ÷ 60分 ＝ 0.6 … 1時間に占める割合
1時間のうち6割がふさがっている、という意味です。式を覚えていなくても、利用率はここまでの数え方で出せます。
利用率が1を超えると、来る速さに処理が追いつかず、行列は無限に伸びていきます。
式の形でも書いておく
参考書や問題集では、いまの数え方が次の形で書かれています。
利用率 ＝ 到着率 × 平均処理時間
到着率は「1時間に何人来るか」、平均処理時間は「1人にどれだけかかるか」です。
この式に当てはめるときは、先に単位をそろえます。到着率が「1時間あたり12人」なら、処理時間のほうも時間に直して 3 ÷ 60 ＝ 0.05時間。
利用率 ＝ 12人 × 0.05時間 ＝ 0.6
同じ答えになりました。
やっていることは、上の数え方と同じです。 上では最後にやった「÷ 60」を、先に済ませてあるだけです。先に割っておくと、残りが掛け算1回で終わります。
単位をそろえ忘れて 12 × 3 と掛けると、出てくるのは 36 です。これは割合ではなく分の数なので、0.6 にはなりません。
待ち時間と応答時間
平均待ち時間 ＝ ρ ÷（1 − ρ）× 平均処理時間
さきほどのATM（利用率 ρ ＝ 0.6、平均処理時間 3分）で、実際に計算してみます。
平均待ち時間 ＝ 0.6 ÷（1 − 0.6）× 3分 ＝ 0.6 ÷ 0.4 × 3分 ＝ 1.5 × 3分 ＝ 4.5分
ここで用語を1つ区別しておきます。待ち時間は並んでいるあいだの時間、応答時間はそれに自分の操作時間を足した、店に入ってから出るまでの全体です。
平均応答時間 ＝ 平均処理時間 ÷（1 − ρ）
同じ数字で計算します。
平均応答時間 ＝ 3分 ÷（1 − 0.6）＝ 3分 ÷ 0.4 ＝ 7.5分
この2つは、自分で検算できます。 応答時間は「待ち時間 ＋ 自分の処理時間」なので、
4.5分（待ち）＋ 3分（処理）＝ 7.5分（応答）
出した2つの値がこの関係になっていれば、式の使い方は合っています。 ずれていたら、どちらかの式を取り違えています。
問題文がどちらを聞いているかで答えが変わります。 ここがこの単元で一番間違えやすいところで、選択肢には必ず両方の値が並んでいます。この例なら、4.5分と7.5分の両方が選択肢に並ぶということです。
分母が（1 − ρ）であることの意味
この単元の要点は、分母が（1 − ρ）だという一点に尽きます。
利用率が1に近づくほど分母が小さくなるので、待ち時間は比例ではなく跳ね上がります。
| 利用率 | 待ち時間（処理時間の何倍か） | 処理時間が3分のATMなら |
|---|---|---|
| 0.5 | 1倍 | 3分 |
| 0.6 | 1.5倍 | 4.5分（上で計算した値） |
| 0.8 | 4倍 | 12分 |
| 0.9 | 9倍 | 27分 |
利用率が 0.5 から 0.8 へ、たった1.6倍になっただけで、待ち時間は4倍です。
この表をグラフにすると、形がはっきりします。
左半分は、ほとんど寝たままの線です。利用率が0.5までは、待ち時間もたいして増えません。ところが0.8を過ぎたあたりから、線が急に立ち上がります。
この立ち上がり方が、分母が（1 − 利用率）であることの中身です。利用率が1に近づくほど割る数が小さくなるので、少し上げただけで待ち時間が跳ね上がります。
この形は、ATMに限らずあらゆる「順番待ち」に当てはまります。サーバ（要求を受け取って、応えを返す側の機械）の使用率、回線の帯域（1秒間に送れる量）、担当者1人あたりの仕事量。遊ばせないよう目一杯まで詰め込むと、かえって全体が待たされる。 「利用率を上げすぎない」という設計判断の根拠が、この式の形そのものにあります。
なお、平均待ち行列長（並んで待っている人数）は ρ² ÷（1 − ρ）です。同じ例で計算します。
平均待ち行列長 ＝ 0.6² ÷（1 − 0.6）＝ 0.36 ÷ 0.4 ＝ 0.9人
ρ を2乗し忘れると 0.6 ÷ 0.4 ＝ 1.5人 になりますが、これは操作中の1人も含めた系内の人数のほうです。
見分けの手がかりは、2つの差がちょうど利用率 ρ になることです。1.5 − 0.9 ＝ 0.6。ATMがふさがっている割合のぶんだけ、系内のほうが多い、という関係になっています。
試験ではこう出る
科目A（旧・午前）で出ます。基本情報での出題は多くありませんが、応用情報では定番の単元です。
多いのは、利用率と平均処理時間から、平均待ち時間や平均応答時間を求める問題です。利用率は、たいてい問題文が与えてくれます。到着率と平均処理時間から利用率を自分で計算させる形は、ほとんど出ません。同じ問題文が、年度をまたいで繰り返し出ることもあります。
力を入れるべきなのは、分母の（1 − ρ）のほうです。式は3つしかないのに、「待ち時間を聞かれているのか、応答時間を聞かれているのか」を読み違えると答えが変わります。問題文のどの言葉がどちらを指すのかを先に押さえてください。選択肢には、取り違えた値が必ず混ざっています。
関連する用語
- キュー
- 先に入れたものから先に出すデータのしまい方。名前は同じだが別の話
- 稼働率
- 装置が使える状態でいる割合。待ち行列理論の利用率とは別の量
- ボトルネック
- 全体の速さを決めてしまう、いちばん詰まっている場所
ミニクイズ
M/M/1の待ち行列モデルで、利用率が0.8、平均処理時間が200ミリ秒のとき、平均待ち時間は何ミリ秒か。
正解は 1番：800ミリ秒
平均待ち時間 ＝ 利用率 ÷（1 − 利用率）× 平均処理時間 なので、0.8 ÷ 0.2 ＝ 4、4 × 200 ＝ 800 です。1000ミリ秒は平均応答時間（待ち時間に処理時間を足した値）、160ミリ秒は利用率に処理時間を掛けただけの値、200ミリ秒は処理時間そのものです。待ち時間と応答時間の取り違えが、この単元でいちばん多い間違いです。
この分野をまとめて解く → 基礎理論と情報メディアのミニテスト（全39問）
最終更新：2026-09-14