Minimierung der maximalen Kosten einer Aufgabe-Maschine-Zuordnung

Question

Ich habe m Maschinen und n Aufgaben. Es gibt eine durch n m Kostenmatrix A wo Aij sind die Kosten der Ausführung von Task j auf Maschinen i. Jede Aufgabe muss genau einer Maschine zugewiesen sein, aber jede Maschine kann mehrere Aufgaben annehmen.

Mein Problem ist es, die Möglichkeit zu finden, die Aufgaben zu Maschinen zu minimieren MakeSpan, die maximalen Kosten für eine Maschine.

Wie kann ich dieses Problem lösen? Ich habe überlegt, den Ungarischen Algorithmus zu verwenden, aber er minimiert die Gesamtkosten und nicht die maximalen Kosten für eine Maschine.

Answer 1

Sie können das Problem als ein ganzzahliges lineares Programm ausdrücken. Sei B[i][j] eine Matrix aus 0 und 1 mit der Bedeutung B[i][j] = 1, wenn wir die j Aufgabe der i ten Maschine zuweisen. Die Tatsache, dass die Aufgaben nicht aufteilbar sind, macht dies zu einem ILP anstatt zu einem LP - andernfalls könnten wir einfach darauf bestehen, dass 0 <= B[i][j] <= 1.

Wir möchten die maximalen Kosten jeder Maschine minimieren. Das ist keine lineare Funktion, aber es gibt einen Standardtrick, um es so auszudrücken, indem man eine Dummy-Variable einführt (die hier im Programm MakeSpan genannt wird).

der ILP ist das Programm, das m + n Einschränkungen hat: die Idee

minimize MakeSpan such that 

sum(B[i][j] for i=1..m) = 1 for all j 
sum(B[i][j]*A[i][j] for j=1..n) <= MakeSpan for all i 

Der erste Satz von Constraints formalisiert, dass jede Aufgabe zu genau einer Maschine zugeordnet ist. Die zweite Einschränkung besteht darin, dass die Kosten für jede Maschine maximal MakeSpan betragen.

Das Minimum MakeSpan wird lokal erreicht, wenn MakeSpan den maximalen Kosten einer Maschine entspricht und global erreicht wird, wenn diese maximalen Kosten ebenfalls minimiert werden.

Um das ILP zu lösen, können Sie Ihren bevorzugten ILP-Solver verwenden. Zum Beispiel ist GLPK ein Open Source Solver.