Takenrooster huisgenoten
Reversi
November 25, 2023
In mijn tijd als student Natuurkunde aan de Universiteit heb ik een periode gehad waarin ik het vak 'Modelvorming en Simulaties' volgde. Dit vak bevatte een aantal programmeeropdrachten met een natuurkundige context, om uit te voeren. Één van deze opdrachten was het schrijven van een sudoku-solver, met behulp van Simulated Annealing.
Simulated Annealing
Het concept van annealing gaat over het langzaam af laten koelen van metalen, zodat de atomen in het metaal langzaam de tijd hebben om in hun laagst-mogelijk energietoestand te kunnen komen. Hierdoor komen in de hele kleine schaal de metaal-atomen netjes in rijen van herhalende patronen terecht. Dit heeft als effect dat het metaal in zijn geheel op grote schaal een andere hardheid krijgt. Dit is onder andere vanwege het verminderde aantal defecten (lege plekken en mismatchende kristal regio’s) in het kristalrooster.
Nu hoor ik je denken, wat heeft een takenrooster van een studentenhuis nou te maken met het Sudoku’s en het afkoelen van metalen en kristallen? Nou een sudoku bestaat net als een soort kristal uit een vast rooster. Dit rooster heeft vaste plaatsen waar op sommige plekken al een getal vooraf ingevuld staat, en je zelf de resterende getallen moet aanvullen.
In een kristal willen atomen graag dichtbij elkaar zijn, en trekken en duwen aan elkaar met de zogeheten Vanderwaals-kracht. Deze krachten bepalen de spelregels van hoe materie op kleine schaal opgebouwd kan worden. Vergelijkbaar zijn er voor sudoku’s ook spelregels waaraan de puzzel moet voldoen om deze resterende getallen goed in te mogen vullen. Zo mogen dezelfde getallen niet direct in dezelfde rij, kolom of 3×3 vierkant voorkomen. Heb je dat wel, dan is de puzzel verkeerd. Heb je 2 getallen direct naast elkaar staan, dan voelen die een soort afstotende kracht. En bekijk je dit over je gehele puzzel, dan spreek je over de totale energie (strafscore) van je puzzel. En door getallen om te wisselen, kan het aantal fouten (en daarmee de totale energie) lager worden. Zodra de energie het laagst mogelijke is geworden, dan heb je de minste dubbelen naast elkaar, en de meest gunstige energietoestand, ofwel de oplossing gevonden. Al met al best een leuk project.
Takenrooster
In mijn studentenhuis, waren er dus mensen die het oneerlijk vonden dat ze elke keer na dezelfde persoon moesten schoonmaken. Niet iedereen doet dat namelijk even netjes. En als je keer op keer een vies achtergelaten keuken van je voorganger extra hard moet schoonmaken, dan kan ik begrijpen dat je daarover gaat klagen. Nu was het aan mij om een eerlijker schoonmaakrooster te bedenken. En toen ik hiervoor ging zitten, kwamen er een aantal gedachten in mij naar boven: In één week schoonmaken wil je niet meerdere taken hoeven doen. En in opvolgende weken schoonmaken wil je niet te vaak na elkaar dezelfde taak hoeven doen. Hmmm wacht eens even, dat klinkt een beetje als een sudoku. Waarbij een tabel met rijen (weken) en kolommen (schoonmaaktaken) gevuld moeten worden met huisgenoten.
Zo kwam ik dus op het idee om een schoonmaakrooster te laten genereren door een studentenprojectje wat ik eerder in mijn studie had opgelost. Het koste me een paar middagen herschrijven. De begin-conditie was bij ons dat er een groep van 3 mensen op een gedeelde badkamer zaten. Dit kon je vergelijken met de vooraf ingevulde getallen in een sudoku. Ook is een normaal sudoku-rooster 9×9, maar ik had 15 huisgenoten in kamers A t/m O. En ik had 10 schoonmaaktaken (keuken poetsen, woonkamer dweilen, gangen dweilen, theedoeken wassen, vuilniszakken schoonmaken, en nog meer).
Dus op zijn minst moest ik een rooster van 10×15 gaan maken. Na wat puzzelen is dit gelukt, en kon ik alle huisgenoten 10 keer eerlijk plaatsen in 15 weken.
En als er klachten kwamen over het rooster, kon ik altijd claimen dat dit volgens de computer een van de beste oplossingen was.
Playground
Hierboven zie je een stukje testcode waarbij je een tabel kan genereren met een gegeven aantal taken, en weken en huisgenoten. Daarna kan de tabel worden geshuffled. Hierbij worden er 250 shuffle rondes gedaan om huisgenoten naar gunstigere taken te ruilen.
Zodra er op de shuffle knop gedrukt wordt, zal interactief ook de “temperatuur” omlaag gaan. Hierdoor zijn atomen in een kristalrooster minder beweeglijk. In ons takenrooster systeem, betekent dit dat de huisgenoten minder makkelijk zullen wisselen van taak. Een wisseling die voordeel oplevert met minder dubbelen per rij of kolom, heeft meer kans om de wisseling plaats te laten vinden. Na verloop van tijd wordt de temperatuur zo koud, dat taken wisselen niet meer mogelijk is. Endan zal er een steady-state behaald zijn waarop de energie (aantal dubbelen per rij en kolom) minimaal is, en er een oplossing is gevonden voor het takenrooster.
In dit stukje code is de afkoelings-rate en de start-temperatuur empirisch gekozen zodat het werkt voor een 4×4 rooster. Voor meer entries en getallen, zal je de start-temperatuur hoger moeten zetten, en het aantal iteraties moeten ophogen. Natuurlijk zijn er ook altijd nog extra randvoorwaarden om te finetunen voor verschillende systemen. Maar dit is hoe het bij mij ging. Voel je vrij om deze javascript code te downloaden uit de source en her te gebruiken en te tweaken naar eigen inzichten.
