Köteori

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

Exempel på situationer som köteorin hanterar:

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

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.

Littles sats

Littles 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

N ¯ : {\displaystyle {\bar {N}}:}

{\bar {N}}:

medelantalet kunder i systemet och W : {\displaystyle W:}

W:

medelväntetiden i kön.

Mellan

N ¯ , {\displaystyle {\bar {N}},}

{\bar {N}},

N q ¯ : {\displaystyle {\bar {N_{q}}}:}

{\bar {N_{q}}}:

medelantalet kunder i kön N s ¯ : {\displaystyle {\bar {N_{s}}}:}

{\bar {N_{s}}}:

medelantalet kunder vid betjäningsstationerna

är sambandet

N ¯ = N q ¯ + N s ¯ {\displaystyle {\bar {N}}={\bar {N_{q}}}+{\bar {N_{s}}}}

{\bar {N}}={\bar {N_{q}}}+{\bar {N_{s}}}

och sambandet mellan

W , {\displaystyle W,}

W,

T : {\displaystyle T:}

T:

medeltiden för kunder i systemet x ¯ : {\displaystyle {\bar {x}}:}

{\bar {x}}:

medeltiden för kunder vid betjäningsstationerna

är

T = W + x ¯ {\displaystyle T=W+{\bar {x}}}

T=W+{\bar {x}}

Littles sats ger ett enkelt samband mellan N ¯ {\displaystyle {\bar {N}}} ${\bar {N}}$ och T {\displaystyle T} $T$

N ¯ = λ e f f ⋅ T {\displaystyle {\bar {N}}=\lambda _{eff}\cdot T}

{\bar {N}}=\lambda _{eff}\cdot T

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

λ e f f {\displaystyle \lambda _{eff}}

\lambda _{eff}

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

N s ¯ = λ e f f ⋅ x ¯ {\displaystyle {\bar {N_{s}}}=\lambda _{eff}\cdot {\bar {x}}}

{\bar {N_{s}}}=\lambda _{eff}\cdot {\bar {x}}

och Little's sats kan skrivas som

N q ¯ + N s ¯ = λ e f f ⋅ ( W ¯ + x ¯ ) {\displaystyle {\bar {N_{q}}}+{\bar {N_{s}}}=\lambda _{eff}\cdot ({\bar {W}}+{\bar {x}})}

{\bar {N_{q}}}+{\bar {N_{s}}}=\lambda _{eff}\cdot ({\bar {W}}+{\bar {x}})

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

N q ¯ = λ e f f ⋅ W ¯ {\displaystyle {\bar {N_{q}}}=\lambda _{eff}\cdot {\bar {W}}}

{\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äningsstationerna och deras medeltid vid betjäningsstationerna

John Little bevisade satsen 1961.

Praktiska tillämpningar/användningsområden

Nyttan av köteori är omfattande och den tillämpas inom en rad områden. Flygplatser, frisersalonger, mataffärer, restauranger, tillverkande industrier, busscheman samt sjukhusbokningar tillhör de områden som drar nytta av köteori. 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

^ ”Arkiverade kopian”. Arkiverad från originalet den 10 februari 2009. https://web.archive.org/web/20090210005612/http://www.f.kth.se/~u1e53yvo/Queue2/Queue2.html. Läst 30 april 2012.
^ ”Agner Krarup Erlang (1878 - 1929)” (på engelska). Plus Maths. https://plus.maths.org/content/agner-krarup-erlang-1878-1929.
^ Körner, U: "Köteori", sidan 50. Studentlitteratur, 2003
^ ”Queueing Theory Applications”. www.andrewferrier.com. https://www.andrewferrier.com/queueing_theory/Henry/index.html.