ADDENDUM FUNCTIONEEL ONTWERP PROTOTYPE ROOSTEREN

ADDENDUM FUNCTIONEEL ONTWERP

PROTOTYPE ROOSTEREN

PROTOTYPE ROOSTEREN

Inleiding Een deel van de het werk van Triple A Ontwerp en Onderzoek heeft betrekking op het ontwikkelen van zogenaamde “complexe functionaliteiten”. Dat betreft vooral het proces van het maken van lesroosters voor deelnemers. Hiervoor heeft Triple A contact gezocht met een gespecialiseerd bureau op het gebied van de toegepaste wiskunde onder andere op het gebied van wiskundige modeleringen, algoritmiek, simulaties en de bijbehorende software ontwikkeling. In november 2008 is begonnen met een onderzoek van het roosterprobleem en het ontwikkelen van de benodigde technologie: het prototype. In dit deel van de encyclopedie vindt u een nadere toelichting op het prototype roosteren zoals dat is ontwikkeld naar aanleiding van de uitwerking van het functioneel ontwerp voor de onderwijslogistiek, roosteren en beheren middelen. Het daarin uitgewerkte roosterproces beschrijft een proces waarin het mogelijk is om een rooster te realiseren op basis van individuele leervragen van deelnemers, met een optimale inzet van middelen. Op basis van het functioneel ontwerp is een prototype ontwikkeld om te toetsen of deze ambitie in de praktijk realistisch is. Dit document beschrijft het prototype roosteren.

Beschrijvend en technisch gedeelte

Legenda:

Dit document bestaat naast de inleiding uit twee delen. Een beschrijvend gedeelte, use case use case buiten dit ontwerp werkopdracht

waarin u in verhaalvorm de opbouw en werking van het prototype kunt lezen. En een technisch gedeelte, waarin de onderdelen van het ontwerp van het prototype gedetailleerd zijn uitgewerkt. In het beschrijvend gedeelte wordt u door de belangrijkste aspecten van het ontwerp geloodst. Daarin wordt beschreven wat de relatie is met de use cases zoals

door de tijd getriggerd

beschreven in het functioneel ontwerp, de aanleiding om het prototype te gaan

document als resultaat

ontwikkelen, de werking van het prototype en wat je er vervolgens (niet) mee kunt. Na het lezen van het beschrijvend gedeelte heeft u een indruk gekregen van het prototype in zijn geheel. Mocht u zich verder willen verdiepen dan kunt u in het technische gedeelte de gedetailleerde uitwerking van de onderdelen van het ontwerp lezen.

3

4

PROTOTYPE ROOSTEREN

Inhoudsopgave Inleiding  Beschrijvend en technisch gedeelte 

3 3

Beschrijvend gedeelte 

7

Relatie met het functioneel ontwerp onderwijslogistiek, roosteren, beheren middelen  Het roosterproces in het onderwijsprocesmodel  Het roosterproces in het functioneel ontwerp 

8 8 9

Aanleiding voor ontwikkeling prototype roosteren  Individuele leervragen  Gebruik van de onderwijscatalogus  Gebruik van bedrijfsregels  Waarom een prototype? 

11 11 11 11 12

Werking van het prototype roosteren  De input voor het roosterproces  Het roosterproces  Handmatig aanpassen van het rooster 

13 13 13 15

Leerervaringen en conclusie

17

Hoe nu verder?  Technisch gedeelte





21 23

PROTOTYPE ROOSTEREN

5

PROTOTYPE ROOSTEREN

Beschrijvend gedeelte

7

8

PROTOTYPE ROOSTEREN

Relatie met het functioneel ontwerp onderwijslogistiek, roosteren, beheren middelen Het roosterproces in het onderwijsprocesmodel Het onderwijsprocesmodel zoals beschreven in de onderwijsvisie laat zien hoe de onderwijsprocessen met elkaar samenhangen. In een aantal processen speelt het roosteren een belangrijke rol. Hieronder worden deze processen uitgelicht.

Aantonen competenties en kennis

Inschrijven

Opleiden en vormen

Examineren

Diplomeren

Leertraject begeleiding

Leervraag arrangeren

Ontwikkelen onderwijs

Beheren onderwijs catalogus

Toewijzen BPV

Beheren loopbaan

Accepteren

Leeraanbod plannen

Registreren aan- en afwezigheid

Uitschrijven

Beheren identiteit

Analyseren aan- en afwezigheid

Overdracht deelnemergegevens

Uitwisseling BRON

Toelevering verantwoordingsinformatie

Inzetten middelen

Aanpassen en aanvullen rooster

Prognotiseren

Aanpassen en aanvullen middelen

Fig. 1, relevante processen in het onderwijsprocesmodel Het roosteren is in de eerste plaats relevant voor het plannen van het leeraanbod. Daar wordt de individuele leervraag afgezet tegen de beschikbare middelen (docenten, lokalen en andere middelen) binnen de instelling. Het daadwerkelijk beschikbaar stellen en inzetten van middelen is een tweede proces dat sterk met het roosteren samenhangt. Nadat het rooster is vastgesteld kan er nog ruimte zijn, of noodzaak zijn, om het rooster aan te vullen of aan te passen. Tenslotte is het proces van prognosticeren van belang, waarin op basis van historische gegevens en inschattingen roosterinformatie wordt gegenereerd.

PROTOTYPE ROOSTEREN

Het roosterproces in het functioneel ontwerp Alle processen zijn in de vorm van use cases nader uitgewerkt in het functioneel ontwerp onderwijslogistiek, roosteren en beheren middelen. Hieronder wordt het overzicht gegeven van de use cases uit dat functioneel ontwerp, waarbij weer de voor het roosteren relevante use cases zijn uitgelicht.

Fig. 2, relevante use cases in het functioneel ontwerp onderwijslogistiek, roosteren, beheren middelen

9

10

PROTOTYPE ROOSTEREN

Er zijn drie use cases waarin de roostermachine een rol speelt, aangeduid met ‘R-machine’ in Figuur 2. Dit zijn use cases waarin op een geautomatiseerde manier een nieuw rooster moet worden geproduceerd op basis van individuele leerarrangementen en beschikbare middelen. In de use case Maken rooster wordt voor de eerstvolgende roosterperiode een daadwerkelijk rooster gemaakt. In de use case Tactische planning wordt voor de periodes daarna een geprognosticeerd rooster gemaakt, deels gebaseerd op aannames over de leervragen en beschikbare middelen op dat moment. Tenslotte is er bij een calamiteit een dusdanige wijziging opgetreden in de beschikbare middelen dat opnieuw roosteren noodzakelijk is. In de use case Oplossen calamiteit wordt daarom ook gebruik gemaakt van de roostermachine. Naast deze drie use cases zijn er nog drie andere use cases die zo sterk met de input of output van de roostermachine verbonden zijn dat we deze hier ook benoemen. Na het maken van het rooster door de roostermachine volgt altijd het effecturen van het rooster waarbij de roosteromgeving in staat moet zijn een individueel deelnemerrooster of docentenrooster op te leveren, of een rooster waarin zichtbaar is wanneer lokalen of andere middelen zijn ingezet. Deze roosterinformatie is nodig om alle belanghebbenden over het rooster te informeren of de middelen definitief vast te leggen. Daarnaast moet het mogelijk zijn om het automatisch geproduceerde rooster nog individueel aan te vullen als daar in het rooster rekening mee is gehouden. Tenslotte moet het mogelijk zijn het rooster aan te passen als zich uitvoeringsproblemen voordoen.

PROTOTYPE ROOSTEREN

Aanleiding voor ontwikkeling prototype roosteren In de use cases zoals opgenomen in het functioneel ontwerp onderwijslogistiek, roosteren en beheren middelen wordt beschreven wat de functie is van de roostermachine. We beschrijven hieronder kort wat de functie van de roostermachine is. Vervolgens wordt toegelicht waarom ervoor gekozen is een prototype te ontwikkelen voor deze problematiek

Individuele leervragen De functie van de roostermachine is, dat deze een rooster produceert op basis van individuele leervragen van deelnemers. Deze individuele leervragen zijn vastgelegd in de vorm van een arrangement waarin is aangegeven welke producten uit de onderwijscatalogus hij of zij wil afnemen. Dit arrangement gaat liefst over een zo lang mogelijke periode, maar tenminste over de komende roosterperiode. Dit arrangement kan in principe voor elke deelnemer verschillend zijn. Deelnemers worden vanwege die verschillen niet meer vooraf in klassen of groepen ingedeeld. Er ontstaat een rooster per deelnemer, van waaruit groepen ontstaan die gelijktijdig hetzelfde onderwijsproduct afnemen.

Gebruik van de onderwijscatalogus De leervraag van deelnemers is uitgedrukt in producten uit de onderwijscatalogus. Deze onderwijsproducten zijn in de onderwijscatalogus voorzien van beschrijvende kenmerken, de zogenaamde metadata. Deze metadata geeft bijvoorbeeld aan welk type docenten voor de uitvoering van het onderwijsproduct nodig zijn en welk type lokaal en eventueel andere middelen. Daarnaast is bijvoorbeeld gedefinieerd welke andere onderwijsproducten eerst door een deelnemer moeten zijn gedaan voordat het onderwijsproduct kan worden afgenomen. Het roosterproces moet met deze metadata kunnen omgaan en op basis daarvan de juiste beslissingen nemen.

Gebruik van bedrijfsregels De roostermachine heeft uiteindelijk de taak een ‘zo goed mogelijk’ rooster te maken. Daarbij moeten uiteraard de leervragen van de deelnemers worden gehonoreerd, maar ook de middelen zo efficiënt en effectief mogelijk worden ingezet. Om te kunnen bepalen wat een goed rooster is, en om af te wegen of het ene rooster beter is dan het andere, zijn bedrijfsregels geïntroduceerd. Bedrijfsregels kunnen betrekking hebben op de bedrijfsvoering (zoals efficiënt lokalengebruik, beperken van tussenuren) en op het onderwijs (zoals verdeling van werkvormen over een dag, geen zwaar theoretische vakken aan het einde van de dag). Deze bedrijfsregels vormen samen met de arrangementen van de deelnemers,

11

12

PROTOTYPE ROOSTEREN

de kenmerken van de onderwijsproducten en de kenmerken van de beschikbare middelen de gegevens op basis waarvan de roostermachine een zo optimaal rooster moet produceren.

Waarom een prototype? In de voorgaande paragrafen is nog eens samengevat wat de roostermachine functioneel gezien zou moeten kunnen. De huidige praktijk van roosteren wijkt hier echter sterk vanaf. Vergeleken daarmee is de hier beschreven werkwijze een idealistische beschrijving die aanzienlijk complexer is. Aan de andere kant is het wel de beweging die nodig is om te zorgen dat meer flexibel, op het individu gericht onderwijs mogelijk wordt gemaakt zonder dat de kosten daarvan uit de hand lopen. Het prototype roosteren is ontwikkeld om vast te stellen of de ambitie met betrekking tot de roostermachine realistisch is en op welke manier zo’n roostermachine daadwerkelijk gerealiseerd kan worden. Het prototype moet inzicht geven in de contouren van de oplossing voor zo’n roostermachine, zonder de ambitie te hebben om zo’n oplossing daadwerkelijk in de markt te zetten.

PROTOTYPE ROOSTEREN

Werking van het prototype roosteren

In dit hoofdstuk wordt het gerealiseerde prototype inhoudelijk toegelicht. Deze beschrijving is opgebouwd door eerst te beschrijven welke gegevens de input vormen voor het roosterproces. Vervolgens bestaat het proces uit twee hoofdfasen waarin het rooster daadwerkelijk wordt geproduceerd. Tenslotte is er nog de mogelijkheid om het rooster handmatig aan te passen of te verfijnen.

De input voor het roosterproces De input voor het roosterproces bestaat uit de volgende gegevensverzamelingen. - Een verzameling onderwijsproducten die voorzien is van de volgende metadata · Soort onderwijsproduct (les, stage, summatieve toets) · Minimum en maximum aantal deelnemers · Benodigde docent(en), gespecificeerd naar het type docent dat nodig is · Benodigde lokalen, gespecificeerd naar het type lokaal dat nodig is · Benodigde andere middelen, gespecificeerd naar het type middel dat nodig is · Onderwijsproducten die voorafgaand aan dit onderwijsproduct moeten zijn

gevolgd

- Een verzameling docenten, met een aanduiding van het type docent - Een verzameling lokalen, met een aanduiding van het type lokaal en de minimale

en maximale capaciteit van het lokaal

- Een verzameling middelen, met een aanduiding van het type middel dat het

betreft

- Een verzameling individuele leerarrangementen van deelnemers, uitgedrukt in de onderwijsproducten die deze deelnemers wensen te volgen. Daarbij wordt ook aangegeven hoeveel onderwijstijd zij minimaal en maximaal aangeboden willen krijgen in de eerstvolgende roosterperiode en aan welke onderwijsproducten

binnen hun arrangement zij de voorkeur geven

- Een verzameling bedrijfsregels die aangeven aan welke voorwaarden het rooster (bij voorkeur) moet voldoen, onderscheiden naar harde en zachte voorwaarden . Harde voorwaarden zijn voorwaarden waar het rooster aan moet voldoen,

anders is het geen uitvoerbaar rooster

13

14

PROTOTYPE ROOSTEREN

· Zachte voorwaarden zijn voorwaarden waaraan het rooster zo goed mogelijk

moet voldoen. Hoe beter een rooster aan de zachte voorwaarden voldoet, hoe



beter het scoort ten opzichte van een ander rooster

