Plannen is NP-hard. We hebben reacties in milliseconden nodig.

Het probleem lijkt simpel. Dat is het niet.

Van buitenaf toont een boekingspagina de tijden waarop iemand vrij is. Onder de motorkap is een maand met boekbare slots de doorsnede van alle onderstaande beperkingen.

• Beschikbaarheidsroosters die zijn gedefinieerd in de eigen tijdzone van de host, vaak meerdere per host

• Datumoverschrijvingen die het terugkerende rooster op specifieke dagen vervangen

• Periodes van afwezigheid en reisroosters die halverwege de maand een tijdzone verschuiven

• Bezettingsmomenten die uit elke gekoppelde externe kalender worden gehaald

• Boekings- en duurbeperkingen per dag, week, maand en jaar

• Minimale termijn, buffers, slotintervallen en offsets die bepalen welke starttijden überhaupt in aanmerking komen

Dat is één host. Elke team-schedulinglink verhoogt de inzet op een andere manier.

• Collective events vereisen dat alle hosts tegelijk beschikbaar zijn, dus de volledige set beperkingen van elke host moet met die van alle anderen worden gecombineerd

• Round robin-events vereisen dat wordt gekozen welke host de boeking krijgt, onder invloed van wegingen, eerlijkheid en prioriteiten

• Managed events zetten één template uit over een heel team, dus één configuratiewijziging herschikt de set beperkingen voor elk lid tegelijk

• Routing versmalt de pool van hosts dynamisch, per booker, voordat überhaupt beschikbaarheid wordt berekend

Elke beperking op zichzelf is makkelijk. De combinatie niet. Het vinden van een optimale vergadertijd voor een groep onder individuele beschikbaarheidsbeperkingen is een goed bestudeerd NP-hard probleem.

Wees precies over waar de moeilijkheid zit. Het opsommen van de vrije slots van één host is polynomiale intervalwiskunde. Wat NP-hard is, is wat we daarboven moeten optimaliseren, zoals het beste gemeenschappelijke tijdstip voor een groep of de eerlijkste verdeling van boekingen over een reeks toekomstige boekingen. De architectuur houdt die twee gescheiden. Het opsommen blijft lineair, en de optimalisatie mag nooit een search worden.

NP-hard betekent dat er geen polynomiaal-tijdalgoritme bekend is, en tenzij P gelijk is aan NP, bestaat het ook niet. Niet “we hebben het nog niet geoptimaliseerd”. Niet “we hebben betere hardware nodig”. Exhaustive search groeit exponentieel. Het voelt direct voor een team van 5 personen en kost vele seconden voor een organisatie met 3.000 leden. De grootste klanten betalen eerst voor een slecht algoritme.

De beperkingen van real-time SaaS

De batchwereld lost dezelfde klasse van probleem op met een fatsoenlijk budget. Airline crew scheduling krijgt uren solver-tijd op dedicated clusters, en niemand stapt aan boord terwijl de optimizer draait. Een boekingspagina krijgt een paar honderd milliseconden, en de deadline komt van de booker die naar een spinner staart, niet van onze infrastructuur.

De voor de hand liggende uitweg is om beschikbaarheid vooraf te berekenen in een achtergrondjob en die uit een tabel te serveren. De inputs blijven daarvoor niet stil liggen. Bezettingsmomenten veranderen zodra iemands kalender verandert, elke nieuwe boeking gebruikt een slot en kan een limiet vullen, en de vraag wordt per booker bepaald door hun tijdzone, de gekozen duur, het venster dat ze bekijken en de hosts die routing voor hen heeft geselecteerd. Alles vooraf berekenen voor elke combinatie is een eigen combinatorische explosie, en elk vooraf berekend antwoord is verouderd op het moment dat er een meeting op de kalender van een host landt. Verouderde beschikbaarheid is erger dan trage beschikbaarheid, omdat die tijden aanbiedt die al bezet zijn. Dus berekenen we slots op het moment van de aanvraag, en de caches vóór die berekening zijn bewust kortlevend.

