待ち行列とは、サービスを受けるために待つ者（物）を指す。 これだけのことですが、これが研究の対象となって多くの興味ある結果が得られる。
私がここでなぜ待ち行列を取り上げるかというと、待ち行列にうらみがあるからだ。 情報処理技術者の試験を何度か受けたが、午前（特に午前１）の問題に１問は必ず待ち行列の問題が出る。 私は必ず待ち行列の問題を間違える。 たかが１問のためにわざわざ時間をかけてホームページをこしらえるのも割に合わない。 しかし、ここで敢然と待ち行列に対して戦うのもいいだろう。しばらくおつき合いのほどお願いする。
情報処理技術者試験に出る、基本的な待ち行列の問題は次の通りである。
１件あたり、平均３分でサービスを行う窓口が１つある（ただしサービス処理時間は、 指数分布に従う）。窓口にくる客は、 平均５分に１回の割合でランダムに来る。客が窓口に並んでからサービスが受けられるまで、 平均何分待つか。
この問題を見て、「なんだ、５分に１回の割合で客が来て３分でサービスが終わるなら、 窓口なんか３分仕事して２分遊んでられるんじゃねえか。まったくいい商売だ。 もちろん、サービスが受けられるまで待つことはねえよ。」 と思う人がいるかもしれない。私も、そう思いたくなる。しかし、 そうはならない。なぜかというと、客が「ランダムに来る」（でたらめに来る、予想がつかない）からだ。 窓口は、客がいなければ暇だが、客が一度にくれば最初の客しか相手ができず、残りの客は順番を待たなければならない。 そのため、平均ゼロ分ということはありえない。 また、窓口の処理時間も一定ではない。ここにも、一筋縄ではいかない問題がある。
答は割合簡単な式になる。まず、答を導くための記号を次のとおり定義する。
次に、公式を導くため次のように仮定する。 最初に問題文中で言及されている内容と重複するところもある。
これらの条件を M/M/1 と書くことがある。 最初のMは客の到着間隔が指数分布に従うこと、次のMはサービス時間が指数分布に従うこと、 最後の1は窓口は１つであることを表す。この記法をケンドールの記法という。
さて、待ち時間の平均 Tw、待ち行列の長さLwは次のようになる。 ここでTw、Lwとも、サービスを受けている時間（人）を含まない。
Tw = Ts * ρ/ (１−ρ )
Lw = ρ/ (１−ρ )
ほかにも、いろいろな値がわかる。 JavaScript を使って、簡単な計算をしてみよう。ρ ≧ 1 (Ts ≧ Ta)のときは、 TwおよびLwの定常解はない。
インターネットで待ち行列について調べてみると、いろいろな例が出ていた。 たとえば、窓口を２倍に増やすとどうなるか。 この場合は、平均サービス率が半分になると考える。 すなわち、サービスを処理できる率が2倍になると考える。そうすると、 同じ到着率でも、待ち時間は半分よりさらに短くなる。 また、平均サービス時間が半分になるとどうなるか。窓口を２倍に増やした場合と比べると、 待ち時間は同じだ。しかし、サービスを受ける時間が、 窓口を２倍に増やした場合より短くなる。だから、客の立場では、 同じレベルのサービス窓口が２つあるより、２倍効率よくサービスしてくれる窓口が１つあるほうが、 サービスを受ける時間が短いぶんうれしい。
待ち行列に関連して、挿話を２つ紹介しよう。
一つは、近藤次郎「オペレーションズ・リサーチ入門」で述べられている話だ。
はるか昔の中国の軍隊で、兵士が洗い物をするために、一つの桶を使っていた。 多くの兵士が桶が使えるのを順番に待っていたため、長い列ができていた。 これを見兼ねたある人が、桶をもう一つ用意した。すると、列がまたたく間に短くなり、 桶が一つの場合の半分未満になった。
この「半分未満」というところが、待ち行列の理論でわかることだ。 もう一つは私の体験である。
私が少年だったころ、銀行に自動預け払い機がなく、 サービスを有人窓口でやっていたころの話である。当時の銀行では、 預金預け払いと振込の窓口にはそれぞれ複数の受付があった。 この状態に対して、あるせこい銀行が目をつけた。預金の預け払いに比べて、 振込みは単位時間当たり稼げる金が少ないという事実があった。そこで、 振込の窓口を１つにしてしまった。当然、振込の窓口には客が長く並ぶが、 せこい銀行は客のことを考えなかった。ひどいことに、この発想は他の銀行にも広がり、 どの銀行も振込窓口は１つになってしまった。客はどこへ行っても、 窓口に長く並ぶことを強いられた。
待ち行列の理論よりさらに大事な法則がある。 リトルの法則と呼ばれるその内容は、次の通り。
システム内にあるものの平均的な数は、それらのものが出ていく平均的な率と、 システム内にある平均的な時間の積に等しい。
これは、次のように言い換えることもできる。
システム内にあるものの数は、入ってくる率と平均的な待ち時間の積に等しい。
わたしはこの法則を今年(2003年)早々適用してみた。 つれあいのお父さんと、つれあいと私は市街地に車で出かけた。 駐車場はどこも混んでいて、やっとみつけた駐車場も車が何台も待っている。 仕方なくこの駐車場に置くことにした。ただ待っているのもしゃくなので、 駐車場に入れるまでに、どのくらい待つか見当をつけてみると二人に宣言した。 私達の前に待っている車は5台で、駐車場は120台くらい入りそうだ。 車を駐車場に入れている時間は 2 時間くらいだろう。 そうすると、駐車場から出ていく車の間隔は、120台/120分 という計算から、 1分に１台は出ていくだろう。自分たちの車は６台めである。 だから、６分待てば６台が入る、そのように答えた。
実際には、２０分かかった。悔しいことに、私達の前の車は１０分以内に入れた。 予想が外れた原因として、「駐車場の収容台数を少なめに見積もってしまった」、 「１台あたりの駐車時間が２時間より長かった」、 「自分達が長くなったのは運が悪かった」などが考えられる。 確かに、収容台数は120台よりは少なそうで。ひょっとしたら100台よりは少なかったかもしれない。 仮に90台としてみよう。１分あたり出ていくのは0.75台だ。６台出るには、 ８分かかる。それでも、足りない。 １台あたり２時間入れているという仮定はどうでか。私達は１時間半で出ている。 このあたりは難しい。 一番考えられるのは、入りの時の波だ。私達が入ったのは午後２時ころだった。 昼過ぎに一度に入っていれば、２時間経過しても、なかなか出る車がないだろう。 事実、わたしたちが駐車場を出るころには、その駐車場へ入る車の列はなかった。
結構世の中には、待ち行列が多いことに気付いた。
なかなか順番が来なくていらいらしている時に、 待ち時間を求める公式とリトルの法則を思い出して、 待ち時間を予想するのは楽しいかもしれない。
2004-07-25 ：ρ ≧ 1 のときは、定常解がないことを計算時に表示するようにした。 その他エラーチェックを厳密にした。 福岡工業大学確率統計関連数理モデルのリンク集(www.fit.ac.jp)の指摘による。 なお、当時は私のこのページへのリンクが指摘も含めてあったが、2020-03-04 現在はない。
2008-06-28 ：語句の修正。
2020-03-27 : 小数点以下の数字の指定オプションを追加
