De matematiske utfordringer knyttet til data- og teletrafikk er større enn noensinne i verdens matematikkår 2000, skriver BENT NATVIG, professor i matematisk statistikk ved Universitetet i Oslo og deltidsansatt ved Norsk Regnesentral. Kronikken skisserer utviklingen av matematisk køteori og er basert på et foredrag på Norsk Telemuseum under Forskningsdagene tidligere i høst.

Køteori - en nøkkel til kortere ventetider

Køer forårsaker store problemer og økonomiske tap for enkeltmennesket og samfunnet. Heldigvis finnes det et matematisk fagfelt, køteori, som kan komme politikerne til unnsetning og brukes til å forkorte ventetidene.

Tiltak for å redusere køene er særdeles kostnadskrevende. Dette er åpenbart i trafikksektoren. Det er ikke mindre åpenbart i helsesektoren. Det oppfattes som hjerterått at mennesker dør i helsekø, mens de f.eks. venter på strålebehandling mot kreft. Politikerne har derfor innført såkalte ventelistegarantier for å prøve å sette en øvre grense for ventetiden til adekvat behandling. Slike garantier blir imidlertid meningsløse hvis en ikke setter inn tilstrekkelige tiltak for å redusere køene og administrere dem på en fornuftigere måte.

Til unnsetning kommer fagfeltet køteori. Dette er matematisk teori basert på sannsynlighetsregning til å dimensjonere et køsystem på en optimal måte.

La oss se på supermarkedet der mange av oss har lang erfaring i køstudier. P.g.a. selvbetjening er køene flyttet til kassene. Et køteoretisk problem er da å bestemme hvor mange kasser som til enhver tid skal være betjent. Kundene ønsker selvsagt dette antallet høyest mulig for å måtte vente minst mulig. Et for høyt antall vil imidlertid medføre at personene i kassene innimellom er fullstendig arbeidsledige i lengre perioder, noe som medfører unødig høye lønnsutgifter for eieren av supermarkedet. Hvis eieren på den annen side stort sett har for få kasser åpne, risikerer vedkommende at alle kundene forsvinner til en konkurrent med kortere køer.

Et stikkord i administreringen av slike køer er fleksibilitet. Den dyktige eier av et supermarked regulerer antall åpne kasser kontinuerlig ut fra lengden på køene, ved å la betjeningen kunne drive annet forefallende arbeid når køene er korte. Det kan også være egne kasser for småhandlerne. På den annen side kan den dyktige kunde oppsøke supermarkedet på de mindre travle tidspunktene og gjøre storhandelen da.

Hvorfor er køteori spesielt aktuelt i år 2000? Et stikkord her er informasjons- og kommunikasjonsteknologi (IKT). For å dimensjonere lokale, nasjonale og internasjonale nett for data- og teletrafikk er en nødt til å ha en teori som grunnlag for å avstemme kundenes bruk og behov mot utbygnings- og driftskostnader. Vi står følgelig

overfor samme type utfordringer som når veinettet, helsesektoren eller betalingssystemet i supermarkedet skal dimensjoneres.

Et sentralt begrep i moderne vitenskap er modell. De fleste er klar over at økonomene i Norges Bank, Statistisk Sentralbyrå og Finansdepartementet forsøker å styre landets

økonomiske utvikling ved hjelp av teoretiske modeller som utnytter innsamlete, relevante data. I prinsippet er ikke det noe annet enn det arkitektfirmaet "Snøhetta" gjør når de bygger en mindre modell av det nye operabygget for at de selv og andre interesserte skal få et godt og forhåpentligvis realistisk bilde av hvordan bygget vil ta seg ut i virkeligheten. Modeller er altså verktøy til å beskrive og styre virkelighetens verden.

For å beskrive og utvikle modeller trengs hjelpemidler, f. eks. språk, tegninger, fysiske konstruksjoner osv. For køteoretisk modellering er matematikken språket og sannsynlighetsregningen en kasse av byggeklosser. Ved konstruksjon av en sannsynlighetsteoretisk modell har en to motstridende interesser. På den ene siden må modellen være så nær opp til den virkelighet vi ønsker å beskrive, at de avledede resultater tilnærmet også gjelder i praksis. På den annen side må modellen være så enkel at vi har muligheter til å bruke matematisk verktøy til å avlede interessante resultater.

