Suche Algorithmus zum Anordnen von Objekten

[AlexM]

Ich erstelle gerade ein Programm für ne Bekannte im Pflegeheim zum Erstellen ihres Dienstplanes.

Jetzt brauche ich einen Sortieralg der mir die Mitarbeiter so verteilt, dass so wenig wie möglich überstunden anfallen, bestimmte Arbeitszeiten eingehalten werden und alle gleich behandelt werden. Ich habe jedoch null Ahnung wie so eine Algorithmus aussehen könnte.

Ich dachte an sowas wie bei meiner Anlage für das Überspielen von CD auf Kassete vo die Anlage die Titel so zusammenstell das die Größte Auslastung gegeben ist, d.h. evtl auch Titel ncih in der selben Reihenfolge überspielt.

Bitte helft mir.
Als Programmiersprache werde ich JAVA einsetzen.

Ic hbrauche nur ein grobkonzept bzw. eine Anregung in welche Richtung ich denken muß...

Danke im Vorraus

AlexM

[maximAL]

hmm, ich glaube, das, was du suchst, ist als rucksack-problem bekannt.
ich hoffe du hast irgendein brauchbares algorithmen-buch (oder eine andere quelle) zur hand. sonst müsste ich mich wegen der implementierung selbst erst nochmal schlau machen...

[beta3]

hmm, ich glaube, das, was du suchst, ist als rucksack-problem bekannt.
ich hoffe du hast irgendein brauchbares algorithmen-buch (oder eine andere quelle) zur hand. sonst müsste ich mich wegen der implementierung selbst erst nochmal schlau machen...

kannst du mir ein paar Algorithmenbuecher empfehlen?
Ich habe noch keines, wuerde mir aber gerne eines zulegen

[maximAL]

kannst du mir ein paar Algorithmenbuecher empfehlen?
Ich habe noch keines, wuerde mir aber gerne eines zulegen

ein standard-werk ist wohl algorithmen in c (welches ich auch habe), davon gibts auch eine ausgabe für C++.
auch mal hier (http://www.c-plusplus.de/cms/modules.php?op=modload&name=mbBooks&func=db&theme=basics) schauen...

[AlexM]

Danke, das war der Anreger den ich brauche.. für C hab ich ne Anleitung. Da fällt mir zu dem Thema die Branch and Bound Lösung ein, oder bin ich da auf dem Holzweg?

Danke und Gruß

AlexM

[Pinoccio]

[...]Als Programmiersprache werde ich JAVA einsetzen. [...]
Ic hbrauche nur ein grobkonzept bzw. eine Anregung in welche Richtung ich denken muß...1.) :up:
2.) Ich habe in ähnlichen Fällen immer eine Kombination "ausgewürfelt" und dann geschaut, ob sie passt.
In deinem Fall könntest du dir eine Bewertung jeder Anordnung erstellen (zB Überstunde: 1 Strafpunkt, Überschneidung: komplett ungültig etc) und dann zufällige Kombinationen testen und die beste gefundene nehmen. Wenn du die beste finden willst müsstest du alle testen (praktisch evtl unmöglich) oder einen besseren Algorithmus finden ... ;-)hmm, ich glaube, das, was du suchst, ist als rucksack-problem (http://de.wikipedia.org/wiki/Rucksackproblem) bekannt.Scheint so, wobei er noch so einige Nebenbedingungen hat.

mfg Sebastian

[AlexM]

Ich habe nur Angst das das ziemlich lange dauert. Das sind 15 Mitarbeiter 3 Schichten a 4 , 3 und 2 Leuten das ganze für 30Tage mit so an die 10 verschiedenen Parameter wie Überstunden, anzahl schwester und hilfskräfte, priorisierung von Überstunden, kein wechsel von nacht auf frühschicht usw.
wenn der das Beste für den Gesamten Monat berechnen sol... ;( ;( ;(

Gruß AlexM

[maximAL]

1.) und dann zufällige Kombinationen testen und die beste gefundene nehmen
:nono:

[ethrandil]

Wenn dir die 'fehlerfreien' Algorithmen zu lange zu berechnen sind, dann google mal nach Tabu-Search, das hat dabei imho sehr gute Resultate gezeigt :-)

- Eth

Edit: zum Prinzip: http://vwww10.hrz.tu-darmstadt.de/bwl3/forsch/projekte/tabu/paper.htm

[AlexM]

Die Frage ist, wie ich diesen Algo implementiere... Hbae nirgends im Internet vernünftige beispeiel für Objekte mit mehreren Attributen gefunden...

MfG AlexM

Edit: Die andere Sache ist, dass ich nciht weiß welchen Algo ich überhaupt nehemn soll, geschweige denn wie zu implementieren

[maximAL]

naja, wenn du was konkreteres hören willst, solltest du ein paar mehr eckdaten liefern, zb. was "gleich behandeln" genau bedeutet, oder wie die mitarbeiter auf die schichten verteilt werden sollen etc.