Winner determination in combinatorial auctions: market based scheduling

Hochschulschrift

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{ ss}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. [.5cm] 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.

Angaben zum Objekt

• Standort: Deutsche Nationalbibliothek Frankfurt am Main
• ISBN: 9783832505585 ; 383250558X
• Maße: 21 cm
• Umfang: VII, 185 S.
• Sprache: Englisch
• Anmerkungen: graph. Darst. ; Zugl.: Kiel, Univ., Diss., 2003

Klassifikation und Themen

• Klassifikation: Wirtschaft
• Schlagwort: Auktionstheorie ; Scheduling

Beteiligte, Orts- und Zeitangaben

• Ereignis: Veröffentlichung
• (wo): Berlin
• (wer): Logos-Verl.
• (wann): 2004
• Urheber: Elendner, Thomas

Weitere Informationen

• Inhaltsverzeichnis: https://d-nb.info/970949812/04
• Rechteinformation: Bei diesem Objekt liegt nur das Inhaltsverzeichnis digital vor. Der Zugriff darauf ist unbeschränkt möglich.
• Letzte Aktualisierung: 11.06.2025, 13:48 MESZ