Nicht lieferbar
Winner Determination in Combinatorial Auctions: Market-based Scheduling
Versandkostenfrei!
Nicht lieferbar
Eine kombinatorische Auktion zeichnet sich dadurch aus, dass mehrere Objekte simultan versteigert werden und die Bieter Gebote auf Teilmengen von Objekten abgeben k önnen. Gibt es keinerlei Beschränkungen bei der Gebotsabgabe, so gestaltet sich die optimale Zuordnung von Objekten zu Bietern (Gewinnerbestimmung) im Allgemeinen als NP--schwer. Dieses Buch besch äftigt sich vorrangig mit der Gewinnerbestimmung; es werden Optimierungs -modelle zu spezifischen kombinatorischen Auktionen aufgestellt und für ausgewählte Modelle Algorithmen entwickelt und getestet. Im Zentrum der Arbeit wird unte...
Eine kombinatorische Auktion zeichnet sich dadurch aus, dass mehrere Objekte simultan versteigert werden und die Bieter Gebote auf Teilmengen von Objekten abgeben k önnen. Gibt es keinerlei Beschränkungen bei der Gebotsabgabe, so gestaltet sich die optimale Zuordnung von Objekten zu Bietern (Gewinnerbestimmung) im Allgemeinen als NP--schwer. Dieses Buch besch äftigt sich vorrangig mit der Gewinnerbestimmung; es werden Optimierungs -modelle zu spezifischen kombinatorischen Auktionen aufgestellt und für ausgewählte Modelle Algorithmen entwickelt und getestet. Im Zentrum der Arbeit wird untersucht, wie eine fiktive Unternehmensleitung (Auktionator) mit Hilfe einer kombinatorischen Auktion Zeitfenster (Objekte) einer kapazit ätsbeschränkten Produktionsanlage auf Profit--Center (Bieter) verteilen kann. Als Optimierungsmodell wird das Weighted Job Interval Scheduling Problem identifiziert; die dafür entwickelte Lagrangeheuristik liefert in Rechenstudien im Mittel bessere untere Schranken als eine aus der Literatur ausgewählte Heuristik. In einer Verallgemeinerung werden knappe Budgets von Seiten der Profit--Center angenommen. In Rechenstudien zeigt sich, dass eine entwickelte Lagrange--Dekompostion bessere obere Schranken als die durch CPLEX berechnete LP--L ösung liefert und die Heuristik im Mittel gute untere Schranken findet. Des weiteren wird die Anwendung von kombinatorischen Auktionen in der Praxis analysiert; in einem Fall wird gezeigt, dass knappe Ressourcen in einem großen deutschen Versicherungsunternehmen effizienter mit einer kombinatorischen Auktion als mit einem von dem Unternehmen vorgeschlagenen Verfahren verteilt werden können. Des weiteren wird ein Pilotprojekt von DaimlerChrysler vorgestellt; hier wurde eine kombinatorische Ausschreibung zur Beschaffung von Transportkapazität erfolgreich angewendet.
In a combinatorial auction many items are put up for auction simultaneously and the bidders are allowed to place bids on subsets of items. If no restrictions on placing bids do exist, the assignment of items to bidders (winner determination) is proven to be NP-hard in the general case. This book focuses on deriving mathematical models and algorithms for the winner determination problem. Mainly, we show how scarce time slots (items) on a machine which is made available by the headquarters (auctioneer) can be assigned to profit--centers (bidders) using a combinatorial auction. The Weighted Job Interval Scheduling Problem serves as winner determination problem; runtime studies show that a Lagrangean heuristic outperforms a heuristic taken from the literature. Furthermore, we analyze the situation where the profit--centers are assumed to be budget--restricted. To solve the winner determination problem a Lagrangean decomposition is used; runtime studies show that our upper bounds outperform the LP--solution calculated by CPLEX and the proposed lower bounds seem to be tight. Afterwards, the application of combinatorial auctions in practice is studied. We state an allocation problem at a large German insurance company; it is shown, that combinatorial auctions can derive more efficient allocations than an algorithm proposed by the company. Finally, we provide the experiences of the first use of a combinatorial reverse auction at DaimlerChrysler where transportation capacity was successfully procured.
In a combinatorial auction many items are put up for auction simultaneously and the bidders are allowed to place bids on subsets of items. If no restrictions on placing bids do exist, the assignment of items to bidders (winner determination) is proven to be NP-hard in the general case. This book focuses on deriving mathematical models and algorithms for the winner determination problem. Mainly, we show how scarce time slots (items) on a machine which is made available by the headquarters (auctioneer) can be assigned to profit--centers (bidders) using a combinatorial auction. The Weighted Job Interval Scheduling Problem serves as winner determination problem; runtime studies show that a Lagrangean heuristic outperforms a heuristic taken from the literature. Furthermore, we analyze the situation where the profit--centers are assumed to be budget--restricted. To solve the winner determination problem a Lagrangean decomposition is used; runtime studies show that our upper bounds outperform the LP--solution calculated by CPLEX and the proposed lower bounds seem to be tight. Afterwards, the application of combinatorial auctions in practice is studied. We state an allocation problem at a large German insurance company; it is shown, that combinatorial auctions can derive more efficient allocations than an algorithm proposed by the company. Finally, we provide the experiences of the first use of a combinatorial reverse auction at DaimlerChrysler where transportation capacity was successfully procured.