Verallgemeinertes Zuordnungsproblem - Generalized assignment problem

In der angewandten Mathematik ist das maximal verallgemeinerte Zuordnungsproblem ein Problem der kombinatorischen Optimierung . Dieses Problem ist eine Verallgemeinerung des Zuweisungsproblems, bei dem sowohl Aufgaben als auch Agenten eine Größe haben. Darüber hinaus kann die Größe jeder Aufgabe von einem Agenten zum anderen variieren.

Dieses Problem in seiner allgemeinsten Form sieht wie folgt aus: Es gibt eine Reihe von Agenten und eine Reihe von Aufgaben. Jeder Agent kann mit der Ausführung jeder Aufgabe beauftragt werden, wodurch Kosten und Gewinn entstehen, die je nach Agenten-Aufgaben-Zuweisung variieren können. Darüber hinaus verfügt jeder Agent über ein Budget, und die Summe der ihm zugewiesenen Aufgabenkosten darf dieses Budget nicht überschreiten. Es ist erforderlich, einen Auftrag zu finden, bei dem alle Agenten ihr Budget nicht überschreiten und der Gesamtgewinn des Auftrags maximiert wird.

In besonderen Fällen

In dem Sonderfall, in dem alle Budgets der Agenten und die Kosten aller Aufgaben gleich 1 sind, reduziert sich dieses Problem auf das Zuordnungsproblem . Wenn die Kosten und Gewinne aller Aufgaben nicht zwischen verschiedenen Agenten variieren, reduziert sich dieses Problem auf das Problem der Mehrfachrucksacke. Wenn es einen einzelnen Agenten gibt, reduziert sich dieses Problem auf das Rucksackproblem .

Erklärung zur Definition

Im Folgenden haben wir n Arten von Artikeln bis und m Arten von Behältern bis . Jedem Behälter ist ein Budget zugeordnet . Für einen Behälter hat jeder Artikel einen Gewinn und ein Gewicht . Eine Lösung ist eine Zuordnung von Artikeln zu Behältern. Eine zulässige Lösung ist eine Lösung, bei der für jeden Behälter das Gesamtgewicht der zugeordneten Artikel höchstens beträgt . Der Gewinn der Lösung ist die Summe der Gewinne für jede Artikel-Platz-Zuordnung. Ziel ist es, eine möglichst gewinnbringende Lösung zu finden. ${\displaystyle a_{1}}$${\displaystyle a_{n}}$${\displaystyle b_{1}}$${\displaystyle b_{m}}$${\displaystyle b_{i}}$${\displaystyle t_{i}}$${\displaystyle b_{i}}$${\displaystyle a_{j}}$${\displaystyle p_{ij}}$${\displaystyle w_{ij}}$${\displaystyle b_{i}}$${\displaystyle t_{i}}$

Mathematisch lässt sich das verallgemeinerte Zuweisungsproblem als ganzzahliges Programm formulieren :

${\displaystyle {\begin{aligned}{\text{maximize}}&\sum _{i=1}^{m}\sum _{j=1}^{n}p_{ij}x_{ij}. \\{\text{vorbehaltlich }}&\sum _{j=1}^{n}w_{ij}x_{ij}\leq t_{i}&&i=1,\ldots ,m;\\&\ Summe _{i=1}^{m}x_{ij}=1&&j=1,\ldots ,n;\\&x_{ij}\in \{0,1\}&&i=1,\ldots ,m,\ quad j=1,\ldots ,n;\end{ausgerichtet}}}$

Komplexität

Das verallgemeinerte Zuweisungsproblem ist NP-schwer . Es gibt jedoch lineare Programmierungsrelaxationen, die eine -Approximation ergeben. ${\displaystyle (1-1/e)}$

Greedy-Approximationsalgorithmus

Für die Problemvariante, bei der nicht jedes Item einem Bin zugeordnet werden muss, gibt es eine Familie von Algorithmen zur Lösung der GAP durch eine kombinatorische Übersetzung eines beliebigen Algorithmus für das Rucksackproblem in einen Approximationsalgorithmus für die GAP.

Unter Verwendung eines beliebigen -Approximationsalgorithmus ALG für das Rucksackproblem ist es möglich, eine ( )-Approximation für das verallgemeinerte Zuweisungsproblem in gieriger Weise unter Verwendung eines Residualgewinnkonzepts zu konstruieren . Der Algorithmus erstellt einen Zeitplan in Iterationen, wobei während der Iteration eine vorläufige Auswahl von zu sortierenden Artikeln ausgewählt wird. Die Auswahl für die Bin kann sich ändern, wenn Elemente in einer späteren Iteration für andere Bins erneut ausgewählt werden. Der Restgewinn eines Artikels für Lagerplatz ist, wenn für keinen anderen Lagerplatz ausgewählt ist oder – wenn für Lagerplatz ausgewählt ist . ${\displaystyle\alpha}$${\displaystyle \alpha +1}$${\displaystyle j}$${\displaystyle b_{j}}$${\displaystyle b_{j}}$${\displaystyle x_{i}}$${\displaystyle b_{j}}$${\displaystyle p_{ij}}$${\displaystyle x_{i}}$${\displaystyle p_{ij}}$${\displaystyle p_{ik}}$${\displaystyle x_{i}}$${\displaystyle b_{k}}$

Formal: Wir verwenden einen Vektor , um den vorläufigen Zeitplan während des Algorithmus anzugeben. Konkret bedeutet , dass der Artikel auf Lagerplatz eingeplant ist und dass der Artikel nicht eingeplant ist. Der Restgewinn in der Iteration wird mit bezeichnet , wobei der Artikel nicht eingeplant ist (dh ) und wenn der Artikel auf Lagerplatz eingeplant ist (dh ). ${\displaystyle T}$${\displaystyle T[i]=j}$${\displaystyle x_{i}}$${\displaystyle b_{j}}$${\displaystyle T[i]=-1}$${\displaystyle x_{i}}$${\displaystyle j}$${\displaystyle P_{j}}$${\displaystyle P_{j}[i]=p_{ij}}$${\displaystyle x_{i}}$${\displaystyle T[i]=-1}$${\displaystyle P_{j}[i]=p_{ij}-p_{ik}}$${\displaystyle x_{i}}$${\displaystyle b_{k}}$${\displaystyle T[i]=k}$

Formal:

Satz ${\displaystyle T[i]=-1{\text{ for }}i=1\ldots n}$

Für tun: ${\displaystyle j=1,\ldots,m}$

Rufen Sie ALG auf, um mithilfe der Residualprofit-Funktion eine Lösung für die Aufteilung zu finden . Bezeichnen Sie die ausgewählten Elemente mit .${\displaystyle b_{j}}$${\displaystyle P_{j}}$${\displaystyle S_{j}}$

Aktualisieren Sie mit , dh für alle .${\displaystyle T}$${\displaystyle S_{j}}$${\displaystyle T[i]=j}$${\displaystyle i\in S_{j}}$

Siehe auch

• Zuordnungsproblem

Verweise

Weiterlesen

Kellerer, Hans; Pferschy, Ulrich; Pisinger, David (2013-03-19). Rucksackprobleme . ISBN 978-3-540-24777-7.

Externe Links