Det er verdt å merke seg at vi ønsker å utlede matematiske resultater på en slik form at de er velegnet for numeriske beregninger. Når den matematiske modellering "møter veggen", må simuleringer på datamaskin overta. For så til slutt å sjekke om modellen og de avledede resultater er i overensstemmelse med data fra virkeligheten, benytter en seg av teknikker fra den statistiske metodelære.

La oss nå se nærmere på telenettet og betrakte en telefonsentral for en større bedrift.

Kunder ringer inn på tilsynelatende helt tilfeldige tidspunkter. Siden sentralen har begrenset kapasitet, risikerer kunden å få et opptattsignal. Unngår kunden dette, vil vedkommende i beste fall umiddelbart få en ledig linje. Hvis ikke, blir kunden plassert i kø, utsettes for ikke altfor smektende musikk og med jevne intervaller gitt beskjed om at "du rykker stadig frem i køen". Kunden kan da etter en stund gi opp og legge på røret eller vente til det blir en ledig linje.

Dimensjoneringen av telefonsentralen skjer på to måter. For det første må en bestemme seg for hvor mange kunder en kan tillate å vente i kø før en gir neste kunde opptattsignalet. Dette kalles generelt "venteromskapasiteten". Dernest må en bestemme antall linjer, generelt kalt "betjenere".

Kunder som har bestilt bord på forhånd, slipper å stå i kø. Dette er et eksempel på et køsystem der kundene tilhører forskjellige prioritetsklasser. Slike systemer er helt vanlige i nett for data- og teletrafikk. Telefonsentralen beskrevet over utgjør det vi kan kalle et køelement. Disse kan kobles sammen på ulike måter til et kønettverk.

Ved hjelp av våre kømodeller ønsker vi å kunne si noe om variasjonen i antall kunder som enten blir betjent eller står i kø på ulike tidspunkter, samt variasjonen i ventetiden frem til betjening for en ankommende kunde. Tilsvarende er vi interessert i variasjonen i tiden en vilkårlig betjener må arbeide i et strekk uten pause, kalt opptattperioden, og variasjonen i tiden vedkommende er uten arbeid i et strekk, kalt ledigperioden. Endelig er vi interessert i prosessen som genereres av tidspunktene når kundene forlater køelementet, kalt outputprosessen. Denne kan være inputprosess til et nytt køelement.

Køteoriens tradisjonelle modeller antar at tidene mellom ankomster av kunder har samme fordeling, og at tidene er innbyrdes uavhengige. Tilsvarende antas det at tidene det tar å betjene kundene har samme fordeling, er innbyrdes uavhengige og også uavhengige av ankomsttidene. En generell kømodell av denne typen betegnes G/G/s/N.

Her står den første "G" for generell fordeling for tidene mellom ankomster, den andre "G" for generell fordeling for betjeningstidene, "s" er antall betjenere mens "N" er venteromskapasiteten.

Den danske ingeniøren Agner Krarup Erlang la grunnlaget for køteorien ved å publisere et arbeid om sannsynlighetsteori og telefonsamtaler i "Nyt Tidsskrift for Matematik" i 1909. I 1917 publiserte han artikkelen "Løsning af nogle Problemer fra Sandsynlighedsregningen af Betydning for de automatiske Telefoncentraler" i "Elektroteknikeren". Her brukte han med stor suksess et spesialtilfelle, betegnet M/M/s/0, av den generelle kømodellen nevnt ovenfor til å beskrive trafikken ved en telefonsentral og til dimensjonering.

De to "M"ene i betegnelsen står for Markovsk etter den russiske matematikeren Andrej Markov (1856 -1922) som er en av grunnleggerne av moderne sannsynlighetsregning. Han ble forøvrig æresdoktor ved Universitetet i Oslo ved Abel-jubileet i 1902.