Het roosterproces Het roosterproces is het geautomatiseerde proces dat vanuit de hiervoor beschreven input een daadwerkelijk rooster produceert. Dit proces verloopt in het prototype in twee hoofdstappen: het plannen van sessies en het plaatsen van de deelnemers in de sessies. Deze twee hoofdstappen worden hieronder nader toegelicht. Stap 1: plannen van sessies In deze stap wordt bepaald welke sessies in het rooster gepland moeten worden als alle leervragen zouden worden gehonoreerd. Dit gebeurt in de volgende stappen. - Het aantal benodigde sessies per onderwijsproduct wordt bepaald op basis van het totaal aantal deelnemers dat het onderwijsproduct in zijn arrangement heeft staan. Hierbij kan een marge worden gehanteerd door er rekening mee te houden dat niet bij elke sessie het maximum aantal deelnemers gepland zal kunnen worden - Verspreiden van de deelnemers over de sessies op basis van een algoritme (het zgn. Carter’s algoritme), zodat deelnemers met zoveel mogelijk overeenkomsten in hun arrangement in dezelfde sessies worden geplaatst - Het plannen van de sessies in de tijd, zodanig dat gelijktijdige sessies zo min mogelijk overlap hebben in de deelnemers die het volgen - Herverdelen van deelnemers over de geplande sessies om de overlap te minimaliseren Het resultaat van deze stap is een soort ‘maximaal rooster’, waarin zo veel mogelijk sessies zijn gepland in de tijd. De arrangementen van alle deelnemers zijn hierin zo veel mogelijk gehonoreerd, maar deelnemers kunnen hierdoor op hetzelfde moment bij meerdere sessies zijn ingepland en zij kunnen voor meer onderwijs zijn ingepland dan het maximum dat in hun arrangement is aangegeven.

PROTOTYPE ROOSTEREN

Stap 2: plaatsen van deelnemers In deze stap wordt bepaald welke deelnemers aan welke sessie daadwerkelijk zullen gaan deelnemen, rekening houdend met de maximum gewenste hoeveelheid onderwijs. Dit gebeurt in de volgende stappen. - Deelnemers worden uit sessies geschrapt als zij voor meer sessies zijn ingepland dan het maximum dat in hun arrangement is aangegeven. De keuze wat er wordt geschrapt hangt van de voorkeuren van de deelnemer af en van de mogelijkheden die kunnen ontstaan om andere conflicten in het rooster op te lossen en eventueel sessies te kunnen schrappen - Deelnemers worden opnieuw over de sessies verdeeld, zodanig dat er geen deelnemers meer zijn gepland in gelijktijdige sessies - Overbodige sessies, waarvoor geen deelnemers meer zijn gepland, of waarvan de deelnemers naar een andere sessie kunnen worden verplaatst, worden geschrapt Het resultaat van deze stap is een daadwerkelijk uitvoerbaar rooster, in de zin dat aan alle harde bedrijfsregels is voldaan. Daarbij is een diagnoserapport beschikbaar waarin per zachte bedrijfsregel is aangegeven op welke punten het rooster niet voldoet aan de betreffende bedrijfsregel.

Handmatig aanpassen van het rooster Nadat het rooster geautomatiseerd tot stand is gekomen zijn er mogelijkheden om het rooster aan te passen. Dit kan met name op de volgende manieren. - Doorvoeren van handmatige wijzigingen

Er kunnen handmatige aanpassingen in het rooster worden gedaan, bijvoorbeeld door deelnemers te verplaatsen naar andere sessies, lokalen of middelen te wisselen of een sessie op een ander tijdstip te plannen.



Het kan zijn dat door deze wijzigingen harde of zachte bedrijfsregels worden overtreden, of dat het rooster slechter scoort dan het oorspronkelijke rooster. Overtreding van harde bedrijfsregels is uiteraard niet toegestaan.

15

16

PROTOTYPE ROOSTEREN

- Voorstellen van alternatieven

De eerste manier om een handmatig gewijzigd rooster te verbeteren, is dat er enkele alternatieven worden voorgestelde met betrekking tot de gewenste wijziging die leiden tot een rooster dat beter (of in ieder geval anders) scoort op de bedrijfsregels, zonder dat harde bedrijfsregels worden overtreden.

- Opnieuw doorrekenen

Daarnaast kan het rooster in zijn geheel opnieuw worden doorgerekend, waarbij is ingesteld dat er zo min mogelijk wijzigingen moeten worden doorgevoerd. Het bestaande rooster is dan het uitgangspunt, niet een compleet nieuwe situatie.

PROTOTYPE ROOSTEREN

LEERERVARINGEN EN CONCLUSIE

Leerervaringen en vervolg Het prototype roosteren had tot doel om inzicht te krijgen in de contouren van de oplossing voor een roostermachine die invulling geeft aan de functionele wensen zoals verwoord in het functioneel ontwerp onderwijslogistiek, beheren middelen en roosteren. De vraag is uiteraard welke inzichten nu zijn opgedaan en in welke mate die functionele wensen daadwerkelijk realiseerbaar zijn gebleken. Haalbaarheid Het prototype zoals dat nu ontwikkeld is geeft een aantal belangrijke inzichten over de haalbaarheid en realiseerbaarheid van de functionele wensen. De belangrijkste inzichten die het onderzoek en het prototype hebben opgeleverd zijn de volgende. - Toepasbaarheid van de gekozen oplosstrategieën

Het onderzoek naar mogelijke oplossingen en wiskundige aanpakken heeft veel inzicht opgeleverd in de complexiteit van het probleem en de mogelijke oplossingen daarvoor. Uiteindelijk is een combinatie van twee oplosstrategieën benoemd die het meest kansrijk zijn voor een concrete implementatie van een rooster-



machine. Het ontwikkelde prototype past deze oplosstrategieën ook daadwerkelijk toe om tot een roosteroplossing te komen.

- Individuele leervraag als uitgangspunt

Het gerealiseerde prototype werkt uitsluitend met individuele leervragen, en niet met klassen en groepen. Het resultaat van het roosterproces is daarmee dus ook een rooster per deelnemer, en per docent.

- Werken met een onderwijscatalogus

Het gerealiseerde prototype werkt met een gestandaardiseerde (gemetadateerde) beschrijving van al het aangeboden onderwijs. Hierbij heeft een onderwijsproduct de betekenis van een roosterbare eenheid. Op basis van de metadata wordt daadwerkelijk bepaald op welk moment, met welk aantal deelnemers, met welke docent en welke aanvullende middelen de sessie moet worden geroosterd.

- Werken met bedrijfs- en onderwijsregels

In het gerealiseerde prototype worden bedrijfs- en onderwijsregels daadwerkelijk gebruikt om het optimalisatieproces te sturen. Harde constraints bepalen of een rooster uitvoerbaar is of niet. Zachte constraint bepalen in welke mate het ene rooster beter is dan het andere. Deze constraints sturen het optimalisatieproces. Deze constraints zouden liefst niet zwart-wit moeten worden

17

18

PROTOTYPE ROOSTEREN



geformuleerd maar moeten aangeven wat de waardering (of teleurstelling) per mogelijkheid is.

- Niet alleen standaardlessen

Er is vooral veel aandacht besteed aan de realiteit dat lang niet alle lessen standaardlessen zijn, waarin gedurende een lesuur een aantal deelnemer met een docent in een lokaal aan de slag is. Er kan gewerkt worden met sessies variërend in lengte van een kwartier tot meerdere weken, met meerdere docenten en lokalen of juist parallel in groepen.

- Rapportage

Het prototype levert een rapportage over het geproduceerde rooster waarin op een aantal punten de kwaliteit van het rooster inzichtelijk wordt gemaakt.

Dit zijn een aantal van de belangrijkste eigenschappen van het gerealiseerde prototype. Het is mogelijk gebleken om een prototype te ontwikkelen dat deze eigenschappen in zich heeft. Bovendien is deze aanpak in de praktijk toegepast op de bestaande gegevens van een (onderdeel van een) instelling. Aan de andere kant heeft het gerealiseerde protoype nog een aantal beperkingen. Een aantal functionele wensen en eigenschappen zijn niet gerealiseerd en beproefd. De belangrijkste verschillen tussen het gerealiseerde prototype en de functionele wensen zijn de volgende. - Geen top-X van roosters

In de functionele eisen wordt uitgegaan van een situatie waarbij de roostermachine een aantal varianten van een rooster levert die echt verschillend zijn maar allemaal goed scoren op de criteria (de contstraints). Uit die roosters kan er dan één gekozen worden.



De huidige roostermachine werkt niet op die manier. Er wordt een zo goed mogelijk rooster gemaakt. Hoe langer aan het rooster gerekend wordt, hoe beter het wordt. Een beter rooster ligt daarmee in het verlengde van een minder goed rooster, maar is geen echt alternatief.



Voor het roosterproces betekent dit, dat in plaats van het kiezen uit de top-X, de roostermaker kan ‘draaien aan de knoppen’ en de roostermachine verder kan laten rekenen. Ook kunnen er handmatig, door de machine ondersteund, aanpassingen aan een rooster worden gemaakt.

PROTOTYPE ROOSTEREN

- Rapportage over (de kwaliteit van) het geproduceerde lesrooster

Met betrekking tot de rapportage over het rooster was het uitgangspunt dat de rapportage inzicht geeft in de score van het rooster op de bedrijfsregels, de mate waarin middelen zijn ingezet en de mate waarin arrangementen van deelnemers zijn gehonoreerd. Het huidige prototype geeft dit inzicht maar gedeeltelijk. Een deel van de bedrijfsregels is sterk verweven met het optimaliseringsalgoritme, waardoor de score op die bedrijfsregel afzonderlijk niet inzichtelijk is. Dit is geen fundamentele beperking maar vergt extra inspanning voor het uitbreiden van de programmatuur.

- Instelbaarheid van bedrijfs- en onderwijsregels

Het ideaalbeeld van de oplossing was dat de roostermachine werkt op basis van een verzameling onderwijs- en bedrijfsregels die instelbaar zijn. De roostermaker kan dan op basis van de rapportage (zie vorige punt) de score analyseren en op basis daarvan ‘aan de knoppen draaien’, waarmee bedoeld wordt dat de onderwijs- en bedrijfsregels kunnen worden aangepast.



Het huidige prototype biedt niet de mogelijkheid om alle bedrijfsregels (constraints) op een uniforme manier te definiëren een gaandeweg het roosterproces bij te stellen. De regels zijn deels onderdeel van het algoritme of in ieder geval onderdeel van de programmatuur en niet allemaal eenvoudig door een gebruiker aan te passen.

- Gedeeltelijk geschikt voor tactische planning

Het huidige prototype werk uitsluitend met feitelijke gegevens en niet met prognoses. Daardoor is het in zijn huidige vorm niet geschikt voor de zogenaamde tactische planning: een roosterprognose voor een periode van een jaar.



Het prototype kan overigens wel roosters voor meerdere periodes maken, ook voor een jaar vooruit, maar alleen als alle gegevens (arrangementen, lokalen, middelen etc.) voor die hele periode beschikbaar zijn. Dat zou bijvoorbeeld mogelijk gemaakt kunnen worden door uit historische gegevens en prognoses fictieve arrangementen voor de deelnemers te maken.

- Beperkte functionaliteit rond inzet docenten

De functionaliteit rond docenten is sterk onderbelicht in het huidige prototype. Zo wordt geen rekening gehouden met de feitelijke beschikbaarheid van docenten (hun jaartaak). Docenten zijn ook vast gekoppeld aan de lessen die zij geven.

19

20

PROTOTYPE ROOSTEREN

- Beperkingen in de user-interface

De programmatuur kan niet eenvoudig worden geïnstalleerd en geconfigureerd. Het huidige prototype beschikt daarom nauwelijks over een user-interface voor eindgebruikers. Zowel de aanlevering van gegevens als de geproduceerde roosters zijn in de vorm van XML-bestanden. Ook is er geen user-interface om bedrijfsregels te bekijken of te wijzen; dit is allemaal vastgelegd in configuratiebestanden of in de programmatuur zelf.

Het gebruik van het prototype vereist daarom op dit moment een behoorlijke hoeveelheid specialistische kennis. Conclusie Het prototype roosteren heeft een aantal belangrijke inzichten opgeleverd. Het belangrijkste is dat er een goed onderbouwde oplossingsstrategie beschikbaar is voor het type probleem zoals dat is geformuleerd. Het prototype heeft laten zien dat deze oplossingstrategie ook daadwerkelijk in de praktijk toepasbaar is. Het prototype heeft echter nog niet de volledige complexiteit in zich, zoals die in werkelijkheid bij instellingen gaat onstaan als echt flexibel en individueel gaat worden geroosterd. Het aantal toe te passen bedrijfs- en onderwijsregels zal groter worden, en de variaties in arrangementen, onderwijsproducten en middelen ook. Daarnaast zal er veel behoefte zijn om te ‘spelen’ met de regels en de effecten te analyseren. De uitdaging is om dat ook voor een gebruiker overzichtelijk te houden. Ondanks de versimpelde werkelijkheid waarop het prototype is gebaseerd, geven de resultaten wel het vertrouwen dat ook de complexe werkelijkheid op een vergelijkbare manier kan worden verwerkt. De oplossingsstrategie is ook geschikt voor deze complexe werkelijkheid, het is meer van hetzelfde. Het prototype is niet bedoeld om als zelfstandig product te worden gebruikt. Daar is het in zijn huidige vorm ook ongeschikt voor. De kennis die in het protoype zit opgesloten over de manier waarop het roosterprobleem kan worden opgelost is het belangrijkste. De programmatuur zal van een adequate user-interface moeten worden voorzien om ook daadwerkelijk gebruikt te kunnen worden. En los daarvan zullen er verschillende koppelingen nodig zijn met andere administraties binnen een instelling: de onderwijscatalogus, deelnemeradministratie en arrangementen, middelenadministratie etc. Het prototype zal inclusief documentatie als open source beschikbaar worden gesteld. Hiermee worden leveranciers en instellingen in staat gesteld om de kennis en de gerealiseerde software te gebruiken in eigen oplossingen.

PROTOTYPE ROOSTEREN

HOE NU VERDER? Het prototype roosteren is niet ontwikkeld om daadwerkelijk door een instelling in gebruik te worden genomen. Het is ook niet ontwikkeld om uiteindelijk door te worden ontwikkeld tot een commercieel product naast de nu in de markt beschikbare roosteroplossingen. Het roosterprototype is bedoeld om inzicht te geven in de mate waarin het roosterprobleem, zoals omschreven in het functioneel ontwerp van Triple A, daadwerkelijk oplosbaar is. Daarnaast is het bedoeld om inzicht te geven in hoe die oplossing er dan op hoofdlijnen uit ziet. Met de inzichten die zijn opgedaan en het prototype dat nu beschikbaar is zien wij de volgende mogelijkheden. - Laboratoriumexperimenten

