IDEAS home Printed from https://ideas.repec.org/p/zbw/cauman/570.html
   My bibliography  Save this paper

Scheduling and combinatorial auctions: Lagrangean relaxation-based bonds for the WJISP

Author

Listed:
  • Elendner, Thomas

Abstract

In this paper we consider the following problem: a Company wants to sell consecutive time slots on a single machine. It wants to maximize the revenues, whereby market prizes are not known. Additionally, consider a number of potential buyers of those time slots providing each at least one job. All these jobs can be executed on that machine, but the number of time slots is not large enough to schedule all jobs. Furthermore assume, that every customer gains a job-specific profit with the processing of one of his jobs, whereby this profit is private information and thus, only known to him. What the company faces then is an allocation problem: Which buyer should get what time slot(s) at what prize in order to maximize the company's revenue. In the following we will show that this problem is well suited to be solved by a combinatorial auction. Within combinatorial auctions bidders are enabled to place bids on any subset of items that are auctioned off. We will focus on the winner determination problem for such an auction. The winner determination is understood as the assignment of items to bidders after all bids have been placed, with the objective to maximize the auctioneers outcome. It will be shown that the winner determination problem here can be described as so-called Weighted Job Interval Scheduling Problem (WJISP). Since this problem is known to be NP-hard, heuristics have become a main research interest. Unfortunately, there has not been done much research on upper bounds so far. Furthermore, to the best of our knowledge, no runtime studies are available in the literature yet. Here, we try to close these gaps. First, we present a Lagrangean heuristic for the WJISP and characterize relevant test instances. Using this test-bed, the considered upper and lower bounds are respectively compared to the LP-solution and to a heuristic taken from the literature.

