Se kilde til Køteori

[[Fil:Erlang.jpg|thumb|Den danske matematiker [[Agner Krarup Erlang]] (1878-1929) var en af pionererne inden for køteori.]]
'''Køteori''' viser sammenhæng mellem belastning og ventetid i køsystemer, hvor der er mange som samtidig ønsker at bruge fælles (men begrænsede) ressourcer. Køteori bruges for eksempel ved dimensionering af veje, flytrafik, jernbanenet, produktionslinjer på fabrikker, telefonnet, mobilnet, sundhedstjenester og tjenester på [[internet]]tet.

Teorien har gennem de sidste hundrede år udviklet et sæt med generelle formler som passer for mange forskellige problemer. Det teoretiske arbejde startede i de nye telefonselskaber som blev dannet omkring århundredeskiftet. En af pionererne var [[Agner Krarup Erlang|A. K. Erlang]] som arbejdede for [[KTAS]] ( Kjøbenhavns Telefon Aktieselskab) og i 1909 publicerede et af de absolut første værker om emnet. Han gav navn til flere klassiske kømodeller ([[Erlang A formel|Erlang-A]], [[Erlang B formel|Erlang-B]], [[Erlang C formel|Erlang-C]]).<ref>[http://videnskab.dk/verden-pa-formler/ak-erlangs-afvisningsformel-er-grundstenen-al-moderne-kommunikation A.K. Erlangs afvisningsformel er grundstenen for al moderne kommunikation]. [[Videnskab.dk]]. Hentet 9/8-2016</ref><ref name="SådanDTU">[http://videnskab.dk/miljo-naturvidenskab/sadan-undgar-man-lange-koer Sådan undgår man lange køer]. [[Videnskab.dk]]. Hentet 9/8-2016</ref> Den norske [[Tore Olaus Engset]] havde også vigtige bidrag (Engset-formelen), mens man i Sverige fik Christian Jacobæus og Conny Palm som i 1930'erne og 40'erne arbejdede for [[Ericsson]] med teoretiske trafikanalyser. Disse var stort set enkeltkøer, men i 1960'erne publicerede amerikaneren Jackson løsningen for sammenkoblede køer, hvor arbejdet (typisk kunderne) videresendes mellem arbejderne.

Med køteoretiske formler får man udregnet ventetider og kølængder baseret på, hvor stor kapacitet man ser for sig, og hvor stor tilgangen (belastningen) fra brugerne vil være. Køteorien er baseret på sandsynlighedsteori ([[Markovmodel]]ler) og tager hensyn til at tilgangen (efterspørgslen) varierer.

Formlerne vil derfor også anslå variation, sådan at man kan dimensionere således, at risikoen for blokering (at man bliver nægtet betjening) er under en givet grænse.

Disse er et vigtig redskab i [[logistik]] og [[operationsanalyse]], og ellers ethvert felt der man søger at optimere transport af varer, tjenester og information. Fordi køteori er matematisk funderet, baseres den ofte på antagelser og forenklede systemer som ofte ikke svarer fuldstændigt til realiteten. Et alternativ til køteori er da at lave en [[simulering]] (et dataprogram) af trafiksystemet, noget som kræver mere tid og ressourcer, men som vil give større detaljeringsgrad og ''realisme''.

Køteori indgår som en del af [[matematik]]studiet på flere af landets [[universitet]]er, som [[DTU]], [[Københavns Universitet]], [[Aarhus Universitet]] og [[Aalborg Universitet]].<ref name="SådanDTU"/>

I Norge har køteori været en naturlig del af oplæringen i [[operationsanalyse]] ved universiteterne, [[Bedriftsøkonomisk institutt]], [[Norges Handelshøyskole]] og logistikuddannelsen ved [[Høgskolen i Molde]]. Køteori indgår også som en del af fagområdet [[telematik]], primært ved [[NTNU]]' Institutt for Telematikk, som danner kernen i forskergruppen ''Centre for the Quantification of Quality of Service (Q2S)'' som i 2003 blev et af landets første [[Senter for fremragende forskning]].  

==Eksempler==
Køteorien er omfattende. Nogle få af de enkleste eksempler omtales herunder (ingen udledning af formlerne).

=== Littles Lov ===
Littles Lov<ref>{{cite book|title=Probability, statistics, and random processes for electrical engineering|author=Alberto Leon-Garcia|publisher=Prentice Hall|year=2008|edition=3rd|isbn=0-13-147122-8}}</ref><ref name="allen">{{cite book | page = [https://archive.org/details/probabilitystati0000alle/page/259 259] | title = Probability, Statistics, and Queueing Theory: With Computer Science Applications | url = https://archive.org/details/probabilitystati0000alle | first = Arnold A. | last = Allen | publisher = Gulf Professional Publishing | year = 1990 | isbn = 0120510510}}</ref> beskriver, at der for et hvert stabilt (stationært) system vil være et forhold mellem ventetid (<math>W</math>), antal som betjenes (<math>L</math>) og tilgang (<math>\lambda</math>) som er
:<math>L=\lambda W</math>
Dette er et matematisk teorem som blev udledt af [[John D. C. Little]] fra [[Massachusetts Institute of Technology]] omkring 1960. De tre værdier er gennemsnit. Forholdet kan kun bruges for at få et gennemsnitsbillede i ethvert system. Det gælder uanset, hvordan selve tilgangen er fordelt, og en behøver ikke kende til hvordan arbejdstiden er fordelt, eller hvordan arbejdet prioriteres.<ref>{{Cite journal | last1 = Simchi-Levi | first1 = D. | last2 = Trick | first2 = M. A. | doi = 10.1287/opre.1110.0941 | title = Introduction to "Little's Law as Viewed on Its 50th Anniversary" | journal = Operations Research | volume = 59 | issue = 3 | pages = 535 | year = 2013}}</ref>

Et eksempel givet af Little er fra en fødeafdeling:<ref>{{kilde bog|title=Little's Law|publisher=[[Springer Sciences]]|date=2008|pages=81-100|url=http://web.mit.edu/sgraves/www/papers/Little's%20Law-Published.pdf|editor=D. Chhajed og T. J. Lowe|author=John D. C. Little og Stephen C. Graves|chapter=Kap. 5 af ''Building intuition: Insights from basic operations management models and principles''}}</ref>
*Tilgangen er <math>\lambda=5</math> fødende hver dag
*Ventetiden er sådan at 10 % ligger 7 dage, resten ligger 2 dage. Gennemsnit bliver <math>W=0.1(7) + 0.9(2)=2.5</math> dage
Med Littles formel finder en at fødeafdelingen i gennemsnit bruger
<math>L=\lambda W = 5(2.5) = 12.5</math> senge. Dette kunne selvsagt fødeafdelingen have fundet uf ved at måle brugen af senge over tid,
men med formlen behøver man ikke gøre det. Formlen giver derimod ikke indsigt i eksempelvis, hvor mange senge der behøves for at sikre maksimalt 1 dags ventetid for 99 % af de fødende. Loven gælder ikke hvis afdelingen er ustabil, som efter en omorganisering.

===En M/M/1-kø===
[[File:Poiuy.png|thumb|300px|right|Fødsels- og dødsproces der kan beskrives med M/M/1.]]
En lidt mere detaljeret kømodel er en M/M/1-kø, hvor man har en (1) arbejder som kan færdiggøre <math>\mu</math> opgaver per tidsenhed (for eksempel hver time). Samtidig kommer der <math>\lambda</math> opgaver per tidsenhed og lægger sig i kø for at blive betjent. Når arbejderen er færdig med en opgave, vil næste opgave blive den som har ventet længst (såkaldt [[FIFO (computerstruktur)|First In First Out]]-betjening). Både belastningen og kapaciteten varierer som [[Poissonfordeling]]en.<ref>[http://www.econ.ku.dk/keiding/underv/opera/K%C3%B8note.pdf Lidt supplerende køteori] {{Webarchive|url=https://web.archive.org/web/20160921133308/http://www.econ.ku.dk/keiding/underv/opera/K%C3%B8note.pdf |date=21. september 2016 }}. [[Københavns Universitet]]. Hentet 9/8-2016</ref> Der er ellers ubegrænset med plads i køen, en urealistisk forenkling i de fleste situationer. Under disse forhold siger køteorien blandt andet at:
*udnyttelsesgrad af arbejderen bliver <math>\rho = \lambda / \mu</math>
*gennemsnitlig ventetid i køen (før kunden bliver betjent) bliver <math>\rho(1/\mu)/(1-\rho)</math>
*gennemsnitlig kølængde (antal som venter) bliver <math>\rho^2/(1-\rho)</math>

Antag en netbank som modtager <math>\lambda = 100</math> henvendelser i sekundet. Man ønsker at gennemsnitlig ventetid ikke skal overgå 0,05 sekunder.

Derfor må netbanken udrustes med en arbejdskapacitet <math>\mu</math> som sikrer dette. Uligheden som må løses for <math>\mu</math> er:
:<math> 0,05 > \rho(1/\mu)/(1-\rho)</math>
:<math> 0,05 > (\lambda/\mu)(1/\mu)/(1-\lambda/\mu)</math>
:<math> 0,05 > (100/\mu)(1/\mu)/(1-100/\mu)</math>
Denne ulighed omskrives til følgende [[andengradsligning]] (fordi <math>\mu > \lambda = 100</math>):
:<math> \mu^2 - 100\mu - 2000 > 0</math>
Den tilsvarende andengradsligning har to løsninger <math>\mu=50\pm 67,08</math>, dvs. for at sikre uligheden skal
<math>\mu > 50 + 67,08 = 117,08</math>. Det betyder at arbejderen (som i dette tilfælde er netbanken) skal have en arbejdskapacitet på mindst <math>117,08</math> i sekundet.

==Referencer==
{{reflist}}

==Litteratur==
*{{cite book|title=Teletrafikksystemer|author=Arne Myskja|publisher=[[Tapir forlag]]|date=1974}} 2 bind.
*{{cite book|title=Køteori|author=Andreas Bachmann|publisher=Bedriftsøkonomens forlag|date=1981}} 185 sider.
*{{cite book|title=Køteori, ventelister og produksjonsplanlegging|url=http://www.nb.no/utlevering/nb/749598005c7c1e6f9152fde5ebd36312#&struct=DIV106|author=Bjørn Nygaard|date=1989|publisher=NKI}} Del av ''Statistikk og planlegging i helsevesenet''.
*{{cite book|title=Køteori|author=[[Jan Evensmo]]|url=http://www.nb.no/utlevering/nb/cfbef6ad1acb0f61d678a0d85a498e9d#&struct=DIV328|date=1991|publisher=Tano}} Del av ''Kvantitative metoder, analyse og simulering av økonomiske og administrative modeller''.
*{{cite book|title=Operasjonsanalyse|url=http://www.nb.no/utlevering/nb/ae470aefd91bf717f41cc22c94095dcc#&struct=DIV318|author=Kurt Jörnsten, Sverre Storøy og Stein W. Wallace|date=1999|publisher=[[Cappelen]] akademisk}} 340 sider.
* {{cite book | first=Donald | last=Gross |author2=Carl M. Harris  | title=Fundamentals of Queueing Theory | publisher=Wiley | year=1998 | isbn=0-471-32812-X}} [http://books.google.com.br/books/about/Fundamentals_of_Queueing_Theory.html?id=K3lQGeCtAJgC Online]
* {{cite book |last=Deitel |first=Harvey M. |title=An introduction to operating systems |orig-year=1982 |url=http://portal.acm.org/citation.cfm?id=79046&dl=GUIDE&coll=GUIDE |edition=revisited first |year=1984 |publisher=Addison-Wesley |isbn=0-201-14502-2 |page=673}} chap.15, pp.&nbsp;380–412
* {{cite book | last=Lazowska | first=Edward D. |author2=John Zahorjan |author3=G. Scott Graham |author4=Kenneth C. Sevcik  | publisher=Prentice-Hall, Inc| year=1984 | title=Quantitative System Performance: Computer System Analysis Using Queueing Network Models | url=http://www.cs.washington.edu/homes/lazowska/qsp/ | isbn=0-13-746975-6}}
* {{cite book | last=Zukerman | first=Moshe | title=Introduction to Queueing Theory and Stochastic Teletraffic Models | url=http://www.ee.cityu.edu.hk/~zukerman/classnotes.pdf}}

== Eksterne henvisninger ==
* [http://www.supositorio.com/rcalc/rcalclite.htm Queueing theory calculator] {{Webarchive|url=https://web.archive.org/web/20161127144552/http://supositorio.com/rcalc/rcalclite.htm |date=27. november 2016 }}
* [http://people.revoledu.com/kardi/tutorial/Queuing/index.html Teknomo's Queueing theory tutorial and calculators]
* [http://www.netlab.tkk.fi/opetus/s383143/kalvot/english.shtml Virtamo's Queueing Theory Course]
* [http://web2.uwindsor.ca/math/hlynka/queue.html Myron Hlynka's Queueing Theory Page]
* [http://www.eventhelix.com/RealtimeMantra/CongestionControl/queueing_theory.htm Queueing Theory Basics]
* [http://queueing-systems.ens-lyon.fr/ A free online tool to solve some classical queueing systems]
* [http://www.slate.com/articles/business/operations/2012/06/queueing_theory_what_people_hate_most_about_waiting_in_line_.html What You Hate Most About Waiting in Line: (It’s not the length of the wait.)], by Seth Stevenson, ''Slate'', 2012 – popular introduction

{{Autoritetsdata}}

[[Kategori:Køstyring]]
[[Kategori:Logistik]]
[[Kategori:Sociofysik]]