# Plannen is NP-hard. We hebben antwoorden in milliseconden nodig.

> Het probleem lijkt simpel. Dat is het niet.

Published: 2026-09-09 · Author: keith-williams

Canonical: https://cal.com/blog/scheduling-is-np-hard-we-need-responses-in-milliseconds

## Het probleem lijkt simpel. Dat is het niet.

Van buitenaf laat een boekingspagina de tijden zien waarop iemand vrij is. Onder de motorkap is één maand met boekbare slots de doorsnede van elke beperking hieronder.

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

-   Datumspecifieke overschrijvingen die het terugkerende rooster op bepaalde dagen vervangen

-   Perioden buiten kantoor en reisschema’s die halverwege de maand een tijdzone verschuiven

-   Bezet tijden die uit elke gekoppelde externe Calendar worden gehaald

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

-   Minimale kennisgeving, 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 doorsneden

-   Round-robin events vereisen dat wordt bepaald welke host de Booking krijgt, onder invloed van gewichten, eerlijkheid en prioriteiten

-   Managed events duwen één template over een heel Team heen, dus één configuratiewijziging herschikt de set beperkingen voor elk lid tegelijk

-   Routing vernauwt de hostgroep dynamisch, per booker, voordat er überhaupt beschikbaarheid wordt berekend

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

Wees precies over waar de complexiteit zit. Eén hosts vrije slots opsommen is polynomiale intervalwiskunde. Wat NP-hard is, is wat we daarbovenop moeten _optimaliseren_, zoals het beste gezamenlijke moment voor een groep of de eerlijkste toewijzing van Bookings over een horizon van toekomstige Bookings. De architectuur houdt die twee gescheiden. De opsomming blijft lineair, en de optimalisatie mag nooit een search worden.

NP-hard betekent dat er geen algoritme met polynomiale tijd bekend is, en tenzij P gelijk is aan NP, bestaat die ook niet. Niet “we hebben het nog niet geoptimaliseerd”. Niet “we hebben betere hardware nodig”. Uitputtend zoeken groeit exponentieel. Het voelt instant 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 realtime SaaS

De batchwereld lost dezelfde klasse problemen op met een echt budget. Crew scheduling voor luchtvaart krijgt uren aan oplostijd op speciale clusters, en niemand stapt in 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 ontsnapping is beschikbaarheid vooraf te berekenen in een background job en die uit een tabel te serveren. De inputs blijven daar niet stil voor. Bezet tijden veranderen zodra iemands Calendar verandert, elke nieuwe Booking verbruikt een slot en kan een limiet vullen, en de vraag wordt per booker gevormd door hun tijdzone, de gekozen Duration, het venster dat ze bekijken en de hosts die Routing voor hen heeft geselecteerd. Alles vooraf berekenen voor elke combinatie is op zichzelf al een combinatorische explosie, en elk vooraf berekend antwoord is meteen verouderd zodra er een vergadering op een host-Calendar landt. Verouderde beschikbaarheid is erger dan trage beschikbaarheid, omdat die tijden biedt die al bezet zijn. Daarom 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 schalen van de app makkelijk maakt. Capaciteit volgt het verkeer zonder dat we iets hoeven te provisionen, instanties zijn langdurig en worden hergebruikt in plaats van per verzoek opnieuw opgezet, cold starts zijn grotendeels verdwenen (pre-warming, bytecode caching), requests delen een instantie, en `waitUntil` schuift niet-kritisch werk voorbij het antwoord. De factuur 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.

## Bewust greedy

We zoeken nooit uitputtend door de ruimte heen. Op elk beslismoment maken we met de informatie die we hebben de lokaal beste keuze, leggen die vast en gaan door. 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 uit dezelfde familie als group scheduling, haalt greedy een logaritmische approximatieratio, en geen algoritme met polynomiale tijd kan 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 op het gevraagde moment beschikbaar zijn, en de selectie is drie volgordefilters:

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

