{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,2,29]],"date-time":"2024-02-29T10:44:23Z","timestamp":1709203463459},"reference-count":36,"publisher":"University of Zielona G\u00f3ra, Poland","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2011,6,1]]},"abstract":"<jats:title>Modern approaches to modeling user requirements on resource and task allocation in hierarchical computational grids<\/jats:title>\n        <jats:p>Tasks scheduling and resource allocation are among crucial issues in any large scale distributed system, including Computational Grids (CGs). These issues are commonly investigated using traditional computational models and resolution methods that yield near-optimal scheduling strategies. One drawback of such approaches is that they cannot effectively tackle the complex nature of CGs. On the one hand, such systems account for many administrative domains with their own access policies, user privileges, etc. On the other, CGs have hierarchical nature and therefore any computational model should be able to effectively express the hierarchical architecture in the optimization model. Recently, researchers have been investigating the use of game theory for modeling user requirements regarding task and resource allocation in grid scheduling problems. In this paper we present two general non-cooperative game approaches, namely, the <jats:italic>symmetric non-zero sum<\/jats:italic> game and the <jats:italic>asymmetric Stackelberg<\/jats:italic> game for modeling grid user behavior defined as user requirements. In our game-theoretic approaches we are able to cast new requirements arising in allocation problems, such as asymmetric users relations, security and reliability restrictions in CGs. For solving the games, we designed and implemented GA-based hybrid schedulers for approximating the equilibrium points for both games. The proposed hybrid resolution methods are experimentally evaluated through the grid simulator under heterogeneity, and large-scale and dynamics conditions. The relative performance of the schedulers is measured in terms of the makespan and flowtime metrics. The experimental analysis showed high efficiency of meta-heuristics in solving the game-based models, especially in the case of an additional cost of secure task scheduling to be paid by the users.<\/jats:p>","DOI":"10.2478\/v10006-011-0018-x","type":"journal-article","created":{"date-parts":[[2011,6,23]],"date-time":"2011-06-23T01:13:30Z","timestamp":1308791610000},"page":"243-257","source":"Crossref","is-referenced-by-count":18,"title":["Modern approaches to modeling user requirements on resource and task allocation in hierarchical computational grids"],"prefix":"10.61822","volume":"21","author":[{"given":"Joanna","family":"Ko\u0142odziej","sequence":"first","affiliation":[]},{"given":"Fatos","family":"Xhafa","sequence":"additional","affiliation":[]}],"member":"37438","reference":[{"key":"1","first-page":"45","article-title":"Nature's heuristics for scheduling jobs on computational grids","author":"A. Abraham","year":"2000"},{"key":"2","first-page":"185","article-title":"Task execution time modeling for heterogeneous computing system","author":"S. Ali","year":"2000"},{"key":"3","volume-title":"Dynamic Non-cooperative Game Theory","author":"T. Ba\u00e7sar","year":"1995"},{"issue":"3-4","key":"4","doi-asserted-by":"crossref","first-page":"231","DOI":"10.1155\/2006\/670375","article-title":"An approach for the high-level specification of qos-aware grid workflows considering location affinity","volume":"14","author":"I. Brandic","year":"2006","journal-title":"Scientific Programming"},{"issue":"6","key":"5","doi-asserted-by":"crossref","first-page":"810","DOI":"10.1006\/jpdc.2000.1714","article-title":"A comparison of eleven static heuristics for mapping a class of independent tasks onto heterogeneous distributed computing systems","volume":"61","author":"T. Braun","year":"2001","journal-title":"Journal of Parallel and Distributed Computing"},{"key":"6","first-page":"517","article-title":"An economy driven resource management architecture for global computational power grids","author":"R. Buyya","year":"2000"},{"issue":"13-15","key":"7","doi-asserted-by":"crossref","first-page":"1507","DOI":"10.1002\/cpe.690","article-title":"Economic models for resource management and scheduling in grid computing","volume":"14","author":"R. Buyya","year":"2002","journal-title":"Journal of Concurrency and Computation: Practice and Experience"},{"key":"8","doi-asserted-by":"crossref","DOI":"10.1002\/9780470455432","volume-title":"Market Oriented Grid and Utility Computing","author":"R. Buyya","year":"2009"},{"issue":"1","key":"9","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1007\/BF02614234","article-title":"On a formulation of discrete n-person non-cooperative games","volume":"18","author":"L. Edlefsen","year":"1972","journal-title":"Metrika"},{"key":"10","first-page":"139","article-title":"Scheduling parallel aplications on utility grids: Time and cost trade-off management","volume":"91","author":"S. Garg","year":"2009"},{"issue":"11","key":"11","doi-asserted-by":"crossref","first-page":"1366","DOI":"10.1016\/j.jpdc.2005.05.013","article-title":"A game theory based pricing strategy for job allocation in mobile grids","volume":"65","author":"P. Ghosh","year":"2005","journal-title":"Journal of Parallel and Distributed Computing"},{"issue":"3","key":"12","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1023\/B:GRID.0000035187.54694.75","article-title":"A flexible framework for fault tolerance in the grid","volume":"1","author":"S. Hwang","year":"2003","journal-title":"Journal of Grid Computing"},{"key":"13","first-page":"101","article-title":"Non-cooperative, semi-cooperative, and cooperative games-based grid resource allocation","author":"S. Khan","year":"2006"},{"key":"14","first-page":"93","article-title":"A game-theoretic and hybrid genetic meta-heuristic model for security-assured scheduling of independent jobs in computational grids","author":"J. Ko\u0142odziej","year":"2010"},{"key":"15","first-page":"108","article-title":"Hierarchic genetic scheduler of independent jobs in computational grid environment","author":"J. Ko\u0142odziej","year":"2009"},{"issue":"5","key":"16","first-page":"1","article-title":"Selfish grids: Game-theoretic modeling and nas\/psa benchmark evaluation","volume":"18","author":"Y.-K. Kwok","year":"2007","journal-title":"IEEE Transactions on Parallel and Distributing Systems"},{"issue":"5","key":"17","doi-asserted-by":"crossref","first-page":"702","DOI":"10.1016\/j.future.2007.01.002","article-title":"A framework model for grid security","volume":"23","author":"G. Laccetti","year":"2007","journal-title":"Future Generation Computer System"},{"issue":"4","key":"18","doi-asserted-by":"crossref","first-page":"658","DOI":"10.1016\/j.future.2006.10.008","article-title":"Efficient hierarchical parallel genetic algorithms using grid computing","volume":"23","author":"D. Lim","year":"2007","journal-title":"Future Generation Computer System"},{"key":"19","first-page":"303","article-title":"Enhancing grid security with trust management","author":"C. Lin","year":"2004"},{"issue":"8","key":"20","doi-asserted-by":"crossref","first-page":"1336","DOI":"10.1016\/j.future.2009.05.022","article-title":"Scheduling jobs on computational grids using a fuzzy particle swarm optimization algorithm","volume":"26","author":"H. Liu","year":"2009","journal-title":"Future Generation Computer System"},{"issue":"1","key":"21","first-page":"91","article-title":"Evolutionary alogorithms for job-shop scheduling","volume":"14","author":"K. Mesghouni","year":"2004","journal-title":"International Journal of AppliedMathematics and Computer Science"},{"issue":"1","key":"22","doi-asserted-by":"crossref","first-page":"113","DOI":"10.1016\/j.cam.2004.06.005","article-title":"Computing nash equilibria through computational intelligence methods","volume":"175","author":"N. Pavlidis","year":"2005","journal-title":"Journal of Computational and Applied Mathematics"},{"issue":"1-2","key":"23","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1016\/S0167-9236(99)00067-6","article-title":"The popcorn market\u2014Online markets for computational resources","volume":"28","author":"O. Regev","year":"2000","journal-title":"Decision Support Systems"},{"key":"24","volume-title":"A fast effective local search for scheduling independent jobs in heterogeneous computing environments","author":"G. Ritchie","year":"2003"},{"issue":"2","key":"25","doi-asserted-by":"crossref","first-page":"332","DOI":"10.1137\/S0097539701397059","article-title":"Stackelberg scheduling strategies","volume":"33","author":"T. Roughgarden","year":"2004","journal-title":"SIAM Journal on Computing"},{"issue":"1-2","key":"26","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1007\/s10723-005-5465-x","article-title":"Trusted grid computing with security binding and trust integration","volume":"3","author":"S. Song","year":"2005","journal-title":"Journal of Grid Computing"},{"issue":"6","key":"27","doi-asserted-by":"crossref","first-page":"703","DOI":"10.1109\/TC.2006.89","article-title":"Risk-resilient heuristics and genetic algorithms for security-assured grid job scheduling","volume":"55","author":"S. Song","year":"2006","journal-title":"IEEE Transactions on Computers"},{"key":"28","volume-title":"Game Theory and Strategy","author":"P. Straffin","year":"1996"},{"issue":"2","key":"29","doi-asserted-by":"crossref","first-page":"84","DOI":"10.1016\/j.jpdc.2009.09.003","article-title":"Cooperative power-aware scheduling in grid computing environments","volume":"70","author":"R. Subrata","year":"2010","journal-title":"Journal of Parallel and Distributed Computing"},{"key":"30","article-title":"Gcommerce: Market formulations controlling resource allocation on the computational grid","author":"R. Wolski","year":"2001"},{"issue":"2","key":"31","doi-asserted-by":"crossref","first-page":"198","DOI":"10.1016\/j.future.2009.08.004","article-title":"An integrated security-aware job scheduling strategy for large-scale computational grids","volume":"26","author":"C. Wu","year":"2010","journal-title":"Future Generation Computer Systems"},{"issue":"4","key":"32","doi-asserted-by":"crossref","first-page":"608","DOI":"10.1016\/j.future.2009.11.005","article-title":"Computational models and heuristic methods for grid scheduling problems","volume":"26","author":"F. Xhafa","year":"2010","journal-title":"Future Generation Computer Systems"},{"issue":"4","key":"33","doi-asserted-by":"crossref","first-page":"427","DOI":"10.1142\/S0219265907002119","article-title":"An experimental study on genetic algorithms for resource allocation on grid systems","volume":"8","author":"F. Xhafa","year":"2008","journal-title":"Journal of Interconnection Networks"},{"issue":"5","key":"34","first-page":"1","article-title":"Genetic algorithm based schedulers for grid computing systems","volume":"3","author":"F. Xhafa","year":"2007","journal-title":"International Journal of Innovative Computing, Information and Control"},{"issue":"2","key":"35","first-page":"237","article-title":"Tabu search algorithm for scheduling independent jobs in computational grids","volume":"28","author":"F. Xhafa","year":"2009","journal-title":"Computer and Informatics Journal"},{"key":"36","doi-asserted-by":"crossref","first-page":"285","DOI":"10.1007\/978-3-642-02319-4_34","volume-title":"Hybrid Artificial Inteligence Systems, Lecture Notes in Computer Science","volume":"5572","author":"F. Xhafa","year":"2009"}],"container-title":["International Journal of Applied Mathematics and Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/content.sciendo.com\/view\/journals\/amcs\/21\/2\/article-p243.xml","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.degruyter.com\/view\/j\/amcs.2011.21.issue-2\/v10006-011-0018-x\/v10006-011-0018-x.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,2,29]],"date-time":"2024-02-29T10:27:12Z","timestamp":1709202432000},"score":1,"resource":{"primary":{"URL":"https:\/\/content.sciendo.com\/doi\/10.2478\/v10006-011-0018-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,6,1]]},"references-count":36,"journal-issue":{"issue":"2"},"URL":"https:\/\/doi.org\/10.2478\/v10006-011-0018-x","relation":{},"ISSN":["1641-876X"],"issn-type":[{"value":"1641-876X","type":"print"}],"subject":[],"published":{"date-parts":[[2011,6,1]]}}}