Köteori

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

Köteori är läran om matematiskt idealiserade köer med stokastiskt tillflöde och utflöde.

De vanligaste tillämpningarna finner man i logistiken samt vid analys av tele- och datornätverk.

Översikt[redigera | redigera wikitext]

Situationen som köteorin hanterar kan beskrivas med följande uppställning[1]:

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

Situationen kan varieras på många sätt. Till exempel kan kunderna komma med jämna mellanrum, eller lite slumpmässigt. Vanligast är att kunderna kommer på ett sätt enligt Poissonprocessen. Det betyder att de kommer slumpmässigt med en viss intensitet. I en sådan process kan det ibland komma många kunder på en gång medan det ibland kan vara långa uppehåll mellan ankomsterna. Tiden det tar att bli betjänad kan också varieras. Man kan t ex tänka sig att det tar lika lång tid vare gång, eller att betjäningstiderna är normalfördelade.

Några viktiga parametrar i köteorin är:

  • Antalet betjäningsstationer
  • Ankomstintensiteten, dvs antalet kunder som ankommer i genomsnitt per tidsenhet
  • Betjäningsintensiteten, dvs hur många kunder som i genomsnitt kan betjänas per tidsenhet.

Historia[redigera | redigera wikitext]

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


Matematik[redigera | redigera wikitext]

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 vill vi ha uttryck för både tillstånds och väntetidsfördelningarna. Ofta kan man enkelt få fram uttryck för motsvarande medelvärden dvs

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

Det finns också samband mellan \bar{N}, \bar{N_q}: medelantal kunder i kön och   \bar{N_s}: medelantal kunder i betjäningsstationerna. Samband existerar även mellan W, T: medeltid i systemet och  \bar{x} medeltid i betjäningsstationerna. Sambanden är:


 \bar{N}= \bar{N_q}+ \bar{N_s}
T=W+ \bar{x}

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

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

Medelantal kunder i systemet är alltså lika med produkten av medeltal ankomster till systemet, nedan:: \lambda_{eff} , och medeltiden i systemet. Medelantal kunder i betjäningsstationerna är lika med avverkad trafik och därmed

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

och vi skriver om Little's sats som

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

och uttnyttjar uttrycket för medelantal kunder i betjänigsstationerna så får vi

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

Således existerar samband mellan

  • medelantal kunder i systemet och medeltid i systemet
  • medelantal kunder i kön och medeltid i kön
  • medelantal kunder i betjäningstationerna och medeltid hos betjäningsstationerna.

John Little bevisade satsen 1961.[3]

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

Nyttan av köteori är stor och den tillämpas inom en rad områden. Några som drar nytta av köteorin är: flygplatser, frisersalonger, mataffärer, restauranger, tillverkande industrier, busscheman, sjukhusbokningar med flera.[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 där det inte skall byggas stack någonstans längs linan. Då kan köteorin komma väl till pass. För att få ett smidigare trafikflöde i en korsning kan det bli aktuellt att bygga om korsningen. Då utifrån en uppfattning om trafikens ankomstintensitet kan man anpassa kapaciteten och bygga en korsning som bilar kan lämna i samma takt som de ankommer. På så sätt begränsas belastningen under rusningstrafik. 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.

  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