Arbeitsspeicherverwaltung
Allgemeine Diskussion
Alle Antworten
-
Hallo Pawel,
ich habe ein wenig gezögert den Code zu Posten, da es sich wie gesagt um eine Arbeit für die Uni handelt. Ich bitte daher nur um Ratschläge, Hinweise etc. damit man mir nacher nicht vorwerfen kann, dass ich in die Fußstapfen eines ehemaligen Verteidigungsministers trete.
Ein weiterer Grund warum ich gezögert habe: Das Problem ist nicht mal eben so erklärt, da es doch etwas komplexer ist. Ich freue mich natürlich, dass du hier deine Hilfe anbietest, aber ich habe auch Verständnis dafür, wenn es dir zu viel Aufwand bereitet den Code zu verstehen.
Zu meinem Problem: Es geht um Dienstplanung genauer gesagt um Dienstreihenfolgenplanung. Ich habe eine bstimmte Anzahl an Diensten gegeben, für die ich die optimale Konstellation finden soll. Dazu generiere ich mir Knoten, die jeweils eine zusammenhängende Folge von Diensten enthalten und lasse von einem Solver (CPLEX 12.0) die Knoten mit der besten Konstellation (niedrigste Kosten) heraussuchen.
Dafür generiere ich zunächst für jeden Knoten alle möglichen und validen Variationen. Beispiel: Mein Knoten umfasst fünf Tage (ein Dienst pro Tag) und an jedem Tag kommen 15 Dienste in Frage. Macht also 5^15 Möglichkeiten, die Dienste miteinander zu kombinieren. Daher die enorme Komplexität des Problems. Habe teilweise Knoten mit 20Mio. Variationen. Damit das Problem nicht zu groß wird, teile ich mir nun die Betrachtung dieser Variationen auf - Teilmengen der gesamten Variationsmenge - und löse diese separat. Ich versuche es zumindest, aber wie oben beschrieben stoße ich an meine technischen Grenzen.
Die folgende Funktion macht genau das, was ich gerade beschrieben habe. Sie ist noch nicht fertig und ich entschuldige mich schon einmal, wenn sie nicht gut lesbar ist. Ich habe versucht durch Kommentare das Vorgehen weitestgehend zu erläutern. Das erzeugen der Variationen kannst du dir wie das Durchprobieren aller Variationen eines Zahlenschlosses vorstellen. Du drehst das Rädchen (in diesem Fall die Dienstmenge für den entsprechenden Tag) immer eins weiter. Bist du einmal durch schiebst du das nächste Rädchen eins weiter und usw.. Die Zahlen in der Grafik unten stehen für jeweils einen bestimmten Dienst. Wie du sieht, müssen die jeweiligen Mengen nicht gleich Groß sein. Stell dir vor die erste Spalte Sei Montag, dann Dienstag usw.
Die Übergabe an den Solver befindet sich am Ende. Das Problem hier ist, dass ich beim Solver ein Scalarprodukt aus der Entscheidungsvariable und den Gewichtungen meiner Zielfunktion bilden muss, was den Speicher zusätzlich enorm belastet, da das für jeden Knoten durchgeführt werden muss.
public nodeObject[] varAllDuties2(nodeObject startNode) { /* Diese Methode gibt einen nodeObject-Array zurueck, das alle zu einem gegebenen Knoten * gueltigen Variationen bezueglich der Dienste enthaelt. */ Duty[][] sheet = new Duty[startNode.NumOfDays][]; int intNumOfVariations = 1; int[] intPointer = new int[startNode.NumOfDays]; // Bestimme erlaubte Dienstmengen für jeden Tag i for (int i = 0; i < startNode.NumOfDays; i++) { sheet[i] = getSetOfDutiesAll(startNode.ShiftIDs[i], (startNode.StartDay + i) % 7); } // Berechne Anzahl der Variationen der Dienste for (int i = 0; i < startNode.NumOfDays; i++) { intNumOfVariations *= sheet[i].Length; } //MessageBox.Show("Anzahl der Variationen: " + intNumOfVariations); // Initialisiere Hilfsarray mit Zeigern, die die aktuelle Variation speichern for (int i = 0; i < startNode.NumOfDays; i++) { intPointer[i] = 1; } // temporaeres Ergebnis-Array zweidimensional nodeObject[][] tempFinalResult = new nodeObject[splProb][]; // Anzahl aller moeglichen Variationen int setSize = intNumOfVariations; int tempCounter = 0; // Fuer jedes Teilproblem... for (int t = 0; t < splProb; t++) { // Zaehler fuer valide Dienst-Folgen int intDiffValidVariations = 0; // groeße der betrachteten Teilmenge int splitSetSize = Convert.ToInt32(Math.Ceiling(Convert.ToDouble(setSize) / Convert.ToDouble(splProb))); // tempraeres Array, in dem die Ergebnisse fuer das t'te Teilproblem gespeichert werden nodeObject[] result = new nodeObject[splitSetSize]; // Untergrenze der betrachteten Teilmenge t int LB = t * splitSetSize; // Obergrenze der betrachteten Teilmenge t int UB = (t * splitSetSize) + splitSetSize; // Für die Anzahl der Variationen des Teilproblems t for (int i = LB; i < UB; i++) { bool boolTempValidSeq = true; int intTime = 0; double overTime = 0; // Pruefe ob Schichtfolge zulaessig for (int k = 0; k < startNode.NumOfDays - 1; k++) { if (isValidSequence(sheet[k][intPointer[k] - 1], sheet[k + 1][intPointer[k + 1] - 1]) == false) { boolTempValidSeq = false; intDiffValidVariations++; break; } } // Wenn Schichtfolge zulaessig... if (boolTempValidSeq == true) { Duty[] dutTempDutiesOne = new Duty[startNode.NumOfDays]; // Knoten generieren und in in result speichern for (int k = 0; k < startNode.NumOfDays; k++) { dutTempDutiesOne[k] = sheet[k][intPointer[k] - 1]; intTime += sheet[k][intPointer[k] - 1].BDZ; overTime += sheet[k][intPointer[k] - 1].BDZ - getGroupWorkingTimePerDay(startNode.GroupID); } overTime = overTime / startNode.NumOfDays; result[i - intDiffValidVariations - (t * splitSetSize)] = new nodeObject(startNode.NodeID, startNode.GroupID, startNode.WeekNo, startNode.NumOfDays, startNode.StartDay, startNode.ShiftIDs, startNode.Cost, dutTempDutiesOne, intTime, overTime); } // Durchlaufe die oben ermittelten Dienstmengen (Zahlenschloss) // Fuer Anzahl der Spalten (Tage) for (int j = 0; j < startNode.NumOfDays; j++) { // Wenn Elementzeiger auf letztem Element von Spalte j dann... if (intPointer[j] == sheet[j].Length) { // Zeiger zurücksetzen intPointer[j] = 1; // und zur naechsten Spalte gehen } // Ansonsten (Elementzeiger nicht auf letztem Element von Spalte j ...) else { // Zeiger hochzählen und Schleife j abbrechen intPointer[j] += 1; break; } } } // Rueckgabearray zuschneiden nodeObject[] tempResult = new nodeObject[result.Length - intDiffValidVariations]; for (int i = 0; i < result.Length - intDiffValidVariations; i++) { tempResult[i] = new nodeObject(result[i]); } // Gebe Array result frei result = null; System.GC.Collect(); // Uebergabe an den Solver tempFinalResult[t] = solveSubProbSplitNodeSet(tempResult); // Gebe Array tempResult frei tempResult = null; System.GC.Collect(); // Zaehle Ergebnisse if (tempFinalResult[t] != null) { tempCounter += tempFinalResult[t].Length; } } // Erzeuge Ergebnis-Array nodeObject[] finalResult = new nodeObject[tempCounter]; int tCounter = 0; // Schreibe Ergebnisse in Ergebnisarray for (int i = 0; i < tempFinalResult.Length; i++) { for (int j = 0; j < tempFinalResult[i].Length; j++) { finalResult[tCounter] = tempFinalResult[i][j]; tCounter++; } } // MessageBox.Show("Ergebnisse: " + finalResult.Length); // Ergebnisse zurueckgeben return finalResult; }
Der Vollständigkeit halber hier nochmal ein Ausschnitt aus der Funktion mit dem Solver zum Aufbau des Modells:// Entscheidungsvariabeln mit Unter- und Obergrenzen ---------------------------------------------- INumVar[] x = cplex.NumVarArray(numOfNodes, 0, 1); // Zielfunktionen --------------------------------------------------------------------------------- IObjective objSubProb = cplex.AddMinimize(); INumExpr maxAveragOverTime; INumExpr[] tempMaxAveragOvertime = new INumExpr[numOfNodes]; INumExpr[] costNotChosenNode = new INumExpr[numOfNodes]; // Kosten fuer Abweichungen vom Wunschturnus und durchschnittliche Arbeitszeit der ausgewaehlten Knoten for (int i = 0; i < numOfNodes; i++) { if (C1 > 0) { cplex.AddToExpr(objSubProb, cplex.Prod(C1, cplex.Prod(nodesDutyVar2D[t][i].Cost, x[i]))); } if (C2 > 0) { cplex.AddToExpr(objSubProb, cplex.Prod(C2, cplex.Prod(nodesDutyVar2D[t][i].AverageWorkTime, x[i]))); } } // Kosten fuer nicht ausgewaehlte Knoten und maximale durchschnittliche Ueberstunden der ausgewaehlten Knoten for (int i = 0; i < numOfNodes; i++) { costNotChosenNode[i] = cplex.Prod(-1, cplex.Prod(1000, cplex.Sum(-1, x[i]))); tempMaxAveragOvertime[i] = cplex.Prod(Convert.ToDouble(nodesDutyVar2D[t][i].AverageOverTime), x[i]); cplex.AddToExpr(objSubProb, costNotChosenNode[i]); } maxAveragOverTime = cplex.Max(tempMaxAveragOvertime); if (C3 > 0) { cplex.AddToExpr(objSubProb, cplex.Prod(C3, maxAveragOverTime)); }
Vielen Dank für jede Hilfe!Viele Grüße
Tost1989
-
****************************************************************************************************************
Dieser Thread wurde mangels weiterer Beteiligung des Fragestellenden ohne bestätigte Lösung abgeschlossen.
Neue Rückfragen oder Ergänzungen zu diesem Thread bleiben weiterhin möglich.
****************************************************************************************************************Robert Breitenhofer, MICROSOFT
Bitte haben Sie Verständnis dafür, dass im Rahmen dieses Forums, welches auf dem Community-Prinzip „Entwickler helfen Entwickler“ beruht, kein technischer Support geleistet werden kann oder sonst welche garantierten Maßnahmen seitens Microsoft zugesichert werden können.
