Wang, Chun (2011) AdSCHE: DESIGN OF AN AUCTION-BASED FRAMEWORK FOR DECENTRALIZED SCHEDULING. Journal of Integrated Design and Process Science, 15 (2). pp. 17-36. ISSN 1875-8959
Preview |
Text (application/pdf)
982kBwang2011b.pdf - Accepted Version |
Official URL: http://iospress.metapress.com/content/e11202213tm4...
Abstract
Decentralized scheduling is one of the newly emerged avenues in scheduling research. It is concerned with allocating resources to alternative possible uses over time, where competing uses are represented by autonomous agents. Compared with classical scheduling models, decentralized scheduling is characterized with the distribution of scheduling knowledge and control, which introduces new levels of complexities, namely the coordination complexity due to the interaction problems among agents and the mechanism design complexity due to the self-interested nature of agents. These complexities intertwine and need to be addressed concurrently. This paper presents an auction-based framework which tackles coordination and mechanism design complexities through integrating an iterative bidding protocol, a requirement-based bidding language, and a constraint-based winner determination approach. Without imposing a time window discretization on resources the requirement-based bidding language allows bidders to bid for the processing of a set of jobs with constraints. Prices can be attached to quality attributes of schedules. The winner determination algorithm uses a depth-first branch and bound search. A constraint directed scheduling procedure is used at each node to verify the feasibility of the allocation. The bidding procedure is implemented by an ascending auction protocol. Experimental results show that the proposed auction framework exhibits improved computational properties compared with the general combinatorial auctions. A case study of applying the framework to decentralized media content scheduling in narrowcasting is also presented.
| Divisions: | Concordia University > Gina Cody School of Engineering and Computer Science > Concordia Institute for Information Systems Engineering |
|---|---|
| Item Type: | Article |
| Refereed: | Yes |
| Authors: | Wang, Chun |
| Journal or Publication: | Journal of Integrated Design and Process Science |
| Date: | 2011 |
| Keywords: | decentralized scheduling, combinatorial auctions, iterative bidding, bidding languages, winner determination |
| ID Code: | 976810 |
| Deposited By: | Danielle Dennie |
| Deposited On: | 28 Jan 2013 16:52 |
| Last Modified: | 18 Jan 2018 17:43 |
References:
Beck, J.C. and Fox, M.S. “A Generic Framework for Constraint-Directed Search and Scheduling,” AI Magazine, vol. 19, No. 4, pp. 101-130, 1998.Boutilier, C., Goldszmidt, M., and Sabata, B., "Sequential auctions for the allocation of resources with complementarities," in Proc. 16th International Joint Conference on Artificial Intelligence (IJCAI-99), Stockholm, 1999, pp. 527-534.
Boutilier C. and Hoos, H. H., "Bidding languages for combinatorial auctions," in Proc. 17th International Joint Conference on Artificial Intelligence, Seattle, Washington, 2001, pp. 1211–1217
Brewer, P. J. and Plott, C. R., "A binary conflict ascending price (BICAP) mechanism for the decentralized allocation of the right to use railroad tracks," International Journal of Industrial Organization, vol. 14, pp. 857-886, 1996
Buyya, R., Abramson, D., Giddy, J., and Stockinger, H., “Economic models for resource management and scheduling in Grid computing,” Concurrency and Computation: Practice and Experience, vol. 14, pp. 1507-1542, 2002.
DeMartini, C., Kwasnica, A. M., Ledyard, J. O., and Porter, D., “A new and improved design for multi-object iterative auctions,” Technical report SSWP 1054, CalTech, March 1999.
de Vries, S. and Vohra, R.V., “Combinatorial Auctions: Survey,” INFORMS journal on Computing, vol.15, no.3, pp.284-309, 2003.
Engelbrecht-Wiggans, R. and Weber, R. J., "A sequential auction involving asymmetrically-informed bidders," International Journal of Game Theory, vol. 12, pp. 123-127, 1983.
Garey, M.R. and Johnson, D. S., Computers and Intractability, a Guide to the Theory of NP-Completeness, W. H. Freeman Company, 1979.
Kutanoglu, E. and Wu, S. D., "On combinatorial auction and Lagrangean relaxation for distributed resource scheduling," IIE Transactions, vol. 31, pp. 813-826, 1999.
Kutanoglu, E. and Wu, S. D., "Incentive compatible, collaborative production scheduling with simple communication among distributed agents," International Journal of Production Research, vol. 44, pp. 421-446, 2006.
Ledyard, J.O., Porter, D., and Rangel, A., “Experiments testing multiobject allocation mechanisms,” Journal of Economic and Management Strategy, vol. 6, pp. 639-675, 1997.
Mackie-Mason, J. K., Osepayshvili, A., Reeves, D. M., and Wellman, M. P., "Price prediction strategies for market-based scheduling," in Proc. 14th International Conference on Automated Planning and Scheduling, Whistler, BC, 2004.
McAfee, R. P. and McMillan, J., "Analyzing the airwaves auction," The Journal of Economic Perspectives, vol. 10, pp. 159-175, 1996.
Milgrom, P., "Putting auction theory to work: the simultaneous ascending auction," Journal of Political Economy, vol. 108, pp. 245-272, 2000.
Parkes, D. C., “iBundle: An Efficient Ascending Price Bundle Auction,” In Proc. 1st ACM Conf. on Electronic Commerce (EC-99), pp. 148-157, 1999.
Parkes, D. C. and Ungar, L. H., "Iterative combinatorial auctions: theory and practice," in Proc. 17th National Conference on Artificial Intelligence, Austin, TX. , 2000, pp. 74–81.
Parkes, D. C. and Ungar, L. H., "An auction-based method for decentralized train scheduling," in Proc. 5th International Conference on Autonomous Agents, Montreal, Quebec, 2001, pp. 43-50.
Pinedo, M., Scheduling: Theory, Algorithms, and Systems: Prentice Hall, 2002.
Rassenti, S. J., Smith V. L., and Bulfin, R. L., “A Combinatorial Auction Mechanism for Airport Time Slot Allocation,” Bell Journal of Economics, vol. 13, no. 2, pp. 402-417, 1982.
Reeves, D. M., Wellman, M. P., MacKie-Mason, J. K., and Osepayshvili, A., "Exploring bidding strategies for market-based scheduling," Decision Support Systems, vol. 39, pp. 67-85, 2005.
Sandholm, T., "Distributed rational decision making," in Multiagent Systems: A Modern Approach to Distributed Artificial Intelligence, Cambridge, MA: MIT Press, 1999.
Sandholm, T., "Algorithm for optimal winner determination in combinatorial auctions," Artificial Intelligence, vol. 135, pp. 1-54, 2002.
Sandholm, T., Suri, S., Gilpin, A., and Levine, D., "CABOB: a fast optimal algorithm for winner determination in combinatorial auctions," Management Science, vol. 51, pp. 374-390, 2005.
Shen, W., "Distributed manufacturing scheduling using intelligent agents," IEEE intelligent systems, pp. 88-94, 2002.
Shen, W., Wang, L., and Qi, H., "Agent-based distributed manufacturing process planning and scheduling: a state-of-the-art survey," IEEE Transactions on Systems, Man, and Cybernetics, Part C: Applications and Reviews, vol. 36, pp. 563-577, 2006.
Smith, A., The wealth of nations, Cannan edition (Modern Library, New York), 1937.
Smith, R. G., "The contract net protocol: High-level communication and control in a distributed problem solver," IEEE Transactions on computers, vol. 100, pp. 1104-1113, 1980.
Smith, S.F. and Cheng, C., “Slack-Based Heuristics for Constraint Satisfaction Scheduling,” In Proceedings of 11th National Conference on Artificial Intelligence. Washington D.C., July 1993.
Smith, S.F. and Becker, M.A., "An Ontology for Constructing Scheduling Systems", Working Notes of 1997 AAAI Symposium on Ontological Engineering, Stanford, CA, March. AAAI Press
Walsh, W. E. and Wellman, M. P., "Efficiency and equilibrium in task allocation economies with hierarchical dependencies," in Proc. 6th International Joint Conference on Artificial Intelligence, Stockholm, 1999, pp. 520-526.
Wang, C., Ghenniwa, H., and Shen, W., "Bidding languages for auction-based distributed scheduling," in Proc. 2009 IEEE International Conference on Systems, Man, and Cybernetics San Antonio, Texas, 2009a, pp. 4518-4523.
Wang, C., Ghenniwa, H. H., and Shen, W. Constraint-based winner determination for auction-based scheduling. IEEE Transactions on Systems, Man and Cybernetics, Part A: Systems and Humans 39(3), 609-618, 2009b.
Wellman, M. P., "A computational market model for distributed configuration design," AI EDAM, vol. 9, pp. 125-133, 1995.
Wellman, M. P., W. E. Walsh, P. R. Wurman, and J. K. MacKie-Mason, “Auction Protocols for Decentralized Scheduling”, Games and Economic Behavior, vol.35, no.1-2, pp.271-303, 2001.
Repository Staff Only: item control page
Download Statistics
Download Statistics