待ち行列

作成日: 2003-02-03
最終更新日:

待ち行列

待ち行列とは、サービスを受けるために待つ者(物)を指す。 これだけのことですが、これが研究の対象となって多くの興味ある結果が得られる。

私がここでなぜ待ち行列を取り上げるかというと、待ち行列にうらみがあるからだ。 情報処理技術者の試験を何度か受けたが、午前(特に午前1)の問題に1問は必ず待ち行列の問題が出る。 私は必ず待ち行列の問題を間違える。 たかが1問のためにわざわざ時間をかけてホームページをこしらえるのも割に合わない。 しかし、ここで敢然と待ち行列に対して戦うのもいいだろう。しばらくおつき合いのほどお願いする。

待ち行列の問題

情報処理技術者試験に出る、基本的な待ち行列の問題は次の通りである。

1件あたり、平均3分でサービスを行う窓口が1つある(ただしサービス処理時間は、 指数分布に従う)。窓口にくる客は、 平均5分に1回の割合でランダムに来る。客が窓口に並んでからサービスが受けられるまで、 平均何分待つか。

この問題を見て、「なんだ、5分に1回の割合で客が来て3分でサービスが終わるなら、 窓口なんか3分仕事して2分遊んでられるんじゃねえか。まったくいい商売だ。 もちろん、サービスが受けられるまで待つことはねえよ。」 と思う人がいるかもしれない。私も、そう思いたくなる。しかし、 そうはならない。なぜかというと、客が「ランダムに来る」(でたらめに来る、予想がつかない)からだ。 窓口は、客がいなければ暇だが、客が一度にくれば最初の客しか相手ができず、残りの客は順番を待たなければならない。 そのため、平均ゼロ分ということはありえない。 また、窓口の処理時間も一定ではない。ここにも、一筋縄ではいかない問題がある。

答は割合簡単な式になる。まず、答を導くための記号を次のとおり定義する。

次に、公式を導くため次のように仮定する。 最初に問題文中で言及されている内容と重複するところもある。

これらの条件を M/M/1 と書くことがある。 最初のMは客の到着間隔が指数分布に従うこと、次のMはサービス時間が指数分布に従うこと、 最後の1は窓口は1つであることを表す。この記法をケンドールの記法という。

さて、待ち時間の平均 Tw、待ち行列の長さLwは次のようになる。 ここでTw、Lwとも、サービスを受けている時間(人)を含まない。

Tw = Ts * ρ/ (1−ρ)

Lw = ρ/ (1−ρ)

ほかにも、いろいろな値がわかる。 JavaScript を使って、簡単な計算をしてみよう。ρ ≧ 1 (Ts ≧ Ta)のときは、 TwおよびLwの定常解はない。

平均サービス時間Ts 平均到着時間Ta:
平均サービス率μ
平均到着率λ
サービス利用率ρ
平均待ち時間Tw
平均待ち行列人数Lw
小数点以下の数字 0 1 2 3 4 5

サービスの変化

インターネットで待ち行列について調べてみると、いろいろな例が出ていた。 たとえば、窓口を2倍に増やすとどうなるか。 この場合は、平均サービス率が半分になると考える。 すなわち、サービスを処理できる率が2倍になると考える。そうすると、 同じ到着率でも、待ち時間は半分よりさらに短くなる。 また、平均サービス時間が半分になるとどうなるか。窓口を2倍に増やした場合と比べると、 待ち時間は同じだ。しかし、サービスを受ける時間が、 窓口を2倍に増やした場合より短くなる。だから、客の立場では、 同じレベルのサービス窓口が2つあるより、2倍効率よくサービスしてくれる窓口が1つあるほうが、 サービスを受ける時間が短いぶんうれしい。

挿話2つ

待ち行列に関連して、挿話を2つ紹介しよう。

一つは、近藤次郎「オペレーションズ・リサーチ入門」で述べられている話だ。

