待ち行列とLittleの法則
先着順の処理記録から待機時間と滞留時間を求め、人数の時間平均との関係を確かめます。
説明
待ち行列では、到着してから処理開始までの待機時間と、処理終了までの滞留時間を分けます。処理中の件数を含むかどうかで、系内件数と待ち件数も異なります。Littleの法則は平均件数L、到着率λ、平均滞留時間WをL=λWで結びます。
窓口一つ、先着順、各処理3秒の記録を使います。到着・開始・終了を一件ずつ求め、件数が時間とともにどう変わるかを集計します。空の状態から全件完了までの同じ期間で対応を確認し、途中で区切った場合に必要な注意も調べます。
1到着時刻と処理時間
4件が時刻0、1、2、8秒に到着し、それぞれ3秒かかります。窓口は時刻0に空いています。
arrivals = [0,1,2,8]到着時刻; service = [3,3,3,3]各処理時間; list(zip(arrivals,service))到着と処理時間の対応到着間隔が処理時間より短い部分で待ちが発生します。平均だけでは到着の集中が分からないので、まず各時刻を保持します。
2開始と終了を順に決める
開始時刻は到着時刻と前件の終了時刻の遅い方です。終了は開始に処理時間を足します。
def schedule(arrivals,service):到着列と処理時間列
finish = 0窓口が空く時刻
rows = []各件の記録
for arrival,duration in zip(arrivals,service):到着順に処理
start = max(arrival,finish)到着済みかつ窓口が空いた時刻
finish = start+duration終了時刻
rows.append((arrival,start,finish,start-arrival,finish-arrival))待機と滞留を記録
return rows全記録出力の列は到着・開始・終了・待機・滞留です。サービス中の割込みや優先順位は入れず、先着順の窓口一つという条件で計算します。
3待機と滞留を集計
同じ記録から全4件の待機・滞留の平均を求めます。
rows = schedule(arrivals,service)時系列を計算; rows到着・開始・終了・待機・滞留, sum(r[3] for r in rows)/4, sum(r[4] for r in rows)/4待機と滞留の平均待機は0・2・4・1秒で平均1.75秒、滞留は3・5・7・4秒で平均4.75秒です。各件の滞留は待機に処理3秒を加えた値です。
4各時刻のシステム内のジョブ数
時刻t以上t+1未満の区間にいる件数を数えます。終了時刻に達した件は除き、同時刻の到着は含めます。
end = rows[-1][2]全件終了時刻; occupancy = [sum(a <= t < f for a,s,f,q,w in rows) for t in range(end)]系内件数; waiting = [sum(a <= t < s for a,s,f,q,w in rows) for t in range(end)]待ち件数; list(zip(range(end),occupancy,waiting))時刻・系内・待ち系内件数は処理中を含み、待ち件数は開始前だけを含みます。この記録のイベントは整数秒なので、1秒幅の区間ごとに件数が一定です。
5システム内の平均ジョブ数と平均滞留時間
0〜12秒の件数を時間積分して12秒で割ります。各区間が1秒なので件数の和が面積です。
area = sum(occupancy)系内件数の面積; rate = len(rows)/end同じ期間の到着率; mean_time = sum(r[4] for r in rows)/len(rows)全件の平均滞留; area, area/end, rate*mean_time面積とLittleの関係面積19件秒、平均系内件数19/12です。到着率4/12件毎秒×平均滞留19/4秒と一致します。各件の滞留を縦に足す方法と、時刻ごとの件数を横に足す方法が同じ面積を数えています。
6待ち行列だけにも適用
処理中を除いた待ち件数を使う場合は、Wも処理時間を除いた待機時間にそろえます。
sum(waiting)/end平均待ち件数, rate*sum(r[3] for r in rows)/len(rows)到着率×平均待機, sum(waiting), sum(r[3] for r in rows)同じ7件秒を二方向から集計平均待ち件数7/12と、到着率×平均待機時間が一致します。Lに待ち件数、Wに処理込みの滞留時間を混ぜると、この対応は崩れます。小数表示の末尾の差は浮動小数点の丸めによるもので、分数では両方7/12です。
7途中で観測を切った場合
0〜5秒だけ観測すると、まだ終了していない件があります。窓内の面積と、完了した件だけの滞留は異なります。
window = 5観測終了を5秒へ変更; clipped = sum(max(0,min(f,window)-max(a,0)) for a,s,f,q,w in rows)窓内に切り取った滞在面積; completed = [r for r in rows if r[2] <= window]窓内で完了した件; clipped, completed, sum(r[4] for r in completed)対象の違いを比較窓内の面積は10件秒ですが、完了したのは最初の1件で滞留合計3秒です。未完了件の窓内滞在分を落として、異なる対象の平均を無理に掛け合わせることはできません。
8処理が速くなった場合
同じ到着記録のまま処理を1秒へ短縮します。到着のタイミングと処理能力の関係を確認します。
faster = schedule(arrivals,[1]*4)処理時間だけを短縮; faster新しい時系列, sum(r[3] for r in faster)/4, sum(r[4] for r in faster)/4待機と滞留の平均この記録では待機0、平均滞留1秒です。Littleの法則は平均量の関係であり、到着率と処理速度だけから任意の到着列の待ち時間を決める公式ではありません。待ち時間の予測には到着・処理の分布などのモデルが必要です。
まとめ
待機時間と滞留時間、待ち件数と系内件数の対象をそろえます。
空から全件完了までの記録では、各件の滞留合計と件数の時間積分が一致します。
途中で区切る場合の境界や、長期平均を使う場合の安定性を確認してLittleの法則を適用します。
操作履歴と解説を振り返れます。
Python 3
arrivals = [0,1,2,8]; service = [3,3,3,3]; list(zip(arrivals,service))[(0, 3), (1, 3), (2, 3), (8, 3)]
def schedule(arrivals,service):
finish = 0
rows = []
for arrival,duration in zip(arrivals,service):
start = max(arrival,finish)
finish = start+duration
rows.append((arrival,start,finish,start-arrival,finish-arrival))
return rowsrows = schedule(arrivals,service); rows, sum(r[3] for r in rows)/4, sum(r[4] for r in rows)/4([(0, 0, 3, 0, 3), (1, 3, 6, 2, 5), (2, 6, 9, 4, 7), (8, 9, 12, 1, 4)], 1.75, 4.75)
end = rows[-1][2]; occupancy = [sum(a <= t < f for a,s,f,q,w in rows) for t in range(end)]; waiting = [sum(a <= t < s for a,s,f,q,w in rows) for t in range(end)]; list(zip(range(end),occupancy,waiting))[(0, 1, 0), (1, 2, 1), (2, 3, 2), (3, 2, 1), (4, 2, 1), (5, 2, 1), (6, 1, 0), (7, 1, 0), (8, 2, 1), (9, 1, 0), (10, 1, 0), (11, 1, 0)]
area = sum(occupancy); rate = len(rows)/end; mean_time = sum(r[4] for r in rows)/len(rows); area, area/end, rate*mean_time(19, 1.5833333333333333, 1.5833333333333333)
sum(waiting)/end, rate*sum(r[3] for r in rows)/len(rows), sum(waiting), sum(r[3] for r in rows)(0.5833333333333334, 0.5833333333333333, 7, 7)
window = 5; clipped = sum(max(0,min(f,window)-max(a,0)) for a,s,f,q,w in rows); completed = [r for r in rows if r[2] <= window]; clipped, completed, sum(r[4] for r in completed)(10, [(0, 0, 3, 0, 3)], 3)
faster = schedule(arrivals,[1]*4); faster, sum(r[3] for r in faster)/4, sum(r[4] for r in faster)/4([(0, 0, 1, 0, 1), (1, 1, 2, 0, 1), (2, 2, 3, 0, 1), (8, 8, 9, 0, 1)], 0.0, 1.0)
演習完了