Suggested Citation

  • Elendner, Thomas, 2003. "Scheduling and combinatorial auctions: Lagrangean relaxation-based bonds for the WJISP," Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel 570, Christian-Albrechts-Universität zu Kiel, Institut für Betriebswirtschaftslehre.
    • Handle: RePEc:zbw:cauman:570
    as

    Download full text from publisher

    File URL: https://www.econstor.eu/bitstream/10419/147634/1/manuskript_570.pdf
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Piotr Berman & Bhaskar Dasgupta, 2000. "Multi-phase Algorithms for Throughput Maximization for Real-Time Scheduling," Journal of Combinatorial Optimization, Springer, vol. 4(3), pages 307-323, September.
    2. J.M. van den Akker & C.A.J. Hurkens & M.W.P. Savelsbergh, 2000. "Time-Indexed Formulations for Machine Scheduling Problems: Column Generation," INFORMS Journal on Computing, INFORMS, vol. 12(2), pages 111-124, May.
    3. Marshall L. Fisher, 1981. "The Lagrangian Relaxation Method for Solving Integer Programming Problems," Management Science, INFORMS, vol. 27(1), pages 1-18, January.
    4. Sven de Vries & Rakesh V. Vohra, 2003. "Combinatorial Auctions: A Survey," INFORMS Journal on Computing, INFORMS, vol. 15(3), pages 284-309, August.
    5. John McMillan, 1994. "Selling Spectrum Rights," Journal of Economic Perspectives, American Economic Association, vol. 8(3), pages 145-162, Summer.
    6. Wolfstetter,Elmar, 2000. "Topics in Microeconomics," Cambridge Books, Cambridge University Press, number 9780521645348, January.
    7. E. William Moore & Janice M. Warmke & Lonny R. Gorban, 1991. "The Indispensable Role of Management Science in Centralizing Freight Operations at Reynolds Metals Company," Interfaces, INFORMS, vol. 21(1), pages 107-129, February.
    8. S.J. Rassenti & V.L. Smith & R.L. Bulfin, 1982. "A Combinatorial Auction Mechanism for Airport Time Slot Allocation," Bell Journal of Economics, The RAND Corporation, vol. 13(2), pages 402-417, Autumn.
    9. Wellman, Michael P. & Walsh, William E. & Wurman, Peter R. & MacKie-Mason, Jeffrey K., 2001. "Auction Protocols for Decentralized Scheduling," Games and Economic Behavior, Elsevier, vol. 35(1-2), pages 271-303, April.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Elendner, Thomas & Femerling, R., 2003. "Allocation of in-house services: Experimental comparison of allocation mechanisms," Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel 577, Christian-Albrechts-Universität zu Kiel, Institut für Betriebswirtschaftslehre.
    2. Jawad Abrache & Teodor Crainic & Michel Gendreau & Monia Rekik, 2007. "Combinatorial auctions," Annals of Operations Research, Springer, vol. 153(1), pages 131-164, September.
    3. Drexl, Andreas & Jørnsten, Kurt & Knof, Diether, 2009. "Non-linear anonymous pricing combinatorial auctions," European Journal of Operational Research, Elsevier, vol. 199(1), pages 296-302, November.
    4. Oktay Günlük & Lászlo Ladányi & Sven de Vries, 2005. "A Branch-and-Price Algorithm and New Test Problems for Spectrum Auctions," Management Science, INFORMS, vol. 51(3), pages 391-406, March.
    5. Tuomas Sandholm & David Levine & Michael Concordia & Paul Martyn & Rick Hughes & Jim Jacobs & Dennis Begg, 2006. "Changing the Game in Strategic Sourcing at Procter & Gamble: Expressive Competition Enabled by Optimization," Interfaces, INFORMS, vol. 36(1), pages 55-68, February.
    6. A Drexl & K Jørnsten, 2007. "Reflections about pseudo-dual prices in combinatorial auctions," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 58(12), pages 1652-1659, December.
    7. Park, Sunju & Rothkopf, Michael H., 2005. "Auctions with bidder-determined allowable combinations," European Journal of Operational Research, Elsevier, vol. 161(2), pages 399-415, March.
    8. Farnia, Farnoush & Frayret, Jean-Marc & Beaudry, Catherine & Lebel, Luc, 2015. "Time-based combinatorial auction for timber allocation and delivery coordination," Forest Policy and Economics, Elsevier, vol. 50(C), pages 143-152.
    9. Drexl, Andreas & Jørnsten, Kurt & Knof, Diether, 2007. "Column aggregation-based pricing combinatorial auctions," Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel 624, Christian-Albrechts-Universität zu Kiel, Institut für Betriebswirtschaftslehre.
    10. Tuomas Sandholm & Subhash Suri & Andrew Gilpin & David Levine, 2005. "CABOB: A Fast Optimal Algorithm for Winner Determination in Combinatorial Auctions," Management Science, INFORMS, vol. 51(3), pages 374-390, March.
    11. Martin Bichler & Alexander Pikovsky & Thomas Setzer, 2009. "An Analysis of Design Problems in Combinatorial Procurement Auctions," Business & Information Systems Engineering: The International Journal of WIRTSCHAFTSINFORMATIK, Springer;Gesellschaft für Informatik e.V. (GI), vol. 1(1), pages 111-117, February.
    12. Mishra, Debasis & Parkes, David C., 2007. "Ascending price Vickrey auctions for general valuations," Journal of Economic Theory, Elsevier, vol. 132(1), pages 335-366, January.
    13. Nicolas Gruyer & Nathalie Lenoir, 2003. "Auctioning airport slots (?)," Post-Print hal-01021718, HAL.
    14. Charles L. Jackson, 2011. "Coase and the New Zealand Spectrum Reforms," Journal of Law and Economics, University of Chicago Press, vol. 54(S4), pages 189-205.
    15. Robert W. Day & Peter Cramton, 2012. "Quadratic Core-Selecting Payment Rules for Combinatorial Auctions," Operations Research, INFORMS, vol. 60(3), pages 588-603, June.
    16. Dellbrügge, Marius & Brilka, Tim & Kreuz, Felix & Clausen, Uwe, 2022. "Auction design in strategic freight procurement," Chapters from the Proceedings of the Hamburg International Conference of Logistics (HICL), in: Kersten, Wolfgang & Jahn, Carlos & Blecker, Thorsten & Ringle, Christian M. (ed.), Changing Tides: The New Role of Resilience and Sustainability in Logistics and Supply Chain Management – Innovative Approaches for the Shift to a New , volume 33, pages 295-325, Hamburg University of Technology (TUHH), Institute of Business Logistics and General Management.
    17. Bourbeau, Benoit & Gabriel Crainic, Teodor & Gendreau, Michel & Robert, Jacques, 2005. "Design for optimized multi-lateral multi-commodity markets," European Journal of Operational Research, Elsevier, vol. 163(2), pages 503-529, June.
    18. Sulin Ba & Jan Stallaert & Andrew B. Whinston, 2001. "Optimal Investment in Knowledge Within a Firm Using a Market Mechanism," Management Science, INFORMS, vol. 47(9), pages 1203-1219, September.
    19. Lawrence M. Ausubel & Peter Cramton & Paul Milgrom, 2012. "System and Method for a Hybrid Clock and Proxy Auction," Papers of Peter Cramton 12acmhc, University of Maryland, Department of Economics - Peter Cramton, revised 2012.
    20. Vangerven, Bart & Goossens, Dries R. & Spieksma, Frits C.R., 2017. "Winner determination in geometrical combinatorial auctions," European Journal of Operational Research, Elsevier, vol. 258(1), pages 254-263.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:zbw:cauman:570. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: ZBW - Leibniz Information Centre for Economics (email available below). General contact details of provider: https://edirc.repec.org/data/ibkiede.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.