Skip to main content
SpringerLink
Log in

On combinatorial auction and Lagrangean relaxation for distributed resource scheduling

  • Published:
IIE Transactions

Abstract

Most existing methods for scheduling are based on centralized or hierarchical decision making using monolithic models. In this study, we investigate a new method based on a distributed and locally autonomous decision structure using the notion of combinatorial auction. In combinatorial auction the bidders demand a combination of dependent objects with a single bid. We show that not only can we use this auction mechanism to handle complex resource scheduling problems, but there exist strong links between combinatorial auction and Lagrangean-based decomposition. Exploring some of these properties, we characterize combinatorial auction using auction protocols and payment functions. This study is a first step toward developing a distributed scheduling framework that maintains system-wide performance while accommodating local preferences and objectives. We provide some insights to this framework by demonstrating four different versions of the auction mechanism using job shop scheduling problems.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Sycara, K., Roth, S., Sadeh, N. and Fox, M. (1991) Distributed constraint heuristic search. IEEE Transactions on System, Man and Cybernetics, 21, 1446–1461.

    Google Scholar 

  2. Liu, J. and Sycara, K.P. (1993) Distributed constraint satisfaction through constraint partition and coordinated reaction, in Proceedings of the 12th International Workshop on Distributed Artificial Intelligence, Hidden Valley, PA.

  3. Liu, J. and Sycara, K.P. (1994) Distributed problem solving through coordination in a society of agents, in Proceedings of the 13th International Workshop on Distributed Artificial Intelligence, Seattle, WA.

  4. Liu, J. and Sycara, K.P. (1995) Exploiting problem structure for distributed constraint optimization, in Proceedings of the 1st International Conference on Multi-agent Systems, San Francisco, CA.

  5. Sadeh, N. (1991) MICRO-BOSS: a micro-opportunistic factory scheduler. Technical Report CMU-RI-TR-91–22, The Robotics Institute, Carnegie Mellon University, Pittsburgh, PA.

    Google Scholar 

  6. Davis, R. and Smith, R.G. (1983) Negotiation as a metaphor for distributed problem solving. Artificial Intelligence, 20, 63–109.

    Google Scholar 

  7. Parunak, H.V.D. (1987) Manufacturing experience with the contract net, in Distributed Artificial Intelligence, Huhns, M.N. (ed), Morgan Kaufmann Publishers, Los Altos, CA, pp. 285–310.

    Google Scholar 

  8. Parunak, H.V.D. (1996) Applications of distributed artificial intelligence, in Foundations of Distributed Arti®cial Intelligence, O'Hare, G.M.P. and Jennings, N.R. (eds), John Wiley and Sons, New York, NY, pp. 139–164.

    Google Scholar 

  9. Baker, A.D. (1996) Metaphor or reality: a case study where agents bid with actual costs to schedule a factory, in Market-Based Control: A Paradigm for Distributed Resource Allocation, Clear water, S.H. (ed), World Scientific, River Edge, NJ, pp. 184–224.

    Google Scholar 

  10. Upton, D.M., Barash, M.M. and Matheson, A.M. (1991) Architectures and auctions in manufacturing. International Journal of Computer Integrated Manufacturing, 4(1), 23–33.

    Google Scholar 

  11. Wang, K. and Veeramani, D. (1995) An adaptive machine bidding strategy for distributed shop-floor control under stochastic part demands, in 5th Industrial Engineering Research Conference Proceedings, Minneapolis, MN, pp. 321–326.

  12. Neiman, D.E., Hildum, D.W., Lesser, V.R. and Sandholm, T.W. (1994) Exploiting meta-level information in a distributed scheduling system, in Proceedings of the 12th Conference on Artificial Intelligence, Seattle, WA, pp. 394–400.

  13. Sandholm, T. (1993) An implementation of contract net protocol based on marginal cost calculations, in Proceedings of the 11th National Conference on Artificial Intelligence, Washington, DC, pp. 256–262.

  14. Wellman, M.P. (1996) Market-oriented programming: some early lessons, in Market-Based Control: A Paradigm for Distributed Resource Allocation, Clearwater, S.H. (ed), World Scientific, River Edge, NJ.

    Google Scholar 

  15. Wellman, M.P. (1993) A market-oriented programming environment and its application to distributed multicommodityflow problems. Journal of Artificial Intelligence Research, 1(1), 1–23.

    Google Scholar 

  16. Ygge, F. and Akkermans, H. (1998) On resource-oriented multicommodiy market computations, in Proceedings of the 4th International Conference on Multi-Agent Systems ICMAS'98, Paris, France.

  17. Wellman, M.P., Walsh, W.E., Wurman, P.R. and MacKie-Mason, J.K. (1998) Some economics of market-based distributed scheduling, in Eighteenth International Conference on Distributed Computing Systems, Amsterdam, Netherlands, pp. 612–621.

    Google Scholar 

  18. McAfee, R.P. and McMillan, J. (1987) Auctions and bidding. Journal of Economic Literature, 25(2), 699–738.

    Google Scholar 

  19. Vickrey, W. (1961) Counterspeculation, auctions and competitive sealed tenders. Journal of Finance, 16(1), 8–37.

    Google Scholar 

  20. Stark, R.M. and Rothkopf, M.H. (1979) Competitive bidding: a comprehensive bibliography. Operations Research, 27, 364–391.

    Google Scholar 

  21. Engelbrecht-Wiggans, R. (1980) Auctions and bidding models: a survey. Management Science, 26(2), 119–142.

    Google Scholar 

  22. Smith, V.L. (1991) Papers in Experimental Economics. Cambridge University Press, New York, NY.

    Google Scholar 

  23. Milgrom, P.R. and Weber, R.J. (1982) A theory of auctions and competitive bidding. Econometrica, 50(5), 1089–1122.

    Google Scholar 

  24. Engelbrecht-Wiggans, R. (1983) An introduction to the theory of bidding for a single object, in Auctions, Bidding, and Contracting: Uses and Theory, Engelbrecht-Wiggans, R., Shubik, M. and Stark, R.M. (eds), New York University Press, New York, pp. 53–103.

    Google Scholar 

  25. Rothkopf, M.H. and Harstad, R.M. (1994) Modeling competitive bidding: a critical essay. Management Science, 40(3), 364–384.

    Google Scholar 

  26. Hylland, A. and Zeckhauser, R. (1979) An efficient allocation of individuals to positions. Journal of Political Economy, 87(2), 293–314.

    Google Scholar 

  27. Leonard, H.B. (1983) Elicitation of honest preferences for the assignment of individuals to positions. Journal of Political Economy, 91(3), 461–479.

    Google Scholar 

  28. Demange, G., Gale, D. and Sotomayor, M. (1986) Multi-item auctions. Journal of Political Economy, 94(4), 863–872.

    Google Scholar 

  29. Sankaran, J.K. (1994) On a dynamic auction mechanism for a bilateral assignment problem. Mathematical Social Sciences,28(2), 143–150.

    Google Scholar 

  30. Bertsekas, D.P. (1988) The auction algorithm: a distributed relaxation method for the assignment problem. Annals of Operations Research, 14, 105–123.

    Google Scholar 

  31. Bertsekas, D.P. (1990) The auction algorithm for assignment and other network flow problems: a tutorial. Interfaces, 20(4), 133–149.

    Google Scholar 

  32. Bertsekas, D.P. (1991) Linear Network Optimization, MIT Press, Cambridge, MA.

    Google Scholar 

  33. Bertsekas, D.P. (1992) Auction algorithms for network flow problems. Computational Optimization and Applications, 1, 7–66.

    Google Scholar 

  34. Banks, J.S., Ledyard, J.O. and Porter, D.P. (1989) Allocating uncertain and unresponsive resources. RAND Journal of Economics, 20(1), 1–25.

    Google Scholar 

  35. Rothkopf, M.H., Pekec, A. and Harstad, R.M. (1998) Computationally manageable combinationial auctions. Management Science, 44(8), 1131–1147.

    Google Scholar 

  36. Graves, R.L., Schrage, L. and Sankaran, J.K. (1993) An auction method for course registration. Interfaces. 23(5), 81–92.

    Google Scholar 

  37. Rassenti, S.J., Smith, V.L. and Bulfin, R.L. (1982) A combinatorial auction mechanism for airport time slot allocation. Bell Journal of Economics, 13, 402–417.

    Google Scholar 

  38. Mas-Colell, A., Whinston, M.D. and Green, J.R. (1995) Microeconomic Theory, Oxford University Press, New York, NY.

    Google Scholar 

  39. Bikchandani, S. and Mamer, J.W. (1997) Competitive equilibrium in an exchange economy with indivisibilities. Journal of Economic Theory, 74, 385–413.

    Google Scholar 

  40. Ma, J. (1997) English auctions and Walrasian equilibria with multiple objects: a dynamic approach. Technical Report 91–02, Rutgers University, Camden, NJ.

    Google Scholar 

  41. Ma, J. (1998) Competitive equilibrium with indivisibilities. Technical Report 98–09, Rutgers University, Camden, NJ.

    Google Scholar 

  42. Gul, F. and Stacchetti, E. (1997) English and double auctions with differentiated commodities. Technical Report 97–02, University of Michigan, Ann Arbor, MI.

    Google Scholar 

  43. Gul, F. and Stacchetti, E. (1997) Walrasian equilibrium without complementarities. Technical Report 97–01, University of Michigan, Ann Arbor, MI.

    Google Scholar 

  44. Pinedo, M. (1995) Scheduling: Theory, Algorithms and Systems, Prentice Hall, Englewood Cliffs, N.J.

    Google Scholar 

  45. Jennergren, P. (1973) A price schedules decomposition algorithm for linear programming problems. Econometrica, 41(5), 965–979.

    Google Scholar 

  46. Jose, R.A., Harker, P.T. and Ungar, L.H. (1997) Auction and optimization: methods for closing the gap caused by discontinuities in demands. Technical Report, University of Pennsylvania, Philadelphia, PA.

    Google Scholar 

  47. Friedman, J.W. (1990) Game Theory With Applications to Economics, Oxford University Press, New York, NY.

    Google Scholar 

  48. Ichiishi, T. (1983) Game theory for Economic Analysis, Academic Press, New York, NY.

    Google Scholar 

  49. Pritsker, A., Watters, L. and Wolfe, P. (1969) Multiproject scheduling with limited resources: a zero-one programming approach. Management Science: Theory, 16(1), 93–108.

    Google Scholar 

  50. Roundy, R.O., Maxwell, W.L., Herer, Y.T., Tayur, S.R. and Getzler, A.W. (1991) A price directed approach to real-time scheduling of production operations. IIE Transactions, 23(2), 149–160.

    Google Scholar 

  51. Parker, R.G. and Rardin, R.L. (1988) Discrete Optimization, Academic Press, Inc., San Diego, CA.

    Google Scholar 

  52. Fisher, M.L. (1985) An application oriented guide to Lagrangian relaxation. Interfaces, 15(2), 10–21.

    Google Scholar 

  53. Lageweg, B., Lenstra, J.K. and Rinnooy Kan, A.H.G. (1997) Job shop scheduling by implicit enumeration. Management Science,24, 441–450.

    Google Scholar 

  54. Cohen, S.I. (1980) Incentives, iterative communication, and organizational control. Journal of Economic Theory, 22, 37–55.

    Google Scholar 

  55. Cohen, S.I. (1986) Truth-telling, dominant strategies, and iterative Groves mechanisms. Public Choice, 51, 333–343.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Industrial Engineering, Bell Engineering Center, University of Arkansas, Fayetteville, AR, 72701, USA

    Erhan Kutanoglu

  2. Manufacturing Logistics Institute, Department of Industrial and Manufacturing Systems Engineering, Lehigh University, 200 W. Packer Ave., Bethlehem, PA, 18015, USA

    S. David Wu

Authors
  1. Erhan Kutanoglu
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. S. David Wu
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints and permissions

About this article

Cite this article

Kutanoglu, E., Wu, S.D. On combinatorial auction and Lagrangean relaxation for distributed resource scheduling. IIE Transactions 31, 813–826 (1999). https://doi.org/10.1023/A:1007666414678

Download citation

  • Issue Date:

  • DOI: https://doi.org/10.1023/A:1007666414678

Keywords

Search

Navigation