Det som kjennetegner en Markovsk ankomstprosess, er at på ethvert tidspunkt er tiden frem til neste ankomst av en kunde uavhengig av tiden siden forrige kunde ankom. Tilsvarende for en Markovsk betjeningsprosess er på ethvert tidspunkt tiden frem til betjeningen blir avsluttet, uavhengig av hvor lenge den allerede har vart.

Ifølge Erlang hjelper det altså lite at du har ventet veldig lenge på at personen i telefonkiosken skal bli ferdig med å skravle. Du er egentlig like langt som da vedkommende startet. Dette er som i Ludo. Om du har kastet terning en lang rekke ganger uten å få "6" for å komme i gang med spillet, er du like langt som da du begynte å slå.

Nordmannen Tore Olaus Engset fulgte opp med et arbeid i 1918 i det tyske "Elektrotechnische Zeitschrift" om bruk av sannsynlighetsregning for å bestemme antall utgående linjer i en automatisk telefonsentral.

Engset antar at denne sentralen skal betjene et bestemt antall kunder som ønsker utgående samtaler til resten av verden. Sentralen har ingen venteromskapasitet. Han ønsker å bestemme antall utgående linjer (betjenere) på en optimal måte. Han antar at hver av kundene ønsker utgående samtaler uavhengig av hverandre.

Uten at Engset presiserer det eksplisitt er han nødt til å anta at hver av ankomstprosessene for disse kundene nettopp er Markovsk. Han beregner så sannsynligheten for at et bestemt, vilkårlig antall utgående linjer er opptatt, og spesielt sannsynligheten for at alle utgående linjer er opptatt. Formelen for dette kalles Engsets tapsformel. For tilfellet at også betjeningsprosessene er uavhengige av hverandre samt uavhengige av ankomstprosessene, blir denne formelen enkel og vakker. Den har da også en sentral plass i køteoretiske fagbøker.

Engset var gjennom hele livet ansatt i Telegrafverket og avsluttet karrieren som Telegrafdirektør fra 1930 - 1935 etter mange år som nestkommanderende. I 1910 ble han medlem av en tremannskomite som skulle gi anbefaling om innføring av en helt ny generasjon av telefonsentraler. Den første av disse ble satt i drift i 1921.

Helt nylig er det dukket opp en 130 siders upublisert rapport som Engset avsluttet i 1915, altså før arbeidet til Erlang fra 1917. Denne er oversatt til engelsk og kommentert av tidligere professor ved NTNU Arne Myskja, som også har skrevet en utmerket biografi om Engset. Alt dette er publisert i Telektronikk i 1998, et tidsskrift utgitt av Telenor Forskning og Utvikling. Arbeidene til Engset er svært imponerende, delvis fordi de ble utført i sene nattetimer utenom ordinært arbeid, men også fordi han ikke hadde tilgang til våre dagers sannsynlighetsteori samt numeriske metoder tilrettelagt for datamaskiner. Moderne køteori har kunnet utvikle langt mer avanserte modeller, der f.eks. både ankomstprosessen og betjeningsprosessen avhenger av det totale antall kunder som enten blir betjent eller står i kø. En kan f.eks. la kundene være fleksible og slutte seg raskere til korte køer og tilsvarende tregere til lange køer. Dette oppnåes i telefonkøer ved at det stadig oppgis hvilket nummer en er i køen. Tilsvarende kan betjenerne arbeide raskere når det er mange i køen og tilsvarende saktere når det er få.

Det er vist, også teoretisk, at dette stort sett leder til kortere ventetider for kundene og mer stabile forhold. Videre kan en ved dagens datamaskinbaserte simuleringsteknikker analysere kompliserte nettverk av køelementer.

Ironisk sett er de matematiske utfordringer knyttet til data- og teletrafikk større enn noensinne. På den annen side er det få av dagens ungdommer som går med en Engset i maven. Realfagene generelt og de matematiske fag spesielt sliter med voldsomme rekrutteringsproblemer. Derfor er det viktig å fokusere på betydningen av realfaglig forskning for moderne samfunnsutvikling.