Problem: Gleichverteilung von Terminen

Werbeanzeige

LInsoDeTeh

Treue Seele

Beiträge: 372

Wohnort: Essen, Deutschland

Beruf: Team Lead Inhouse-Entwicklung

18.04.2013, 11:05

Problem: Gleichverteilung von Terminen

Hallo zusammen,
hier mal eine Frage an die Mathematiker hier: Aktuell habe ich ein Problem beim Gleichverteilen von Terminen in einem Kalender.

Gegeben ist ein Kalender mit den Tagen Montag bis Samstag, und jeden Tag gibt es zwischen 7 und 20 Uhr "Slots" von 1 Stunde länge, das heißt ich kann Termine immer genau auf 8 Uhr, 9 Uhr, 10 Uhr etc. legen.
Für die Termine (die auch immer genau die Länge 1 Stunde haben, sprich genau einen Slot belegen) habe ich für jeden Slot die Information, ob er dort liegen darf, oder nicht. Also eine Art "Öffnungszeiten", zum Beispiel: Termin A darf Montags auf 8, 9, und 10 Uhr und Mittwochs auf 14, 15, und 16 Uhr platziert werden, Termin B dagegen darf Dienstags auf 11, 12, und 13 Uhr, und Donnerstags auf 18, 19 und 20 Uhr platziert werden.
Dabei sind es aber so viele Termine, dass eine Überschneidung der Öffnungszeiten ohne weiteres möglich ist.

Nun ist die Frage, wie bekomme ich per Algorithmus eine Verteilung hin, sodass die maximale Anzahl von Terminen in dem Kalender platziert werden können?
Wenn man das händisch macht, hat man ja ein menschliches Auge, das feststellt, dass z.B. eine Gruppe von Terminen nur Donnerstags platziert werden können und deswegen andere Termine, die andere Möglichkeiten als Donnerstag haben, den Donnerstag nicht belegen sollten. Doch wie löse ich das algorithmisch?

Mein bisheriger Ansatz war, die Termine nach der Anzahl ihrer Platzierungsmöglichkeiten zu sortieren und beginnend beim unflexibelsten nach und nach zum frühstmöglichen Zeitpunkt zu platzieren, doch das führt dazu, dass die ersten 3 Tage recht schnell voll sind und dann Termine, die evtl. nur in den drei Tagen platziert werden dürften, keinen freien Slot mehr finden. Was ein menschliches Auge anders gelöst hätte, weil es nicht frühstmöglich platziert, sondern im Gesamtkontext schaut.

Hat da jemand eine Idee, wie man das algorithmisch umsetzen kann, oder sowas vielleicht schonmal gemacht?

Vielen Dank für eure Hilfe!

Zum Seitenanfang

TGGC

1x Rätselkönig

Beiträge: 1 799

Beruf: Software Entwickler

18.04.2013, 12:42

Alle Moeglichkeiten durchprobieren (Backtracking ist ein Algo dafuer) kommt zu einer Loesung. Braucht allerdings auch lange fuer die Loesung. Also vielleict versuchen, das Problem zu zerlegen. Eine Andere Idee ist, alle aequivalenten Loesungen zu einer zusammenzufassen. Als Beispiel, wenn ich von jedem Termin weiss, das er entweder am Montag von 8-18 Uhr darf, oder aber am Montag ueberhaupt nicht darf, dann kann ich einfach 10 Termine auf Montag legen und erst spaeter eine beliebige Reihenfolge auswaehlen.

Eine andere Moeglichkeit waere eine Art Heuristik, wie du sie schon versucht hast. Nur bekommst du halt hier nicht unbedingt die beste Loesung und welche Heuristik gut funktioniert, haengt von den konkreten Daten ab, so das dir hier niemand helfen kann.

Tetris Meeting Mainz | WMK Gamesroom | Schau dem neuen Tetris Großmeister zu

Zum Seitenanfang

Schorsch

Supermoderator

Beiträge: 5 145

Wohnort: Wickede

Beruf: Softwareentwickler

18.04.2013, 16:34

Müsste das nicht ähnlich wie Sudoku zu lösen sein? Dort sind es halt Zahlen die auf den Feldern verteilt werden und das zwar auch über andere Regeln, aber das sollte ja trotzdem vergleichbar zu lösen sein.
edit:
Was auch sicher gut möglich ist, wäre die Situation von einem Kalender als Knoten in einem Graphen darzustellen. Du bewertest eine Situation danach, wie viele Termine in der Situation einen Platz haben. Diese Bewertung nimmst du als Heuristik für einen Ansatz mit A*. Dass sollte eigentlich recht gut funktionierten.

