待ち行列理論（queueing theory）

• テクノロジ系
• 基礎理論
• 基本情報
• 応用情報
• 重要度 ★★★☆☆

もう少し詳しい説明

待ち行列理論は、行列がどれくらい伸びるかを計算する方法です。

コンビニに1台だけ置いてあるATMを思い浮かべてください。待ち時間を決めているのは2つの数字です。どれくらいの間隔で人が来るか、そして1人あたり何分かかるか。この2つが分かれば、平均で何分待つことになるかが計算できます。

試験に出るのは M/M/1 という一番単純な形です。M/M/1 とは「人の来かたもばらばら、かかる時間もばらばら、窓口は1つ」という意味で、まさにこのATMの状況です。

まず利用率から

一番大事な数字が利用率（記号は ρ・ロー）で、これはATMがふさがっている時間の割合です。

1時間に12人来て、1人あたり3分かかるとします。12人ぶんで 12 × 3 ＝ 36分ふさがるので、60分のうち36分。36 ÷ 60 ＝ 0.6 が利用率です。

これを式の形にすると、こうなります。

利用率 ＝ 到着率 × 平均処理時間

さきほどの数字を当てはめてみます。単位を「1時間」にそろえたいので、3分は 3 ÷ 60 ＝ 0.05時間に直します。

利用率 ＝ 到着率 12人 × 平均処理時間 0.05時間 ＝ 0.6

気をつけるのは単位です。 到着率が「1時間あたり12人」なら、処理時間も時間に直してから掛けます。3分のまま 12 × 3 と掛けると出てくるのは 36 で、これは割合ではなく分の数です（60で割れば 0.6 に戻ります）。問題文が「1分あたり」「1秒あたり」で来ることもあるので、掛ける前に両方の単位をそろえる、とだけ決めておけば間違えません。

利用率が1を超えると、来る速さに処理が追いつかず、行列は無限に伸びていきます。

待ち時間と応答時間

平均待ち時間 ＝ ρ ÷（1 − ρ）× 平均処理時間

ここで用語を1つ区別しておきます。待ち時間は並んでいるあいだの時間、応答時間はそれに自分の操作時間を足した、店に入ってから出るまでの全体です。

平均応答時間 ＝ 平均処理時間 ÷（1 − ρ）

問題文がどちらを聞いているかで答えが変わります。 ここがこの単元で一番間違えやすいところで、選択肢には必ず両方の値が並んでいます。

分母が（1 − ρ）であることの意味

この単元の要点は、分母が（1 − ρ）だという一点に尽きます。

利用率が1に近づくほど分母が小さくなるので、待ち時間は比例ではなく跳ね上がります。

利用率が 0.5 から 0.8 へ、たった1.6倍になっただけで、待ち時間は4倍です。

この形は、ATMに限らずあらゆる「順番待ち」に当てはまります。サーバの使用率、回線の帯域、担当者1人あたりの仕事量。遊ばせないよう目一杯まで詰め込むと、かえって全体が待たされる。 「利用率を上げすぎない」という設計判断の根拠が、この式の形そのものにあります。

なお、平均待ち行列長（並んでいる人数）は ρ² ÷（1 − ρ）です。ρ を2乗し忘れると、操作中の1人も含めた系内の人数のほうになってしまいます。

→ 待ち行列の練習問題を解く

試験ではこう出る

科目A（旧・午前）では、利用率と平均処理時間から平均待ち時間や平均応答時間を求める計算問題として出ます。基本情報での出題は多くありませんが、応用情報では定番の単元です。式は3つしかないのに、「待ち時間を聞かれているのか、応答時間を聞かれているのか」を読み違えると答えが変わるため、問題文のどの言葉がどちらを指すのかを先に押さえておくのが確実です。

到着率と処理時間から利用率を出すところから始めさせる、2段構えの問題も出ます。選択肢には待ち時間と応答時間を取り違えた値が必ず混ざっています。

→ 待ち行列（M/M/1）の練習問題

関連する用語

キュー

先に入れたものから先に出すデータのしまい方。名前は同じだが別の話

稼働率

装置が使える状態でいる割合。待ち行列理論の利用率とは別の量

ボトルネック

全体の速さを決めてしまう、いちばん詰まっている場所

ミニクイズ

最終更新：2026-09-14