Dit betekent dat met ‘echte’ gegevens van een instelling wordt onderzocht wat het zou betekenen als op de nieuwe manier zou worden geroosterd. Hiermee kan inzicht worden verkregen in de consequenties van flexibel, individueel roosteren. Daarbij kan inzicht worden verkregen in de mogelijkheden voor optimalisatie van bepaalde bedrijfsregels, zoals lokalenbezetting of belasting van docenten.

- Aanbieden aan leverancier van roosteroplossingen

Het prototype roosteren is beschikbaar als open source software en zal in die vorm beschikbaar komen voor leveranciers. Zij kunnen de software zonder kosten inzien en gebruiken, mits zij het intellectueel eigendom respecteren.



Dit betekent dat verschillende leveranciers (delen van de) oplossing kunnen integreren in hun eigen roosteroplossing. Zo kunnen in de markt verschillende roosteroplossingen ontstaan die (deels) zijn gebaseerd op de resultaten van dit prototype. Het grote verschil is, dat commerciële softwareleveranciers ook veel aandacht hebben voor de gebruikersinterface, het opmaken en publiceren van de roosters en mogelijkheden om de invoer of import van gegevens gebruiksvriendelijk te ondersteunen.

21

PROTOTYPE ROOSTEREN

technisch gedeelte

23

24

PROTOTYPE ROOSTEREN

Inhoudsopgave Inleiding

26

Doelstelling van het technische gedeelte Leeswijzer

26 26

Deel I: Globale requirements Werkprocessen rondom de rooster-engine Uitwerking van het werkproces “Maken rooster”  Uitwerking van harde constraints  Uitwerking van zachte constraints, weging  Deel II: Globaal functioneel ontwerp  Consequenties voor de rooster-engine  Simulaties, fictieve resources  Uitwerking van de beoordeling van roosters 

27 27 29 33 34

Deel III: Globaal technisch ontwerp Belangrijke onderdelen van de rooster-engine  Uitwerking van entiteiten in het roosterprobleem De onderwijscatalogus  Deelnemers, docenten en middelen  Het rooster  Symbolische weergave van een rooster  Symbolische weergave van de constraints  Analyse, decompositie van het probleem  Verwachtingen en tactische planning  Andere technische keuzes op het globale niveau

40 40

37 37 38 39





41 41 42 42 43 45 46 47 48

PROTOTYPE ROOSTEREN

Deel IV: Wiskundige oplosstrategieën voor roosterproblemen Introductie: optimalisatie, lineair programmeren  Introductie van combinatorische problemen  Introductie van de column generation techniek  Introductie van local search methoden  Beoordeling/inschatting van de oplosrichtingen  Evaluatie van de UniTime/CourseTT programmatuur Voorgestelde aanpak voor het roosteren  Deel V: Conclusies en aanbevelingen Aanpak en conclusies van VORtech Oplossingsrichtingen  Evaluatie van het product UniTime/CourseTT

 







49 45 51 52 55 55 58 60 62 62 62 63

25

26

PROTOTYPE ROOSTEREN

Inleiding Doelstelling van het technische gedeelte In dit technische gedeelte wordt uitgewerkt wat de beoogde rooster-engine zou moeten doen (requirementsanalyse, functioneel ontwerp) en hoe dat gedaan kan worden (technisch ontwerp, oplosmethoden). - zodat de beoogde gebruikers van het systeem (de instellingen, vertegenwoordigd door Triple A) kunnen beoordelen of het ontwerp aansluit op de wensen en eisen; - zodat de ontwikkelaars van een systeem een opzet/overzicht hebben voor het maken ervan en kunnen beoordelen of deze aanpak haalbaar is. Uiteindelijk zou het technisch gedeelte gedetailleerd moeten beschrijven hoe het roosterprobleem volgens Triple A moet worden geformuleerd en hoe het vervolgens opgelost kan worden. Leeswijzer Op basis van het hierboven geschetste uiteindelijke doel bestaat het technisch gedeelte uit vijf delen. - Eerst wordt de problematiek van het roosteren en de behoeftes van de ROC/ AOC’s beschreven: de functionele requirements, Deel I. - Vervolgens wordt beschreven wat de rooster-engine moet kunnen om in deze behoeftes te voorzien: het globale functioneel ontwerp, Deel II. - Als derde wordt een globale uitwerking van het systeem geschetst. Dat vormt de architectuur of het globaal technisch ontwerp: Deel III. - Deel IV geeft een overzicht van wiskundige technieken die gebruikt kunnen worden voor roosterproblemen. Op basis van gesprekken met deskundigen en opgedane ervaringen tijdens het maken van het prototype wordt hier een keuze in voorgesteld. - Tenslotte worden in Deel V de belangrijkste conclusies en aanbevelingen samengevat. Het prototype roosteren is stapsgewijs ontworpen en gerealiseerd. Niet alle aspecten van het vraagstuk zijn in dezelfde mate uitgewerkt en gerealiseerd in het prototype. Ook in dit technische gedeelte zijn daarom bepaalde aspecten verder uitgewerkt dan andere.

PROTOTYPE ROOSTEREN

DEEL I: Globale requirements Dit deel beschrijft een inventarisatie van werkprocessen bij de instellingen rondom het roosterprobleem. Dit kan worden gezien als een analyse van de globale requirements voor het te ontwikkelen roostersysteem.

Werkprocessen rondom de rooster-engine De procesbeschrijvingen met betrekking tot het roosteren en de daarbij te identificeren use cases worden uitgebreid besproken in het functioneel ontwerp Onderwijslogistiek, roosteren en beheren middelen dat onderdeel is van de Triple A encyclopedie. Hieronder worden de use cases die van belang zijn voor het roosteren beknopt samengevat. Formuleren van de leervraag Deelnemers gaan een overeenkomst aan met een instelling. In overleg met een begeleider wordt er een leervraag vastgelegd. Deze bestaat uit produkten uit de onderwijscatalogus, (eventueel) aangevuld met additionele wensen en voorwaarden. In veel gevallen gebeurt dit op een hoog aggregatieniveau. Arrangement specificeren Tijdens het arrangeren wordt de leervraag uitgewerkt naar produkten op het laagste aggregatieniveau uit de onderwijscatalogus. Ook worden in het arrangement randvoorwaarden van de deelnemer gespecificeerd. Bij het arrangeren zijn verwachtingen omtrent het rooster van belang. Een arrangement kan over een langere periode gaan dan een enkele roosterperiode, waarmee speelruimte wordt geboden aan het roosterproces. Maken rooster Op basis van de arrangementen per deelnemer, de beschikbare docenten, lokalen en middelen, wordt er periodiek een nieuw rooster gemaakt. Dit wordt uitgewerkt in de hierna volgende paragraaf Uitwerking van het werkproces “Maken rooster”, waar de overeenkomstige use case uit het functioneel ontwerp is overgenomen. Effectueren rooster Een rooster dat in het roosterproces is opgesteld wordt definitief gemaakt door met alle betrokkenen te communiceren, de benodigde middelen toe te wijzen, benodigde veranderingen in middelen en arrangementen in gang te zetten en indien van toepassing, de deelnemersacceptatie te starten.

27

28

PROTOTYPE ROOSTEREN

Monitoren acceptatie Afhankelijk van het beleid van een instelling kan er om acceptatie door de deelnemers worden gevraagd. Dat betekent dat een rooster ook kan worden afgewezen, waarna er naar een oplossing moet worden gezocht, door opnieuw te roosteren of op een andere manier. Individueel roosterprobleem oplossen Als een deelnemer problemen rapporteert met betrekking tot het rooster, hetzij bij de acceptatiestap, hetzij door veranderende omstandigheden, dan treedt hij in gesprek met zijn begeleider voor het oplossen van een individueel roosterprobleem. Daarbij wordt naar een passende oplossing gezocht. Afhandelen niet-planbare arrangementen Uit het roosterproces komt een diagnoserapport waarin zichtbaar is welke arrangementen niet geheel planbaar zijn. Dit kan gebeuren doordat te weinig deelnemers hebben gekozen voor een onderwijsproduct of doordat er te weinig middelen zijn om het product aan te kunnen bieden. In overleg met de begeleider wordt naar een aanpassing van de leervraag of het arrangement gezocht die wel kan worden ingepland. Individueel aanvullen rooster Een leervraag van een deelnemer kan tijdens een roosterperiode veranderen door opgedane ervaringen. Een instelling kan hierop inspelen door een deelnemerrooster niet geheel te vullen, maar een rooster met “gaten” te maken. Op deze manier kan een rooster naderhand individueel worden aangevuld met bijvoorbeeld workshops, aanvullende begeleiding, extra onderwijsproducten, stages e.d. Controle rooster realisatie Als een roosterperiode is geëindigd, wil een instelling weten of de vraag en het aanbod samen zijn gekomen. Om te kunnen voldoen aan wet- en regelgeving wil men weten of het geplande rooster ook daadwerkelijk is uitgevoerd. Daarnaast wil men weten of het geplande rooster kwalitatief heeft voldaan. Oplossen uitvoeringsprobleem Er zijn situaties denkbaar dat het rooster veranderd moet worden ondanks dat dit reeds is vastgesteld. Een docent kan ziek worden, een bal vliegt door een ruit, een stageplaats is toch niet beschikbaar etc. Het gaat hier dus om incidenten rondom in te zetten middelen die niet goed voorspelbaar zijn. Bij het oplossen wordt gestreefd naar het zo veel mogelijk intact houden van het bestaande rooster.

PROTOTYPE ROOSTEREN

Oplossen calamiteit Calamiteiten zijn veranderingen in situaties met betrekking tot middelen die een grotere omvang en impact hebben, zoals langdurige afwezigheid van een docent en het afbranden van een gebouw. Hierdoor wordt opnieuw roosteren noodzakelijk. Tactische planning Roosterinformatie moet kunnen worden geanalyseerd over de korte en middellange termijn. Dit is van belang voor “forward mapping”: het maken van voorspellingen over het te realiseren onderwijs en de benodigde middelen op de middellange termijn. Hierbij worden ervaringscijfers uit het verleden gebruikt.

Uitwerking van het werkproces “Maken rooster” Voor het ontwikkelen van een rooster-engine is vooral de use case “Maken rooster” van belang. De beschrijving van deze use case is overgenomen uit het functioneel ontwerp Onderwijslogistiek, roosteren en beheren middelen. Inleiding Deze use case is het eerste onderdeel in de roostercyclus: 1. Maken rooster (vooraf aan roosterperiode) 2. Individueel aanvullen rooster (gedurende roosterperiode) 3. Controle realisatie rooster (na roosterperiode) De toepassing van deze use case is afhankelijk van een groot aantal keuzes die gemaakt kunnen worden door de instelling zelf. Voorbeelden: - Is de deelnemer altijd een bepaalde tijd aanwezig (bijv. 09.00 tot 16.00 of 08.00 tot 13.00)? - Plannen we het rooster van een deelnemer geheel vol of laten we ruimte voor ad hoc invulling? - Kiezen we bij het beoordelen van een definitief rooster voor het raadplegen van deelnemers? - Is in een arrangement beschreven welke onderwijsproducten uit de onderwijscatalogus in welke volgorde en periode moeten worden uitgevoerd of wordt hier meer ruimte voor geboden? - Maken we voor alle onderdelen van de instelling tegelijkertijd een nieuw rooster? Daarnaast moet er een keuze door de instelling worden gemaakt voor: - Controle realisatie rooster (na roosterperiode) - Periode waarvoor rooster gemaakt wordt. Bijv. 1 dag, 10 weken of heel jaar - Frequentie van het maken van een nieuw rooster. Bijv. elke dag, elke 10 weken

of 1 keer per jaar

29

30

PROTOTYPE ROOSTEREN

Lengte van de periode voorafgaande aan de ingangsdatum van een rooster, waarop deze definitief moet zijn. Bijvoorbeeld 1 week voor start moet een rooster zijn vastgesteld. Het uitgangspunt bij het beschrijven van de activiteiten is dat er nog geen keuzes gemaakt zijn. De use case moet alle mogelijke scenario’s afdekken. Het voordeel is dat het maximale flexibiliteit aan de onderwijsinstelling biedt, omdat de definitieve inrichtingskeuze pas bij invoering in een onderwijsinstelling hoeft te worden gemaakt. Aanleiding Periodiek (zie inleiding: bijv. iedere 10 weken) zal er in opdracht van het management van een instelling een compleet nieuw rooster worden gemaakt. Waar instelling staat kan ook een deel van de instelling worden gelezen. of Door een ernstig uitvoeringsprobleem (vanuit de use case Oplossen Calamiteit). Er zal een nieuw rooster voor het restant van de huidige periode gemaakt moeten worden. of Door een massale afwijzing van het rooster door leerlingen (vanuit de use case “Monitoren acceptatie deelnemersrooster”). Er zal een nieuw rooster voor (een deel) van de deelnemers gemaakt moeten worden. Actoren - Operator (OP) (houdt zich bezig met de roostermachine) - Roostermaker (RM) (houdt zich bezig met analyseren van resultaten en begeleidt het roosterproces) - Manager onderwijs (MO) - Manager bedrijfsvoering (MB) - Deelnemer (optioneel) - Begeleider (optioneel) Doel We maken een rooster om de vraag naar onderwijsproducten van deelnemers en het aanbod daarvan door de instelling op elkaar af te stemmen. We zoeken daarbij een balans tussen deelnemer-, onderwijs- en bedrijfseconomische belangen. Beschrijving acties Een aantal beheersacties moeten vooraf zijn uitgevoerd. De frequentie hiervan zal laag zijn (bijvoorbeeld 1x per jaar).

PROTOTYPE ROOSTEREN

- Beheren regels

De RM vraagt aan de MO om onderwijsregels en aan de MB om bedrijfsvoeringregels. Voorbeelden van onderwijsregels zijn, maximaal 8 lesuren per dag of 3 tussenuren per week voor een deelnemer, maximaal 1 afwijzing van een onderwijsproduct uit een arrangement van een deelnemer, geen leervakken na het 8e uur, altijd bevoegde docenten. Voorbeelden van bedrijfsvoeringregels zijn, maximaal 8 lesuren per docent per dag, praktijklokaal koken alleen op maandag, iedere docent moet voor minimaal 50% worden ingeroosterd, een onderwijsproduct mag alleen worden aangeboden bij een minimale inschrijving van 5 deelnemers.



