🔢 mathematics

Polling on a circle with non-uniform batch arrivals

Dit artikel analyseert een pollsysteem op een cirkel met niet-uniforme batch-aankomsten, waarbij de Laplace-Stieltjes-transformatie van de batch-vertraging voor een globaal gated-beleid wordt afgeleid en een gemiddelde-waarde-analyse-algoritme voor een exhaustief beleid wordt voorgesteld, terwijl tegelijkertijd exacte licht- en zware verkeerslimieten voor de systeemprestaties worden vastgesteld.

Oorspronkelijke auteurs: Tim Engels, Ivo Adan, Onno Boxma, Jacques Resing

Gepubliceerd 2026-10-07

📖 4 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Tim Engels, Ivo Adan, Onno Boxma, Jacques Resing

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (https://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

In de wereld van logistiek en wachtrijtheorie bestuderen onderzoekers hoe een enkele server, zoals een buschauffeur of een computerprocessor, meerdere wachtrijen van klanten beheert. Een klassiek model hiervoor is het polling-systeem, waarbij één server in een cirkel beweegt, bij verschillende punten stopt om wachtende items af te handelen voordat hij naar het volgende punt verdergaat. Decennialang hebben wetenschappers deze systemen geanalyseerd onder de aanname dat klanten met gelijke waarschijnlijkheid op willekeurige plekken langs de cirkel arriveren, vergelijkbaar met regendruppels die uniform op een trommelvel vallen. In de echte wereld gedragen systemen zich echter zelden met zodanige perfecte willekeur. In magazijnen worden bijvoorbeeld populaire artikelen vaak in specifieke, voorspelbare zones opgeslagen om het verzamelen te versnellen, terwijl minder populaire artikelen elders worden weggestopt. Dit creëert een niet-uniform patroon waarbij sommige gebieden van de cirkel veel drukker zijn dan andere. Begrijpen hoe een server presteert wanneer de vraag geclusterd is in specifieke locaties, in plaats van gelijkmatig verspreid, is cruciaal voor het ontwerpen van efficiënte systemen die alles afhandelen, van geautomatiseerde magazijnrobots tot datanetwerken.

Een team onderzoekers van de Eindhoven University of Technology heeft deze complexiteit aangepakt door een continu polling-systeem te analyseren waarbij batches klanten op willekeurige tijdstippen arriveren, maar hun locaties een specifieke, niet-uniforme verdeling volgen. Ze richtten zich op twee verschillende manieren waarop een server kan opereren: het "globally gated" beleid en het "exhaustive" beleid. Onder de globally gated aanpak maakt de server een momentopname van alle wachtende klanten op het moment dat hij een nieuwe ronde begint en bedient hij alleen degenen die er al waren, waarbij hij iedereen negeert die arriveert terwijl hij aan het werk is. In tegen te contrary is het exhaustive beleid dynamischer; de server blijft elke klant die hij tegenkomt bedienen totdat de hele cirkel vrij is van wachtende items, zelfs als er tijdens het proces nieuwe klanten arriveren. De onderzoekers waren bijzonder geïnteresseerd in twee prestatie-maten: de tijd die het kost om een specifieke groep klanten te bedienen (de batch sojourn time) en de totale tijd totdat die hele groep terug is afgeleverd bij het startpunt (de tijd tot levering).

Met behulp van geavanceerde wiskundige technieken heeft het team exacte formules afgeleid voor het globally gated beleid, waarbij zij de precieze verdeling van wachttijden berekenden, ongeacht hoe de klanten verspreid waren. Voor het complexere exhaustive beleid ontwikkelden zij een nieuwe methode om de gemiddelde wachttijden te berekenen door in kaart te brengen hoe klanten zich over de cirkel verspreiden ten opzichte van de positie van de server. Hun analyse onthulde een verrassend en contra-intuïtief resultaat: het specifieke patroon van waar klanten arriveren heeft zeer weinig impact op de algehele gemiddelde prestaties van het systeem. Of de klanten nu dicht bij het begin van de route geclusterd zijn, gelijkmatig verspreid zijn of geconcentreerd zijn aan het verre uiteinde, de gemiddelde tijd om een batch te bedienen en te leveren blijft opmerkelijk stabiel. Deze bevinding suggereert dat voor veel praktische toepassingen, zoals de "milkrun" orderpicking-systemen die in moderne magazijnen worden gebruikt, managers er niet voor nodig hebben om de opslaglocaties perfect te optimaliseren om een hoge efficiëntie te bereiken.

De studie vergeleek ook de twee servicenormen onder verschillende verkeersomstandigheden. Wanneer het systeem licht belast is, met weinig bestellingen die arriveren, presteert het exhaustive beleid over het algemeen beter omdat de server geen tijd verspilt aan teruglopen naar het begin om zijn lijst te resetten voordat hij nieuwe items oppakt. Echter, naarmate het systeem zwaarder belast wordt met veel orders, kan het globally gated beleid soms efficiënter zijn, vooral wanneer de tijd die nodig is om rond het magazijn te reizen lang is in verhouding tot de tijd die nodig is om een item te pakken. De onderzoekers bevestigden deze theoretische voorspellingen via numerieke simulaties, waarbij zij lieten zien dat hoewel de keuze van het opslagbeleid er in zeer specifieke, laag-verkeer scenario's toe doet, het verschil verwaarloosbaar is in de meeste real-world situaties. Uiteindelijk biedt het werk een robuust wiskundig fundament voor het begrijpen van continue polling-systemen, en laat het zien dat de stabiliteit en efficiëntie van het systeem veel veerkrachtiger zijn tegen veranderingen in klantlocatiepatronen dan voorheen werd aangenomen.

Technische Samenvatting: Polling op een Cirkel met Niet-Uniforme Batch-Aankomsten

Probleemdefinitie
Dit artikel analyseert een continu polling-systeem op een cirkel met een omtrek van 1, waarbij een enkele server met een constante snelheid cyclisch rondrijdt om klanten te bedienen. Het systeem wordt gekenmerkt door twee primaire kenmerken:

Batch-aankomsten: Klanten arriveren in batches volgens een Poisson-proces. De batchgroottes zijn onafhankelijk en identiek verdeeld (i.i.d.).
Niet-uniforme Aankomstlocaties: In tegenstelling tot eerdere continue polling-modellen die uitgaan van uniforme aankomstlocaties, gaat dit artikel ervan uit dat elke klant binnen een batch wordt toegewezen aan een locatie op de cirkel volgens een algemene, bekende continue distributie $\pi(x)$ . Dit modelleert real-world scenario's zoals magazijnlogistiek (milkrun order picking) waarbij opslagbeleid de locaties van artikelen dicteert.

De studie richt zich op twee prestatie-indicatoren voor een batch:

Batch Verblijftijd ( $S_B$ ): De tijd vanaf de aankomst van een batch tot de voltooiing van de service van de laatste klant in die batch.
Tijd tot Levering ( $D$ ): De tijd vanaf de aankomst van een batch tot de gehele batch is teruggeleverd bij het centrale depot.

Er worden twee serviceregimes onderzocht:

Globally Gated (Globaal Gated): De server bedient alleen klanten die aanwezig zijn aan het begin van de cyclus.
Exhaustive (Uitputtend): De server bedient alle klanten die worden tegengekomen totdat de wachtrij leeg is.

Methodologie
De auteurs hanteren verschillende analytische benaderingen voor de twee serviceregimes vanwege de complexiteit die wordt geïntroduceerd door niet-uniforme aankomstlocaties.

Globally Gated Beleid: De analyse steunt op het afleiden van de Laplace-Stieltjes-Transformatie (LST) van de cyclustijd. Door de cyclustijd te modelleren als een functionele vergelijking die de aankomstprocessen en servicetijden betreft, leiden de auteurs de LST voor de cyclustijd af als een oneindig product. Met behulp van de gezamenlijke distributie van de leeftijd (age) en de resterende cyclustijd, leiden zij exacte LST's af voor de tijd tot levering ( $D$ ) en de batch verblijftijd ( $S_B$ ). De afleiding voor $S_B$ geschiedt door te conditioneren op de locatie van de verste klant in een batch ten opzichte van het depot.
Exhaustive Beleid: Het afleiden van exacte LST's voor het exhaustive beleid met niet-uniforme aankomsten is onhandelbaar. In plaats daarvan stellen de auteurs een Mean-Value Analysis (MVA) voor.
- Zij definiëren $f(x, y)$ als de gemiddelde dichtheid van wachtende klanten op locatie $x$ , gegeven dat de server zich op locatie $y$ bevindt.
- Met behulp van een vertakkingsproces-argument (branching process) met immigratie en een variant van de Wet van Little, bewijzen zij dat $f(x, y)$ een specifieke integraalvergelijking voldoet.
- Zij tonen aan dat deze integraalvergelijking een unieke oplossing heeft in een specifieke functieklasse, die gevonden kan worden via opeenvolgende substituties.
- De auteurs bieden partiële analytische oplossingen voor de integraalvergelijking (door termen te scheiden die gerelateerd zijn aan reistijd, resterende servicetijd en batchgrootte-effecten) en leiden exacte expressies af voor de gemiddelde batch verblijftijd en de gemiddelde tijd tot levering op basis van de oplossing van deze integraalvergelijking.
Limietgedrag: Het artikel leidt exacte expressies af voor de systeemprestaties in zowel de lichte verkeerssituatie ( $\lambda \downarrow 0$ ) als de zware verkeerssituatie ( $\rho \uparrow 1$ ) voor beide servicebeleid.

Belangrijkste Bijdragen

Exacte Expressies voor het Globally Gated Beleid: Het artikel leidt de exacte LST's en gemiddelde waarden af voor zowel de batch verblijftijd als de tijd tot levering onder het globally gated regime, waarbij rekening wordt gehouden met algemene aankomstlocatie-distributies.
Integraalvergelijking voor het Exhaustive Beleid: Voor het exhaustive regime bewijzen de auteurs dat de gemiddelde spreiding van klanten aan een integraalvergelijking voldoet. Zij bieden een methode (opeenvolgende substitutie) om deze vergelijking numeriek op te lossen en leiden exacte expressies af voor de gemiddelde prestatie-indicatoren afhankelijk van deze oplossing.
Light- en Heavy-Traffic Limieten: Exacte limietexpressies worden afgeleid voor beide beleid. Met name de heavy-traffic analyse laat zien dat de invloed van de aankomstlocatie-distributie $\pi(x)$ afneemt naarmate het systeem verzadiging nadert, met name voor de batch verblijftijd.
Toepassing op Milkrun-systemen: De theoretische resultaten worden toegepast op een milkrun order picking systeem in de magazijnlogistiek. De studie onderzoekt hoe verschillende opslagbeleid (bijv. willekeurige versus klasse-gebaseerde opslag) de systeemprestaties beïnvloedt.

Resultaten

Impact van Opslagbeleid: Een contra-intuïtieve bevinding is dat de aankomstlocatie-distributie (opslagbeleid) een minimaal effect heeft op de gemiddelde systeemprestaties, met name onder zwaar verkeer of voor het exhaustive servicebeleid. Hoewel de verwachte batch verblijftijd gevoelig is voor de reistijd naar de verste klant in een batch, zijn de algehele prestatieverschillen tussen diverse opslagbeleid (bijv. het plaatsen van snelle loopers aan het begin, midden of einde van de route) verwaarloosbaar in de meeste praktische scenario's.
Vergelijking van Beleid:
- Onder licht verkeer is het exhaustive beleid over het algemeen te verkiezen boven het globally gated beleid, omdat de server niet naar het depot hoeft terug te keren voordat nieuwe aankomsten worden bediend, wat de stationaire reistijd vermindert.
- Onder zwaar verkeer hangt de voorkeur af van de ratio tussen reistijd en servicetijd. Als reistijden groot zijn ten opzichte van servicetijden, blijft het exhaustive beleid te verkiezen. Echter, als servicetijden groot zijn en de batchgroottes aanzienlijk zijn, kan het globally gated beleid beter presteren omdat het voorkomt dat de server "vast komt te zitten" in het bedienen van nieuwe aankomsten terwijl een batch nog wordt verwerkt.
Effecten van Batchgrootte: Voor het globally gated beleid verhoogt een grotere batchgrootte de verwachte verblijftijd vanwege de toegenomen verwachte afstand naar de verste klant in een batch. Voor het exhaustive beleid is het effect van de aankomstlocatie-distributie op de prestaties prominenter bij kleine batchgroottes en licht verkeer, maar dit neemt af naarmate de batchgroottes en de verkeersbelasting toenemen.

Betekenis en Claims
Het artikel claimt de bestaande literatuur over continue polling-modellen uit te breiden door de aanname van uniforme aankomstlocaties los te laten, wat cruciaal is voor het modelleren van real-world toepassingen zoals magazijnlogistiek waar opslagbeleid niet-uniform is. De auteurs benadrukken dat hoewel de wiskundige afleiding aanzienlijk complexer wordt (van een eendimensionale naar een tweedimensionale representatie), de resulterende prestatie-indicatoren verrassend robuust zijn voor de specifieke keuze van het opslagbeleid.

De betekenis ligt in het bieden van een rigoureus analytisch kader voor continue polling met batch-aankomsten en niet-uniforme locaties, met exacte oplossingen voor het gated geval en een robuuste algoritmische aanpak voor het exhaustive geval. De bevindingen suggereren dat het optimaliseren van het opslagbeleid (bijv. klasse-gebaseerde opslag) voor milkrun-systemen een afnemende meeropbrengst biedt vergeleken met de keuze van het servicebeleid (exhaustive versus gated), vooral in omgevingen met een hoge belasting. Het artikel concludeert door op te merken dat het huidige model onafhankelijke aankomstlocaties binnen een batch veronderstelt en suggereert dat toekomstig werk gecorreleerde locaties (bijv. afhankelijk items die samen worden opgeslagen) en stochastische looptijden zou kunnen verkennen.

Meer zoals dit