Køteori

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å internettet. 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 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, Erlang-B, Erlang-C).[1][2] 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 (Markovmodeller) 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 matematikstudiet på flere af landets universiteter, som DTU, Københavns Universitet, Aarhus Universitet og Aalborg Universitet.[2] I Norge har køteori været en naturlig del af oplæringen i operasionsanalyse 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[3][4] beskriver, at der for et hvert stabilt (stationært) system vil være et forhold mellem ventetid (), antal som betjenes () og tilgang () som er

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.[5]

Et eksempel givet af Little er fra en fødeafdeling:[6]

  • Tilgangen er fødende hver dag
  • Ventetiden er sådan at 10 % ligger 7 dage, resten ligger 2 dage. Gennemsnit bliver dage

Med Littles formel finder en at fødeafdelingen i gennemsnit bruger 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ø

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 opgaver per tidsenhed (for eksempel hver time). Samtidig kommer der 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 First In First Out-betjening). Både belastningen og kapaciteten varierer som Poissonfordelingen.[7] 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
  • gennemsnitlig ventetid i køen (før kunden bliver betjent) bliver
  • gennemsnitlig kølængde (antal som venter) bliver

Antag en netbank som modtager henvendelser i sekundet. Man ønsker at gennemsnitlig ventetid ikke skal overgå 0,05 sekunder. Derfor må netbanken udrustes med en arbejdskapacitet som sikrer dette. Uligheden som må løses for er:

Denne ulighed omskrives til følgende andengradsligning (fordi ):

Den tilsvarende andengradsligning har to løsninger , dvs. for at sikre uligheden skal . Det betyder at arbejderen (som i dette tilfælde er netbanken) skal have en arbejdskapacitet på mindst i sekundet.

Referencer

  1. ^ A.K. Erlangs afvisningsformel er grundstenen for al moderne kommunikation. Videnskab.dk. Hentet 9/8-2016
  2. ^ a b Sådan undgår man lange køer. Videnskab.dk. Hentet 9/8-2016
  3. ^ Alberto Leon-Garcia (2008). Probability, statistics, and random processes for electrical engineering (3rd udgave). Prentice Hall. ISBN 0-13-147122-8.
  4. ^ Allen, Arnold A. (1990). Probability, Statistics, and Queueing Theory: With Computer Science Applications. Gulf Professional Publishing. s. 259. ISBN 0120510510.
  5. ^ Simchi-Levi, D.; Trick, M. A. (2013). "Introduction to "Little's Law as Viewed on Its 50th Anniversary"". Operations Research. 59 (3): 535. doi:10.1287/opre.1110.0941.
  6. ^ John D. C. Little og Stephen C. Graves (2008). "Kap. 5 af Building intuition: Insights from basic operations management models and principles". I D. Chhajed og T. J. Lowe (red.). Little's Law (PDF). Springer Sciences. s. 81-100.
  7. ^ Lidt supplerende køteori Arkiveret 21. september 2016 hos Wayback Machine. Københavns Universitet. Hentet 9/8-2016

Litteratur

Eksterne henvisninger

Medier brugt på denne side