We draaien dit op Vercel's Fluid Compute omdat het het makkelijk maakt om de app te schalen. Capaciteit volgt het verkeer zonder dat we iets hoeven te provisionen, instances zijn langlevend en worden hergebruikt in plaats van per request opgestart, cold starts zijn grotendeels verdwenen (pre-warming, bytecode-caching), requests delen een instance, en waitUntil schuift niet-kritisch werk voorbij de response. De facturering wordt gedomineerd door actieve CPU. Wachten op een calendar API is bijna gratis, en CPU verbranden aan een combinatorische search is precies waar we voor betalen.

Greedy by Design

We doen nooit een exhaustive search over de ruimte. Op elk beslissingspunt maken we de lokaal beste keuze met de informatie die we hebben, committeren we ons daaraan en gaan we verder. Geen lookahead. Geen backtracking.

In de SaaS-wereld heeft greedy een negatieve bijklank en kan het klinken als de naïeve optie. Maar voor sommige problemen is greedy aantoonbaar het beste wat je kunt doen. Voor set cover, een klassiek NP-hard probleem in dezelfde familie als group scheduling, haalt greedy een logaritmische benaderingsratio, en geen enkel polynomiaal-tijdalgoritme kan het beter doen tenzij P gelijk is aan NP.

Round-robin hosttoewijzing is het duidelijkste voorbeeld. “Correct” toewijzen zou betekenen dat je optimaliseert over elke mogelijke toekomstige toewijzing, de exponentiële search die we weigeren uit te voeren. In plaats daarvan is de haalbare set de hosts die beschikbaar zijn op het gevraagde tijdstip, en selectie is drie filterstappen op volgorde:

pool = hostsAvailableAt(requestedTime)
if (weightedDistribution) pool = largestShortfall(pool) // fairness
pool = highestPriority(pool)
return leastRecentlyBooked(pool)                        // tie-break

Eerlijkheid vergelijkt de werkelijke boekingen van elke host over het recente interval met een gewogen doelaandeel en houdt de hosts die het verst achterlopen over (de hoogste weging breekt gelijke standen). Concreet:

3 hosts, equal weights, 12 bookings this interval
target: 4 each
actual: A=6  B=4  C=2
shortfall: A=-2  B=0  C=+2  ->  C gets the booking

De volgorde van de filters is een productbeslissing. Eerlijkheid draait vóór prioriteit en prioriteit vóór recency, en het omwisselen van twee filters geeft dezelfde boeking aan een andere host. Hoe dan ook is de beslissing een paar lineaire scans, of de pool nu 5 hosts of 5.000 hosts heeft.

Dit is wat “we weigeren die search uit te voeren” kost. Een round-robin-event met 3.000 hosts zit achter routing. Een booker beantwoordt de routingvragen en de pool krimpt tot 40 gekwalificeerde hosts. Een geboekte host wordt nooit uit de pool verwijderd, alleen lager gerangschikt (als iedereen anders out of office is, krijgt de host die net een boeking kreeg ook de volgende), dus elke boeking heeft onafhankelijk 40 mogelijke toegewezen hosts.

40 hosts, volgende 25 boekingen

40²⁵ ≈ 10⁴⁰ mogelijke toewijzingen. Bij een miljard checks per seconde draait die search 3,6 × 10²³ jaar, ongeveer 26 biljoen keer de leeftijd van het universum.

40 hosts, volgende 50 boekingen 40⁵⁰ ≈ 10⁸⁰ mogelijke toewijzingen. Dat is ongeveer het aantal atomen in het waarneembare universum.

De greedy-cascade. Drie lineaire passes over 40 hosts. Ongeveer 100 vergelijkingen, in ruim minder dan een milliseconde.