Als de RM de regels krijgt, controleert hij deze op volledigheid, correctheid, realiseerbaarheid en of de regels gezamenlijk niet in conflict zijn en koppelt het resultaat terug aan de MO en MB. In overleg worden de mogelijke problemen opgelost en de regels vastgesteld en vastgelegd in de roostermachine door de OP.

- Beheren weegfactoren

Na het vaststellen en vastleggen van de regels moeten weegfactoren bepaald worden over de relatieve zwaarte van een regel. De zwaarte van een regel heeft direct effect op de uitkomst van een rooster. De machine levert een top-x van roosters op met diagnoserapporten (x is bijvoorbeeld 5). De regels met de weegfactor bepalen de kwaliteitvolgorde van de opgeleverde roosters.



De MO en MB zullen over de zwaarte van de regels met elkaar moeten onderhandelen. De RM kan dit proces begeleiden. Als de weegfactoren zijn vastgesteld zal de OP ze vastleggen in de machine.

- Beheren overige instellingen:

De OP zal de overige instellingen, zoals inhoud en lay-out van het diagnoserapport, aantal te bewaren top-x roosters, etc, in de roostermachine vastleggen. Hij doet daartoe voorstellen die door de organisatie moeten worden gefiatteerd.

- Communicatie peildatum

Voorafgaande aan het laten draaien van machine worden alle betrokkenen geïnformeerd (via moderne communicatiemiddelen) over de startdatum van het maken van een nieuw rooster, zodat iedereen weet wanneer de arrangementen gereed moeten zijn.

31

32

PROTOTYPE ROOSTEREN

- Uitvoeren controles

De OP zal voordat hij de roostermachine start controleren of voor alle ingeschreven deelnemers een arrangement is gespecificeerd. Als dit niet het geval is wordt de RM op de hoogte gesteld en deze zal in overleg met de MO en MB bepalen welke oplossingsrichting bewandeld wordt. Te denken valt aan het tijdelijk stopzetten van het roosterproces. Begeleiders en arrangeurs krijgen dan x dagen de tijd. Maar het roosterproces kan ook gewoon doorgaan. Met de betreffende individuele deelnemer worden dan afspraken gemaakt over wat er wordt gedaan met hun arrangement.

- Vullen roostermachine

De arrangementen van de deelnemers en de beschikbaar gestelde middelen



worden door de OP opgehaald en in de database van de roostermachine opgeslagen. Hiermee worden de beschikbare middelen en opgevoerde arrangementen bevroren gedurende het roosterproces. Veranderingen in arrangementen of middelen die gedurende het roosteren worden aangebracht in de productieomgeving, worden niet meegenomen in de lopende roostercyclus. Deze veranderingen worden zichtbaar in de use case “Effectueren rooster”.

- Opstellen roostervoorstellen

De roostermachine wordt gestart. De machine zal voortdurend de x beste roostervoorstellen en bijbehorende diagnoserapporten beschikbaar stellen. Zichtbaar is hoeveel roosters er zijn doorgerekend en wanneer de laatste verandering in de top x heeft plaats gevonden. Daarmee is er inzicht in de voortgang van de “run”.

- Beoordelen roostervoorstellen

De roostervoorstellen en de bijbehorende diagnoserapporten worden door de RM geanalyseerd. De voorstellen en de analyse worden overlegd met de MO en MB. De roostervoorstellen zullen door de MO worden beoordeeld met oog voor de belangen van de deelnemer en de kwaliteit van het onderwijs. De MB zal de belangen van de docenten en de bedrijfseconomische belangen mee laten wegen in zijn oordeel. De MO en de MB kunnen (indien gewenst) overleggen met individuele deelnemers en/of begeleiders en docenten. Alleen in het ideale geval zal het rooster meteen geaccepteerd worden. Indien er geen geschikt roostervoorstel bij zit, kunnen er aanpassingen in de vraag (arrangementen) en het aanbod (middelen en regels) worden gedaan om te simuleren in de roostermachine. Als er gebruik wordt gemaakt van een fictief middel, is het uitgangspunt dat dit fictieve middel voor aanvang van de start van een periode is gerealiseerd. Deze simulatie levert nieuwe roostervoorstellen en de bijbehorende diagnoserapporten op. Opnieuw worden de roostervoorstellen en diagnoserapporten geanalyseerd, besproken en beoordeeld.

PROTOTYPE ROOSTEREN

- Vaststellen rooster

Uiteindelijk zal er, mogelijk gedwongen door de tijd, besloten worden met roostervoorstel en het bijbehorende diagnoserapport akkoord te gaan. Er gaat dan een signaal naar de use case “Effectueren rooster”.

Resultaat - Een goedgekeurd rooster voor een vastgestelde periode met indien van toepassing de toezegging om de voorgestelde aanpassingen te realiseren. Frequentie Het gehele proces vindt in ieder geval plaats voor iedere nieuwe roosterperiode. De instelling bepaalt de frequentie hiervan zelf. Deze zal varieren van 1x per jaar tot 1x per dag. Daarnaast kunnen de use cases “Oplossen calamiteit” en “Monitoren acceptatie “ de frequentie verhogen.

Uitwerking van harde constraints Hierboven is een overzicht gegeven van het (verwachte) proces van het maken van lesroosters, met veronderstellingen (requirements) over hoe de rooster-engine kan worden gebruikt. Daarnaast is van belang waar de lesroosters zelf aan moeten voldoen, het roosterprobleem zelf. Dit wordt beschreven via welke soorten onderwijs er allemaal moeten worden ondersteund, aan welke wensen en eisen van deelnemers, docenten en instellingen moet kunnen worden voldaan. Met betrekking tot eisen en wensen maken we onderscheid tussen harde en zachte constraints. Harde constraints zijn constraints waaraan altijd door het rooster moet worden voldaan. Zo niet dan wordt het rooster afgekeurd. Zachte constraints zijn constraints die eventueel wel mogen worden geschonden. Constraints die niet altijd hard zijn kunnen beter als “heel erge” zachte constraints worden aangemerkt. Opmerking: In deze paragraaf sommen we de harde constraints op die tot nu toe zijn geïdentificeerd. Deze lijst kan steeds verder worden aangevuld. - Eisen van deelnemers . kan maar op een plek tegelijk zijn; . is op bepaalde momenten niet beschikbaar (‘s nachts, vakantie); . heeft tijd nodig om van de ene naar de andere lokatie te gaan; . kan bepaalde fysieke beperkingen hebben waar rekening mee moet worden

gehouden;

. kan bepaalde restricties opleggen vanuit culturele achtergrond.

33

34

PROTOTYPE ROOSTEREN

- Eisen van onderwijsgevenden . kan maar op een plek tegelijk zijn; . is op bepaalde momenten niet beschikbaar (‘s nachts, vakantie); . heeft tijd nodig om van de ene naar de andere lokatie te gaan. - Eisen van onderwijsproducten - Eisen van ruimtes/middelen - Eisen van bedrijfsvoering - Eisen van wet- en regelgeving . minimaal aantal contacturen per jaar; . ARBO-wetgeving, CAO.

Uitwerking van zachte constraints, weging Zachte constraints zijn eisen en wensen die niet direct leiden tot afwijzing van een rooster maar leiden tot “teleurstelling”. In deze paragraaf sommen we de zachte constraints op die tot nu toe zijn geïdentificeerd. Deze lijst kan steeds verder worden aangevuld. - Eisen en wensen van deelnemers . einddoel, diploma; . arrangement; . beschikbaarheid zoals wensen m.b.t. vakantie; . weinig tussenuren; . spreiding per dag (zwaarte, soorten vakken), over de week; . consistentie t.a.v. docent, lokaal; . voorkeuren voor docenten; . rekening houden met fysieke beperkingen, “belastbaarheid”; . wensen vanuit culturele achtergrond. - Eisen en wensen van onderwijsgevenden . jaartaak, afspraken uit aanstelling, CAO . beschikbaarheid: competenties, omvang inspanning, tijden, geplande

afwezigheid;

. voorkeuren t.a.v. inzet.

PROTOTYPE ROOSTEREN

- Eisen en wensen van onderwijsproducten . tijd- en plaatsafhankelijkheid; . koppeling aan ruimte, faciliteiten, capaciteiten docent; . volgorde-relaties “geschikt voor start”; . vereiste leerstijl; . aantal sessies per week (verschillende dagen), uren per sessie, aantal weken

achter elkaar;

. minimum en maximum aantal deelnemers.

Dit kan verder worden uitgewerkt met behulp van de metadata die in de onder



wijscatalogus wordt gebruikt.

- Eisen en wensen van ruimtes/middelen . geschiktheid van ruimtes: capaciteit, faciliteiten; . beschikbaarheid stageplaatsen.

Hierover komt informatie beschikbaar via de metadatering van middelen. Er kan



daarnaast worden gekeken naar een kernregistratie middelen waarin informatie



beschikbaar is over de inzetbaarheid van middelen.

- Eisen en wensen van bedrijfsvoering . openingstijden per locatie, opleiding, docent, e-learning; . kosten per docent, middel; . (gewenste) benutting middelen, ruimtes, docenten; . opbrengst per onderwijsproduct, diploma. Weging: hoe scoor je een rooster? Uiteindelijk zal er een weging moeten plaatsvinden om te bepalen of het ene rooster beter scoort dan het andere. De zachte constraints zijn bepalend voor deze weging. Hieronder zijn op basis van de zachte constraints een aantal wegingsfactoren benoemd. Ook deze lijst kan steeds verder worden aangevuld. - Niet-volledig gerealiseerde arrangementen; - te weinig uren voor de urennorm; - veel en/of grote gaten (exclusief bewust vrijgelaten ruimte); - spreiding zware vakken door de week; - mix van theorie en praktijk; - bezettingsgraad: uren lokaal per week, aantal studenten per sessie, m2 per student;

35

36

PROTOTYPE ROOSTEREN

. aantal niet-gehonoreerde voorkeuren deelnemers en docenten; . aantal bewegingen tussen locaties; . gebalanceerde verdeling werklast over docenten. Het is de verwachting dat er nog veel impliciete wensen bestaan die moeilijk getalsmatig kunnen worden uitgedrukt. Daarvoor zouden mogelijke roosters door gebruikers moeten worden beoordeeld om te bepalen wat er nog aan schort. Een ander interessant experiment is handmatig gemaakte roosters te laten beoordelen door de formule en te kijken wat de “kwaliteit” hiervan is in vergelijking met roosters die automatisch zijn gegenereerd.

PROTOTYPE ROOSTEREN

Deel II: Globaal functioneel ontwerp

De rooster-engine is een ICT-systeem dat lesroosters maakt voor instellingen. In het vorige deel is beschreven in welke omgeving dit systeem moet kunnen worden gebruikt en welke eisen er daarom aan worden gesteld. In dit deel wordt uitgewerkt wat het beoogde systeem (functioneel) zou moeten kunnen doen. - Het moet gericht zijn op competentie-gericht onderwijs, met individuele leervragen per deelnemer; - Het moet proberen voor alle deelnemers een goed aanbod samen te stellen en moet hiervoor vraaggestuurd werken; - Het moet geschikt zijn voor kleine en voor grote instellingen, variërend van 200 tot 25.000 deelnemers; - Vanwege de omvang van het probleem moet het roosteren verregaand worden geautomatiseerd, rekening houdend met allerlei soorten constraints

Consequenties voor de rooster-engine Uit de uitgewerkte use cases van deel I kan worden afgeleid wat voor eisen er aan de rooster-engine worden gesteld. Een belangrijke constatering is dat er veel menselijk inzicht aanwezig is in het hele proces. De rooster-engine hoeft zich niet te focusen op een perfect resultaat (zo dat al bestaat). In plaats daarvan moeten de mensen die vragen en problemen hebben goed kunnen worden ondersteund. - Het is de bedoeling dat de roosterengine uit zichzelf een redelijk goed initieel rooster kan maken. Een eerder ingevuld rooster moet kunnen worden ingelezen en als initieel rooster kunnen worden gebruikt. - De operator, roostermaker en onderwijskundige moeten overzichtelijke informatie krijgen over de knelpunten die de roosterengine signaleert en dan ingrepen op het rooster kunnen doen. Daarna kan de rooster-engine weer verder worden aangezet. - Mogelijke ingrepen van de roostermaker zijn: · hard vastzetten van activiteiten in het rooster; · verwisselen van activiteiten in het rooster; · (tijdelijk) aanpassen van de constraints, met name inzetbaarheid van

middelen;

· (tijdelijk) toevoegen van fictieve middelen, simuleren wat voor effect het

uitbreiden van middelen heeft.

- Een mogelijke ingreep van de onderwijskundige is: · (tijdelijk) aanpassen van de arrangementen van deelnemers, simuleren wat

voor effect op het roosteren dat heeft.

37

38

PROTOTYPE ROOSTEREN

- De roosterengine moet kunnen aangeven welke aanpassingen waarschijnlijk nuttig kunnen zijn. - Het is de verwachting dat er veel aanvullende wensen bestaan die niet goed

expliciet te maken of te kwantificeren zijn. Daarom zullen mensen een ander gevoel van “kwaliteit” van het rooster kunnen hebben dan wat de rooster-engine de kwaliteit noemt.

