Utility pricing auction for multi-period resource allocation in multi-machine flow shop problems

ABSTRACT

In this paper, we consider a multi-machine multi-period resource allocation problem among multiple agents, each of which is responsible to solve a flowshop scheduling problem. We present an iterated combinatorial auction approach in which bid generation is performed within each agent, and the concept of utility pricing is then applied in the process of price adjustment. We compare with the conventional price adjustment scheme proposed in Fisher (1985), and show better convergence properties. Experimentally, we compare our approach against an integer programming model as well as conventional price adjustment schemes, and achieve drastic run time improvement.

REFERENCES

• 1: S. Bikhchandani and J. W. Mamer. Competitive equilibrium in an exchange economy with indivisibilities. Journal of Economic Theory, 74(2):385--413, 1997.
• 2: John Q. Cheng , Michael P. Wellman, The WALRAS Algorithm: A Convergent Distributed Implementation of General Equilibrium Outcomes, Computational Economics, v.12 n.1, p.1-24, August 1998 [doi>10.1023/A:1008654125853]
• 3: G. Confessore, S. Giordani, S. Rismondo, A market-based multi-agent system model for decentralized multi-project scheduling, Annals of Operations Research, Vol.150, No.1, pp.115--135, 2007.
• 4: M. L. Fisher An application oriented guide to Lagrangian relaxation. Interfaces, 15(2):pp.10--21, 1985.
• 5: Ross A. Gagliano , Martin D. Fraser , Mark E. Schaefer, Auction allocation of computing resources, Communications of the ACM, v.38 n.6, p.88-102, June 1995 [doi>10.1145/203241.203262]
• 6: P. Joyce. The Walarsian tatonnement mechanism and information. RAND Journal of Economics, 15(3):pp.416--425, 1984.
• 7: E. Kutanoglu and S. D. Wu. On combinatorial auction and Lagrangean relaxation for distributed resource scheduling. IIE Transactions, 31, 1999.
• 8: E. Kutanoglu, S. David Wu, Improving Scheduling Robustness via Preprocessing and Dynamic Adaptation, IIE Transactions, vol.36, pp.1107--1124, 2004.
• 9: A. B. Pritsker, L. J. Watters and P. Wolfe. Multi-project scheduling with limited resources: a zero-one programming approach. Management Science: Theory, 16(1):pp.93--108, 1969.
• 10: E. Toczywski, I. Zoltowska, "A new pricing scheme for a multi-period pool-based electricity auction", to appear European Journal of Operational Research (2008),
• 11: L. Walras. Elements of pure economics. Homewood, Irwin, 1954.
• 12: M. P. Wellman, W. E. Walsh, P. R. Wurman and J. K. MacKie-Mason. Auction protocols for decentralized scheduling. Games and Economic Behavior, 35, 2001.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sequencing and scheduling

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.11 Distributed Artificial Intelligence
            Subjects: Multiagent systems
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Scheduling

General Terms:
Algorithms, Experimentation