Dat is nadat routing al 2.960 hosts heeft weggefilterd. Dezelfde eerlijkheidsgaranties, maar bijna veertig ordes van grootte verschil in kosten.

Geen enkele beslissing hoeft perfect te zijn, omdat het systeem zichzelf corrigeert. Als je vandaag een host te zwaar belast, krimpt hun achterstand, zodat eerlijkheid hen morgen lager prioriteert. Correcties rijden op hetzelfde criterium mee. Een host die halverwege het interval binnenkomt, krijgt krediet voor het gemiddelde aantal boekingen per host van vóór hun komst, en een host die terugkeert uit out of office krijgt krediet voor hun aandeel in de boekingen die tijdens hun afwezigheid zijn gedaan. De achterstandsberekening ziet een aangepast aantal. Geen herberekende geschiedenis, geen herverdelingsronde.

Slotgeneratie is op dezelfde manier greedy. Normaliseer elke beperking op één absolute tijdas, loop één keer vooruit, geef elk overlevend starttijdstip uit en kom nooit terug. Zelfs de instelling voor slot-optimalisatie van de schedulinglink, die bepaalt waar het raster begint binnen elk vrij venster, is tijdens dezelfde sweep één regel rekenwerk, geen vergelijking van layouts.

De trade-off is echt, en het hoekgeval is makkelijk te construeren. Geef één host een smal beschikbaarheidsvenster dat overlapt met dat van alle anderen, laat greedy hen de eerste boeking daarin geven, en je hebt het enige slot geblokkeerd dat een latere, meer beperkte boeking had kunnen gebruiken. Exhaustive search had dat zien aankomen. Greedy kijkt niet vooruit. We weten dat dit soort gevallen bestaat en moeten dit oké vinden om te shippen, omdat we milliseconden hebben. De achterstandsberekening trekt het in de tijd weer recht.

Hoe lineair er echt uitziet

“We verwerken beperkingen lineair” is makkelijk om te zeggen. Concreet is de beweging altijd dezelfde. Zet alles om naar intervallen op één absolute tijdas, sorteer één keer, sweep.

Beperkingen worden intervallen voordat iets ze aanraakt. Een wekelijkse regel wordt niet per kandidaat-slot geëvalueerd. Die wordt één keer uitgebreid, in één loop over de dagen van het gevraagde venster, naar UTC-intervallen:

rule: Mon-Fri, 09:00-17:00, Europe/Berlin

Mon ██████ 07:00Z-15:00Z
Tue ██████ 07:00Z-15:00Z
Wed ██████ 07:00Z-15:00Z
Thu ██████ 07:00Z-15:00Z
Fri ██████ 07:00Z-15:00Z
Sat (none)
Sun (none)

Die loop is waar reisroosters halverwege de maand de tijdzone wisselen en daylight saving een offset verschuift, dus werk dat niet van de dag afhangt wordt daarbuiten geplaatst. Tijdzoneconversie domineert de loop, en die draait één keer per dag per regel, niet één keer per slot.

Collective events zijn een two-pointer-merge, geen cross product. Dertig hosts hebben de tijden nodig waarop alle dertig vrij zijn. Elk interval tegen elk interval vergelijken is twee keer kwadratisch. In plaats daarvan worden de intervallen van elke host gesorteerd op begintijd en samengevoegd tot een lopende lijst met “gemeenschappelijke beschikbaarheid”:

common: 09:00-13:00, 15:00-18:00
host B: 11:00-16:00
result: 11:00-13:00, 15:00-16:00

Eén pointer loopt door de gemeenschappelijke lijst, één door de lijst van de volgende host, en we schuiven altijd het interval op dat het eerst eindigt. De kern van de echte implementatie is precies zo klein.

while (commonIndex < common.length && userIndex < userRanges.length) {
  const a = common[commonIndex];
  const b = userRanges[userIndex];
  const start = Math.max(a.startValue, b.startValue);
  const end = Math.min(a.endValue, b.endValue);
  if (start < end) intersected.push({ start, end });
  // advance whichever range ends first
  if (a.endValue <= b.endValue) commonIndex++;
  else userIndex++;
}