Simulaties, fictieve resources In de stappen hierboven is te zien dat er tussentijds simulaties/experimenten moeten kunnen worden uitgevoerd die later weer moeten kunnen worden teruggedraaid. Een aandachtspunt hierbij is dat er hiervoor ook tijdelijke aanpassingen aan dataobjecten nodig zijn, die niet in de “echte” administratie (databases) van objecten mogen worden doorgevoerd. Fictieve resources kunnen zijn een extra leraar Duits, een extra beamer, een extra lokaal met bepaalde eigenschappen, etc. De fictieve resources hebben verschillende toepassingen. Bijvoorbeeld maken van een rooster met een extra leraar Duits (voltijds aanstelling) of kijken hoeveel fte extra Duits er nodig is. In het eerste geval moet de fictieve resource gelijk aan echte resources worden beschouwd, in het tweede geval moet hij zo min mogelijk worden ingezet. In de aanpassingen van de roostermaker is te zien dat sommige constraints gemakkelijk te overrulen zijn. Er kunnen gemakkelijk wat extra stoelen in een lokaal worden geplaatst, een praktijklokaal kan voor theorie worden gebruikt, er kunnen meerdere activiteiten tegelijk in een lokaal worden geplaatst en soms kunnen wandjes worden gezet of verplaatst. Vergelijkbare flexibiliteit bestaat bij leraren: wat overuren draaien, toch maar een ander vak erbij doen, wat eerder beginnen, etc. Dit kan allemaal via fictieve middelen of tijdelijke aanpassingen aan echte middelen worden gesimuleerd, maar zou ook van tevoren al via de constraints, business rules en weging kunnen worden aangepakt. Er zou naar moeten worden gestreefd om de “echte” constraints en businessrules te identificeren en te gebruiken in de roosterengine. Met name voor terugkerende situaties. Ervaring moet uitwijzen hoe goed dit mogelijk is, of dat er toch vaak handmatig overrulen van constraints nodig blijft. Voor het aanpassen van arrangementen van deelnemers is onderwijskundig inzicht vereist. De knelpunten in roosters per deelnemer (veel teleurstelling) kunnen worden opgesomd en door een onderwijskundige worden beoordeeld. Die kan aangeven hoe een individueel arrangement mogelijk kan worden aangepast. Er kan

PROTOTYPE ROOSTEREN

worden gesimuleerd of dat een beter rooster geeft. In overleg met de begeleider van de deelnemer kan de aanpassing aan het arrangement vervolgens worden geëffectueerd. Arrangementen kunnen ook op grotere schaal worden aangepast. Met name kunnen zwakke afhankelijkheden tussen vakken worden overruled.

Uitwerking van de beoordeling van roosters Voor iedere constraint kan een waardering worden aangegeven: 0. voorkeur: bijvoorbeeld uitslapen op maandagochtend; 1. wens: bijvoorbeeld kinderen naar school brengen op maandagochtend; 2. sterke wens: bijvoorbeeld bijbaantje op maandagochtend; 3. eis: bijvoorbeeld ziekenhuisbezoek op maandagochtend. Hiermee kan er per constraint een getal worden aangegeven dat aangeeft hoeveel teleurstelling(spunten) niet-honoreren van de constraint geeft. De roosterengine kan van ieder type constraint en van iedere gradatie tellen hoe vaak hij niet wordt gehonoreerd door een roostervoorstel. Hiermee kan de totaalscore voor de teleurstelling van een roostervoorstel worden bepaald. Binnen de teleurstelling kan onderscheid worden gemaakt tussen verschillende belanghebbenden (docenten, deelnemers, instelling). Ook moet er een balans zijn tussen de verschillende deelnemers en docenten, en moet worden voorkomen dat het rooster volledig op deelnemers of docenten die veel eisen stemmen wordt afgestemd. De kosten van een roostervoorstel kunnen ook in kaart worden gebracht. Via weegfactoren kan worden gestuurd hoe zwaar de verschillende belanghebbenden meetellen in de uiteindelijke beoordeling.

39

40

PROTOTYPE ROOSTEREN

DEEL III: GLOBAAL TECHNISCH ONTWERP Belangrijke onderdelen van de rooster-engine Een eerste globale opzet van de rooster-engine wordt geschetst in figuur 3. Deze figuur laat zien welke gegevens de engine nodig heeft, produceert en welke componenten er kunnen worden geïntroduceerd. De centrale component in het geheel is het gebruikte data-model. Dat is de beschrijving van de data-objecten die worden onderkend. De centrale objecten in het data-model zijn: - Roosterbare eenheid of Leeractiviteit. Dit is een onderdeel uit de onderwijscatalogus van het laagste aggregatieniveau. Zo’n onderwijsproduct heeft allerlei vereisten zoals een bepaald type docent, voorkeur voor een lokaal, minimaal en maximaal aantal deelnemers, en relaties met andere produkten (startvoorwaarden). - Arrangement. Een arrangement is een lijst van onderwijsproducten die een deelnemer wil volgen. Hier kunnen items bij staan waarvoor nog niet aan de startvoorwaarden wordt voldaan. - Deelnemer. Een leerling/student van een instelling waarvoor een rooster moet worden gemaakt. Een deelnemer heeft een lijst van produkten die al zijn afgerond, een arrangement van gewenste produkten, beschikbaarheidstijden, voorkeuren, e.d. Deelnemers kunnen ook bijv. van bedrijven afkomstig zijn voor contractonderwijs. - Sessie of Event. Dit is de kleinste eenheid in een volledig rooster: een bijeenkomst van een of meer docenten, leerlingen en middelen van een bepaalde duur op een tijd en plaats (een of meer lokalen), ten behoeve van een leeractiviteit (roosterbare eenheid). - Volledig rooster. Dit is de verzameling van events voor een vooraf gekozen roosterperiode. - (Deelnemer-, docent-, middel-) Agenda. Dit is de lijst van bezigheden van een deelnemer, docent, lokaal, e.d. Naast sessies/events die bij het roosteren worden ingevuld met restricties kunnen daarin ook de beschikbaarheid (uitslapen, bijbaantjes) en andere afspraken worden ingevuld.

PROTOTYPE ROOSTEREN

Fig. 3, Mogelijke globale structuur van de rooster-engine.

Uitwerking van entiteiten in het roosterprobleem De onderwijscatalogus De precieze invulling van de onderwijscatalogus is per instelling verschillend. De manier waarop de onderwijsproducten worden beschreven, met behulp van metadata, is wel voor alle instellingen gelijk. Er blijken ook items te zijn die je wel wilt kunnen roosteren maar niet in de “echte” onderwijscatalogus zouden moeten staan. Daarom wordt er naast de “echte onderwijscatalogus” ook een “uitgebreide onderwijscatalogus” geïntroduceerd. De roosterengine werkt met het tweede object. Als voorbeelden van items uit de uitgebreide catalogus kan worden gedacht aan monitorgesprekken of aan lege ruimte van een bepaalde soort. Reistijd kan dan als een aparte activiteit worden ingevoerd en op die manier in het rooster worden verwerkt. De “uitgebreide catalogus” kan worden gebruikt als vehikel om tijdelijke aanpassingen aan leeractiviteiten te kunnen maken. Dan kunnen bijvoorbeeld volgordeconstraints, die in de echte onderwijscatalogus zijn opgegeven, in de uitgebreide catalogus worden overruled en kunnen hiermee simulaties worden uitgevoerd.

41

42

PROTOTYPE ROOSTEREN

Deelnemers, docenten en middelen Voor deelnemers, docenten en middelen geldt iets vergelijkbaars als voor de onderwijscatalogus. Het is gewenst dat er tijdens het roosteren aanpassingen kunnen worden gemaakt aan de “echte data”. - Er moeten simulaties kunnen worden uitgevoerd waarin bepaalde keuzes (constraints, voorkeuren) worden overruled; - Er moeten simulaties kunnen worden uitgevoerd waarin extra docenten of middelen worden ingezet. - Er moeten tijdens het roosteren aanpassingen kunnen worden gemaakt aan de “echte data” die niet in het roosteren worden meegenomen (inschrijven deelnemers). Een aandachtspunt is dat de “echte data” in de tijd kan variëren, door steeds nieuwe informatie vanuit deelnemers, docenten en middelen. Dit is misschien lastig te verwerken in het roosterproces. Daarvoor ligt het voor de hand om op een gegeven moment de echte data te “bevriezen”, tijdelijk geen wijzigingen toe te staan of de wijzigingen die gemaakt worden niet mee te nemen in het roosterproces. De bevroren data zijn dan de “echte data” voor het roosterproces. Van deze echte data kan dan een kopie worden gemaakt, waarbij in de kopie aanpassingen ten behoeve van simulaties kunnen worden gemaakt. Tijd

Het rooster Een rooster is een grote verzameling van sessies/events voor een bepaald onderwijsperiode. Deze verzameling kan worden gevisualiseerd als de “Deventer koek” of een driedimensionaal GRID: op ieder moment (vierkant) worden er meerdere sessies gehouden (verticale as), waarbij meerdere deelnemers, docenten, lokalen en andere middelen worden gebruikt (horizontale as). Verschillende vierkanten

Mens

(tijdstippen) volgen elkaar op. De verticale as kan ook met de locaties waar sessies worden gehouden worden Middel

geassocieerd. De roosterengine kan ook worden gebruikt voor het maken van een voorlopig rooster voor een of meer periodes vooruit. Hiermee kan aan de betrokkenen worden getoond wat de verwachtingen zijn ten aanzien van bijv. de termijn waarop vakken weer worden aangeboden, wat helpt bij het formuleren van de arrangementen. Deze voorlopige roosters dienen verder voor het in kaart brengen van knelpunten. Een verschil ten opzichte van het maken van het echte rooster voor de komende onderwijsperiode is dat de arrangementen nog niet (volledig) zijn ingevuld. Dit wordt opgelost door het (automatisch) aanvullen van arrangementen op basis van kentallen.

PROTOTYPE ROOSTEREN

Het maken van een rooster kan worden gezien als het vullen van de agenda’s van de deelnemers, docenten en middelen. Daarin is een subtiliteit dat de agenda niet alleen door het rooster wordt gevuld. Er kunnen al andere afspraken staan en nadat het rooster is ingevuld kunnen er verdere afspraken worden toegevoegd.

Tabel 1: Een impressie van de weergave van een roostervoorstel in een spreadsheet.

Tabel 2: De matrix die is verkregen door het spreadsheet uit Tabel 4.1 te coderen naar numerieke data.

Symbolische weergave van een rooster In deze sectie proberen we een begin te maken met een iets formelere beschrijving van het probleem van rooster-generatie. Het doel hiervan is om het probleem zodanig op te schrijven dat wiskundige methoden kunnen worden gebruikt om het probleem te analyseren en/of op te lossen. De eerste stap is het uitwerken van “het rooster” of een “roostervoorstel”. Dit wordt gedaan in tabel 1. Hierin is een roostervoorstel omgezet naar een tabel of spreadsheet. Elke rij van het roostervoorstel betreft een sessie (roosteronderdeel), zoals een les uit een bepaalde cursus. De eerste kolom van de tabel bevat een uniek ID, de tweede de beschrijving van het roosteronderdeel en de andere kolommen bevatten de verdere informatie betreffende de invulling van het roosteronderdeel in het roostervoorstel. De tweede stap betreft het omzetten van de informatie in het roostervoorstel (die kan bestaan uit data, namen, of allerlei andere soorten informatie), naar numerieke data (getallen dus). Hiervoor kunnen bijvoorbeeld de lokaties, docenten en deelnemers genummerd worden. Het resultaat is een spreadsheet met alleen getallen. Een dergelijk spreadsheet lijkt sterk op een matrix. Een dergelijke matrix is te zien in tabel 2.

43

44

PROTOTYPE ROOSTEREN

De letters in deze tabel zijn toegevoegd om duidelijk te maken dat de verschillende kolommen over verschillende soorten data gaan: de waarde 2 in de eerste kolom betreft het roosteronderdeel met ID 2, in de vierde kolom betreft het lokaal 2, en in de zesde kolom het tweede lesuur. Een eerste formulering van het roosterprobleem wordt verkregen wanneer we de ingevulde waardes uitgummen uit tabel 2: wijs aan iedere sessie een leeractiviteit, een lokatie, een of meer docenten, een of meer deelnemers etc. toe, zodanig dat de gevraagde leeractiviteiten worden ingepland en waarbij aan de constraints wordt voldaan. Dit probleem wordt in een meer gebruikelijke vorm gezet door alle invulvakjes onder elkaar te zetten. Hiermee wordt de onbekende een vector in plaats van dat een matrix moet worden ingevuld. De hieruit volgende representatie van het roostervoorstel van tabel 2 wordt geïllustreerd in tabel 3.

[v7, g2, k7, m4, u3, d123, s25, s123, … , v12, g7, k2, …]T

Tabel 3: De vector die is verkregen door de rijen van de matrix uit tabel 4.2 onder elkaar te zetten. Een andere formulering wordt verkregen wanneer we niet alle invulvakjes van de matrix, maar de beschikbare objecten onder elkaar zetten. Hiermee krijgen we een vector zoals geïllustreerd in tabel4.



[v1, v2, … , v100, g1, …, g5, s1, …, s20.000, … ]T

Tabel 4: De vector van toe te wijzen leeractiviteiten, lokaties, lokalen, docenten, deelnemers, etc. Met deze vector kan de matrix van tabel 2 ook worden geschreven als een veel bredere matrix met nullen en enen erin. Op de eerste rij (r1) van deze nieuwe “sparse matrix” staat een 1 in de zevende kolom (v7), de 102e kolom (g2), etc. De matrix van tabel 2 is een compacte representatie van de uitgebreide sparse 0/1 matrix.

PROTOTYPE ROOSTEREN

Het maken van lesroosters kan nu worden opgevat als het invullen van enen in een matrix, zodanig dat de gevraagde leeractiviteiten worden bereikt en waarbij aan de constraints wordt voldaan.

Symbolische weergave van de constraints De matrix die het rooster voorstelt noemen we RL. De overeenkomstige vector (tabel 3) noemen we rL.

Het lesrooster bevat alle benodigde informatie, maar niet altijd in een handige vorm. Bepaalde informatie kan eenvoudiger worden afgelezen uit andere “views”, zoals de docentenagenda’s Ad, de lokalenagenda’s Ak (k voor “kamer”) en de leerlingenagenda’s As. Deze agenda’s kunnen worden afgeleid uit het lesrooster. Dat geven we weer met de volgende formules:

(1)

Het is mogelijk om lesroosters te maken waaruit de andere roosters niet correct kunnen worden berekend. Het gaat hierbij om roosters waarin docenten, lokalen of deelnemers dubbel zijn geboekt. Dit zou moeten worden afgevangen bij het oplossen van het probleem. Voor het evalueren van de constraints is een groot aantal extra grootheden (“criteria”) vereist. Bijvoorbeeld het aantal tussenuren per deelnemer. Deze grootheden hebben betrekking op de kwaliteit van het rooster. Sommige van deze grootheden kunnen het makkelijkst worden berekend uit het lesrooster; sommige uit de docenten- of andere agenda’s. We kunnen dus spreken van les-, docenten-, lokalen- en leerlingcriteria, die worden gegroepeerd in vectoren jL, jd, jk en js. Dat deze criteria kunnen worden berekend uit de verschillende views wordt weergegeven in de volgende formules:

