Algoritme personen inplannen

[wouterwouter2]

Voor een applicatie wil ik personen zo efficient mogelijk inplannen. Als voorbeeld:

Mogelijke dagen: donderdag en vrijdag

Persoon A: beschikbaar, beide dagen
Persoon B: beschikbaar, donderdag middag
Persoon C: beschikbaar: donderdag middag, van 3 uur tot 4 uur.

Algoritme plant dus eerst persoon C, dan B en dan A. Simpel voorbeelt, maar met 12 personen een stuk lastiger.

Helaas kan ik geen info vinden om dit aan te pakken.

Ik heb op verschillende keywords gezocht, maar de meeste resultaten gaan over het plannen van een meeting: welke tijd schikt het beste voor zoveel personen.
En zoeken op sequence of achterelkaar brengt mij alleen bij project planning tools.

Hoe heet deze manier van plannen? En welke zoekterm heb ik nodig om hier meer over te vinden?

[EfBe]

Het probleem heet 'Nurse Scheduling' en is NP-hard (Wikipedia: Nurse scheduling problem). Zoek bij google scholar op nurse scheduling en je komt veel papers tegen. Het is niet oplosbaar (np-hard) en dus hoef je je niet druk te maken of je een efficiente, in polynomiale tijd executerende oplossing zult vinden, die is er nl. niet.

Wellicht is het simpeler in jouw geval omdat je weinig constraints hebt, maar verkijk je er niet op. Ookal plan jij geen verplegers/verpleegsters in, het probleem is hetzelfde.

offtopic:
In het regeeraccoord van het huidige kabinet maken ze overigens de klassieke fout door geen weet van dit probleem te hebben, waarbij ze stellen dat roosters (zelfde probleem) aan bepaalde regels moeten worden onderworpen, maar die regels zijn zo strict, dat het niet mogelijk is het op te lossen, (dus wat er in het accoord staat kan helemaal niet ). Dit probleem lijkt zo simpel dat voor een onwetende het triviaal lijkt om het efficient op te lossen, maar de wetenschap heeft aangetoond dat dit een foute aanname is.

[ Voor 38% gewijzigd door EfBe op 19-12-2010 12:48 ]

[Soultaker]

Ik zou niet zo snel tot die conclusie komen terwijl allerlei details onbekend zijn. De beschrijving op wikipedia is dermate vaag dat het geen zinnige probleembeschrijving te noemen is en claims als "appears to be NP-hard" zijn volledig ononderbouwd.

De vraag is nu dus vooral hoe het probleem van de TS eruit ziet. Op basis van het voorbeeld zou ik zeggen: rooster persoon A in, en ontsla de rest. Maar dat is vast niet de bedoeling. Er zijn dus beperkingen die niet expliciet genoemd zijn (één persoon mag maximaal x uur werken bijvoorbeeld?); welke beperkingen zijn dat precies?

[Verwijderd]

Of het probleem nou NP-hard is of niet, ik zou geen aandacht besteden aan een exacte oplossing als het ernaar uitziet dat die inefficiënt zal zijn. Roostermaken blijft lastig om het exact te doen, zelfs al heb je duidelijke constraints.

Natuurlijk moet de TS eerst wat meer constraints geven, maar ik denk dat het verstandiger is om een heuristische methode te gebruiken. Genetische algoritmen zijn razend populair in het probleemgebied van roosters maken. Maar vergis je niet: het vergt inzicht en/of experimenten om de juiste keuzes in het ontwerp van een GA te maken.

[ Voor 13% gewijzigd door Verwijderd op 19-12-2010 18:15 ]

[wouterwouter2]

Bedankt voor de antwoorden.

Het is inderdaad nurse scheduling wat ik bedoelde, bedankt voor de juiste term. Ook goed om te weten dat het dus niet zo makkelijk is als ik gehoopt had. Voor de volledigheid zal ik wat meer informatie geven. Een voorbeeld:

Manager A werkt Donderdag en Vrijdag en hij wilt elke werknemer een uur spreken. Zijn beschikbare tijden zijn:
9 - 10 uur
10 - 11 uur
11 - 12 uur
lunch
13 - 14 uur
14 - 15 uur
15 - 16 uur.

Natuurlijk hebben de werknemers zelf ook verschillende taken en zijn ze niet altijd beschikbaar:

Persoon A: beschikbaar, beide dagen
Persoon B: beschikbaar, donderdag ochtend
Persoon C: beschikbaar: donderdag ochtend, van 9 uur tot 10 uur.
etc

Ideale oplossing is:
9 - 10 uur Persoon C
10 - 11 uur Persoon A/B
11 - 12 uur Persoon A/B
- Manager vrij in de middag.

Wat mij nu het handigst leek, was eerst de personen met de minste flexibiliteit inplannen, en het zo opbouwen. Maar zo te zien kom ik dan meer problemen tegen dan verwacht:
- Wie gaat er om 10 uur? A of B
- Wat te doen bij conflicten