Elke host kost één lineaire pass, en op het moment dat de gemeenschappelijke lijst leeg raakt, stoppen we. Als hosts één tot en met zeven geen gedeelde tijd hebben, kunnen hosts acht tot en met dertig daar niets aan veranderen.

Bezettingsmomenten worden in één gesorteerde sweep afgetrokken. Boekingen, externe kalendergebeurtenissen en periodes van out of office komen allemaal in één uitsluitingslijst terecht, één keer gesorteerd op begintijd. Elk beschikbaarheidsbereik loopt er in volgorde doorheen en houdt de gaten over:

available: 09:00-17:00
busy:      10:00-11:00, 13:00-14:30
result:    09:00-10:00, 11:00-13:00, 14:30-17:00

for (const busy of sortedBusyTimes) {
  if (busy.start >= sourceEnd) break;     // everything after is irrelevant
  if (busy.end <= currentStart) continue; // already behind us
  if (busy.start > currentStart) {
    result.push({ start: currentStart, end: busy.start }); // keep the gap
  }
  currentStart = busy.end; // jump past the busy block
}
if (currentStart < sourceEnd) {
  result.push({ start: currentStart, end: sourceEnd }); // keep the tail gap
}

Omdat de uitsluitingen gesorteerd zijn, wordt alles achter de break nooit bekeken.

Boekingslimieten worden synthetische bezettingstijd. “5 boekingen per dag” zou tegen elk kandidaat-slot kunnen worden gecontroleerd, tegen een kost van slots × limieten × boekingen. In plaats daarvan wordt het hele tijdvak, zodra de telling de limiet bereikt, één bezettingsinterval en rijdt het mee in dezelfde aftreksweep:

limit: 5 per day
Sep 14 reaches 5 bookings
-> emit busy interval: Sep 14 00:00-24:00
-> subtracted like any calendar event

De limietcontrole draait één keer per periode, en de slotloop leert nooit dat limieten bestaan.

Geen van deze stappen is op zichzelf slim. Een NP-hard probleem binnen een millisecondebudget los je niet op met één briljant algoritme. Je lost het op door bij elke stap te weigeren dat welke berekening dan ook afhangt van het product van twee grote getallen.

Alles om het algoritme heen is ook begrensd

Een perfect algoritme gevoed door een trage query levert nog steeds een trage boekingspagina op, en de datalaag is waar enterprise-scale als eerste pijn doet.

Reads worden gebatcht en daarna in geheugen geïndexeerd. De naïeve vorm is een loop over hosts met drie queries erin. Dertig hosts betekenen 90 round trips naar Postgres voordat er ook maar één interval is berekend, onzichtbaar voor een team van 5 en een productie-incident voor 3.000. De slots-pipeline haalt daarom alles vooraf op:

per host (N+1)

┌─ host 1 ─▶ query bookings
├─ host 2 ─▶ query bookings
├─ host 3 ─▶ query bookings
│ ...
└─ host N ─▶ query bookings

batched

┌─ ONE query: bookings, all hosts
├─ ONE query: OOO days, all hosts
├─ batched queries: limits, all hosts
└─ group into Map<userId, rows>
then a pure in-memory pass per host

Boekingen en out-of-office-dagen worden gelijktijdig geladen onder één Promise.all, en limieten volgen in een tweede gebatchte ronde. Resultaten worden één keer gegroepeerd in Map<userId, rows>-lookups, en vanaf dat moment raakt de beschikbaarheidswiskunde geen database meer aan. De functie per host is getypeerd om de vooraf opgehaalde data te vereisen, zodat niemand stilletjes een query per gebruiker kan terugbrengen zonder dat de compiler klaagt.