(2)

Het aantal tussenuren per deelnemer kan bijvoorbeeld gemakkelijk worden berekend aan de hand van de deelnemeragenda en wordt daarom (voor iedere deelnemer apart) in js gestopt. Alle afgeleide grootheden worden nu samen gegroepeerd in de vector j en is een functie van het rooster rL:

45

46

PROTOTYPE ROOSTEREN

(3)

Een algemene waarderingsscore J voor het rooster wordt berekend door de verschillende criteria op de juiste manier te combineren. Deze combinatie kan op een wiskundig eenvoudige wijze worden gedaan, bijvoorbeeld door een lineaire combinatie van de verschillende criteria te berekenen of een gewogen kwadratische norm, maar kan ook een ingewikkelde niet-lineaire berekening zijn. De berekening van de uiteindelijke waardering wordt weergegeven als het toepassen van de functie

J op de criterium-vector j:

(4)

Analyse, decompositie van het probleem Wanneer het oplossen van roosterproblemen veel rekentijd kost, dan is een goede mogelijkheid om het probleem te splitsen en over meerdere processoren of computers te verdelen. Er zijn verschillende analyses mogelijk waarmee een roosterprobleem in deelproblemen kan worden gedecomponeerd. Een voorbeeld van een wiskundige techniek is het opstellen van een afhankelijkheidsgraaf van de criterium-functie J, waarbij in kaart wordt gebracht welke onderdelen van het rooster worden gebruikt bij het berekenen van welke criteria. Een dergelijke afhankelijkheidsgraaf kan worden geanalyseerd, bijvoorbeeld om een partitionering te maken: een opdeling van het rooster in deelproblemen die zo weinig mogelijk met elkaar te maken hebben. Een gerelateerde techniek is gebaseerd op de sparse 0/1 matrix van het roosterprobleem. Per rij wordt ingevuld welke leeractiviteit er wordt bedoeld. Vervolgens worden er enen gezet bij alle objecten die van toepassing kunnen zijn. Alle deelnemers die mogelijk zijn geïnteresseerd, alle docenten die bevoegd zijn voor het vak, etc. Daarna kan de overlap tussen verschillende rijen worden bepaald. Als twee rijen overlap hebben dan kunnen ze in elkaars vaarwater terechtkomen. Zo niet dan kunnen ze volledig onafhankelijk van elkaar worden gescheduled.

PROTOTYPE ROOSTEREN

Verwachtingen en tactische planning Enerzijds is er een wens om de rooster-engine te kunnen gebruiken voor tactische planningen. Bijvoorbeeld voor het beantwoorden van welke middelen er op afzienbare tijd onderbezet of juist extra nodig zijn. Anderzijds zit er in het maken van een rooster een relatie met volgende periodes. Het is wellicht mogelijk om voor de huidige periode een beter rooster te maken wanneer alle moeilijke vragen uit arrangementen worden doorgeschoven. Dat leidt dan wel in de volgende periode tot een probleem. Bij de discussie van deze items is het volgende principe bedacht: - De rooster-engine bepaalt in iedere periode een rooster voor N blokken van Y weken vooruit. - De eerste van deze N blokken is bedoeld als het “echte” rooster. - De volgende N - 1 blokken worden “verwachtingen”. Deze kunnen voor de tactische planning worden gebruikt. - De kwaliteit van de roosters voor blokken 2 … N wordt meegenomen in de optimalisatieprocedure, zodat het overall beste rooster voor de komende periode wordt bepaald. - In de blokken 2 … N worden arrangementen van deelnemers uitgebreid met extra activiteiten, op basis van kentallen van de instelling over het te verwachten gedrag van deelnemers. - In het eerste blok worden geen aanvullingen op de arrangementen gebruikt. Dit principe sluit aan bij het roosteren als continu proces, het beeld van het GRID en de Deventer koek. Een nuance is dat er niet “oneindig” vooruit wordt gepland maar steeds een eindige horizon wordt gebruikt. Een conclusie die naar aanleiding van de uitwerking van het prototype is getrokken is dat dit mechanisme niet zou moeten worden gebruikt voor tactische planningen voor bijvoorbeeld een jaar vooruit. De meerwaarde van de rooster-engine zit in het meenemen van precieze plaatsing in de tijd: wordt een les een periode doorgeschoven of niet? En in de afwegingen die hierin worden gemaakt om andere lessen te vergemakkelijken. Op de langere termijn kunnen hier nog geen goede verwachtingen voor worden gemaakt omdat er meer onzeker is over de precieze arrangementen per deelnemer. Het mechanisme hierboven sluit niet uit dat een instelling gaat rekenen met N * Y = 52. Verder kan er op basis van onderdelen van de rooster-engine een aparte tool worden gemaakt voor ondersteuning bij het langere termijn probleem.

47

48

PROTOTYPE ROOSTEREN

Andere technische keuzes op het globale niveau - Representatie van tijd. Veel sessies zullen op vaste lesuren zijn gebaseerd (1e; 2e; 3e uur). Daarnaast zullen er sessies zijn die gescheduled worden in werkelijke tijd. Daarbij kan een basiseenheid van 15 minuten worden geïntroduceerd en tussen bijvoorbeeld 8:00 en 18:00 worden ingepland. - XML file-formaat. Bij de Universiteit van Twente wordt gewerkt aan een standaard XML file-formaat voor het beschrijven van roosterproblemen. Daarbij aansluiten is voordelig omdat het probleem dan ook met anderen kan worden uitgewisseld. Verder biedt dit formaat mogelijk aanvullende informatie over geschikte representaties voor onderdelen van het probleem.

PROTOTYPE ROOSTEREN

Deel IV: Wiskundige oplosstrategieën voor roosterproblemen

Roosterproblemen behoren tot het vakgebied van de “operations research”. Dat betreft het toepassen van wiskundige technieken en modellen om processen binnen organisaties te verbeteren of te optimaliseren. Afhankelijk van de precieze vraagstelling (lesroosters, treinroosters, crew-scheduling, ...) worden er heel verschillende technieken voor gebruikt. Technieken die ook nog weer diverse andere toepassingen hebben binnen de wiskunde en de informatica. Daarom is het lastig om een classificatie of overzicht te geven van het vakgebied. Dit deel geeft een introductie van de relevante terminologie en technologie. Vervolgens wordt een overzicht gegeven van mogelijke oplosrichtingen voor het roosterprobleem. Tenslotte beschrijft dit hoofdstuk welk onderzoek is uitgevoerd,welke keuzes zijn gemaakt en hoe het roosterprobleem zou kunnen worden opgelost.

Introductie: optimalisatie, lineair programmeren Deze paragraaf beschouwt de lineaire optimalisatieproblemen. Een prototype voorbeeld betreft een boerenbedrijf dat de vraag stelt: op welk deel van mijn land zal ik aardappelen telen en op welk deel maïs? Deze vraag kan op verschillende manieren wiskundig worden geanalyseerd. Oftewel: gemodelleerd. Een typische aanpak bestaat uit de volgende onderdelen: - keuze van de zogenaamde beslisvariabelen; - beschrijving van de beperkingen (constraints) aan deze variabelen; - berekening van de opbrengst (doelfunctie) die moet worden gemaximaliseerd. In dit voorbeeld kan een geschikte keuze voor het eerste item bestaan uit de variabelen aa en am voor het areaal (oppervlakte) aardappelen en mais. Een eerste beperking betreft de som van aa en am die kleiner of gelijk moet zijn aan het totale areaal van het bedrijf. Verder zijn aa en am allebei niet-negatief. Tenslotte kunnen er allerlei beperkingen worden toegevoegd vanuit bijvoorbeeld bewerkelijkheid, geschiktheid van het land, beschikbaarheid van kunstmest, enz. Als doelfunctie kan tenslotte worden gekozen voor verwachte opbrengsten pa en pm per areaal-eenheid voor aardappelen en voor mais. Het probleem kan dan als volgt worden uitgedrukt:

49

50

PROTOTYPE ROOSTEREN

(5)

Formulering (5) heet een lineair optimalisatieprobleem met beperkingen ofwel een lineair programma, een LP-probleem. De doelfunctie en de nevenvoorwaarden hangen lineair af van de beslisvariabelen. Dit is een prettige vorm voor optimalisatieproblemen. De beperkingen kunnen dan namelijk (in twee dimensies) allemaal als rechte lijnen worden voorgesteld en de toegestane combinaties van aa , am zijn te vinden binnen een (mogelijk open) polygoon (meer dimensies: polyhedron, veelvlak). Er bestaan standaard oplosmethoden voor LP-problemen, met name de simplex-methode en interior-point methoden. Deze zijn beschikbaar in diverse softwareprodukten, in het bijzonder in het commerciële CPLEX pakket van IBM ILOG. Een belangrijk aspect van de theorie over LP’s gaat over het duale probleem. Bij ieder (primaal) maximalisatie-probleem is er een duaal minimalisatie-probleem. Hierin zijn de rollen van doelfunctie en constraints verwisseld ten opzichte van het primale probleem. Het duale probleem bevat in zijn doelfunctie de coëfficiënten uit de constraints van het primale probleem en in zijn constraints de coëfficiënten uit de doelfunctie van het primale probleem. De oplossing van het duale probleem biedt extra informatie over het primale probleem. Ze geeft aan wat de meeropbrengst is wanneer de beperkingen van het primale probleem worden verruimd.

(6)

Het optimalisatieprobleem (5) kan gemakkelijk veel moeilijker worden gemaakt. Bijvoorbeeld door te willen meenemen dat de opbrengst p per areaaleenheid afhankelijk is van het areaal a, ten gevolge van schaal voor- en nadelen. De doelfunctie is dan niet langer lineair. De optimale combinatie van aa , am hoeft dan niet langer een hoekpunt van het polygoon te zijn en de simplex-methode verliest hiermee zijn toepasbaarheid.

PROTOTYPE ROOSTEREN

Een andere uitbreiding die het probleem moeilijker maakt is door te vragen naar geheeltallige waardes voor aa en am. Het probleem (5.1) wordt dan een integer (lineair) programma IP of ILP genoemd. ILP’s zijn een stuk lastiger op te lossen dan vergelijkbare LP’s. Een typische aanpak is om eerst het bijbehorende LP op te lossen en vervolgens extra voorwaarden toe te voegen aan dat LP om geheeltallige oplossingen af te dwingen. Bekende technieken hiervoor heten branch-and-bound (splitsen in twee sub-LP’s, bijv. aa <= n1 v aa >= n1 + 1) en branch-and-cut

(toevoegen extra constraints door integer hoekpunten).

Introductie van combinatorische problemen Een heel andere manier om roosterproblemen te benaderen is via combinatoriek. Die technologie gaat over combinaties van toewijzingen. Een voorbeeld is het sudoku-probleem. Gegeven een matrix van 9 x 9 vakjes met op verschillende plekken cijfers tussen 1 en 9 ingevuld, zoek een invulling van de cijfers 1 t/m 9 in de overige vakjes zodanig dat aan de gestelde opgave wordt voldaan. Een botte methode voor dit probleem is door alle mogelijkheden uit te proberen. Hieraan gerelateerd is de techniek van back-tracking. Hierbij worden systematisch alle invullingen die kunnen leiden tot een acceptabele oplossing uitgeprobeerd. Eerst wordt er voor een vrij vakje een toegestane keuze gemaakt, dan voor een tweede, derde, vierde vakje, etc. Als op een bepaald niveau geen oplossingen mogelijk zijn, dan wordt het laatst ingevulde cijfer weer weggehaald en wordt daar een nieuwe mogelijkheid geprobeerd. Als er op dat niveau geen mogelijkheden meer zijn dan wordt er nog een niveau hoger gegaan en wordt daar hetzelfde geprobeerd. Net zolang totdat alle mogelijkheden zijn uitgeprobeerd of dat er een complete oplossing is bepaald. Binnen back-tracking algoritmen kunnen allerlei slimmigheden worden ingebouwd. Zo is het heel ongunstig als er op een vroeg niveau een foute keuze wordt gemaakt. Daarom is de volgorde van invullen van het probleem van groot belang. Verder kan er intelligentie worden ingebouwd voor het herkennen van deelproblemen die reeds zijn onderzocht, waarvoor er geen oplossing bestaat. Het type problemen dat met deze technieken wordt onderzocht wordt “constraint satisfaction problems” genoemd, de oplostechnieken worden constraint programming methodes genoemd. Dit vakgebied heeft veel toepassingen binnen de informatica en wordt daardoor minder tot de operations research gerekend. Merk op dat er in de

51

52

PROTOTYPE ROOSTEREN

basisbeschrijving van het probleem geen doelfunctie voorkomt die wordt geoptimaliseerd. Er is geen beoordeling ingebouwd omtrent de voorkeur binnen de set van toegestane oplossingen. Hiervoor zijn uitbreidingen van de problemen en oplosmethoden vereist, waarmee het weer meer “operations research” wordt. Gerelateerd aan combinatorische problemen en het roosterprobleem is het graafkleuringsprobleem. Gegeven een graaf waarmee afhankelijkheden (verbindingen, edges) tussen verschillende items (knooppunten, nodes) wordt uitgedrukt, zoek een inkleuring van de nodes zodanig dat iedere node alleen verbonden is met nodes van andere kleuren. In het roosterprobleem kan voor iedere les een node worden gebruikt, kunnen conflicten tussen vakken via verbindingen worden aangegeven en kan vervolgens ieder toegestaan tijdstip met een kleur worden geassocieerd. Het inkleuren van nodes komt dan overeen met het toewijzen van lessen aan tijdstippen en dient zodanig te worden gedaan dat twee lessen die conflicteren (dezelfde deelnemers, docenten, e.d.) niet op hetzelfde tijdstip worden ingepland. Via deze beschouwing is ook het belang van graaftheorie voor het roosterprobleem aanschouwelijk gemaakt.