Zo te zien vergt dit dus om een andere aanpak, waar ik even over na ga denken.

[BCC]

Laat ik hier nou net hierop afgestudeerd zijn Eigenlijk zit de crux in het volgende:
Bedenk een formule die een cijfer geeft aan een gegenereerd rooster.
Zo kun je twee roosters vergelijken en daaruit de beste kiezen.

Dan moet je natuurlijk roosters genereren om een cijfer te geven. Hier zijn eigenlijk twee smaken in:
1) Brute force alle roosters genereren
2) Een slimme set roosters genereren en met de beste set verder werken.

Optie 2 bevat een hele grote hoeveelheid mogelijke oplossingen welke voor elke specifieke toepassing beter of slechter zullen werken. Bijvoorbeeld:
- Branching & Bounding
- Simulated Annealing
- Genetische Algoritmes
- Random roosters
- Et cetera

Afhankelijk van de complexiteit van je rooster becijferings formule is dit probleem NP-hard of niet. Bij kleine datasets is dit voor de hedendaagse computers is een complexe formule echter geen enkel probleem Gewoon bruteforcen en klaar! Als het om een stuk of 50 medewerkers gaat met 150 taken en er ook nog zaken als routeplanning bij in komen, dan zul toch echt moeten gaan werken met optie 2.

Zoals je zelf al aangeeft moet je eerst helder hebben wat een 'goed' rooster is en hoe je dit in een formule uitdrukt. Ook belangrijk punt is dat de meeste automatische rooster generatoren niet beter zijn dan een mens, maar vooral consistenter. (lees: sommige mensen krijgen geen voorkeursbehandeling meer)

[ Voor 33% gewijzigd door BCC op 20-12-2010 09:10 ]

[djluc]

Die is wel sterk inderdaad, als je een kwaliteitsregel bepaalt dan is het inderdaad brute forcen wat toch een optimaal resultaat geeft.

Het is wel handig om je constraints nog wat duidelijker te maken. Iemand kan van 9-5 aanwezig zijn. Maar is overwerken ook een optie of juist absoluut niet? Als je het wel toestaat geeft dat minpunten maar het kan wel, als je het niet toestaat kan het wellicht gewoon niet uitkomen qua planning. Wat opzich ook een goede conclusie kan zijn.

[ReenL]

Blijft lastig inderdaad. Ik vind dat BCC een hele mooie oplossing heeft.

Ik heb ooit het algoritme bedacht om "Zo snel mogelijk" in te plannen voor een soort gelijk probleem. Misschien kun je hem gebruiken icm de oplossing 2 van BCC.

Bij mijn systeem moesten alleen alle taken die niet aan bod komen bewaard voor de volgende ronde. Het ging dus niet zo zeer om een rooster, maar meer over een taak die eenmalig uitgevoerd moest worden binnen een bepaald tijd-frame. Ook maakt het de computer niet uit of hij een kwartiertje tussendoor niets te doen heeft

1) Sorteer alle taken op start tijd (Heel de dag is dus 9:00) en daarna op eindtijd;
2) Hou tijdens het sorteren bij welke start-tijden er zijn;
3) Maak een variable waarin je bijhoud hoever je bent met inplannen;
4) Ga de taken op volgorde inplannen totdat je bij een nieuwe start-tijd aankomt;
5) Loop door alle taken en zorg dat de start-tijd minimaal de huidige inplan tijd is;
6) Sorteer alle taken zoals bij 1, let op een aantal taken hebben nu een andere start tijd;
7) Ga naar 4.

Je kunt berekenen hoeveel tijd een Manager maximaal "vrij" kan krijgen. Als dat een middag is ga je alle dagen af om te kijken of er een persoon is die niet alleen op dat moment kan. Hier moet je dan een beetje mee tweaken en de beschikbare tijd voor die manager aanpassen.

[eamelink]

EfBe schreef op zondag 19 december 2010 @ 12:43:
In het regeeraccoord van het huidige kabinet maken ze overigens de klassieke fout door geen weet van dit probleem te hebben, waarbij ze stellen dat roosters (zelfde probleem) aan bepaalde regels moeten worden onderworpen, maar die regels zijn zo strict, dat het niet mogelijk is het op te lossen, (dus wat er in het accoord staat kan helemaal niet ).

Dat lijkt me niet. Het is niet verplicht om de optimale oplossing te vinden, slechts een oplossing die aan de constraints voldoet. Ik kan me niet voorstellen dat de regels die de overheid stelt zodanig ingewikkeld zijn dat dat er niet een oplossing te vinden is met genetisch programmeren en local search. Je hoeft ook niet de allerbeste oplossing te hebben, zolang hij maar aan de harde eisen voldoet, en een lokaal optimum is (zodat het niet heel gemakkelijk is om de oplossing te verbeteren door één shift te wisselen van twee nurses, want dat ondermijnt het vertrouwen in de kwaliteit van het rooster )