基本情報の待ち行列問題の解き方|利用率と平均待ち時間を例題で解説
待ち行列の問題は、記号と式が多くて何から手を付ければいいのか分からない。
λ(ラムダ)やρ(ロー)が並んだ問題文を見て、そのまま次の問題へ進んでしまったことはありませんか?
先に答えをお伝えします。基本情報の待ち行列問題は、ほとんどが2つの式で解けます。
1つ目は「利用率 = 到着率 × 平均サービス時間」、2つ目は「平均待ち時間 = 利用率 ÷(1 − 利用率)× 平均サービス時間」です。
この記事では、待ち行列の考え方と用語を整理してから、2つの式の使い方を例題で確かめます。そのうえで、利用率が上がると待ち時間がどう増えるかを計算表で示し、式が使える場面と使えない場面を区別します。
例題はすべてこの記事のために作ったもので、途中の式も省かずに書きます。
科目Aの計算問題の全体像を先に知りたい人は、こちらの記事が参考になります。待ち行列を含む8分野の代表的な式を、1つずつまとめています。
【関連記事】基本情報の科目A計算問題まとめ|苦手になりやすい8分野と解き方の順番
待ち行列とは?窓口に並ぶ人を計算で表す考え方¶
待ち行列とは、順番を待つ人や仕事の列を、数式で扱えるようにした考え方です。身近な例では、銀行の窓口やスーパーのレジに並ぶ列がそれにあたります。
コンピュータの世界でも、同じことが起きています。サーバに届いた処理の依頼や、プリンタに送られた印刷の指示は、前の仕事が終わるまで順番を待ちます。
待ち行列の計算を使うと、混み具合から待ち時間を見積もれます。
覚えておきたい4つの用語¶
待ち行列の問題には、決まった用語が出てきます。まず、それぞれが何を表すのかを押さえておきましょう。
用語の意味を表にまとめます。
| 用語 | 記号の例 | 意味 | レジでたとえると |
|---|---|---|---|
| 到着率 | λ | 単位時間あたりに、平均で何件の依頼が届くか | 1分間に平均何人が列に加わるか |
| 平均到着間隔 | 1/λ | 依頼が届く間隔の平均 | 前の客が来てから次の客が来るまでの平均時間 |
| 平均サービス時間 | Ts | 1件の処理にかかる平均の時間 | 1人の会計にかかる平均時間 |
| 利用率 | ρ | 窓口が仕事をしている時間の割合 | レジが会計中でふさがっている割合 |
到着率と平均到着間隔は、逆数の関係にあります。逆数とは、1をその数で割った値のことです。
平均到着間隔が10分なら、到着率は 1 ÷ 10 = 0.1(件/分)になります。
平均待ち時間と平均応答時間の違い¶
待ち行列の問題では、「待ち時間」と「応答時間」が区別されて出てきます。ここを取り違えると、選択肢のどれかにぴったり合う間違いの答えを選んでしまいます。
平均待ち時間とは、列に並んでから自分の処理が始まるまでの平均の時間です。平均応答時間とは、列に並んでから処理が終わるまでの平均の時間で、待ち時間にサービス時間を足したものになります。
レジでいえば、待ち時間は「並び始めてから会計が始まるまで」です。応答時間は「並び始めてから会計が終わってレジを離れるまで」にあたります。
問題文がどちらを聞いているのか、最初に印を付けておくと安心です。
待ち行列の2つの式と例題¶
ここからは、実際に式を使って計算してみます。基本情報で出題される待ち行列は、窓口が1つの単純なモデルが中心です。
1つ目の式:利用率を求める¶
利用率は、到着率と平均サービス時間のかけ算で求めます。
利用率 ρ = 到着率 λ × 平均サービス時間 Ts
平均到着間隔が与えられている場合は、平均サービス時間を平均到着間隔で割っても同じ値になります。どちらの形で問題文に書かれていても対応できるようにしておきましょう。
例題1です。ある窓口には、平均10分に1人の割合で客が来ます。
1人の受付には平均8分かかります。この窓口の利用率を求めます。
到着率は 1 ÷ 10 = 0.1(人/分)です。利用率は 0.1 × 8 = 0.8 になります。
平均到着間隔で割る形なら、8 ÷ 10 = 0.8 で同じ答えです。
利用率0.8は、窓口が全体の時間の8割で受付をしているという意味です。残りの2割は、客がいなくて空いている時間になります。
2つ目の式:平均待ち時間を求める¶
利用率が分かれば、平均待ち時間を求められます。
平均待ち時間 Tw = ρ ÷(1 − ρ)× Ts
例題1の続きです。利用率0.8、平均サービス時間8分の窓口で、平均待ち時間を求めます。
まず ρ ÷(1 − ρ)を計算します。0.8 ÷(1 − 0.8)= 0.8 ÷ 0.2 = 4 です。
これに平均サービス時間を掛けて、4 × 8 = 32分になります。
平均応答時間は、待ち時間に受付の時間を足して 32 + 8 = 40分です。受付そのものは8分で終わるのに、並び始めてからは平均40分かかる計算になります。
計算の流れを表で確かめる¶
例題1の計算を、手順ごとに表へ並べておきます。本番でも、この順番で数字を書き出せば迷いません。
| 手順 | やること | 計算 | 結果 |
|---|---|---|---|
| 1 | 到着率を出す | 1 ÷ 10 | 0.1 人/分 |
| 2 | 利用率を出す | 0.1 × 8 | 0.8 |
| 3 | ρ ÷(1 − ρ)を出す | 0.8 ÷ 0.2 | 4 |
| 4 | 平均待ち時間を出す | 4 × 8 | 32 分 |
| 5 | 平均応答時間を出す | 32 + 8 | 40 分 |
手順3の値は、待っている間に自分の前に平均で何件分の処理があるかの目安だと考えると、イメージしやすくなります。この値にサービス時間を掛けるので、待ち時間になるわけです。
平均して何人が並んでいるか¶
問題によっては、待ち時間ではなく「平均して何人がいるか」を聞かれることもあります。窓口で処理中の人も含めた平均人数は、ρ ÷(1 − ρ)で求められます。
例題1では、0.8 ÷ 0.2 = 4人です。到着率 × 平均応答時間でも、0.1 × 40 = 4人と同じ値になります。
人数と時間は到着率でつながっている、と覚えておくと検算に使えます。
利用率が上がると平均待ち時間はどう増えるか¶
待ち行列でいちばん大事な性質は、利用率が1に近づくと待ち時間が急に長くなることです。ここを理解しておくと、式を丸暗記しなくても答えの見当が付くようになります。
計算表で増え方を見る¶
平均サービス時間を1分に固定して、利用率だけを変えてみます。ρ ÷(1 − ρ)の値が、そのまま平均待ち時間(分)になります。
利用率ごとの値を表にまとめます。
| 利用率 ρ | 1 − ρ | ρ ÷(1 − ρ) | 平均待ち時間(Ts=1分) | 平均応答時間 |
|---|---|---|---|---|
| 0.5 | 0.5 | 1 | 1 分 | 2 分 |
| 0.6 | 0.4 | 1.5 | 1.5 分 | 2.5 分 |
| 0.7 | 0.3 | 約2.33 | 約2.33 分 | 約3.33 分 |
| 0.8 | 0.2 | 4 | 4 分 | 5 分 |
| 0.9 | 0.1 | 9 | 9 分 | 10 分 |
| 0.95 | 0.05 | 19 | 19 分 | 20 分 |
利用率が0.5から0.8へ上がると、待ち時間は1分から4分になります。0.8から0.9へは、わずか0.1上がっただけで4分から9分へ、倍以上に伸びています。
分母の 1 − ρ が0に近づくと、割り算の答えが大きくなるからです。窓口の空き時間が少なくなるほど、少しの混雑が後ろの人にまとめてのしかかる、と考えるとイメージがつかめます。
利用率が1以上になるとどうなるか¶
利用率が1になると、分母の 1 − ρ が0になり、式が計算できなくなります。これは、窓口がずっとふさがっていて、列がいつまでも短くならない状態です。
利用率が1を超えると、処理できる量より届く量のほうが多くなります。列は時間とともに伸び続けるので、平均待ち時間は決まった値になりません。
問題で利用率が1以上になったら、計算の途中で単位や数字を取り違えていないかを見直しましょう。
窓口を速くすると待ち時間はどう変わるか¶
待ち時間を短くする方法の1つは、1件あたりの処理時間を短くすることです。例題1の窓口で、受付の時間を8分から6分に縮めてみます。
利用率は 0.1 × 6 = 0.6 になります。平均待ち時間は 0.6 ÷(1 − 0.6)× 6 = 1.5 × 6 = 9分です。
受付の時間は2分縮んだだけですが、平均待ち時間は32分から9分へ大きく減りました。利用率が高いところでは、少しの改善が大きな効果を生むということです。
サーバの性能を上げると応答が見違えるほど速くなるのも、同じ理屈です。
待ち時間の目標から利用率の上限を逆算する¶
試験では、待ち時間の目標を先に決めて、そこから許される利用率や到着率を求める問題もあります。この場合は、ρ ÷(1 − ρ)の値から逆にたどります。
例題2です。あるサーバでは、1件の処理に平均2秒かかります。
平均待ち時間を6秒以下にしたいとき、1秒あたりの到着件数はいくつまでにすればよいでしょうか。
平均待ち時間は ρ ÷(1 − ρ)× 2 なので、これが6以下になるには ρ ÷(1 − ρ)が3以下であればよいことになります。ρ ÷(1 − ρ)= 3 を解くと、ρ = 3 × (1 − ρ)、つまり ρ = 3 − 3ρ で、4ρ = 3 から ρ = 0.75 です。
利用率は到着率 × 2 なので、到着率は 0.75 ÷ 2 = 0.375(件/秒)以下にすればよいと分かります。計算の途中で ρ の式を解く場面は、選択肢の値を1つずつ代入して確かめる方法でも答えにたどり着けます。
M/M/1の式が使える場合と使えない場合¶
ここまで使ってきた式は、M/M/1と呼ばれる待ち行列のモデルで成り立つものです。M/M/1という名前は、到着のしかた、サービス時間のばらつき方、窓口の数の3つを表しています。
M/M/1の前提¶
M/M/1の式を使うには、いくつかの前提が必要です。試験の問題文に「M/M/1の待ち行列モデルが適用できるものとする」と書かれているのは、この前提が成り立つと約束するためです。
前提の中身を表にまとめます。
| 記号の位置 | 前提 | やさしく言うと |
|---|---|---|
| 1つ目のM | 到着がランダム(ポアソン到着) | 客はばらばらのタイミングで来て、前の客とは関係なく到着する |
| 2つ目のM | サービス時間が指数分布に従う | 受付の時間は、短い人もいれば長い人もいて、ばらつきがある |
| 3つ目の1 | 窓口は1つ | 列は1本で、受付する人も1人だけ |
| そのほか | 列の長さに上限がなく、先着順に処理する | 何人並んでもよく、横入りはない |
ポアソン到着とは、一定の平均の割合で、たがいに無関係に起きる到着のしかたのことです。指数分布は、短い時間で終わることが多く、ときどき長くかかることもある、というばらつき方を表します。
名前を覚える必要はあまりなく、ばらばらに来て、ばらばらの時間で終わると理解しておけば十分です。
式をそのまま使えない場面¶
前提が崩れると、ここまでの式では正しい値が出ません。どんな場面で使えなくなるのかを知っておくと、問題文の条件を読み落とさなくなります。
代表的な場面を表で比べます。
| 場面 | 何が違うか | 考え方 |
|---|---|---|
| 窓口が2つ以上ある | 窓口が1つという前提が崩れる | M/M/1の式は使えない。問題文に別の条件や式が示されるのが一般的 |
| 処理時間が毎回まったく同じ | サービス時間のばらつきが無い | ばらつきがある場合より待ち時間は短くなる。M/M/1の式では長めに出てしまう |
| 客が予約制で一定の間隔で来る | 到着がランダムではない | 列ができにくくなるため、M/M/1の式とは合わない |
| 利用率が1以上 | 処理が届く量に追いつかない | 列が伸び続け、平均待ち時間は求まらない |
| 列に並べる人数に上限がある | 列の長さに上限がないという前提が崩れる | あふれた客は帰ってしまうため、計算の前提が変わる |
処理時間が毎回同じ場合は、M/D/1と呼ばれる別のモデルになります。このモデルでは、平均待ち時間が M/M/1 の半分になることが知られています。
基本情報の科目Aでは M/M/1 の式を使う問題が中心なので、まずは「前提が書かれていたら M/M/1 の式を使う」と判断できれば大丈夫です。
窓口を2つに分けるときの注意¶
窓口を増やせば待ち時間が減る、という直感は正しい方向です。ただし、窓口が2つになった時点でM/M/1の式は使えません。
よく出てくる工夫は、窓口を2つに分けて、それぞれに別の列を作る考え方です。例えば、到着率0.1(人/分)の客を2つの窓口に半分ずつ振り分けると、それぞれの窓口は到着率0.05のM/M/1として計算できます。
受付時間が8分なら、それぞれの利用率は 0.05 × 8 = 0.4 です。
平均待ち時間は 0.4 ÷(1 − 0.4)× 8 で、およそ5.33分になります。窓口が1つのときの32分と比べると、大きく減っていることが分かります。
このように、問題文が「それぞれをM/M/1とみなす」と条件を付けてくれれば、ここまでの式がそのまま使えます。
試験で間違えやすいポイント¶
待ち行列の問題は、式そのものより、数字の読み取りでつまずくことが多い分野です。ここでは、計算の前に確かめたいことを整理します。
単位をそろえてから計算する¶
到着率が1時間あたり、サービス時間が秒で書かれていることがあります。単位が違ったまま掛け算すると、利用率が1を大きく超えるなど、おかしな値になります。
例題3です。ある窓口には1時間に平均20件の依頼が届き、1件の処理には平均2分かかります。
到着率を1分あたりに直すと、20 ÷ 60 = 1/3(件/分)です。
利用率は 1/3 × 2 = 2/3、およそ0.67になります。平均待ち時間は(2/3)÷(1/3)× 2 = 2 × 2 = 4分です。
分数のまま計算すると、割り切れない小数を扱わずに済むので楽になります。
よくある間違いと防ぎ方¶
最後に、待ち行列の問題で起きやすい間違いを表にまとめます。原因を知っておけば、本番で同じミスを避けられます。
| 間違い | 原因 | 防ぎ方 |
|---|---|---|
| 応答時間を聞かれているのに待ち時間を答えた | 2つの時間の違いを読み落とした | 問題文の「待ち時間」「応答時間」に印を付ける |
| 利用率が1を超えた | 時間と分などの単位がそろっていなかった | 到着率とサービス時間の単位を先に書き出す |
| 平均到着間隔をそのまま到着率に使った | 到着率と到着間隔が逆数だと忘れた | 「件/分」か「分/件」かを確かめる |
| 窓口が2つなのにM/M/1の式を使った | 前提の条件を確かめなかった | 窓口の数と、問題文が示す前提を最初に読む |
待ち行列の考え方は、通信回線の混み具合を考えるときにも出てきます。回線の利用率やデータ量から時間を求める問題は、こちらの記事で詳しく扱っています。
【関連記事】基本情報のデータ転送時間の求め方|通信速度・回線利用率・ビットとバイトを整理
待ち行列の次に取り組みたいこと¶
待ち行列は、テクノロジ系のなかでもシステムの性能を考える分野で扱われます。同じように割合を扱う稼働率の問題とあわせて練習すると、計算の型が身につきやすくなります。
稼働率の考え方は、こちらの記事で直列と並列の例題を使って説明しています。
【関連記事】基本情報の稼働率の計算問題|直列・並列システムとMTBF・MTTRを解説
同じ日に公開した損益分岐点の記事も、固定費と変動費の関係から式を組み立てる練習になります。
【関連記事】基本情報の損益分岐点の求め方|固定費・変動費・限界利益を例題で理解
試験全体の出題内容や難しさを確かめたい人は、親記事もあわせて読んでおくと安心です。
【関連記事】基本情報技術者試験とは?試験内容・難易度・勉強法を初心者向けに解説
数字を表に書き出して1つずつ追う練習は、科目Bで擬似言語のプログラムを読むときにも役立ちます。擬似言語とは、試験のために決められた書き方でプログラムを表したものです。
私たちの Giji Academy では、擬似言語シミュレーターでプログラムを1行ずつ実行し、変数の値が変わる様子を確かめられます。講座は擬似言語の講座一覧から始められます。
まとめ¶
待ち行列の問題は、利用率 = 到着率 × 平均サービス時間と、平均待ち時間 = ρ ÷(1 − ρ)× 平均サービス時間の2つの式で解けます。平均応答時間は、待ち時間にサービス時間を足した値です。
利用率が1に近づくと、待ち時間は急に長くなります。この性質を知っておけば、選択肢の大きさから答えの見当を付けることもできます。
M/M/1の式は、到着がランダムで、窓口が1つという前提のもとで使えることも忘れないようにしましょう。
式の意味と前提が分かれば、待ち行列は落ち着いて得点できる分野です。今日の例題を、もう一度自分の手で解いてみてください。