Winner determination in combinatorial auctions: market based scheduling

Meer over het boek

Eine kombinatorische Auktion ermöglicht es, mehrere Objekte gleichzeitig zu versteigern, wobei Bieter Gebote auf Teilmengen abgeben können. Ohne Gebotsbeschränkungen gestaltet sich die optimale Zuordnung der Objekte zu den Bietern (Gewinnerbestimmung) als NP-schwer. Dieses Buch konzentriert sich auf die Entwicklung von Optimierungsmodellen und Algorithmen für die Gewinnerbestimmung. Im Mittelpunkt steht die Verteilung knapper Zeitfenster (Objekte) einer Produktionsanlage an Profit-Center (Bieter) durch einen Auktionator. Das Weighted Job Interval Scheduling Problem wird als Optimierungsmodell identifiziert; eine entwickelte Lagrangeheuristik zeigt in Rechenstudien bessere Ergebnisse als eine aus der Literatur stammende Heuristik. Zudem wird die Annahme von knappen Budgets der Profit-Center berücksichtigt. Hierbei liefert eine Lagrange-Dekomposition bessere obere Schranken als die LP-Lösung von CPLEX, während die Heuristik gute untere Schranken ermittelt. Die praktische Anwendung kombinatorischer Auktionen wird ebenfalls analysiert; ein Beispiel zeigt, dass ein großes deutsches Versicherungsunternehmen Ressourcen effizienter mit einer kombinatorischen Auktion als mit einem eigenen Verfahren verteilen kann. Zudem wird ein Pilotprojekt von DaimlerChrysler vorgestellt, bei dem eine kombinatorische Ausschreibung zur Beschaffung von Transportkapazitäten erfolgreich durchgeführt wurde.