Köteori

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

Köteori är läran om idealiserade köer med stokastiska tillflöden och utflöden.

De vanligaste tillämpningarna förekommer inom logistik och analys av tele- och datornätverk.

Översikt[redigera | redigera wikitext]

Exempel på situationer som köteorin hanterar: [1]

  • Kunder kommer till en plats och vill få ett ärende hanterat. Det kan till exempel vara personer som vill handla i en restaurang eller affär, vill ringa ett telefonsamtal eller ta sig ur en bilkö.
  • Det finns ett ändligt antal betjäningsstationer där kunden kan uträtta sitt ärende. Betjäningen tar en viss tid.
  • Om ingen betjäningsstation är ledig kan kunden antingen stå i kö eller lämna platsen med oförrättat ärende.

Situationerna kan varieras på många sätt. Till exempel kan kunderna komma med jämna mellanrum, eller slumpmässigt. Vanligast är att kundernas ankomsttider är poissonfördelade, vilket betyder att de anländer slumpmässigt med en viss intensitet. I en sådan process kan det ibland anlända många kunder samtidigt, medan det ibland kan vara långa uppehåll mellan ankomsterna. Tiden det tar att bli betjänad kan också varieras. Man kan till exempel anta att varje betjäning tar lika lång tid, eller att betjäningstiderna är normalfördelade.

Några viktiga parametrar inom köteorin är

  • Antalet betjäningsstationer
  • Ankomstintensiteten, det vill säga antalet kunder som anländer i genomsnitt per tidsenhet
  • Betjäningsintensiteten, det vill säga hur många kunder som i genomsnitt kan betjänas per tidsenhet.

Historik[redigera | redigera wikitext]

Den danske ingenjören Agner Krarup Erlang var den förste att publicera inom ämnet köteori. Han tillämpade sannolikhetsteori på problem rörande telekommunikation och publicerade resultaten år 1909. [2]

Little's sats[redigera | redigera wikitext]

Little's sats beskriver förhållandet mellan kunders ankomstfrekvens, deras betjäningstid och det genomsnittliga antal kunder som befinner sig i ett system.

För betjäningsstationerna behövs uttryck för både tillstånds- och väntetidsfördelningarna. Ofta är det enkelt att få fram uttryck för motsvarande medelvärden, det vill säga

\bar{N}: medelantalet kunder i systemet och
W: medelväntetiden i kön.

Mellan

\bar{N},
\bar{N_q}: medelantalet kunder i kön
\bar{N_s}: medelantalet kunder vid betjäningsstationerna

är sambandet

\bar{N}= \bar{N_q}+ \bar{N_s}

och sambandet mellan

W,
T: medeltiden för kunder i systemet
\bar{x}: medeltiden för kunder vid betjäningsstationerna

är

T=W+ \bar{x}

Little's sats ger ett enkelt samband mellan \bar{N} och T

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

Medelantalet kunder i systemet är alltså lika med produkten av medelantalet ankomster till systemet

 \lambda_{eff}

och medeltiden för kunderna i systemet. Medelantalet av kunder vid betjäningsstationerna är lika med avverkad trafik och därmed

 \bar{N_s}=\lambda_{eff} \cdot\bar{x}

och Little's sats kan skrivas som

 \bar{N_q}+ \bar{N_s}=\lambda_{eff} \cdot (\bar{W} + \bar{x})

och uttnyttjas uttrycket för medelantalet kunder vid betjäningsstationerna erhålls

 \bar{N_q}=\lambda_{eff} \cdot  \bar{W}

Således existerar samband mellan

  • Medelantalet kunder i systemet och deras medeltid i systemet
  • Medelantalet kunder i kön och deras medeltid i kön
  • Medelantalet kunder vid betjäningstationerna och deras medeltid vid betjäningsstationerna

John Little bevisade satsen 1961.[3]

Praktiska tillämpningar/användningsområden[redigera | redigera wikitext]

Nyttan av köteori är omfattande och den tillämpas inom en rad områden. Flygplatser, frisersalonger, mataffärer, restauranger, tillverkande industrier, busscheman, sjukhusbokningar tillhör de områden som drar nytta av köteori.[4] En restaurang kan till exempel beräkna optimalt antal kassor som skall vara öppna under en lunch då man gärna förknippar korta köer med en bättre kundupplevelse men samtidigt inte vill betala för överkapacitet. Samma tillämpning kan tänkas även för frisersalonger och mataffärer. Tillverkande industrier kan vilja bygga produktionslinor enligt Just in time och Lean production utan mellanlager någonstans längs linan. För att få ett smidigare trafikflöde i en korsning kan korsningen byggas om. Med kännedom om trafikens ankomstintensitet kan kapaciteten anpassas och en korsning byggas som bilar kan lämna i samma takt som de ankommer. Flygplan är lönsamma då de flygs och dyra att ha stående på marken. Med hjälp av köteori försöker flygplatser optimera så att flygplan inte ska vänta på varandras lyft och landning i onödan.

Referenser[redigera | redigera wikitext]

  1. ^ http://www.f.kth.se/~u1e53yvo/Queue2/Queue2.html
  2. ^ http://pass.maths.org.uk/issue2/erlang/index.html
  3. ^ Körner, U: "Köteori", sidan 50. Studentlitteratur, 2003
  4. ^ http://www.andrewferrier.com/oldpages/queueing_theory/Henry/index.html