Introductie van de column generation techniek Column generation is een techniek die door deskundigen relevant wordt genoemd voor het roosterprobleem. We illustreren deze techniek aan de hand van het zogenaamde “cutting stock” probleem. Stel dat je latten van tien meter lengte hebt en dat er door afnemers om 100 latten van twee meter en 300 latten van anderhalve meter wordt gevraagd. Hoe moet je de lange latten dan verzagen zodanig dat er zo min mogelijk materiaal wordt verspild? Een eerste oplossing is om eerst alle latten van twee meter te maken (20 latten van tien meter) en dan die van anderhalve meter (50 latten). Dus met 70 latten kun je zeker toe. Maar het eindprodukt omvat 650 meter hout, dus misschien kun je met 65 latten toe. Hoe bepaal je dat? Column generation is allereerst een modelleringstechniek, een manier voor het wiskundig vangen van het probleem. Een naïeve aanpak kan zijn om voor alle latten van tien meter beslisvariabelen nl20; nl15 te introduceren voor hoeveel latten van twee en van anderhalve meter eruit worden gezaagd. Per lat l kun je dan een voorwaarde opstellen cf.:

(7)

PROTOTYPE ROOSTEREN

Verder moet gelden

(8)

Tenslotte moet er een doelfunctie worden gemaakt die telt hoeveel latten l er worden gebruikt. Deze aanpak leidt tot een groot ILP met veel beslisvariabelen en constraints. Verder heeft het ILP een ongunstige structuur. Dat komt doordat de verschillende beslisvariabelen onderling sterk uitwisselbaar zijn, er zit veel symmetrie in het probleem. Een veel betere aanpak voor beschrijving van het probleem is door vantevoren na te gaan welke combinaties er kunnen worden gemaakt: 1. (5, 0): vijf latten van twee meter, nul van anderhalve meter, samen precies tien meter; 2. (4, 1): vier van twee meter, een van anderhalve meter, een halve meter ongebruikt; 3. (3, 2) (een meter ongebruikt); 4. (2, 4) (geen rest); 5. (1, 5) (halve meter rest); 6. (0, 6) (rest een meter). Met deze combinaties kan het probleem worden gesteld in de variabelen ai die aan-

geven hoe vaak patroon i, (xi, yi) wordt gebruikt. In matrix-vector notatie:

(9) Hierin moeten de ai geheeltallig zijn, dus dit is een ILP. Dit ILP kan in principe direct aan een standaard ILP-solver worden gevoerd en is dan veel gemakkelijker te verwerken dan de naïeve vorm die hierboven is gepresenteerd. Het nieuwe ILP is gesteld in termen van kolommen van wat geschikte combinaties lijken te zijn. Dat is een zwakte van column generation als modelleringstechniek. Men moet alle mogelijke combinaties van parameterwaardes genereren om zeker te zijn dat men de optimale oplossing bereikt. Dat aantal combinaties kan voor grotere

53

54

PROTOTYPE ROOSTEREN

problemen schier oneindig zijn. Om dit te omzeilen wordt column generation ook gebruikt als oplostechniek. Dit gaat via het volgende stramien: 1. Men beschouwt eerst het LP-equivalent van (9), dus met reëelwaardige ai.

(a) Kies een of meer initiële kolommen, bijvoorbeeld (5, 0) en (0, 6);



(b) Los het LP-probleem op waarin alleen deze kolommen worden gebruikt. Dit heet het master-probleem (oplossing: a1 = 20; a6 = 50, doelfunctie f = 70);



(c) Bepaal de duale oplossing van het master-probleem. Dit zijn de schaduwprijzen die met de constraints verbonden zijn (oplossing: y1 = 1/5, y2 = 1/6, verhogen van coëficiënt 100 in (9) naar 101 verhoogt f met 1/5.);



(d) Onderzoek of er een of meer nieuwe kolommen kunnen worden toegevoegd. Deze moeten toegestane combinaties aangeven: geheeltallige waarden >= 0 en <= 10m. Verder moeten ze goed scoren (beter dan de al gevonden kolommen) met betrekking tot de schaduwprijzen y1, y2. De beste kolom die kan worden gevonden is (2, 4) (waarde 2/5 + 4/6 = 1.0666);



(e) Los het master-probleem opnieuw op met de nieuwe verzameling kolommen (oplossing: a1 = 0, a4 = 50, a6 = 16.666, f = 66.666, duale oplossing y1 = 1/6, y2 = 1/6).



(f) Onderzoek het sub-probleem, zoek een kolom die gewogen naar de schaduwprijzen meer oplevert dan de bestaande kolommen. Hierbij komt alleen (1, 5) nog in aanmerking, met dezelfde opbrengst (1.0) als de al aanwezige kolommen (4, 2) en (0, 6). Er zijn dus geen betere kolommen meer.



Opmerking: toevoegen van de kolom (1, 5) levert oplossing a1 = 0, a4 = 33.33, a5 = 33.33, a6 = 0, f = 66.666, even goed als de al gevonden oplossing.

2. Zoek met de gevonden verzameling kolommen en de reëelwaardige oplossing

als startpunt naar de optimale geheeltallige oplossing. Dat is in dit geval



a1 = 0, a4 = 50, a6 = 17, f = 67.

In deze beschrijving is te zien dat er een splitsing wordt gemaakt in een masterprobleem en een sub-probleem. Het sub-probleem (orakel ) levert toegestane deeloplossingen aan. Het wordt daarbij gestuurd door de schaduwprijzen uit het master-probleem. Het orakel mag gebruik maken van iedere willekeurige techniek,

PROTOTYPE ROOSTEREN

met name van bijvoorbeeld een backtracking aanpak. Het master-probleem wordt vervolgens met een LP-solver opgelost.

Introductie van local search methoden Local search is de benaming van een oplosstrategie voor optimalisatieproblemen die werkt met kandidaatroosters en met kleine aanpassingen daaraan. In de local search aanpak wordt uitgegaan van een doelfunctie die moet worden geoptimaliseerd. Er wordt een notie van “buren” gebruikt. Twee kandidaatroosters zijn buren van elkaar als ze via een elementaire transformatie in elkaar overgaan. Elementaire operaties kunnen zijn het toevoegen van een sessie aan een rooster, verwijderen van een sessie, verwisselen van twee sessies, etc. Binnen local search kunnen verschillende meta-heuristieken worden gebruikt. Bijvoorbeeld kan er een tijd lang alleen worden gezocht naar aanpassingen die een betere beoordeling opleveren. Dit wordt “hill climbing” genoemd en leidt naar een lokaal optimum. Daarna kan er worden geprobeerd of er via een omweg uit het lokale optimum kan worden ontsnapt. Bijvoorbeeld door aanpassingen toe te staan die de beoordeling niet meer dan een instelbaar percentage verslechteren. Een andere manier om uit lokale optima te ontsnappen is via “simulated annealing”. Hierbij wordt bij aanpassingen die een verslechtering betekenen met een dobbelsteen gegooid om te bepalen of ze toch worden geaccepteerd.

Beoordeling/inschatting van de oplosrichtingen Het roosterprobleem kan het beste worden beschouwd als een optimalisatieprobleem met een sterke combinatorische kant. Als alle beoogde vakken voor alle deelnemers passen op de beschikbare middelen dan zijn er waarschijnlijk te veel middelen en kan hierin bedrijfsmatig worden geoptimaliseerd. Het roosterprobleem is dus geen puur constraint satisfaction probleem, er moet een doelfunctie worden gebruikt om te kiezen tussen verschillende toegestane (incomplete) oplossingen. Aan de andere kant is het roosterprobleem ook geen standaard optimalisatieprobleem. Er gelden veel voorwaarden met betrekking tot ongelijktijdigheid waaraan perse moet worden voldaan. Dit introduceert een graaf-theoretisch gedeelte of combinatorische kant in het probleem. Deze moet in de oplosmethode worden benut om snel te komen tot een goede toegestane oplossing. Het probleem wordt beschouwd als de optimalisatie van een doelfunctie: “minimaliseren van de teleurstelling”. Er kan daarbij onderscheid worden gemaakt tussen

55

56

PROTOTYPE ROOSTEREN

harde en zachte constraints. Harde constraints gaan over dingen die niet kunnen bestaan, bijvoorbeeld een voorstel waarin een docent op twee plekken tegelijk moet zijn, of een powerpoint presentatie geven zonder computer. Zachte constraints leiden niet tot inconsistenties maar leiden tot teleurstelling. Bijvoorbeeld een deelnemer waarvoor te veel of te weinig uren zijn ingepland, tussenuren, lessen die een deelnemer wel wil maar niet kan volgen, etc. Andere teleurstelling kan gaan over voorkeuren van docenten die niet worden gehonoreerd, te weinig uren in verhouding tot de jaartaak, inefficiënt gebruik van middelen etc. Via gesprekken met deskundigen (van de TU Eindhoven, Universiteit Utrecht en TU Delft), literatuurstudie, het raadplegen van bronnen op internet en bestudering van open source programmatuur is een overzicht gevormd van de beschikbare technieken voor het roosterprobleem. Hieruit zijn de volgende vier oplosrichtingen gedestilleerd: 1. “botte” recht-toe-recht-aan heuristieken, weinig systematisch, daarentegen juist sterk probleemspecifiek. 2. constraint programming, zoeken van invullingen van het rooster waarbij aan alle (harde) constraints wordt voldaan, dus zonder beoordeling/weging van UniTime/CourseTT is een open

(zachte) constraints waar niet aan wordt voldaan. Hiertoe behoort ook back-

source pakket ontwikkeld door

tracking (systematisch aflopen van mogelijke oplossingen). Deze oplosrichting is

Tomáš Müller. Hij heeft van 2001

vooral van belang voor het maken van een initiëel rooster dat met de volgende

tot 2005 promotieonderzoek

richting kan worden verfijnd.

gedaan aan de technische universiteit van Praag naar constraint

3. local search methoden, waarbij een initiëel rooster steeds met kleine wijzigingen

programming, in een onderzoek

en verwisselingen wordt aangepast. Hierbij horen ook “hill climbing” (systema-

voor Purdue universiteit in de VS.

tisch verbeteren) en “simulated annealing” (introduceren van willekeur om uit

Aansluitend heeft hij drie jaar aan

lokale optima te kunnen ontsnappen).

de Purdue universiteit gewerkt aan het verder uitbreiden van deze pro-

4. column generation technieken, waarbij allerlei mogelijke deeloplossingen

grammatuur ten behoeve van het

(“columns”) worden gegenereerd en via standaard “ILP technieken” de beste

roosteren voor 39.000 studenten,

combinatie van deeloplossingen wordt bepaald. ILP staat voor geheeltallig

9.000 vakken en 570 lokalen.

programmeren; binnen het oplossen van ILP’s moeten lineaire programma’s (LP’s) worden opgelost. Hiervoor moet een commerciële bibliotheek worden gebruikt omdat deze ordes (1000 x) sneller is dan open source software. Een belangrijke vraag is op welke van deze richtingen men zou moeten inzetten. Tijdens dit onderzoek is daar een mening over gevormd. Daarbij gaat de keuze vooral tussen een combinatie van 2 en 3 (constraint programming plus local search) enerzijds en 4 (column generation) anderzijds. Voor de evaluatie van local search

PROTOTYPE ROOSTEREN

(2, 3) is gestart met het ontwikkelen van een eigen prototype. Later is dit werk stilgelegd en is overgegaan tot het evalueren van het open source pakket UniTime/ CourseTT (zie kader). Voor de evaluatie van column generation (4) is meerdere keren met gesproken met deskundigen en zijn verschillende artikelen bestudeerd. De column generation techniek bestaat uit twee delen: 1. het sub-probleem, het maken van veel geschikte deeloplossingen, bijvoorbeeld meerdere mogelijke invullingen per lesuur, en 2. het master-probleem, een optimalisatie-routine voor het zo goed mogelijk combineren van de deeloplossingen. De techniek werkt vooral goed als alle lastige onderdelen van het totale probleem, constraints waarin verschillende entiteiten worden gecombineerd, in het subgedeelte kunnen worden gestopt. Bij het roosterprobleem is dit niet (zeker) het geval. Met name wanneer je de deeloplossingen verbindt met lesuren (”allerlei mogelijke invullingen voor het 1e uur op maandag”, ”invullingen 2e uur”, etc.), dan blijven er nog veel restricties over in het master-gedeelte: restricties aan de volgorde van lessen, lessen die elkaar niet direct mogen opvolgen vanwege reistijd, lastig te tellen tussenuren, e.d. Om column generation beter te kunnen toepassen voor het lesroosterprobleem zal er naar een opdeling in deelproblemen moeten worden gezocht die minder lastige constraints over laat voor het master-probleem. Dit kan misschien door deeloplossingen te gaan zoeken voor afdelingen, jaarniveaus, lokaties, etc. Tijdens het onderzoek is geconcludeerd dat column generation een interessante techniek is, maar dat het op dit moment niet de meest wenselijk richting is. Het is met name zo interessant omdat de techniek heel systematisch werkt en gericht naar de optimale oplossing toewerkt. Het geeft daarbij onderweg informatie over de voortgang, via schattingen van de hoeveelheid teleurstelling die in de optimale oplossing overblijft. Anderzijds zijn meerdere restricties van het roosterprobleem slecht te verwerken in een eenvoudige uitwerking van column generation voor het roosterprobleem. Het is volgens deskundigen niet zeker of er een andere uitwerking van column generation kan worden bedacht waarin alle restricties goed kunnen worden ingebracht. Al met al vergt de column generation techniek het nodige onderzoek en is een goede uitkomst niet gegarandeerd. Deze conclusie over constraint programming plus local search is vooral gebaseerd op de ervaringen met de UniTime/CourseTT programmatuur van Tomáš Müller. Deze programmatuur was winnaar in twee categorieën van de international timetabling contest in 2007 en finalist in de derde categorie. Tomáš heeft van 2001 tot 2005

57

58

PROTOTYPE ROOSTEREN

