Een dagprogramma als optimalisatieprobleem
Voor het carrière-evenement van Techniek Bedrijven moeten studenten en bedrijven bij elkaar passen én alle programma's kloppen. We bouwden een platform dat die indeling berekent met Python en PuLP. Het werk begon bij het vertalen van de praktijk naar een wiskundig model.
Opdrachtgever
- Branche
- Onderwijs & recruitment
- Locatie
- Delft
Team
De uitdaging
Wie ontmoet welk bedrijf?
Stichting Techniek Bedrijven organiseert een jaarlijks carrière-evenement voor technische studenten. Deelnemers volgen op één dag drie programmaonderdelen bij verschillende bedrijven. Studenten geven aan waar hun interesses liggen; bedrijven zoeken mensen met een bepaalde opleiding, ervaring of achtergrond. Er zijn meer aanmeldingen dan plaatsen.
Achter de inschrijving zit daardoor een flinke puzzel. Welke studenten nodig je uit, en hoe geef je ieder van hen een passend dagprogramma? Wij bouwden de techniek voor het platform, aanvankelijk in opdracht van onze vrienden Sping, dat het productdesign verzorgde. Later namen we het project volledig over en gingen we rechtstreeks met STB verder.
Een match is nog geen planning
Bij één student en één bedrijf kun je vrij overzichtelijk bepalen hoe goed ze bij elkaar passen. Zodra je een hele dag indeelt, gaan die keuzes elkaar beïnvloeden. Een plek die je aan de ene student geeft, is voor een ander bezet. Een student kan maar één onderdeel tegelijk volgen en moet aan het einde van de dag drie verschillende bedrijven hebben ontmoet.
Daarom horen selectie en planning bij elkaar. Kies je eerst per bedrijf de favoriete kandidaten, dan kun je verderop vastlopen: iemand heeft bijvoorbeeld wel een plek in de ochtend, maar geen passend middagprogramma. Wij herkenden hierin een optimalisatieprobleem. We moesten de mogelijke indelingen als geheel kunnen afwegen.
De vraag achter de vraag
Wat moet het algoritme goed doen?
Een inschrijfformulier vertelt je wie een student is en wat die zoekt. Voor de matching heb je ook de andere kant nodig: wat vinden de deelnemende bedrijven belangrijk? Een bedrijf kan bijvoorbeeld veel waarde hechten aan een bepaalde opleiding, terwijl een ander meer gewicht geeft aan ervaring naast de studie.
Dat inzicht bepaalde mede welke gegevens het platform moest verzamelen. Samen met STB werkten we de criteria uit. We brachten studentprofielen, interesses en bedrijfsvoorkeuren onder in een vorm waarmee de software kan rekenen. Zo begon het technische ontwerp al bij de vragen op het formulier.
Van antwoorden naar scores
Daar zitten ook ogenschijnlijk kleine keuzes in. Vergelijkbare opleidingen heten bij verschillende onderwijsinstellingen anders. We groepeerden die in gedeelde opleidingstags, zodat een bedrijfsvoorkeur op dezelfde manier kan aansluiten op studenten van verschillende instellingen.
Met de profielgegevens en gewogen criteria berekent de applicatie een score voor iedere combinatie van student en programmaonderdeel. Die scores vormen de invoer voor de planning. Door het berekenen van scores apart te houden van het verdelen van plaatsen, kunnen we beide vragen afzonderlijk uitwerken: hoe waarderen we een match, en welke combinatie van matches past binnen het programma?
De regels opschrijven vóór we gaan rekenen
We kozen voor lineair programmeren. Daarbij beschrijf je welke keuzes mogelijk zijn, wat je wilt optimaliseren en aan welke voorwaarden de uitkomst moet voldoen. Een bestaand rekenprogramma, een solver, zoekt vervolgens een oplossing voor dat model.
Voor STB is het doel een zo hoog mogelijke totaalscore van alle toegewezen bezoeken. Daarnaast leggen we vast dat alle beschikbare plaatsen worden gevuld, iedere geselecteerde student een volledig programma krijgt en niemand twee keer hetzelfde bedrijf bezoekt. Die afspraken staan expliciet in het model. Daardoor kunnen we met STB bespreken wat een regel of een andere weging voor de indeling betekent.
Techniek die het verschil maakt
De hele indeling in één berekening
Een klein rekenvoorbeeld laat zien waarom we de keuzes samen berekenen. Stel: er zijn twee kandidaten en nog plaatsen voor één volledig dagprogramma. Kandidaat A scoort bij de drie bedrijven een 10, een 2 en een 1. Kandidaat B scoort drie keer een 8.
Wie bij het eerste bedrijf begint, kiest A. Over de hele dag scoort B hoger: 24 tegenover 13. In deze fictieve vergelijking kun je dat direct zien. Bij het echte evenement moet de software alle kandidaten, plaatsen en voorkeuren in samenhang verwerken.
Python en PuLP voor het model
We bouwen het model met PuLP, een Python-library voor lineaire optimalisatie. Iedere toewijzing is een ja/nee-keuze: deze student krijgt deze plaats, of niet. Ook deelname zelf is zo'n keuze. Omdat je geen halve student kunt indelen, gebruiken we de variant met gehele waarden: integer linear programming.
De solver zoekt vervolgens een indeling met een hoge totaalscore die aan alle voorwaarden voldoet. We hoeven daarvoor niet zelf een zoekalgoritme te schrijven. Ons werk zit in het modelleren: welke keuzes hangen samen, welke regels zijn verplicht en welke voorkeuren mogen tegen elkaar worden afgewogen?
Rekenen buiten de webapplicatie
Zo'n berekening hoort niet in een webverzoek waarop de browser blijft wachten. We hebben de Python-engine daarom als aparte rekentaak ingericht. De TypeScript-backend berekent de scores en start de taak op AWS. Python leest de invoer uit S3 en schrijft het resultaat daar terug. Via een bericht in een wachtrij komt de uitkomst weer bij de applicatie terecht.
Die scheiding laat ons Python en PuLP gebruiken voor het rekenwerk, naast React en TypeScript voor het portaal en de beheeromgeving. De backend verwerkt het resultaat tot dagprogramma's die het bestuur kan bekijken.
Ook een mislukte berekening hoort bij het ontwerp
We controleren de invoer voordat de solver begint. Zijn er genoeg kandidaten en verschillende bedrijven? Hebben de dagdelen evenveel totale capaciteit? Dat laatste is nodig om alle plaatsen te vullen én iedere deelnemer een volledige dag in te delen.
Ook de uitkomst wordt gecontroleerd: kloppen de capaciteit, de toewijzingen en de volledige programma's? Een berekening die stopt zonder geldige oplossing mag geen onvolledig rooster opleveren. In de tests komen daarom ook onmogelijke indelingen en tijdslimieten met en zonder bruikbaar resultaat aan bod.
Wat het mogelijk maakte
Van inschrijving naar een te beoordelen dagprogramma
STB kan in hetzelfde platform inschrijvingen verzamelen, criteria beheren, de matching starten en de berekende programma's bekijken. Het bestuur kan scores opvragen en bepaalt wanneer de indeling wordt gepubliceerd. Daarna ziet iedere student het eigen dagprogramma in het portaal.
Die beoordeling hebben we bewust een plek gegeven. Een hoge score zegt iets over de criteria die we samen hebben ingesteld. Als een uitkomst vreemd lijkt, moeten we dus ook kunnen terugkijken naar de invoer en de weging. Met opeenvolgende besturen bespreken we de werking en mogelijke verbeteringen; technische bestuursleden kijken daarbij ook mee in de code.
De technische basis laten meegroeien
De eerste versie bouwden we deels op de registratie en beheerfuncties van Strapi. Daarmee konden we binnen het beschikbare budget zowel het ontwerp als de matching realiseren. Later maakten het maatwerk rond gebruikersdata en ingrijpende CMS-upgrades die combinatie steeds lastiger te onderhouden.
We gaven het studentenportaal daarom een eigen backend. Strapi bleef beschikbaar voor content en evenementinformatie. Dat is ook onderdeel van onze samenwerking met STB: blijven beoordelen of een eerdere technische keuze nog past bij het product dat inmiddels is ontstaan.
Hetzelfde gereedschap voor onze eigen planning
Ook binnen 10KB gebruiken we PuLP. Voor onze maandplanning verdelen we beschikbare developers over projecten, met afspraken over uren, teams en voorkeuren. De regels verschillen, maar het werk begint op dezelfde manier: het planningsprobleem precies genoeg begrijpen om er een model van te maken.
In onze blog over lineair programmeren vertellen we meer over die techniek. Het is een van de gereedschappen die we inzetten bij het bouwen van matchingplatforms, wanneer voorkeuren en beperkte capaciteit samen de uitkomst bepalen.
Wat we meenemen
Van praktische regels naar werkende software
Bij Techniek Bedrijven komen modelleren, applicatieontwikkeling en onderhoud samen. Deze afwegingen gebruiken we ook bij andere plannings- en matchingvraagstukken.
Modelleer samenhangende keuzes samen
Wie mag deelnemen en bij welke bedrijven iemand wordt ingedeeld, bepalen we in één berekening. Zo telt het volledige dagprogramma mee.
Bij volgende projecten
We onderzoeken welke beslissingen elkaar beïnvloeden voordat we een proces in losse automatiseringen verdelen.
Maak regels expliciet
Bedrijfscriteria en studentvoorkeuren worden scores. Capaciteit en volledige deelname zijn harde voorwaarden in het model.
Bij volgende projecten
We bepalen samen met de opdrachtgever wat de software moet optimaliseren en aan welke afspraken iedere uitkomst moet voldoen.
Bouw de controle mee
De applicatie controleert invoer en berekende programma's. Het bestuur kan daarna scores bekijken en de indeling publiceren.
Bij volgende projecten
We ontwerpen ook wat er vóór en na een berekening gebeurt, zodat gebruikers met de uitkomst kunnen werken.
Ewout
Een planning waar steeds meer regels bij komen?
Mensen, voorkeuren en beperkte capaciteit kunnen een verdeling behoorlijk ingewikkeld maken. We denken graag mee over het model en de software die daarbij passen.