Eerlijkheid vergelijkt voor elke host het aantal echte Bookings in het recente interval met een gewogen doelaandeel en houdt de hosts die het verst achterlopen vast (hoogste gewicht 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 als je twee filters omwisselt, krijgt een andere host dezelfde Booking. 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 naar 40 gekwalificeerde hosts. Een geboekte host wordt nooit uit de pool verwijderd, alleen lager gepositioneerd (als iedereen anders out of office is, neemt de host die net een Booking kreeg ook de volgende), dus elke Booking heeft onafhankelijk 40 mogelijke toegewezen hosts.

40 hosts, de volgende 25 Bookings

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 heelal.

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

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, met een kostenverschil van bijna veertig ordes van grootte.

Geen enkele beslissing hoeft perfect te zijn, omdat het systeem zichzelf corrigeert. Overbelast je vandaag een host, dan wordt hun achterstand kleiner, dus eerlijkheid zet ze morgen lager. Correcties rijden op dezelfde maatstaf. Een host die halverwege het interval aansluit, krijgt de gemiddelde Bookings per host van vóór hun aansluiting toegeschreven, en een host die terugkomt van out of office krijgt hun aandeel toegeschreven van de Bookings die tijdens hun afwezigheid zijn genomen. De achterstandslogica ziet een gecorrigeerde telling. Geen herberekende geschiedenis, geen herverdelingsronde.

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

De afweging is echt, en het hoekgeval is eenvoudig te construeren. Geef één host een smal beschikbaarheidsvenster dat overlapt met dat van iedereen anders, laat greedy hen de eerste Booking daarin geven, en je hebt het enige slot geblokkeerd dat een latere, meer beperkte Booking had kunnen gebruiken. Uitputtend zoeken had dat zien aankomen. Greedy kijkt niet vooruit. We weten dat dit soort gevallen bestaat en moeten oké zijn met shippen, omdat we milliseconden hebben. De achterstandslogica brengt dingen over de tijd weer in balans.

## Hoe lineair er echt uitziet

“We verwerken beperkingen lineair” is makkelijk 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. Hij 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 reisschema’s halverwege de maand de tijdzone wisselen en zomertijd een offset verschuift, dus dagonafhankelijk werk wordt daaruit omhoog getild. Tijdzoneconversie domineert de loop, en die draait één keer per dag per regel, niet één keer per slot.

**Collective events zijn een merge met twee pointers, geen cartesisch product.** Dertig hosts hebben de tijden nodig waarop alle dertig vrij zijn. Elk interval met elk interval vergelijken is twee keer kwadratisch. In plaats daarvan worden de intervallen van elke host gesorteerd op starttijd en samengevoegd in een lopende lijst van “gezamenlijke 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 gezamenlijke 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 zodra de gezamenlijke lijst leeg is, stoppen we. Als hosts één tot en met zeven geen overlap hebben, kunnen hosts acht tot en met dertig daar niets aan veranderen.

**Bezet tijden worden afgetrokken in één gesorteerde sweep.** Bookings, externe Calendar-gebeurtenissen en out-of-officeperioden komen allemaal in één exclusion list terecht, één keer gesorteerd op starttijd. Elk beschikbaarheidsbereik loopt er in volgorde doorheen en bewaakt de gaten:

```
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 exclusions gesorteerd zijn, wordt alles achter de `break` nooit bekeken.

**Boekingslimieten worden synthetische bezette tijd.** “5 Bookings per dag” zou tegen elk kandidaat-slot kunnen worden gecontroleerd, tegen een kostprijs van slots × limieten × Bookings. In plaats daarvan wordt, zodra de telling de limiet raakt, de hele periode één bezet interval en rijdt mee op dezelfde subtractie-sweep:

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

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

Geen van deze stappen is op zichzelf geniaal. Een NP-hard probleem binnen een budget van een milliseconde los je niet op met één briljant algoritme. Je lost het op door bij elke stap te weigeren dat enige berekening afhankelijk wordt van het product van twee grote getallen.

## Alles rond het algoritme is ook begrensd

Zelfs een perfect algoritme gevoed door een trage query is nog steeds een trage boekingspagina, en de datalaag is waar enterprise-schaal het eerst pijn doet.

**Reads worden gebatcht en daarna in het geheugen geïndexeerd.** De naïeve vorm is een loop over hosts met drie queries erin. Dertig hosts betekenen 90 round trips naar Postgres vóór er één interval is berekend, onzichtbaar voor een team van 5 personen en een productie-incident voor 3.000. De slots-pijplijn haalt daarom alles eerst 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
```

Bookings en out-of-office-dagen laden gelijktijdig onder één `Promise.all`, en limieten volgen in een tweede gebatchede 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 per-user query kan terugbrengen zonder dat de compiler klaagt.

**Externe Calendars krijgen een cache met strikte regels.** Eén round trip naar een provider weegt zwaarder dan de hele intervalberekening, dus de cache is gebouwd 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, overal binnen de horizon. En een mislukte provider-call wordt nooit gecachet, omdat een fout cachen als “voor de hele horizon vrij” stilletjes slots boven echte vergaderingen zou aanbieden. Een storing kost een retry, nooit een fout antwoord.

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

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

## Waar we eerlijk zijn dat we er 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 als 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 rekenkundige kant groeit met het team. De database voegt zijn eigen vertraging toe. Team-availability haalt linkconfiguratie, Bookings, limieten en out-of-office-rows voor elke host uit tabellen met miljoenen records, en sommige van die queries zijn nog steeds traag.

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

## Elke boekingsfunctie is een algoritmische beslissing

Elke boekingsfunctie die we uitbrengen moet een vraag beantwoorden die de meeste SaaS-producten nooit stellen. Ontploft de search? Een functie die als nog een volgorderfilter in de greedy cascade kan worden uitgedrukt, is op elke schaal bijna gratis. Een die ons dwingt combinaties te vergelijken, wordt herontworpen totdat dat niet meer hoeft.

Greedy kiest soms een slechtere optie dan een uitputtende search zou hebben gedaan, en dat zal altijd zo blijven. We accepteren dat, begrenzen het en corrigeren het in de loop van de tijd, omdat het uitputtende antwoord pas komt nadat de booker is opgehouden te wachten. De afweging werkt al voor individuele boekingspagina’s. Het sneller maken voor een organisatie met 3.000 leden is het werk dat we nu doen.
