2009年12月21日

生活に役立つ(?)「待ち行列理論」

たまには実際の生活に直接応用のできる数学の話をしたいと思って、今日は「待ち行列」の話をします。そもそも数学(情報工学)的な世界での「待ち行列理論」とは、確率を駆使して最適ネットワークを作るための基礎的理論の事ですが、ネットワークの話になるとかなり専門的になるので、ここでは「スーパーのレジ」という日常に密着した例で考えて見ます。

ex_queue.jpg
さて、↑のように二台のレジがあった場合、お客がどう並ぶかは@のように「2列に並ぶ場合」と、Aのように「1列に並ぶ場合」の2通り考えられます。今の例の場合、お客を効率的に処理するという事は「お客の平均待ち時間を最小化する」と言い換える事ができるでしょう。よって、@とAでお客の平均待ち時間がどのように変わるのかを計算してみます。
ちなみに先に正解を言っておくと、Aの方がお客の平均待ち時間は少なかったりします。



さて、まずは今から説明する事が成り立つための前提条件を3つ説明します。
@お客は時刻に依存せずに、完全にランダムにレジに並ぶものとする。
→「特売日の開店直後」や「閉店間際」は、通常時とは違ってお客がレジに殺到するわけですが、どの時刻においても客の到着の仕方はランダムであるという仮定です。
Aお客は他の客の動向に関係なくレジに来るものとする。
→実際は、レジに100人も並んでいれば、お客のうちの大半がレジに並ぶのを諦めてしまいますが、ここではそういう事は関係なくお客が一定の確率でレジに並ぶという仮定です。
B同時にお客が並ぶ事はない。
→複数のお客が同時に並ぼうとする時に、並ぶ順番でけんかしないという仮定です。つまり、「複数のお客は必ず時間差をともなって到着する」という事にします。

上記の@〜Bの条件が成立することが、これから説明する平均待ち時間を計算するための前提条件となります。(ちなみに数学的に言うと、お客の到着が「ポアソン分布」、お客の並びが「指数分布」に従うという事です。)

そして、平均待ち時間を出すためには
「λ:お客の平均到着率」(1分当たりに並ぶお客の数(人/分))
「μ:1台のレジでの平均サービス率」(1分当たりに処理できるお客の数(人/分))
この上記2つが必要です。

今の@のレジの例の場合は、λ=0.2でμ=1.0のわけですが、この時の「t:平均待ち時間」は
t=( λ / μ ) / ( 1 - λ / μ ) = 0.25分 (15.0秒)
となるわけです。ちなみに、λ/μは「単位時間当たりの、"サービスを受ける客の人数"に対する"到着する客の人数"の比(サービス利用率)」を表していて重要な指標になります。

一方でAの場合は、@の場合と比べると列が半減するので、お客の平均到着率が2倍になる事によりλ=0.4でμ=1.0、サービス利用率が( λ / μ ) ^ 2となります。よって、この場合の「平均待ち時間」は
t = ( λ / μ ) ^ 2 / ( 1 - ( λ / μ ) ^ 2 ) = 0.19分 (11.4秒)
となります。

これらの結果から
@での平均待ち時間=15.0秒
Aでの平均待ち時間=11.4秒
となるために、この例の場合は、複数のレジに対して1列に並ぶ方がお客の平均待ち時間は少ない事になります。(結局はλとμの値次第ではあるわけですが)


ちなみにこれ、待ち時間を少なくさせようと努力している銀行のATMなんかでは、実際に複数列で並ばせずに1列で並ばせようとしてますよね。銀行のATMだけではありませんが、こういったように1列で並ばせるのは、それなりに数学的背景があるわけですよ。という事で、今後も機会があればこの手の話をしていくつもりです。



今日のエントリーで、「なるほど」「ふむふむ」「面白い」などと思ってくれた方で、一票を頂ける方は是非ともお願いします。↓
人気ブログランキングへ
posted by きらっち at 01:41| Comment(0) | TrackBack(0) | 科学
この記事へのコメント
コメントを書く
お名前:

メールアドレス:

ホームページアドレス:

コメント:

この記事へのトラックバックURL
http://blog.sakura.ne.jp/tb/34311596

この記事へのトラックバック