Simulation-Based Auction Protocol for Resource Scheduling Problems
Publication: Journal of Construction Engineering and Management
Volume 138, Issue 1
Abstract
Resource scheduling, or the allocation of resources over time, is a challenging problem in large-scale or multiple-project environments. Traditional network scheduling techniques are ineffective in modeling the dynamic nature and resource interactions of large or multiunit projects. This paper presents a simulation-based auction protocol (SBAP) to solve resource scheduling problems in large-scale construction projects. SBAP is a hybrid framework that integrates multi agent resource allocation (MARA) in a simulation environment. SBAP deploys a centralized resource allocation approach, referred to as an auction protocol, whereby agents bid on different combinations of resources at the start of a simulation cycle. Agents attempt to improve their individual welfare by acquiring a combination of resources; an auctioneer looks at the entire system and allocates resources to the agents using a combinatorial algorithm to maximize an overall objective function (e.g., maximizing the system’s revenue or minimizing total costs). The auction is repeated on a regular basis. Simulation is also employed in large-scale projects to track the availability of resources, capture and release the resources, and satisfy constraints of the problem. This paper demonstrates the architecture of the SBAP framework and discusses implementation of SBAP in a real case study of crane allocation in an industrial project.
Get full access to this article
View all available purchase options and get full access to this article.
Acknowledgments
This project was funded by the Natural Science and Engineering Research Council (NSERC) of Canada/Alberta under the Construction Industry Research Chair (IRC) and Collaborative Research and Development (CRD) grants. The support of PCL Industrial Management Inc. in accomplishing the crane scheduling case study is greatly appreciated. Particular gratitude is also extended to Holly Parkis for technical writing assistance, and to the reviewers of this paper.
References
AbouRizk, S., and Mohamed, Y. (2002). “Optimal construction project planning.” Proc. of the Winter Simulation Conf., 2, IEEE, New York, 1704–1708.
Arrow, K. J., Sen, A. K., and Suzumura, K. (2002). Handbook of social choice and welfare, Elsevier, Amsterdam, The Netherlands.
Bellifemine, F. L., Caire, G., and Greenwood, D. (2007). Developing multi-agent systems with JADE, Wiley, Chichester, UK.
Bertsekas, D. (1988). “The auction algorithm: A distributed relaxation method for the assignment problem.” Ann. Oper. Res., 14(1), 105–123.
Bertsekas, D. P. (1992). “Auction algorithms for network flow problems: A tutorial introduction.” Comput. Optim. Appl., 1(1), 7–66.
Borrego, D. (2004). “Simulation-based scheduling of module assembly yards with logical and physical constraints.” Ph.D. thesis, Univ. of Alberta, Edmonton, AB, Canada.
Buisman, H., Kruitbosch, G., and Peek, N. (2007). “Simulation in multiagent resource allocation.” Proc. of the 1st NSVKI Student Conf., Nederlandse Studievereniging Kunstmatige Intelligentie, The Netherlands.
Callan, S., and Thomas, J. M. (2004). “Modeling the market process.” Chapter 2, Environmental economics & management: Theory, policy, and applications, South-Western, Mason, OH.
Chevaleyre, Y., et al. (2006). “Issues in multiagent resource allocation.” Inf., 30(1), 3–31.
Chevaleyre, Y., Dunne, P. E., Endriss, U., Lang, J., Maudet, N., and Rodríguez-Aguilar, J. (2005). “Multiagent resource allocation.” Knowl. Eng. Rev., 20(2), 143–149.
Chevaleyre, Y., Endriss, U., Estivie, S., and Maudet, N. (2004). “Multiagent resource allocation with k-additive utility functions.” Proc. DIMACS-LAMSADE Workshop on Computer Science and Decision Theory, 3, ILLC, 83–100.
Chevaleyre, Y., Endriss, U., Estivie, S., and Maudet, N. (2008). “Multiagent resource allocation in k-additive domains: Preference representation and complexity.” Ann. Oper. Res., 163(1), 49–62.
Di Fatta, G., and Fortino, G. (2007). “A customizable multi-agent system for distributed data mining.” Proc. of the ACM Symp. on Applied Computing, Association for Computing Machinery, New York, 42–47.
Endriss, U., Maudet, N., Sadri, F., and Toni, F. (2006). “Negotiating socially optimal allocations of resources.” J. Artif. Intell. Res., 25, 315–348.
Engelbrecht-Wiggans, R. (1980). “Auctions and bidding models: A survey.” Manage. Sci., 26(2), 119–142.
Fatemi Ghomi, S. M. T., and Ashjari, B. (2002). “A simulation model for multi-project resource allocation.” Int. J. Proj. Manage., 20(2), 127–130.
Feng, C. (1998). “Applications of genetic algorithms for multi-objective resource allocation of construction projects under certainty.” Ph.D. thesis, Univ. of Illinois, Urbana-Champaign, IL.
Goncalves, J. F., Mendes, J. J. M., and Resende, M. G. C. (2008). “A genetic algorithm for the resource constrained multi-project scheduling problem.” Eur. J. Oper. Res., 189(3), 1171–1190.
Gopalakrishnan, K. N. (1998). “Design and development of a decision support system for scheduling steel fabrication projects.” Ph.D. thesis, Univ. of Alberta, Edmonton, AB, Canada.
Hajjar, D., and AbouRizk, S. M. (1996). “Building a special purposes simulation tool for earth moving operations.” Proc. of the 28th Conf. on Winter Simulation, IEEE, New York, 1313–1320.
Hajjar, D., and AbouRizk, S. M. (1999). “Simphony: An environment for building special purpose construction simulation tools.” Proc. of the 31st Conf. on Winter Simulation, IEEE, New York, 998–1006.
Halpin, D. W. (1977). “CYCLONE—Method for modeling job site processes.” J. Constr. Div., 103(3), 489–499.
Klemperer, P. (1999). “Auction theory: A guide to the literature.” J. Econ. Surv., 13(3), 227–286.
Kumar, V. (1992). “Algorithms for constraint-satisfaction problems: A survey.” AI Magazine, 13, 32–44.
Kutanoglu, E., and Wu David, S. (1999). “On combinatorial auction and Lagrangean relaxation for distributed resource scheduling.” IIE Trans., 31(9), 813–826.
Leu, S. S., Yang, C. H., and Huang, J. C. (2000). “Resource leveling in construction by GA-based optimization and its DSS application.” J. Autom. Constr., 10(1), 27–41.
Liu, Y., and Mohamed, Y. (2008). “Multi-agent resource allocation (MARA) for modeling construction processes.” Proc. of the 40th Conf. on Winter Simulation, IEEE, New York, 2361–2369.
Martinez, J. C., and Ioannou, P. G. (1994). “General purpose simulation with stroboscope.” Proc. of the 26th Conf. on Winter Simulation, IEEE, New York, 1159–1166.
McCabe, B. Y. (1997). “An automated modeling approach for construction performance improvement using simulation and belief networks.” Ph.D. thesis, Univ. of Alberta, Edmonton, AB, Canada.
Mohamed, Y., and AbouRizk, S. M. (2005). “Framework for building intelligent simulation models of construction operations.” J. Comput. Civ. Eng., 19(3), 277–291.
Mohamed, Y., Borrego, D., Francisco, L., Al-Hussein, M., Abourizk, S., and Hermann, U. (2007). “Simulation-based scheduling of module assembly yards: Case study.” Eng. Constr. Archit. Manage., 14(3), 293–311.
Moore, J. C., Rao, H. R., and Whinston, A. B. (1994). “Multi-agent resource allocation: An incomplete information perspective.” IEEE Trans. Syst. Man Cybern., 24(8), 1208–1219.
Mukherjee, A. (2005). “A multi-agent framework for general purpose situational simulations in construction management.” Ph.D. thesis, Univ. of Washington, Seattle, WA.
Nwana, H. S. (1996). “Software agents: An overview.” Knowl. Eng. Rev., 11(3), 205–244.
Parkes, D. C., and Ungar, L. H. (2001). “An auction-based method for decentralized train scheduling.” Proc. of the Int. Conf. on Autonomous Agents, Association for Computing Machinery, New York, 43–50.
Pinedo, M. (2008). Scheduling: Theory, algorithms, and systems, Springer, New York.
Pritsker, A. B. (1986). Introduction to simulation and SLAM II, Wiley, New York.
Reddy, H. R., and Varghese, K. (2002). “Automated path planning for mobile crane lifts.” Comput. Aided Civ. Infrastruct. Eng., 17(6), 439–448.
Ren, Z., and Anumba, C. J. (2004). “Multi-agent systems in construction–State of the art and prospects.” Autom. Constr., 13(3), 421–434.
Rothkopf, M. H., and Harstad, R. M. (1994). “Modeling competitive bidding: A critical essay.” Manage. Sci., 40(3), 364–384.
Sawhney, A. (1994). “Simulation-based planning for construction.” Ph.D. thesis, Univ. of Alberta, Edmonton, AB, Canada.
Sawhney, A. (2003). “Agent-based modeling and simulation in construction.” Proc. of the Winter Simulation Conf., 2, IEEE, New York, 1541–1547.
Schwindt, C. (2005). Resource allocation in project management, Springer, Berlin.
Shoham, Y., and Leyton-Brown, K. E. (2009). Multiagent systems: Algorithmic, game-theoretic, and logical foundations, Cambridge University Press, Cambridge, UK.
Smith, V. L. (1991). Papers in experimental economics, Cambridge University Press, Cambridge, UK.
Stark, R. M., and Rothkopf, M. H. (1979). “Competitive bidding: A comprehensive bibliography.” Oper. Res., 27(2), 364–390.
Sucur, M., and Grobler, F. (1996). “Construction planning through multiagent constraint satisfaction.” Proc. 3rd Congress of Computing in Civil Engineering, ASCE, Reston, VA, 240–246.
Taghaddos, H. (2010). “Developing a generic resource allocation framework for construction simulation.” Ph.D. thesis, Univ. of Alberta, Edmonton, AB, Canada.
Taghaddos, H., AbouRizk, S. M., Mohamed, Y., and Hermann, U. (2009). “Integrated simulation-based scheduling for module assembly yard.” Proc. of the 2009 Construction Research Congress, ASCE, Reston, VA, 1270–1279.
Taghaddos, H., AbouRizk, S. M., Mohamed, Y., and Hermann, U. (2010). “Simulation-based multiple heavy lift planning in industrial construction.” Proc. of the 2010 Construction Research Congress, ASCE, Reston, VA, 349–358.
Taghaddos, H., AbouRizk, S. M., Mohamed, Y., and Ourdev, I. (2008). “Distributed agent-based simulation of construction projects with HLA.” Proc. of the 2008 Winter Simulation Conf., IEEE, New York, 2413–2420.
Tantisevi, K., and Akinci, B. (2008). “Simulation-based identification of possible locations for mobile cranes on construction sites.” J. Comput. Civ. Eng., 22(1), 21–30.
Thompson, K., and Bordwell, D. (2010). Film history: An introduction, McGraw-Hill Higher Education, New York.
Tommelein, I. D. (1998). “Pull-driven scheduling for pipe-spool installation: Simulation of lean construction technique.” J. Constr. Eng. Manage., 124(4), 279–288.
Van Tol, A. A. (2005). “Agent embedded simulation modeling framework for construction engineering and management applications.” Ph.D. thesis, Univ. of Alberta, Edmonton, AB, Canada.
Varghese, K., Dharwadkar, P., Wolfhope, J., and O’Connor, J. T. (1997). “A heavy lift planning system for crane lifts.” Microcomput. Civ. Eng., 12(1), 31–42.
Vickrey, W. (1961). “Counterspeculation, auctions and competitive sealed tenders.” J. Finance, 16(1), 8–37.
Wang C., Ghenniwa, H., and Shen W. (2007a). “AdSCHE: An auction-based decentralized scheduling framework.” Proc. of IEEE SMC 2007, IEEE, New York, 2865–2870.
Wang, C., Ghenniwa, H., and Shen, W. (2007b). A winner determination algorithm for auction-based decentralized scheduling, Association for Computing Machinery, New York, 686–693.
Weiss, G. (1999). Multiagent systems: A modern approach to distributed artificial intelligence, Massachusetts Institute of Technology, Cambridge, MA.
Wellman, M. P., Walsh, W. E., Wurman, P. R., and MacKie-Mason, J. K. (2001). “Auction protocols for decentralized scheduling.” Games Econ. Behav., 35(1–2), 271–303.
Wilken, K., Liu, J., and Heffernan, M. (2000). “Optimal instruction scheduling using integer programming.” Proc. of the ACM SIGPLAN 2000 Conf. on Programming Language Design and Implementation, Association for Computing Machinery, New York, 121–133.
Zhou, F. (2006). “An integrated framework for tunnel shaft construction and site layout optimization.” Ph.D. thesis, Univ. of Alberta, Edmonton, AB, Canada.
Information & Authors
Information
Published In
Journal of Construction Engineering and Management
Volume 138 • Issue 1 • January 2012
Pages: 31 - 42
Copyright
© 2012 American Society of Civil Engineers.
History
Received: Dec 28, 2009
Accepted: Mar 29, 2011
Published online: Mar 31, 2011
Published in print: Jan 1, 2012
Authors
Metrics & Citations
Metrics
Citations
Download citation
If you have the appropriate software installed, you can download article citation data to the citation manager of your choice. Simply select your manager software from the list below and click Download.