Author:

Keywords:

itec

Abstract:

In deze doctoraatsthesis worden verscheidene reële timetablingproblemen uit het onderwijs- en gezondheidszorgdomein beschreven, gemodelleerd en opgelost. Timetablingproblemen worden gekarakteriseerd door schaarse en/of dure middelen die moeten toegewezen worden aan een tijdstip e n plaats, daarbij rekening houdend met allerlei beperkingen. In de m eeste timetablingproblemen is de tijd onderverdeeld in discrete t 07;dssloten. Typerend voor deze middelen is dat ze bijvoorbeel d niet gedeeld kunnen worden in hetzelfde tijdsslot. De nodige voorz orgen zullen dan ook moeten genomen worden om te vermijden dat een m iddel meer dan eenmaal toegewezen wordt aan een tijdsslot. Voorbeeld en van timetablingproblemen zijn het automatisch opstellen van uur- en examenroosters of personeelsplanning. In het eerste geval zijn de middelen docenten, studenten, en lokalen en de doelstelling is om lesse n of vakken toe te wijzen aan lokalen en tijdssloten, rekening h oudend met het feit dat bijvoorbeeld geen enkele student meer dan ee n vak kan volgen of meer dan een examen kan afleggen in hetzelfde tijdsslot. In het laatste geval wordt personeel toegewezen aan t 7;dssloten rekening houdend met wettelijke regels en persoonlijk e voorkeuren. Een heel bekend voorbeeld is verpleegsterplanning waarin v erpleegkundigen toegewezen worden aan shifts zodat aan de gewenste bezet ting per shift en eveneens aan de persoonlijke wensen en wettelij ;ke regels voldaan is. De reële timetablingproblemen die we in deze scriptie behandelen komen u it het domein van de gezondheidszorg en het onderwijs. Enerzijds zijn reële problemen door hun specifieke beperkingen een wete nschappelijke uitdaging om op te lossen. Timetablingproblemen uit he t onderwijs en de gezondheidszorg werden anderzijds gekozen daar deze sectoren alsmaar meer onder druk staan om hun kosten te drukken, e n daardoor ook gedwongen worden hun beschikbare middelen efficiënte r te gebruiken. Deze sectoren hebben met andere woorden veel baat bij ; een geautomatiseerde oplossing voor hun problemen. Enerzijds komen er middelen vrij die zich niet meer moeten bezighouden met het manu eel opstellen van roosters en anderzijds kan er verwacht worden dat deze automatisch gegenereerde oplossing van een betere kwaliteit zal z&# 307;n dan de manueel opgestelde. Reële problemen blijken door hun gr ootte en ongewone beperkingen heel moeilijk optimaal op te lossen. E chter, in de realiteit wilt men niet altijd de meest optimale oploss ing, maar een voldoende goede oplossing die binnen een redelijke rek entijd gevonden kan worden. Dit zijn de ideale omstandigheden om heuristieken toe te passen. Exacte methodes garanderen dat als een ‘fea sible’ (uitvoerbare) oplossing bestaat, dat deze zeker optimaal is; heur istieken, daarentegen, garanderen dit niet. Anderzijds, kan het vind en van een optimale oplossing met een exacte methode heel lang duren, te rwijl een heuristische methode een oplossing kan vinden in een redel ijke rekentijd. De kunst is nu om deze heuristieken zodanig te c onstrueren dat het resultaat van het zoekproces goed genoeg is om een ui tvoerbare oplossing te bekomen. Natuurlijk, de verwachting is dat he t resultaat van het zoekproces zodanig goed van kwaliteit is dat een men selijke planner de gevonden oplossing onmogelijk kan verbeteren. Dit is enkel mogelijk op voorwaarde dat alle beperkingen waarmee de menselijke planner rekening houdt gekend zijn bij de softwa re-ontwikkelaar. De bedoeling van deze thesis is dan ook om in zo’n korte mogelijke o ntwikkelingstijd verscheidene reële timetablingproblemen op te losse n. Alle in deze thesis behandelde problemen worden op een zelfde manier aangepakt. Initieel wordt in deze procedure een domeinmodel opgesteld da t de basisconcepten van het bewuste probleem beschrijft. Daarna word en de verschillende onderdelen van de heuristieken ontwikkeld. Essentiël e onderdelen zijn onder andere de voorstelling van de zoekruimte en de omgevingen. Een omgeving is de verzameling van oplossingen die kan be reikt worden vanuit de huidige oplossing door het uitvoeren van een zet. De keuze van zowel de voorstelling van de zoekruimte als de omgevingen hebben een grote invloed op de performantie van het zoekalgoritme. In het eerste gedeelte van deze scriptie behandelen we reële timetabling problemen uit het onderwijsdomein. We lossen achtereenvolgens een cu rriculumgebaseerd uurroosterprobleem aan de KaHo Sint-Lieven, een post-e nrolment gebaseerd uurroosterprobleem aan de K.U. Leuven en een examenro osterprobleem eveneens aan de KaHo Sint-Lieven op. De drie problemen wor den respectievelijk opgelost met een token-ring tabu search, een hyb riede guided local search en hyperheuristiek algoritme. Voor het examenr oosterprobleem vinden we een oplossing waarbij er minder tijdssl oten nodig zijn dan die van de menselijke planner. Het tweede de el van de scriptie behandelt twee reële problemen uit de gezondheidszorg : enerzijds een verpleegstersplanningsprobleem en het probleem van h et automatisch toekennen van patiënten aan bedden. Het eerste probleem w ordt oplost met een tabu search algoritme, terwijl het laatste probl eem opgelost wordt met zowel een token-ring tabu search als een hyperheu ristiek algoritme. Wat betreft het laatste probleem presteert de algemen e hyperheuristiek beter dan het tabu search algoritme.