はるか昔の中国の軍隊で、兵士が洗い物をするために、一つの桶を使っていた。 多くの兵士が桶が使えるのを順番に待っていたため、長い列ができていた。 これを見兼ねたある人が、桶をもう一つ用意した。すると、列がまたたく間に短くなり、 桶が一つの場合の半分未満になった。

この「半分未満」というところが、待ち行列の理論でわかることだ。 もう一つは私の体験である。

私が少年だったころ、銀行に自動預け払い機がなく、 サービスを有人窓口でやっていたころの話である。当時の銀行では、 預金預け払いと振込の窓口にはそれぞれ複数の受付があった。 この状態に対して、あるせこい銀行が目をつけた。預金の預け払いに比べて、 振込みは単位時間当たり稼げる金が少ないという事実があった。そこで、 振込の窓口を1つにしてしまった。当然、振込の窓口には客が長く並ぶが、 せこい銀行は客のことを考えなかった。ひどいことに、この発想は他の銀行にも広がり、 どの銀行も振込窓口は1つになってしまった。客はどこへ行っても、 窓口に長く並ぶことを強いられた。

理論以前のこと

待ち行列の理論よりさらに大事な法則がある。 リトルの法則と呼ばれるその内容は、次の通り。

システム内にあるものの平均的な数は、それらのものが出ていく平均的な率と、 システム内にある平均的な時間の積に等しい。

これは、次のように言い換えることもできる。

システム内にあるものの数は、入ってくる率と平均的な待ち時間の積に等しい。

わたしはこの法則を今年(2003年)早々適用してみた。 つれあいのお父さんと、つれあいと私は市街地に車で出かけた。 駐車場はどこも混んでいて、やっとみつけた駐車場も車が何台も待っている。 仕方なくこの駐車場に置くことにした。ただ待っているのもしゃくなので、 駐車場に入れるまでに、どのくらい待つか見当をつけてみると二人に宣言した。 私達の前に待っている車は5台で、駐車場は120台くらい入りそうだ。 車を駐車場に入れている時間は 2 時間くらいだろう。 そうすると、駐車場から出ていく車の間隔は、120台/120分 という計算から、 1分に1台は出ていくだろう。自分たちの車は6台めである。 だから、6分待てば6台が入る、そのように答えた。

実際には、20分かかった。悔しいことに、私達の前の車は10分以内に入れた。 予想が外れた原因として、「駐車場の収容台数を少なめに見積もってしまった」、 「1台あたりの駐車時間が2時間より長かった」、 「自分達が長くなったのは運が悪かった」などが考えられる。 確かに、収容台数は120台よりは少なそうで。ひょっとしたら100台よりは少なかったかもしれない。 仮に90台としてみよう。1分あたり出ていくのは0.75台だ。6台出るには、 8分かかる。それでも、足りない。 1台あたり2時間入れているという仮定はどうでか。私達は1時間半で出ている。 このあたりは難しい。 一番考えられるのは、入りの時の波だ。私達が入ったのは午後2時ころだった。 昼過ぎに一度に入っていれば、2時間経過しても、なかなか出る車がないだろう。 事実、わたしたちが駐車場を出るころには、その駐車場へ入る車の列はなかった。

待ち行列の応用

結構世の中には、待ち行列が多いことに気付いた。

なかなか順番が来なくていらいらしている時に、 待ち時間を求める公式とリトルの法則を思い出して、 待ち時間を予想するのは楽しいかもしれない。


更新履歴

2004-07-25 :ρ ≧ 1 のときは、定常解がないことを計算時に表示するようにした。 その他エラーチェックを厳密にした。 福岡工業大学確率統計関連数理モデルのリンク集(www.fit.ac.jp)の指摘による。 なお、当時は私のこのページへのリンクと指摘も含めてあったが、2020-03-04 現在はない。

2008-06-28 :語句の修正。

2020-03-27 : 小数点以下の数字の指定オプションを追加


まりんきょ学問所JavaScript 手習い ≫ 待ち行列


MARUYAMA Satosi