[Algoritme] inroosteren van personeel *

[DogZero]

Hoi

voor school moet ik een programmatje schrijven in visual basic waarmee we een roosterprogramma kunnen maken voor een klein bedrijfje. Het gaat erom dat je mensen hebt die op bepaalde tijden en dagen kunnen werken. Daarnaast heb je dagen en tijden dat er gewerkt kan worden. Deze twee zaken/ invoerlijsten moeten dus op een of ander manier samen tot 1 rooster worden geshuffeld.

Het probleem is dat ik niet weet hoe zo'n algoritme eruit moet zien. Heeft een van jullie mischien een idee?

Ik dacht dat het mischien te maken heeft met het algoritme waarmee reisplanners gemaakt worden. Maar ik weet niet waar ik die kan vinden.

Alvast bedankt

[Nexopheus]

Idee is mischien om een negatief rooster systeem te maken.
Dwz vastleggen wanneer iemand NIET kan.
maakt het algemene algoritme eenvoudiger (lijkt me)

[mbravenboer]

(kleine titel aanpassing ).

Dit is inderdaad een optimaliserings-probleem (vind het rooster wat het beste bij alle opgestelde eisen past.

Als je niet erg veel ervaring hebt met zoek-algoritmen en optimaliserings-problemen kan het erg complex worden.

[mbravenboer]

Hum je moet roosteren trouwens wel goed opvatten .

[Nielsz]

Hmmmz, julllie mogen mijn baas wel eens roosteren

damn, zo traag

[DogZero]

waar zou ik kunnen zoeken naar algoritmen en welke keywords zou ik moeten gebruiken voor het zoeken.

[D2k]

titel ff iets verder gemod

[Verwijderd]

heb ik ook al es gevraagd ik zal es kieken
edit: Gevonden [topic=238493/1/50]

[RickN]

Afhankelijk van hoe klein het kleine bedrijfje is (en hoe klein het blijft) zou je een bruteforce aanpak kunnen overwegen. Gewoon alle roosters afgaan en dan uit de geldige roosters de beste kiezen. Maar, de rekentijd die hiervoor nodig is loop al gauw uit de klauwen.

Wil je het toch anders aanpakken dan kom je al snel terecht bij allerlei heuristische zoekmethoden en daar kun je en zijn boeken over vol geschreven. Als je daar niet een beetje mee bekend bent wordt het al gauw complex zoals mbravenboer al zei. Ik weet niet op welke termijn je school iets van je verwacht, maar afhankelijk van de eisen die ze aan je uiteindelijke oplossing stellen ga jij hier nog een hele kluif aan krijgen...

[Verwijderd]

Je PC optimaal laten roosteren is een business die niet zo geschikt is als je er niet het naadje van de kous van weet. Waar een PC alles voor moet narekenen kaneen mens vaak in één oogopslag zien hoe een rooster kan gaan werken.

/me adviseert dan ook:
Doorloop éénmalig de beschikbaarheid van je mensen en laat die invullen op overeenkomende plekken in het rooster, indien nog niet gevuld. Maak dan een scherm waarop de beschikbaarheid van mensen en de gevraagde diensten getoond worden, met mogelijkheden voor de gebruiker om vraag en aanbod te matchen en aan te passen.

[Verwijderd]

Dit is een voorbeeld van een "operations research" probleem. Het vinden van de optimale oplossing in dit soort problemen is vaak niet triviaal. Veelal zijn het NP-hard problemen. In de praktijk houdt dit in dat het systeem alle mogelijkheden moet afgaan om de garantie te hebben om de beste oplossing te vinden. Een ander voorbeeld in deze categorie is het zogenaamde travelling salesman problem.

Dit probleem is een probleem dat met "integer programming" is op te lossen. In sommige gevallen kan dit gedaan worden door eerst het lineaire probleem op te lossen (bijvoorbeeld via simplex methode) waarbij je geen rekening houdt met de integer restricties, om daarna naar de dichtsbijzijnde integer oplossing te gaan. Dat is echter niet gegarandeerd de beste oplossing, en heeft hier niet veel zin.

Een betere aanpak is waarschijnlijk het gebruik van een tree-zoek algoritme, bijvoorbeeld branch & bound. Wat je hierbij doet is alle mogelijkheden afgaan (depth first search). Hierbij wordt steeds bijgehouden wat de best gevonden oplossing tot nu toe is (laagste "cost"). Bij elke afdaling in de tree wordt de minimale cost berekend die de nodes onder het huidige punt nog nodig hebben (*1). Als de huidige cost, plus de cost van alle nodes die eronder liggen hoger is dan die van de best gevonden oplossing tot nu toe, kan gestopt worden met het afdalen in het huidige gedeelte van de tree.

Voor een voorbeeld van een dergelijk zoeksysteem, kun je kijken op http://www.cs.utwente.nl/~knoppel/ultrakoeien/
Dit is de uitwerking van opdracht 3 van de programmeerwedstrijd van ganz ( http://www.ganz.nl/ ), waarmee mijn team de 1e prijs heeft gewonnen. Dit systeem maakt echter niet gebruik van een "pure" branch & bound. Onze bound-functie maakt namelijk geen echt preciese schatting, deze schatting kan te hoog uitvallen, waardoor er teveel gesnoeid wordt in de tree. We hebben hiervoor gekozen omdat de tijd redelijk krap was (ik heb het b&b gedeelte in 1 middag en avond moeten implementeren), en omdat we in enkele minuten een acceptabel resultaat wilden krijgen.

(*1) deze cost hoeft niet exact te zijn, het mag ook een schatting zijn die maximaal de min cost oplevert. Als de schatting te hoog is, wordt er teveel gesnoeid in de tree, waardoor de meest efficiente oplossing niet meer gegarandeerd gevonden wordt, als de schatting te laag is, wordt er minder gesnoeid, waardoor het zoeken trager zal zijn. Als het maken van een exacte functie te ingewikkeld is, of het uitvoeren ervan in verhouding lang duurt, zal een afweging gemaakt moeten worden tussen precisie en efficiency van de schattingsfunctie.

[wasigh]

dit probleem staat toch ook wel bekend als het "dansparen probleem" ??

[Verwijderd]

Op maandag 04 februari 2002 12:06 schreef wasigh het volgende:
dit probleem staat toch ook wel bekend als het "dansparen probleem" ??

Dit probleem ken ik zo niet, met een korte search op Google kan ik het ook niet vinden. Maar misschien is het vergelijkbaar met een ander probleem, waar ik de naam trouwens niet van weet (ik ben het alleen ergens een keer als voorbeeld tegengekomen). Hierbij moet een indeling gemaakt worden voor een studentenhuis, waarbij steeds 2 studenten een appartement delen (het zouden ook bv 8 studenten kunnen zijn, dat maakt voor het probleem niet uit). Hierbij moet rekening worden gehouden met studenten die niet bij elkaar kunnen, omdat ze bijvoorbeeld niet met elkaar kunnen opschieten.

Het probleem is echter niet geheel hetzelfde als het hier gegeven roosterprobleem. Het begin is inderdaad wel hetzelfde, er moeten nu alleen matchende uur + persoon paren worden gevonden. Er moet echter nog verder worden gezocht naar de optimale oplossing. Het optimale rooster zal bijvoorbeeld zo weinig mogelijk gaten bevatten voor de werknemers. Het zijn beide echter NP-problemen, dus alleen bij kleine verzamelingen is er met brute force de beste oplossing te vinden.

[DogZero]

Alvast bedank voor jullie reacties.

Ben aardig opgeschoten met het zoeken naar de juiste algoritme.

Het gaat hier om meer dan 10 personen. soms rond de 100. Brute force is dus geen optie.

Ik doe de opdracht met nog een paar anderen. Wij dachten om Excel te gebruiken voor de invoer en uitvoer en de berekening te laten doen door een vb-script (macro).

Nou heb ik een algoritme gevonden, de zogenaamde "stable marriage" algoritme.
Ik heb zelfs de java source file gevonden op:

http://www.cs.wustl.edu/~kjg/cs101/Notes/SoftwareDesign/design.html

en

http://www.cs.columbia.edu/~evs/intro/stable

Maar ja dit is de eerste keer dat wij zo'n ingewikkelde algoritme gaan gebruiken zou het wel handig zijn als we een voorbeeld hadden in visual basic(script)zelf of in basic.

[Verwijderd]

Op maandag 04 februari 2002 18:22 schreef DogZero het volgende:
[...]

Maar ja dit is de eerste keer dat wij zo'n ingewikkelde algoritme gaan gebruiken zou het wel handig zijn als we een voorbeeld hadden in visual basic(script)zelf of in basic.

Klinkt als: "maak het eens voor me, dan kopieer ik het wel en doe alsof ik he gemaakt heb" ... maar misschien ben ik wat wantrouwig.

Nogmaals: dit is niet een triviaal probleem, dus verwacht dat het een ieder (dus ook de gevorderde programmeur) aardig wat tijd zal kosten. Verwacht dus niet dat mensen meer gaan doen dan je op weg helpen, en een algoritme voor jou omzetten in cut & pastable werk.

Laat eens zien wat je al wel hebt en waar je vast komt te zitten, en dan zullen er zat mensen zijn die je willen helpen, maar geef het niet op voordat je begonnen bent.

Succes!

[Verwijderd]

Haha luite, superkewle wedstrijd... Is ie dit jaar weer? Krijg je eens wat concurrentie van de Universiteit Maastricht(Tegenwoordig tUL).

Even over het algoritme:
Je kunt dit probleem ook met een neuraal netwerk oplossen . Dit is echter helemaal niet gemakkelijk als je nog niet eens met normale design patterns bekend bent, zou wel een goede aanpak zijn. Zou je echter eens een paar AI boeken moeten lezen.

Vorig blok hebben wij dit probleem aangepakt met java, die PROLOG aanroepte voor het algoritme, maar dit heeft ook zijn nadelen, duurde vrij lang om te berekenen.

Ik weet ook niet of Excel / VBScript zo'n goede oplossing is...
Probeer in ieder geval eens het probleem in een paar deelproblemen op te lossen... dit werkt vaak beter.

Greetz en heel veel suc6,
daRoBBie.

[Tomatrix]

Op maandag 04 februari 2002 18:22 schreef DogZero het volgende:
Maar ja dit is de eerste keer dat wij zo'n ingewikkelde algoritme gaan gebruiken zou het wel handig zijn als we een voorbeeld hadden in visual basic(script)zelf of in basic.

Zo ingewikkeld is die Java code niet, lijkt mij vrij triviaal om die om te zetten naar VB.

[Tomatrix]

Op dinsdag 05 februari 2002 07:56 schreef daRoBBie het volgende:
Je kunt dit probleem ook met een neuraal netwerk oplossen .

Maar heb je dan de garantie dat je de meest ideale oplossing hebt gevonden, en niet in een lokaal minimum bent blijven hangen? Het algorithme waar de link naar verwijst garandeert dat het een ideale oplossing vindt.

Dit is echter helemaal niet gemakkelijk als je nog niet eens met normale design patterns bekend bent, zou wel een goede aanpak zijn.

Het configureren van een neuraal netwerk heeft volgens mij weinig met design patterns te maken...

[DogZero]

Toen we begonnen met het probleem leek het redelijk eenvoudig. Maar naarmate het eisenplan groeide en we verder ondezochten welk algoritme we zouden gebruiken werd het lastiger. Het probleem is gewoon dat wij niet genoeg programmeer ervaring hebben om in korte tijd alles erin te zetten wat erin moet. wij doen ICT-consultancy en geen IT. Grafen -Theory/ Neurale netwerken krijgen we niet.

Vandaag zijn we dus naar de lerares gestapt om te vragen hoe het zat met andere soortgelijke opdrachten.

Tot onze verbazing zegt ze dan: "Ik begrijp dat het een ingewikkeld probleem is. Wat mij betreft kun je volstaan met een ontwerpschema, marktondezoek, keuze van een goede applicatie en de implementatie hiervan".|:(

Het gaat hier om een echt bedrijf voor wie we de opdracht uitvoeren dus we moeten een degelijke applicatie afleveren.

We hebben het grootste gedeelte van onze tijd besteed aan het opstellen van de DFD/0 schema en eisenplan. Wat nu dus moet komen is in plaats van de "hard-core" programming onderzoek naar een goede applicatie.


Iedereen die heeft meegeholpen

Bedankt.>:)