Schoolrooster maken

[reddevil001]

Stel dat ik software wil maken waarin een rooster samengesteld wordt. Er zijn dan een hoop variabelen waar je rekening mee moet houden. Wanneer werken de medewerkers, wanneer zijn de klassen beschikbaar, wat voor soort lokaal is nodig, hoe lang zijn de lessen, etc. etc.

Hoe kan je zorgen dat je een rooster maakt dat zo goed mogelijk past bij die wensen?
Daar hebben vast mensen over nagedacht en/of daar is vast een wiskundig algoritme voor.

Dit probleem is volgens mij vergelijkbaar met het plannen van een reis (NS/OV9292/TomTom) en er zijn vast vergelijkbare situaties waarbij met veel variabelen toch een optimaal resultaat geboekt moet worden.

[NMe]

Hier een topic openen is vast niet het eerste wat je doet. Er is over dit soort problematiek zó veel geschreven...wat had je zelf al gevonden en wat is daar niet duidelijk aan?

[Termi]

Volgens mij zijn er standaardpakketten die rekening houden met diverse variabele en het optimale rooster berekenen.

[reddevil001]

Ik heb inderdaad een hoop gegoogled en nee ik ben niet geinteresseerd in een roosterpakket. Ik wil alleen weten hoe je een dergelijke selectie maakt.

Mogelijk dat ik niet op het goed zoek, maar dan weet ik gewoon niet met welke terminologie ik wel moet zoeken. Ik ben reeds tegen vele medische artikelen aangelopen. Veel wiskundige modellen gevonden voor specifieke doeleinden waarvan ik niet het gevoel hebt dat ze aansluiten bij een dergelijk probleem.

[Raynman]

Als er een opensource pakket (of iets met een niet al te oppervlakkige) beschrijving te vinden is, kun je dat natuurlijk wel als studieobject gebruiken, of in elk geval wat terminologie ontdekken om aan google te voeren.

Algemeen: combinatorische optimalisering. Aantal relevante technieken (wat ik zo uit mijn hoofd weet, verder zoeken mag je zelf doen): lineair programmeren (LP), lokaal zoeken. Maar als je gewoon op scheduling/timetabling zoekt, moet dat ook vanzelf naar voren komen.

[reddevil001]

Raynman schreef op maandag 16 juli 2012 @ 20:44:
Algemeen: combinatorische optimalisering. Aantal relevante technieken (wat ik zo uit mijn hoofd weet, verder zoeken mag je zelf doen): lineair programmeren (LP), lokaal zoeken.

Bedankt ik denk dat ik hier voorlopig wel weer mee verder kan. Ik ga zoeken naar bruikbare methodes. Ik kwam toevallig het Knapzak probleem tegen en ik zag dat ik daar al eens naar gekeken had.

[pedorus]

reddevil001 schreef op maandag 16 juli 2012 @ 17:03:
Dit probleem is volgens mij vergelijkbaar met het plannen van een reis (NS/OV9292/TomTom)

Nee, het plannen van een reis ligt over het algemeen in P, het roosterprobleem ligt over het algemeen in NP en is dan ook veel lastiger. (Even uitgegaan van P!=NP.)

[boreus]

Voor mijn BSc eindproject heb ik een tijd (ca. 5 of 6 jaar) geleden een tabu search algoritme geimplementeerd. Dat is een local search variant. Het had best aardige resultaten, maar de code heb ik (zelf) niet (meer). Een simpele(re) local search variant is wellicht relatief eenvoudig te implementeren. Daarna kan je altijd kijken of je nog meer aan je algoritme wilt sleutelen of dat je resultaten al goed genoeg zijn.