Køteori

**Køteori** viser sammenheng mellom belastning og ventetid i køsystemer, der det er mange som samtidig ønsker å bruke felles (men begrensede) ressurser. Køteori brukes for eksempel ved dimensjonering av veitrafikk, flytrafikk, jernbanenett, produksjonslinjer i fabrikker, telefonnett, mobilnett, helsetjenester og tjenester på Internett.  
Teorien har gjennom de siste hundre år utviklet et sett med generelle formler som passer for
mange varierte problemer. Det teoretiske arbeidet startet i de nye telefonselskapene som ble dannet rundt
århundreskiftet.  En av pionerene var A. K. Erlang som jobbet for det danske televerket og i 1909 publiserte ett av de absolutt første
arbeidene. Han ga navn til flere klassiske
kømodeller (Erlang-A, Erlang-B, Erlang-C).  Den norske  Tore Olaus Engset hadde også viktige bidrag (Engset-formelen), mens man i Sverige fikk Christian Jacobæus og Conny Palm
som på 30- og 40-tallet jobbet for Ericsson med teoretiske trafikkanalyser.  Disse var stort sett enkeltkøer, men på 60-tallet publiserte amerikaneren Jackson løsningen for sammenkoblede køer, der jobbene (kundene) videresendes mellom arbeiderne.

Med køteoretiske  formler får man regnet ut ventetider og kølengder, basert på hvor stor kapasitet man ser for seg og hvor stor pågangen 
(belastningen) fra brukerne vil være.  Køteorien er basert på sannsynlighetsteori (Markovmodeller) og tar hensyn til at pågangen (etterspørselen) varierer.
Formlene vil derfor også anslå variasjon, slik at man kan dimensjonere slik at sjansen for blokkering (at man blir nektet betjening) er under gitte grenser.
Disse er et viktig redskap i logistikk og operasjonsanalyse, og ellers ethvert felt der man søker å optimalisere transport av varer, tjenester og
informasjon.  Fordi køteori er matematisk fundert, gjør den forenklinger som ofte ikke samsvarer med realiteten. Et alternativ til køteori er da å
lage en simulering (et dataprogram) av trafikksystemet, noe som krever mere tid og ressurser, men som vil gi større detaljeringsgrad og *realisme*.

I Norge har køteori vært en naturlig del av opplæringen i operasjonsanalyse ved universitetene, Bedriftsøkonomisk institutt, Norges Handelshøyskole og logistikkutdanningen ved Høgskolen i Molde. Køteori inngår også som en del av fagområdet telematikk, primært ved NTNU sitt Institutt for Telematikk, som danner kjernen i forskergruppen *[[Centre for the Quantification of Quality of Service]] (Q2S)* som i 2003 ble ett av landets første senter for fremragende forskning.  

## Eksempler
Køteorien er omfattende. Noen få av de enkleste eksemplene omtales under (ingen utledning av formlene).

### Little's Lov
I et hvert stabilt (stasjonært) system er forholdet mellom ventetid (W), antall som betjenes (L) og pågang (\lambda) at
:L=\lambda W
Dette er et matematisk teorem som ble utledet av John D. C. Little fra Massachusetts Institute of Technology rundt 1960. De tre verdiene er gjennomsnitt. Forholdet kan kun brukes for å få et gjennomsnittsbilde i ethvert system. Det fine er at den gjelder ansett hvordan selve pågangen er fordelt, og en trenger ikke kjenne til hvordan arbeidstiden er fordelt eller hvordan arbeidet prioriteres. 

Et eksempel gitt av Little er fra en fødeavdeling:
*Pågangen er \lambda=5 fødende hver dag
*Ventetiden er slik at 10 % ligger 7 dager, resten ligger 2 dager.  Gjennomsnitt blir W=0.1(7) + 0.9(2)=2.5 dager
Med Little's formel finner en at fødeavdelingen i gjennomsnitt bruker
L=\lambda W = 5(2.5) = 12.5 senger.  Dette kunne selvsagt fødeavdelingen ha funnet ut ved å måle sengebruken over tid,
men med formelen trenger en ikke gjøre det.  Formelen  gir derimot ikke innsikt i for eksempel hvor mange
senger en trenger for å sikre maksimalt 1 dag ventetid for 99 % av de fødende. Og, loven gjelder ikke
hvis avdelingen er ustabil, som etter en omorganisering.
### En M/M/1-kø
En litt mer detaljert kømodell er en M/M/1-kø, der man har en (1) arbeider som kan gjøre ferdig \mu jobber per tidsenhet (for eksempel hver time).  Samtidig
kommer det \lambda jobber per tidsenhet og legger seg i kø  for å bli betjent.  Når arbeideren er ferdig med en jobb, vil neste jobb bli den som har ventet
lengst (såkalt First In First Out betjening).  Både belastning og kapasitet varierer som Poissonfordelingen. Det er ellers ubegrenset med plass i køen, en urealistisk forenkling i de fleste situasjoner.  Under disse forholdene sier køteorien blant annet at:
*utnyttelsesgrad av arbeideren blir \rho = \lambda / \mu
*snitt ventetid i køen (før kunden blir betjent) blir \rho(1/\mu)/(1-\rho)
*snitt kølengde (antall som venter) blir \rho^2/(1-\rho)

Anta en nettbank som mottar \lambda = 100  henvendelser i sekundet. Man ønsker at snitt ventetid ikke skal overgå 0,05 sekund.
Derfor må nettbanken utrustes med en arbeidskapasitet \mu som sikrer dette.  Ulikheten som må løses for  \mu er:
: 0,05 > \rho(1/\mu)/(1-\rho)
: 0,05 > (\lambda/\mu)(1/\mu)/(1-\lambda/\mu)
: 0,05 > (100/\mu)(1/\mu)/(1-100/\mu)
Denne ulikheten ordnes om til følgende andregradsligning:
: \mu^2 - 100\mu - 200 > 0
som har to løsninger, der den praktiske er at
\mu > 50 + 67,08.  Det betyr at arbeideren (postbanken) må ha en arbeidskapasitet på minst 117,08 i sekundet.
## Se også
* Køsniking

## Referanser


## Litteratur
*
*
*
*
*