„Es ist doch so. Zwei und zwei macht irgendwas, und vier und vier macht irgendwas. Leider nicht dasselbe, dann wär's leicht.
Das ist aber auch schon höhere Mathematik.“

Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von »Schorsch« (18.04.2013, 16:47)

Zum Seitenanfang

Jonathan_Klein

Community-Fossil

Beiträge: 3 820

19.04.2013, 00:29

Ich habe echt länger nichts mehr damit gemacht, aber ich bin mir sehr sicher, dass du das als Problem der 'Linearen Optimierung' formulieren kannst:
http://de.wikipedia.org/wiki/Lineare_Optimierung
(Die Variable, die du optimieren möchtest wäre in diesem Falle die Anzahl der untergebrachten Termine).
Du nimmst also einfach ein Toolkit, z.B. GLPK (http://www.gnu.org/software/glpk/) formulierst dein Problem darin und lässt es durchrechnen. Der Vorteil ist, dass du beinahe nichts selber machen muss und direkt deine Lösung hast, die dann auch sehr gut funktioniert. Der Nachteil ist, dass es eventuell effizientere Lösungen oder Heuristiken gibt. Du musst dich also fragen, ob du das Problem lösen willst, oder die Theorie dahinter studieren möchtest.

Achja: Gleichverteilung ist ein fester Begriff aus der Stochastik. Außerdem heißt es ja nicht, dass eine gleichmäßige Verteilung (also z.b. jeden Tag genau 2 Termine) in irgendeiner Weise ein Optimum ist. Das hat mich nur erst irritiert, da die Frage in diesem Sinne dann nichts mehr mit dem Titel zu tun hatte.

Lieber dumm fragen, als dumm bleiben!

Zum Seitenanfang

TGGC

1x Rätselkönig

Beiträge: 1 799

Beruf: Software Entwickler

19.04.2013, 08:47

Zitat von »Jonathan_Klein«

aber ich bin mir sehr sicher, dass du das als Problem der 'Linearen Optimierung' formulieren kannst:
http://de.wikipedia.org/wiki/Lineare_Optimierung

Ich bin mir sehr sicher, das es damit nicht geht, weil seine Variable diskret und nicht stetig sind.

Tetris Meeting Mainz | WMK Gamesroom | Schau dem neuen Tetris Großmeister zu

Zum Seitenanfang

Jonathan_Klein

Community-Fossil

Beiträge: 3 820

21.04.2013, 10:42

Naja, GLPK kann ja auch mit ganzzahligen oder sogar boolschen Variablen umgehen. Ich meine mich auch daran zu erinnern, dass in den Beispielen ein Sudoku-Solver enthalten war. Und hier ist eine Aufgabe, die auch mit GLPK gelöst werden soll und so ähnlich wie die des Thread-Erstellers ist.

Lieber dumm fragen, als dumm bleiben!

Zum Seitenanfang

LInsoDeTeh

Treue Seele

Beiträge: 372

Wohnort: Essen, Deutschland

Beruf: Team Lead Inhouse-Entwicklung

23.04.2013, 11:31

Vielen Dank für Eure Antworten!

Ich habe jetzt doch viel über Heuristiken und Randparameter gemacht. Das liefert bisweilen ganz gute Ergebnisse. Leider gibt es doch immer mal wieder ein paar Termine, die nicht platziert werden können, oder eine gewisse Linkslastigkeit in den einzelnen Spalten eines Tages, wo das Auge beim Draufgucken sofort sagt: Warum schieb ich das nicht einfach da hin?
Naja, da muss der Kunde dann jetzt wohl einfach mit leben und nach dem automatischen Generieren noch 2-3 Minuten manuelles Verschieben investieren

Zum Seitenanfang

DarioFrodo

Treue Seele

Beiträge: 349

Wohnort: Kerkau, 100km nördlich von Magdeburg

Beruf: Selbstständig

28.04.2013, 12:41

Genau solche Art von Problemen haben wir in der Uni mit Prolog gelöst.
Wenn du du willst kann ich dir ja mal meine Unterlagen zukommen lassen von der Uni.
Sobald ich wieder Zuhause bin (ende nächste Woche).

Erst wenn der letzte Fluss vergiftet,
der letzte Baum gefällt,
der letzte Fisch gefangen,
dann werdet ihr merken, dass man Geld nicht essen kann

Man verkauft die Erde nicht, auf der die Menschen wandeln.

- Indianerweisheiten

Ich bin auch ein einhornimmond