Externe kalenders krijgen een cache met strikte regels. Eén round trip naar een provider weegt zwaarder dan de hele intervalberekening, dus de cache is opgebouwd rond drie regels:

miss:  fetch the full 90-day horizon in one provider call, cache it
many calendars miss at once: one batched provider call covers all
error: cache nothing

Eén miss betaalt voor elke volgende read ergens in het venster. En een mislukte provider-call wordt nooit gecachet, omdat een fout cachen als “vrij voor het hele venster” stilzwijgend slots bovenop echte meetings zou aanbieden. Een storing kost een retry, nooit een verkeerd antwoord.

Datumafhandeling is hot-path code. Tijdzonebewuste rekenkunde in een per-slot-loop domineert al het andere, dus conversie gebeurt één keer aan de rand en de inner loops vergelijken gewone UTC-milliscondenwaarden.

Tijdsbudgetten worden getest, niet verondersteld. Unit suites bewijzen dat elk algoritme binnen de tijdsgrens blijft die we op enterprise-schaal hebben, niet alleen dat het het juiste antwoord geeft, zodat een complexiteitsregressie faalt in CI in plaats van in productie.

Waar we eerlijk zijn over waar we nog niet zijn

Alles hierboven is de discipline, niet het eindresultaat. Hier is de kloof, gemeten op mijn eigen 15-minuten-event tegen de productie-API terwijl ik deze post schreef:

slot computation: tens of ms
warm-cache response: 30-75 ms
cold request: ~600 ms (a 200-300 ms Google free/busy call plus lookups and compute)
20-person team page: ~3 s

De berekening blijft binnen budget. De hele pagina blijft alleen binnen budget wanneer de caching vóór de provider-calls zijn werk doet. Teams lopen verder achter, en om meer dan één reden. We draaien de Google-calls voor alle hosts parallel, dus de externe kosten blijven ongeveer vlak terwijl de computationele kant meegroeit met het team. De database voegt zijn eigen vertraging toe. Team availability haalt linkconfiguratie, boekingen, limieten en out-of-office-rows op voor elke host uit tabellen met miljoenen records, en sommige van die queries zijn nog steeds traag.

Round robin is waar we eerst de teamkloof aanpakken, omdat het een eigenschap heeft die het algemene probleem niet heeft. Een collective event heeft elke host vrij nodig, maar een round robin-boeking heeft precies één host nodig. De boekingspagina hoeft niet te weten wie op elk slot beschikbaar is, alleen of iemand beschikbaar is. Dus bouwen we een cache op hoger niveau die voor een maand aan slots het aantal beschikbare hosts opslaat, één keer berekend. Elke boeking verlaagt de aantallen die het beïnvloedt, en de volledige herberekening draait alleen wanneer het aantal van een slot zo laag wordt dat er echt hosts kunnen opraken. De meeste slots komen daar nooit. De dure vraag, welke host de boeking krijgt, wordt nog steeds greedy beantwoord op het moment van boeken. De goedkope vraag, of iemand vrij is, wordt een teller-read.

Elke boekingsfunctie is een algoritmische beslissing

Elke boekingsfunctie die we shippen moet een vraag beantwoorden die de meeste SaaS-producten nooit stellen. Blaast dit de search op? Een functie die als een extra ordering filter in de greedy-cascade kan worden uitgedrukt, is op elke schaal bijna gratis. Iets dat ons dwingt combinaties te vergelijken, wordt opnieuw ontworpen totdat dat niet meer nodig is.

Greedy kiest soms een slechtere optie dan exhaustive search zou hebben gekozen, en dat zal altijd zo blijven. We accepteren dat, begrenzen het en corrigeren het in de tijd, omdat het exhaustieve antwoord pas komt nadat de booker is gestopt met wachten. De trade werkt nu al voor individuele boekingspagina's. Het sneller maken voor een organisatie met 3.000 leden is het werk dat we nu doen.