Maximierung von Zuweisungs-Bewertungen unter Bedingungen

22.01.2016, 15:50	DS87	Auf diesen Beitrag antworten »
Maximierung von Zuweisungs-Bewertungen unter Bedingungen Hallo zusammen, ich möchte gerne eine Zuweisungs-Optimierungen unter verschiedenen Bedingungen schaffen und dabei dabei zwei Ideen wie es möglich wäre. Gerne würde ich dabei von euch wissen, ob es vielleicht andere Methoden die ich anwenden sollte um auf eine bessere Lösung zu kommen. Als Optimierung gilt die Maximierung der Summe der Bewertungen. Um die Bedingungen und das folgende Beispiel greifbar zu machen stellt $\begin{eqnarray} X \end{eqnarray}$ : Personen und $\begin{eqnarray} Y \end{eqnarray}$ : Aufgaben dar. Dabei gelten folgenden Bedingungen: 1.) Es gibt eine Zeitkomponente (bspw. 10-12 Uhr) die von $\begin{eqnarray} y_i \end{eqnarray}$ festgelegt wird. D.h. eine Aufgabe kann nur zu einem festgelegten Zeitpunkt gemacht werden. 2.) Person $\begin{eqnarray} x_i \end{eqnarray}$ hat verfügbare Zeiten (z.B.: von 10-18 Uhr). 3.) Eine Person $\begin{eqnarray} x_i \end{eqnarray}$ kann zeitgleich nur einer Aufgabe $\begin{eqnarray} y_i \end{eqnarray}$ zugewiesen werden. Hat $\begin{eqnarray} x_i \end{eqnarray}$ schon eine Zuweisung um diese Uhrzeit kann keine weitere Zuweisung erfolgen. 4.) Einer Aufgabe $\begin{eqnarray} y_i \end{eqnarray}$ darf maximal eine Person $\begin{eqnarray} x_i \end{eqnarray}$ zugewiesen werden. 5.) Jede Zuweisung $\begin{eqnarray} x_i \end{eqnarray}$ ( $\begin{eqnarray} y_i \end{eqnarray}$ ) hat eine Bewertung (Bpsw. $\begin{eqnarray} x_1(y_1) = 70, x_2(y_1) = 50, x_1(y_2) = 55 \end{eqnarray}$ ). Dies zeigt wie gut eine Person für eine Aufgabe geeignet ist. 6.) (zunächst Optional, daher erstmal nicht beachten) Die Bewertung der Zuweisung kann sofern ein Vorgänger und / oder ein Nachfolger besteht marginal variieren. Hier ist ein konkretes Beispiel: $\begin{eqnarray} \begin{tabular}{c\|c\|c\|} & x1 (10-18) & x2 (9-17) \\ \hline y1 (11-14) & 70 & 65 \\ y2 (10-12) & 60 & 30 \\ y3 (13-15) & 60 & 25 \\ \end{tabular} \end{eqnarray}$ Die Ideale Summe ist $\begin{eqnarray} x_2(y_1) + x_1(y_2) + x_2(y_3) = 65 + 60 + 60 = 185 \end{eqnarray}$ . Dadurch das x1 die Aufgaben von 10-12 und von 13-15 Uhr macht, kann er y1 nicht mehr machen da er zeitlich nicht mehr verfügbar ist. Doch mit welchem Verfahren kann ich das Ergebnis maximieren wenn ich bspw. 100 Aufgaben und 50 Personen habe? Ich habe die Vermutung dass sich das Problem ab einer bestimmten Größe nicht optimal bestimmen lässt da die Rechenzeit zu intensiv wäre. Daher habe ich folgende Ideen um das große Problem in mehrere kleine Probleme aufzuteilen. Idee 1: Ich weise immer die höchste Bewertung zu. Anschließend wird die nächst höhere mögliche Bewertung zugewiesen bis es keine möglichen Kombinationen gibt. Dieser Ansatz ist einfach, kann aber suboptimal sein. Je größer der Datensatz ist umso weniger suboptimal wird es (In diesem Fall würde es zunächst $\begin{eqnarray} x_1(y_1) \end{eqnarray}$ dann $\begin{eqnarray} x_2(y_2) \end{eqnarray}$ , $\begin{eqnarray} x_2(y_3) \end{eqnarray}$ = 125 ergeben). Idee 2: Ich berechne alle möglichen Kombination je Person. In dem Fall hätte x1 die Kombinationen y1 = 70 und y2 + y3 = 120. x2 hätte die Kombinationen y1 = 65 und y2 + y3 = 55. Nun gucke ich mir die größte Summe der Kombinationen an - welche 120 $\begin{eqnarray} x_1(y_2) + x_1(y_3) \end{eqnarray}$ ist und weise diese Kombinationen durch. Anschließend berechne ich wieder alle übrig gebliebene Kombinationen und weise wieder die Höchste zu solange bis es keine Kombination mehr gibt. Dies ist natürlich zunächst ein hoher initialier Rechenaufwand für die Kombinationen. Die Verteilung anschließend sollte jedoch schnell gehen. Die Idee 1 an sich habe ich schnell implementiert gehabt, die Ergebnisse waren ok mit großen Datensätzen, gehen aber bestimmt noch besser. Idee 2 habe ich noch nicht implementiert, da dies ein bisschen länger dauern würde. Bevor ich das jedoch mache, würde ich gerne von euch wissen, ob es ein anderes / besseres Verfahren gibt das ich mir davor noch anschauen sollte bevor ich dieses implementiere. Ich freue mich über jede Anregung, Kritik und Hilfe
26.01.2016, 17:44	DS87	Auf diesen Beitrag antworten »
RE: Maximierung von Zuweisungs-Bewertungen unter Bedingungen Hat keiner eine Idee oder Hinweis ? Ist meine Frage schlecht gestellt, fehlerhaft, zu kompliziert oder oder oder?

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »