MENÜ MENÜ  

cover

Winner Determination in Combinatorial Auctions: Market-based Scheduling

Thomas Elendner

ISBN 978-3-8325-0558-5
193 pages, year of publication: 2004
price: 40.50 €
Inhalt:
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 Optimierungsmodelle 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.

content:
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.

Keywords:
  • Combinatorial Auctions
  • Winner Determination
  • Resource Allocation
  • Scheduling
  • Combinatorial Optimization

BUYING OPTIONS

40.50 €
in stock
cover cover cover cover cover cover cover cover cover