En introduktion till köningsteori

Köteori är den matematiska studien av kö eller väntar i rader. Köerna innehåller kunder (eller "artiklar") som personer, objekt eller information. Köer bildas när det finns begränsade resurser för att tillhandahålla en service. Om det till exempel finns 5 kassaapparater i en livsmedelsbutik, kommer det att bildas kö om mer än 5 kunder vill betala för sina varor samtidigt.

En grundläggande kösystem består av en ankomstprocess (hur kunder anländer till kön, hur många kunder som finns totalt), själva köen, serviceprocessen för att ta hand om dessa kunder, och avgångar från systemet.

Matematisk kömodeller används ofta i programvara och företag för att bestämma det bästa sättet att använda begränsade resurser. Kömodeller kan svara på frågor som: Vad är troligt att en kund väntar 10 minuter i rad? Vad är den genomsnittliga väntetiden per kund? 

Följande situationer är exempel på hur köteori kan tillämpas:

• Väntar i rad i en bank eller en butik
• Väntar på att en kundtjänst svarar på ett samtal efter att samtalet har placerats i väntetid
• Väntar på att ett tåg kommer
• Väntar på att en dator ska utföra en uppgift eller svara
• Väntar på en automatisk biltvätt för att rengöra en rad bilar

Karaktäriserar ett kösystem

Kömodeller analyserar hur kunder (inklusive personer, objekt och information) får en tjänst. Ett kösystem innehåller:

• Ankomstprocess. Ankomstprocessen är helt enkelt hur kunderna anländer. De kan komma i en kö ensam eller i grupper, och de kan komma med vissa intervall eller slumpmässigt.
• Beteende. Hur uppför sig kunderna när de står i linje? Vissa kanske är villiga att vänta på sin plats i kön; andra kan bli otåliga och lämna. Ännu andra kan bestämma sig för att gå igen i kön senare, till exempel när de hålls kvar med kundservice och beslutar att ringa tillbaka i hopp om att få snabbare service. 
• Hur kunderna servas. Detta inkluderar hur lång tid en kund servas, antalet servrar som är tillgängliga för att hjälpa kunderna, vare sig kunderna serveras en efter en eller i batchar, och i vilken ordning kunderna servas, även kallad tjänstedisciplin.
• Servicedisciplin hänvisar till regeln där nästa kund väljs. Även om många detaljhandelsscenarier använder "först till kvarn" -regeln, kan andra situationer kräva andra typer av tjänster. Till exempel kan kunder serveras i prioriterad ordning, eller baserat på antalet varor de behöver servas (till exempel i en expressbana i en livsmedelsbutik). Ibland kommer den sista kunden som kommer att serveras först (sådana är i fallet i en bunt med smutsiga diskar, där den ovanpå är den första som tvättas).
• Väntrum. Antalet kunder som får vänta i kön kan vara begränsat baserat på tillgängligt utrymme.

Matematik för köteori

Kendalls notation är en kortfattad notation som anger parametrarna för en grundläggande kömodell. Kendalls notation är skriven i formen A / S / c / B / N / D, där var och en av bokstäverna står för olika parametrar.

• Termen beskriver när kunder anländer till kön - i synnerhet tiden mellan ankomst eller interarrivaltider. Matematiskt specificerar denna parameter sannolikhetsfördelningen som gränsövervakningstiderna följer. En vanlig sannolikhetsfördelning som används för A-termen är Poisson-distributionen.
• S-termen beskriver hur lång tid det tar innan en kund får service efter att den lämnat kön. Matematiskt anger denna parameter sannolikhetsfördelningen som dessa servicetider Följ. Poisson-distributionen används också ofta för S-termen.
• Termen c anger antalet servrar i kösystemet. Modellen antar att alla servrar i systemet är identiska, så att alla kan beskrivas med S-termen ovan.
• B-termen anger det totala antalet objekt som kan finnas i systemet och inkluderar objekt som fortfarande är i kön och de som servas. Även om många system i den verkliga världen har en begränsad kapacitet är modellen lättare att analysera om denna kapacitet anses oändlig. Följaktligen antas systemet ofta vara oändligt om kapaciteten hos ett system är tillräckligt stor.
• N-termen anger det totala antalet potentiella kunder - dvs antalet kunder som någonsin skulle kunna komma in i kösystemet - vilket kan betraktas som begränsat eller oändligt.
• D-termen specificerar servicedisciplinen för kösystemet, till exempel först till kvarn eller senast in-först-ut.

Lilles lag, vilket först bevisades av matematikern John Little, säger att det genomsnittliga antalet objekt i en kö kan beräknas genom att multiplicera genomsnittsfrekvensen som artiklarna anländer till systemet med den genomsnittliga tiden de spenderar i den.

• I matematisk notation är Little's lag: L = λW
• L är det genomsnittliga antalet artiklar, λ är den genomsnittliga ankomsthastigheten för artiklarna i kösystemet, och W är den genomsnittliga tiden som artiklarna spenderar i kösystemet.
• Lits lag antar att systemet är i ett "stadigt tillstånd" - de matematiska variablerna som karakteriserar systemet förändras inte över tid.

Även om Lilles lag endast behöver tre ingångar är den ganska allmän och kan tillämpas på många kösystem, oavsett vilka typer av objekt i kön eller hur artiklar bearbetas i kön. Lits lag kan vara användbar för att analysera hur en kö har presterat under en tid, eller för att snabbt mäta hur en kö för närvarande presterar.

Till exempel: ett skoboksföretag vill ta reda på det genomsnittliga antalet skobox som lagras i ett lager. Företaget vet att den genomsnittliga ankomsthastigheten för lådorna till lagret är 1 000 skoboxar / år, och att den genomsnittliga tiden de tillbringar i lagret är cirka 3 månader, eller ¼ av ett år. Således ges det genomsnittliga antalet skoboxar i lagret av (1000 skoboxar / år) x (¼ år), eller 250 skokartonger.

Key Takeaways

• Köteori är den matematiska studien av kö eller väntar i rader.
• Köerna innehåller "kunder" som personer, objekt eller information. Köer bildas när det finns begränsade resurser för att tillhandahålla en tjänst.
• Köteori kan tillämpas på situationer som sträcker sig från att vänta i kö i mataffären till att vänta på att en dator ska utföra en uppgift. Det används ofta i programvara och affärsprogram för att bestämma det bästa sättet att använda begränsade resurser.
• Kendalls notation kan användas för att specificera parametrarna för ett kösystem.
• Lits lag är ett enkelt men generellt uttryck som kan ge en snabb uppskattning av det genomsnittliga antalet objekt i en kö.

källor

• Beasley, J. E. "Queuing theory."
• Boxma, O. J. “Stokastisk prestandamodellering.” 2008.
• Lilja, D. Mätning av datorprestanda: En utövares guide, 2005.
• Little, J., and Graves, S. “Kapitel 5: Little's law.” År Byggnadsintuition: Insikter från modeller för grundläggande driftshantering och principer. Springer Science + Business Media, 2008.
• Mulholland, B. "Lilla lag: Hur man analyserar dina processer (med smygbomber)." Process.st, 2017.