Littles lag

Från Wikipedia
Hoppa till: navigering, sök

Littles lag, Littles sats, eller Littles formel är en formel inom köteorin som beskriver sambandet mellan det genomsnittliga antalet kunder i ett kösystem (N), det genomsnittliga antalet icke blockerade ankomster till systemet per tidsenhet (\lambda_{eff}), samt den genomsnittliga tiden en kund tillbringar i systemet (T).

N = \lambda_{eff} \cdot T

Littles lag har många tillämpningar inom till exempel telekommunikation och datorteknik. Den till synes triviala formeln bevisades för första gången så sent som 1961[källa behövs] av John Little, som också givit formeln dess namn, men sedan dess har ett par enklare bevis presenterats. Ett enkelt bevis som publicerades av EILON 1970[1], redogörs för nedan.

Bevis[redigera | redigera wikitext]

[2]

Kunder anländer inom tidsintervallet [0,t] där

 \alpha (t) - antal kunder som kommit till systemet (och ej avvisats) i intervallet  [0,t].
 \delta (t) - antalet kunder som lämnat systemet och blivit färdigbetjänade i  [0,t]
 N(t) = \alpha (t) - \delta (t) antalet kunder i systemet vid tidpunkten t.
\gamma (t) = total tid som alla kunder tillsammans tillbringat i systemet under intervallet  [0,t]


Eftersom \alpha (t) är definierad som antal ankomster till systemet i intervallet  [0,t] kan vi skriva medelantal ankomster per tidsenhet under intervallet som

 \lambda_t = \alpha (t) /t

Medeltid i systemet per kund i intervallet  [0,t] ges av

 T_t = \gamma (t) / \alpha (t)

eller uttryckt i ord

T_t = Summan av alla tider kunder har tillbringat i systemet under tidsintervallet  [0,t], genom antalet ankomster till systemet under  [0,t]


Låt nu  \bar{N_t} vara medelantal kunder i systemet i intervallet  [0,t] . Vi inser att \bar{N_t} = \gamma (t) /t , genom att förlänga med {\alpha (t) \over \alpha (t)} (= 1), kan skrivas

 \bar{N_t}= {\gamma (t) \over \alpha (t)} \cdot {\alpha (t) \over t} = \bar{N_t} \cdot \lambda_t

Låter vi nu  t gå mot oändligheten och förutsätter att gränsvärdena existerar

 \lim_{t \to \infty} \bar{N_t} = \lim_{t \to \infty} \bar{T_t} \cdot \lim_{t \to \infty}\lambda_t
Antag enligt ovan att
 \lim_{t \to \infty} \lambda_t = \lambda_{eff} < \infty
 \lim_{t \to \infty} T_t = T < \infty

och inför beteckningen

 \bar{N} = \lim_{t \to \infty}\bar{N_t}

Vi kan då skriva:

 \bar{N} = \lambda_{eff} \cdot T

vilket är Little's sats.

  1. ^ Körner, U: "Köteori", sidan 50. Studentlitteratur, 2003
  2. ^ Körner, U: "Köteori", sidan 51-52. Studentlitteratur, 2003