リトルの法則

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動: 案内検索

リトルの法則 (:Little's law) あるいはリトルの定理(Little's theorem)とは、待ち行列理論において

安定な系において長時間平均化した顧客数 L (与えられた負荷、offered load)は、長時間平均化した到着率λと、長時間平均化した顧客が系に費やす時間 W の積に等しい、すなわち
\, L= \lambda W.

という法則である。

本法則は直感的には理にかなったものであるが、対象がどのような確率分布であってもこの振る舞いをするという点と、到着した顧客やサービスする顧客に基づいてどのようにスケジュールするかについて何の仮定も設けない点は特筆すべきである。

最初の証明は1961 年に当時ケース・ウェスタン・リザーブ大学にいたジョン・リトルen)によって発表された。彼の法則はいかなるシステムにも適用でき、また特にシステム内のシステムに適用することができる。銀行では顧客の列や窓口の係が一つのサブシステムであり、リトルの法則はそのそれぞれについても、全体についても適用することができる。リトルの法則の必要条件は、系が安定していて割り込みがないということのみであり、またこの条件により開始時や終了時などの状態遷移を除外している。

リトルの法則の例[編集]

カウンター一つと、商品を閲覧するスペースがある 小さな小売店を考える。一度に一人の客しかカウンターの前に行くことができず、 商品を買わずに立ち去ることはないとすると、この系は大まかに以下の状態を持つ。

入店 → 商品の閲覧 → カウンター → 退出

これは安定した系であり、一定時間に顧客が店に入る割合は、カウンターに行く割合、店を出る割合に等しい。これを到着率とする。

リトルの法則により、店内にいる顧客の平均的な数 L は、到着率 λ に 顧客が店内で過ごす平均時間 W を掛けたものになる。

\, L= \lambda W.

顧客が一時間当たり 10 人到着し、平均的に 0.5 時間店内に滞在するとすると、平均的な店内の顧客数は 5 人である。

店がもっと宣伝を行って、平均到着率を一時間当たり 20人に引き上げようと考えたとする。すると、店は平均 10 人の客が滞在しても大丈夫なようにするか、各顧客が店内で過ごす時間を半分の 0.25 時間に減らさなければならない。後者は、店は支払いの時間を短くしたり、商品を眺めている顧客に「何かお探しですか?」と尋ねたりすることで、これを達成できるかもしれない。

リトルの法則は店の中の系にも適用することができる。たとえば、カウンターとその待ち行列である。平均的に2 人の客がカウンターの前に並んでいるとすると、平均到着率が一時間当たり 10 人であるので、平均 0.2 時間会計に費やしていることがわかる。

さらに、リトルの法則をカウンターそのものに適用することもできる。カウンターには一度に一人の客しかいられないので、カウンターにいる人数の平均は、0~1 の間である。この場合、この数字がいわゆるカウンターの利用率(utilization)になる。

コンピュータシステムの性能検証での応用[編集]

リトルの法則はソフトウェアの性能テストにおいて、試験環境がボトルネックを生じていないことを保証するために用いられる。下記のリンクを参照。

参考文献[編集]

関連項目[編集]