Køteori

Køteori
	Køteori på Commons

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:^[1]

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

^ John D. C. Little og Stephen C. Graves (2008). D. Chhajed og T. J. Lowe, red. Little's Law (PDF). Springer Sciences. s. 81-100. [Kap. 5 av Building intuition: Insights from basic operations management models and principles]

Litteratur

Arne Myskja (1974). Teletrafikksystemer. Tapir forlag. [2 bind]
Andreas Bachmann (1981). Køteori. Bedriftsøkonomens forlag. [185 sider]
Bjørn Nygaard (1989). Køteori, ventelister og produksjonsplanlegging. NKI. [Del av Statistikk og planlegging i helsevesenet]
Jan Evensmo (1991). Køteori. Tano. [Del av Kvantitative metoder, analyse og simulering av økonomiske og administrative modeller]
Kurt Jörnsten, Sverre Storøy og Stein W. Wallace (1999). Operasjonsanalyse. Cappelen akademisk. [340 sider]

[1] John D. C. Little og Stephen C. Graves (2008). D. Chhajed og T. J. Lowe, red. Little's Law (PDF). Springer Sciences. s. 81-100. [Kap. 5 av Building intuition: Insights from basic operations management models and principles]

[1]