PhD-onderzoek gedaan aan de technische universiteit van Praag naar constraint programming, in een onderzoek voor Purdue universiteit in de VS. Aansluitend heeft hij drie jaar aan de Purdue universiteit gewerkt aan het verder uitbreiden van deze programmatuur. De programmatuur is in 2007 open source gemaakt. Naast de software van Müller zijn artikelen van andere groepen bekeken om inzicht te krijgen in de gekozen aanpak van het roosterprobleem. De ervaringen met UniTime/CourseTT zijn positief. Het is netjes opgezet, zit slim in elkaar en de gebruikte methoden zijn uitgebreid gedocumenteerd. CourseTT gebruikt generieke principes die “Iteractive Forward Search” en “Conflict Based Statistics” worden genoemd. Die principes zijn heel flexibel en kunnen voor allerlei verschillende situaties geschikt worden gemaakt. De programmatuur laat verder zien dat er met deze aanpak grote roosterproblemen kunnen worden opgelost (Purdue: 39.000 studenten, 9.000 vakken, 570 lokalen). De aanpak is wel meer ad-hoc van aard dan met name de column generation methodiek: men moet zelf bedenken in welke volgorde de solver keuzes moet evalueren en dit is tot op zekere hoogte probleem-specifiek. De local search methodiek is daarom uiteindelijk misschien minder krachtig dan de column generation methodiek, maar het geeft een stuk meer zekerheid dat de techniek goed (genoeg) gaat werken als men er voldoende tijd en energie in stopt.

Evaluatie van de UniTime/CourseTT programmatuur Het pakket UniTime bestaat uit twee aparte delen: een user-interface gedeelte dat ook UniTime wordt genoemd en een solver-pakket CourseTT. Het user-interface gedeelte biedt een uitgebreide faciliteit aan de Purdue universiteit om allerlei aspecten van het roosterprobleem in te voeren: gegevens van lessen, lokalen, voorkeuren van deelnemers etc. Dit gaat via web-services en de gegevens worden vervolgens opgeslagen in een database. Het pakket CourseTT (course time-tabling, lesroosteren) staat in principe los van het overkoepelende UniTime-systeem. Dit onderdeel is geschreven in Java en omvat circa 40.000 regels code. De gebruikte algoritmes zijn uitvoerig gedocumenteerd via publicaties en via de programmatuur (www.unitime.org/api/cpsolver-1.1/ index.html). Dit gedeelte van de programmatuur wordt aangestuurd via een invoerfile in XML formaat. Het Wellant College te Gorinchem heeft gegevens (Excel-sheets) toegeleverd ten behoeve van dit onderzoek. Via een hulpprogramma zijn deze gegevens omgezet naar invoer voor de CourseTT programmatuur. Dit heeft de nodige moeite gekost omdat de toegeleverde data niet overal compleet en consistent waren. Vakken die altijd geroosterd worden kwamen niet in keuzelijsten voor, namen van deelnemers

PROTOTYPE ROOSTEREN

worden soms verschillend afgekort, e.d. Met behulp van de data van het Wellant College is uitgeprobeerd wat de CourseTT software wel en niet kan en is het beeld aangevuld over hoe deze software werkt. Hieronder zijn de de belangrijkste beperkingen van CourseTT voor het Triple A-roosterprobleem opgesomd: 1. De CourseTT software was bedoeld voor een zich wekelijks herhalend rooster en was daarom niet voorbereid op een te roosteren periode van meer dan tien dagen. Door een kleine aanpassing te maken in de software is deze periode opgerekt. Het is echter niet duidelijk of dit later mogelijk problemen met betrekking tot de performance geeft. 2. CourseTT ging ervan uit dat alle vakken die in de invoerfile worden opgegeven ook daadwerkelijk geroosterd moeten worden, dus dat er een complete oplossing bestaat. Hij zocht eerst naar zo’n complete oplossing en begon pas daarna met verfijnen daarvan. Als er geen complete oplossing gevonden werd dan werd het zoekproces afgebroken met de melding van wat er wel past.

Hiervoor is een oplossing gevonden door een eenvoudige beschrijving te maken van de “reward” voor iedere sessie die wordt ingepland (op basis van het aantal deelnemer-minuten). Vervolgens wordt gelijk vanaf het begin naar de totale reward geoptimaliseerd.

3. CourseTT is oorspronkelijk bedoeld voor verwachte student-wensen in plaats van echte student-wensen. Het is al wel gericht op individuele leervragen, maar levert niet alle benodigde functionaliteit. Een praktische beperking was dat er nog geen voorkeuren van studenten konden worden ingevoerd, bijvoorbeeld hoe sterk een vak wordt gewenst, wanneer de student afwezig is e.d. Een meer

inhoudelijke beperking is dat de wensen niet zwaar meetellen in het zoekproces. Met name wordt er tijdens het zoeken niet gekeken of het introduceren van een extra (parallel-)sessie voor een vak of het herverdelen van studenten over parallel-



sessies meer tevredenheid bij de studenten geeft.



Ook hiervoor is een oplossing gevonden door in de arrangementen van deelnemers een “reward” toe te voegen, net als de minimum en maximum gewenste inplanning van de deelnemer. De berekening is vervolgens in twee fases gesplitst: eerst een maximale inplanning, waarbij alle wensen van alle deelnemers worden nagestreefd en conflicten niet hard worden geteld, en vervolgens het toewijzen of schrappen, waarbij deelnemers over sessies worden verdeeld en het aantal ingeplande sessies wordt geminimaliseerd.

59

60

PROTOTYPE ROOSTEREN

Daarnaast zijn er ook meerdere kleinere of meer praktische beperkingen die waarschijnlijk redelijk gemakkelijk kunnen worden opgelost: - Alle opeenvolgende sessies voor een vak worden op hetzelfde tijdstip van de dag en in hetzelfde lokaal gescheduled, wat met name voor langere reeksen misschien onhandig is. - De manier van invoeren van toegestane tijdstippen voor sessies is omslachtig, met name wanneer langere te roosteren periodes mogelijk worden gemaakt. - Er wordt nog niet veel aandacht besteed aan de docenten. Met name kan niet worden opgegeven hoe veel uur docenten beschikbaar zijn en wordt voldoen aan hun jaartaak niet meegenomen in de beoordeling. - Op dit moment wordt de docent per sessie niet geoptimaliseerd, maar moet in de invoerfile worden opgegeven welke docent/docenten welke sessie begeleidt/ begeleiden. Aan de andere kant kan de software ook al veel wel: - lokalen met verschillende eigenschappen en geschiktheid voor verschillende vakken; - parallelsessies, meerdere sessies van hetzelfde vak voor verschillende groepen van deelnemers; - vrije dagen en voorkeuren van docenten; - lessen van verschillende groottes, variërend van een kwartier tot meerdere weken fulltime; - speciale lessen die meerdere lokalen en/of docenten tegelijk nodig hebben; - relaties tussen lessen, zoals een theorie- en een praktijkles; - omvangrijke roosterproblemen, zoals voor de Purdue universiteit. Een vergelijkbaar beeld geldt voor de rapportage over de geproduceerde lesroosters. CourseTT levert al een goede beoordeling op een aantal punten, maar niet op alle punten die voor Triple A nodig zijn. Via een stuk post-processingprogrammatuur is hiervoor een aanvulling in gemaakt. Het bedrijfsmatige gedeelte hiervan (kosten van een rooster) wordt nog niet meegenomen. Hier is dus ook nog het nodige werk te doen.

Voorgestelde aanpak voor het roosteren Op basis van de ervaringen met de CourseTT programmatuur lijkt de volgende aanpak geschikt voor het roosterprobleem. - De CourseTT programmatuur is een goed uitgangspunt. Als het gebruik van de programmatuur voor een leverancier minder wenselijk is, bijvoorbeeld vanwege het open source zijn of de keuze voor Java, dan nog zou van de methode van CourseTT moeten/kunnen worden uitgegaan.

PROTOTYPE ROOSTEREN

- Aan de invoerkant moet een module worden gemaakt die uit de arrangementen van deelnemers een lijst van gewenste sessies samenstelt. Hierbij moet er per vak bepaald worden hoeveel parallelsessies er maximaal zijn toegestaan. - De methode van CourseTT moet worden uitgebreid om niet alle gewenste sessies te willen inroosteren. Met name moeten hierin ook de kosten van parallelsessies worden meegewogen. - De methode van CourseTT kan worden uitgebreid om deelnemers te kunnen herverdelen over de ingeroosterde sessies, gedurende het zoekproces. - De performance van de nieuwe versie van CourseTT moet voor een groter testprobleem worden onderzocht. Als er te veel rekentijd nodig is dan kan het probleem goed over meerdere computers worden verdeeld. Hiervoor zijn standaard partitioneringsalgoritmen en pakketten beschikbaar. - De jaartaak van docenten kan worden meegenomen in de beoordeling van kandidaatroosters via een target inplanning per periode en teleurstelling als daar (te) veel van afgeweken wordt. - Het principe van “N blokken vooruit” (zoals in deel III beschreven bij Verwachtingen en tactische planning) kan waarschijnlijk via een gelaagde aanpak worden gerealiseerd. Hierbij bepaalt een aparte module welke sessies in welke periode zal moeten worden ingepland en wordt CourseTT steeds voor een enkele periode gebruikt. - De praktische beperkingen van CourseTT kunnen één voor één worden opgelost.

61

62

PROTOTYPE ROOSTEREN

Deel V: Conclusies en aanbevelingen

In het functioneel ontwerp onderwijslogistiek, roosteren en beheren middelen is onder andere de gewenste functionaliteit van een roostermachine uitgewerkt. De beschreven functionaliteit voor het roosteren gaat daarbij uit van individuele leervragen van deelnemers en het gebruik van een onderwijscatalogus. Deze manier van roosteren is aanzienlijk complexer dan wat nu de praktijk is binnen de instellingen, maar is wel een belangrijke voorwaarde om meer flexibel, op het individu gericht onderwijs mogelijk te maken. Om die reden is besloten tot de realisatie van een prototype roosteren, om zo zicht te krijgen op de haalbaarheid van deze roostermachine. Vanaf november 2008 is VORtech hierbij betrokken en wordt er samengewerkt aan het in kaart brengen van het roosterprobleem en het realiseren van een werkend prototype.

Aanpak en conclusies van VORtech In de periode december 2008 - januari 2009 heeft VORtech een voorstudie uitgevoerd naar het roosterprobleem. Hierin is de problematiek in kaart gebracht. Er is een beschrijving gemaakt van wat de beoogde rooster-engine zou moeten doen: requirementsanalyse en functioneel ontwerp. Dit is beschreven in de delen I en II. Van februari t/m mei 2009 is er een vervolgonderzoek uitgevoerd. Hierin is met name onderzocht hoe het roosterprobleem kan worden opgelost (technisch ontwerp, wiskundige oplostechnieken, delen III en IV). Van juli 2009 t/m januari 2010 is er gewerkt aan het samenstellen van een geschikte data-set voor het roosterprobleem en is de geschiktheid en uitbreidbaarheid van CourseTT onderzocht (deel IV). Oplossingsrichtingen In dit vervolgonderzoek zijn twee relevante oplosrichtingen gevonden: enerzijds de “column generation” techniek, anderzijds “constraint programming plus local search”. Via gesprekken met deskundigen, het bestuderen van wetenschappelijke publicaties en experimenteren met open source programmatuur zijn de sterktes en zwaktes van deze richtingen bepaald. Op basis hiervan is het de inschatting dat column generation in potentie een heel krachtige techniek is, maar dat niet kan worden gegarandeerd dat deze gaat werken voor het gedefinieerde roosterprobleem. Het alternatief, kortweg local search genaamd, is meer heuristisch (informeel, speculatief) en minder systematisch van aard. Het is daarentegen een beproefde, flexibele en uitbreidbare methode voor roosterproblemen. Het is daarom onze inschatting dat op deze richting moeten worden ingezet. Dit is verder gemotiveerd bij de “Beoordeling/inschatting van de oplossingsrichtingen” in deel IV.

PROTOTYPE ROOSTEREN

Evaluatie van het product UniTime/CourseTT Voor de evaluatie van (de potentie van) de local search strategie is geëxperimenteerd met de UniTime/CourseTT programmatuur van Tomáš Müller en hierover met hem gecorrespondeerd. Deze programmatuur kwam goed uit de bus bij een internationale competitie en ziet er goed verzorgd en gedocumenteerd uit. Via deze programmatuur is meer inzicht verkregen in de ins en outs van de local search aanpak dan via het maken van een eigen prototype. De ervaringen met deze programmatuur voor de testcase van het Wellant College in Gorinchem is beschreven bij de “Evaluatie van de UniTime/CourseTT programmatuur” in deel IV. Op basis van de ervaringen met de CourseTT programmatuur en het goede contact hierover met Müller wordt ingeschat dat (de methode van) CourseTT kan worden uitgebreid tot een complete rooster-engine voor het roosterprobleem. Wel is duidelijk geworden dat hiervoor nog een flinke inspanning vereist is. Enerzijds moet de methode wezenlijk worden aangepast. De grootste knelpunten in het huidige programma zijn dat de doelfunctie gedeeltelijk impliciet in het algoritme is verwerkt en dat het algoritme nog verder moet worden aangepast naar het Triple-A-probleem. Verder moeten er nog de nodige praktische aspecten worden geïmplementeerd. Zo kunnen op dit moment nog onvoldoende voorkeuren van docenten en deelnemers worden gespecificeerd, worden nog niet voldoende wensen en constraints meegenomen in de beoordeling en rapportage en moet bepaalde informatie op een omslachtige manier worden opgeschreven in CourseTT’s invoerfile. De benodigde inspanning om te komen tot een complete rooster-engine is sterk afhankelijk van de afbakening van dit werk. Naast het roosteren zelf moet er worden gewerkt aan het verzorgen van de in- en uitvoer, de aansluiting van de engine op bestaande databases en/of andere data-bronnen. Hier kan een meer of minder groot user-interface gedeelte omheen worden gemaakt. Een ander aspect van afbakening is hoe compleet de engine zelf wordt uitgewerkt, met als uitersten enerzijds recht-toe-recht-aan implementeren van een van tevoren vastgelegde strategie en anderzijds net zo lang verfijnen daarvan totdat de engine in alle gevallen goed werkt. In het laatste geval moet er het nodige onderzoekswerk worden uitgevoerd.

63

Colofon Triple A, Eerste druk 2010 Tekst en tekstredactie: Triple A, Woerden Fotografie: Beeldsmaak Amersfoort, istockphoto.com Vormgeving en opmaak: Linda van Drie, Amersfoort Druk: ADdruk Zeist Op het gebruik van dit materiaal is een Creative Commons Licentie van toepassing. Ga naar http://creativecommons.org/licenses/by/3.0/nl/ om deze licentie te bekijken.

Triple A ontwerp & onderzoek

Houttuinlaan 6

3447 GM Woerden

Tel: 0348 - 753 500

www.tripleaonderwijs.nl