A Clock‐and‐Offer Auction Market for Grid Resources When Bidders Face Stochastic Computational Needs

A Clock‐and‐Offer Auction Market for Grid Resources When Bidders Face Stochastic Computational Needs

0.00 Avg rating0 Votes
Article ID: iaor201111060
Volume: 23
Issue: 4
Start Page Number: 630
End Page Number: 647
Publication Date: Sep 2011
Journal: INFORMS Journal on Computing
Authors: , , , ,
Keywords: allocation: resources, heuristics, programming: transportation
Abstract:

Although significant technical advances have been made in the commercial deployment of grid computing, the pricing and allocation of distributed computing resources remains understudied. We develop a customized clock auction that is able to allocate grid resources and discover separate prices for the different computing resources under the condition that buyers do not know with certainty how much of these resources they will need. The proposed clock auction facilitates the discovery of unit prices for the resources in each time period in a finite‐horizon market. Our mechanism exploits the lopsided nature of the grid market where a small number of large‐scale jobs are expected to be completed by a large number of heterogeneous, distributed machines. The traditional stopping rule used for clock auctions is not effective in our setting, and therefore we design several adaptations that can be implemented in real time, geared toward ending the auction process quickly while producing a close‐to‐efficient allocation. Our extensive computations show that our clock‐and‐offer auction outperforms the traditional clock auction in terms of computational tractability, social welfare, and expected bidder's utility. For large problems of practical interest, we develop a transportation‐based heuristic for the NP‐complete bid feasibility problem and demonstrate theoretically and computationally that it quickly produces high‐quality solutions to the overall problem.

Reviews

Required fields are marked *. Your email address will not be published.