Scheduling Strategies in Grid Computing Environment: a Survey

D. I. George Amalarethinam(1), Muthulakshmi Palaniandy(2*)

(1) Department of Computer Science, Jamal Mohamed College, Trichirappalli, Tamil Nadu, India
(2) SRM University, India
(*) Corresponding author


DOI's assignment:
the author of the article can submit here a request for assignment of a DOI number to this resource!
Cost of the service: euros 10,00 (for a DOI)

Abstract


Grid Computing is a technology that integrates various forms of resources that contribute themselves in a geographically distributed environment. The heterogeneous resources are utilized by large-scale business and scientific applications. The resource management complexities increase due to the heterogeneity of resources and scalable nature of the grid environment. To manage the issues efficient resource management techniques are needed. Proper scheduling strategies can increase the efficiency of resource management systems. Scheduling is the process of allocating the jobs to the appropriate resources. This paper presents a package of scheduling strategies and factors that influence grid scheduling. The study finds algorithms that are data intensive, computation intensive, communication intensive, application intensive and so on. Generally these algorithms emphasis minimum execution time, load balancing, fault tolerance, task duplication, network behavior, job migration, rescheduling, dependencies, etc.


Copyright © 2014 Praise Worthy Prize - All rights reserved.

Keywords


Parallel Processing; Distributed Computing; Grid Computing; Scheduling Policies; Scheduling Algorithms, Heuristics; Hybrid Scheduling Algorithms

Full Text:

PDF


References


I Foster, C Kesselman, S Tuecke, The Anatomy of the Grid: Enabling Scalable Virtual organizations, International Journal of Supercomputer Applications, 2001.

Hwang K., Advanced Computer Architecture: Parallelism, Scalability, and Programmability, Mc. Graw Hill, Inc., New York, 1993.

D P Anderson, J Cobb, E Korpela, M Lebofsky, D Werthimer, Seti@home: An Experiment in Public-Resource Computing, Communications of the ACM, 2002.

Fatos Xhafa, Ajith Abraham, Computational Models and Heuristic Methods for Grid Scheduling Problems, Future Generation Computer Systems, 2010.

T Casavant and J Kuhl, A Taxonomy of Scheduling in General Purpose Distributed Computing Systems, IEEE Transactions on Software Engineering, 1988.

M Arora, S K Das, R Biswas, A Decentralized Scheduling and Load Balancing Algorithm for Heterogeneous Grid Environments, Proceedings of International Conference on Parallel Processing, 2002.

L Lee, C Liang, H Chang, An Adaptive Task Scheduling System For Grid Computing, Proceedings of the 6th IEEE international Conference on Computer and information Technology, 2006.

Yinglong Xia, Viktor K Prasanna, James Li, Hierarchical Scheduling of DAG Structured Computations on Many Core Processors with Dynamic Thread Grouping, Job Scheduling strategies for parallel processing, Lecture Notes in Computer Science, 2010.

J Yu, R Buyya and K Ramamohanrao, Workflow Scheduling Algorithms for Grid Computing, Metaheuristics for scheduling in distributed computing environments, Springer link, 2008.

S Sahni, Scheduling Master-Slave Multiprocessor Systems, IEEE Transactions on Computers, 1996.

U Schwiegelshohn, R Yahyapour, Analysis Of First-Come-First-Serve Parallel Job Scheduling, Proceedings of the 9th SIAM Symposium on Discrete Algorithms, 1998.

M Maheswaran, S Ali, H J Siegel, D Hensgen and R F Freund, Dynamic Matching and Scheduling of a Class of Independent Tasks onto Heterogeneous Computing Systems, Journal of Parallel and Distributed Computing, 1999.

R Armstrong, D Hensgen, T Kidd, The Relative Performance of Various Mapping Algorithms is Independent of Sizable Variances In Run-Time Predictions, 7th IEEE Heterogeneous Computing Workshop, 1998.

R F Freund, M Gherrity, S Ambrosius, M Campbell, M Halderman, D Hensgen, E Keith,T Kidd, M Kussow, J D Lima, F Mirabile, L Moore, B Rust, and H J Siegel, Scheduling Resources in Multi-User, Heterogeneous, Computing Environments with Smartnet, 7th IEEE Heterogeneous Computing Workshop, 1998.

R F Freund and H J Siegel, Heterogeneous Processing, IEEE Transactions on Computers, 1993.

Ahuva W Mualem, Dror G Feitelson, Utilization, Predictability, Workloads, and User Runtime Estimates in Scheduling the IBM SP2 with Backfilling. IEEE Transactions on Parallel and Distributed Systems, 2001.

Stavrinidis G, H D Karatza, Performance Evaluation of Gang Scheduling in Distributed Real-Time Systems with Possible Software Faults, Proceedings of the International Symposium on Performance Evaluation of Computer and Telecommunication Systems, 2008.

Ruay Shiung Chang, Jih Sheng Chang, Po Sheng Lin, An Ant Algorithm for Balanced Job Scheduling in Grids, Future Generation Computer Systems, 2009.

C L Liu and J W Layland, Scheduling Algorithm for Multi Programming in a Hard Real Time Environment, Journal of the Association for Computing Machinery, 1973.

R Braun, H Siegel, N Beck, L Boloni, M Maheswaran, A Reuther, J Robertson, M Theys, B Yao, D Hensgen, R Freund, A Comparison of Eleven Static Heuristics for Mapping a Class of Independent Tasks onto Heterogeneous Distributed Computing Systems, Journal of Parallel and Distributed Computing, 2001.

O H Ibarra, C E Kim, Heuristic Algorithms for Scheduling Independent Tasks on Non-Identical Processors, Journal of Association of Computer Machines, 1977.

M Dorigo, C Blum, Ant Colony Optimization Theory: A Survey, Theoretical Computer Science, 2005.

M Dorigo, Ant Colony Optimization, http://www.aco-metaheuristic.org.

M Dorigo, L M Gambardella, Ant Colony System: A Cooperative Learning Approach to the Traveling Salesman Problem, IEEE Transactions on Evolutionary Computation, 1997.

E Salari, K Eshghi, An ACO Algorithm for Graph Coloring Problem, Congress on Computational Intelligence Methods and Applications, 2005.

Xiaoxia Zhang, Lixin Tang, CT-ACO-Hybridizing Ant Colony Optimization with Cycle Transfer Search for the Vehicle Routing Problem, Congress on Computational Intelligence Methods and Applications, 2005.

R Prodan, T Fahringer, Dynamic Scheduling of Scientific Workflow Applications on the Grid using a Modular Optimisation Tool: A Case Study, The 20th Symposium of Applied Computing, 2005.

Y. Liu, Survey on Grid Scheduling, http://www.cs.uiowa.edu/~yanliu, (for Ph.D Qualifying Exam), 2004.

Kennedy J, Eberhart R, Particle swarm optimization, Proceedings of IEEE International Conference on Neural Networks, 1995.

L Young, S McGough, S Newhouse, and J Darlington, Scheduling Architecture and Algorithms within the ICENI Grid Middleware, Proceedings of UK e-Science All Hands Meeting, 2003.

I De Falco, R Del Balio, E Tarantino, R Vaccaro, Improving Search by Incorporating Evolution Principles in Parallel Tabu Search, IEEE Conference on Evolutionary Computation, 1994.

F Glover and M Laguna, Tabu Search, Kluwer Academic, 1997.

Jiayi Zhou, Kun-Ming Yu, Chih-Hsun Chou, Li-An Yang, Zhi-Jie Luo, A Dynamic Resource Broker and Fuzzy Logic Based Scheduling Algorithm in Grid Environment, 8th International Conference Proceeding of Adaptive and Natural Computing Algorithms, 2007.

K M Yu, Zh J Luo, Ch H Chou, Ch K. Chen, J Zhou, A Fuzzy Neural Network Based Scheduling Algorithm for Job Assignment on Computational Grids, Lecture Notes in Computer Science, Springer, 2007.

Xianwen Hao, Yu Dai, Bin Zhang, Tingwei Chen, Lei Yang, QoS-Driven Grid Resource Selection Based on Novel Neural Networks, First International Conference proceeding of Advances in Grid and Pervasive Computing, 2006.

Li-Ya Tseng, Yeh-Hao Chin, Shu-Ching Wang, A Minimized Makespan Scheduler with Multiple Factors for Grid Computing Systems, Expert Systems with Applications, 2009.

Sofia K Dimitriadou, Helen D Karatza, Multi-Site Allocation Policies on a Grid and Local Level, Electronic Notes in Theoretical Computer Science, 2010.

Tchernykh, A, Ramirez J M, Avetisyan A, Kuzjurin N, Grushin D, Zhuk S, Two Level Job-Scheduling Strategies for a Computational Grid, Parallel Processing and Applied Mathematics, Springer Verlag, 2006.

J H Abawajy, Adaptive Hierarchical Scheduling Policy for Enterprise Grid Computing Systems, Journal of Network and Computer Applications, 2009.

Thain D, Bent J, Arpaci Dusseau A, Arpaci Dusseau R, Livny M. Gathering at the Well: Creating Communities for Grid I/O, Proceedings of Super Computing, 2001.

Joanna Kolodziej, Fatos Xhafa, Meeting Security and User Behavior Requirements in Grid Scheduling, Simulation Modeling Practices and Theory, 2010.

Joanna Kolodziej, Fatos Xhafa, A Game Theoretic and Hybrid Genetic Meta-heuristic Model for Security Assured Scheduling of Independent Jobs in Computational Grids, Proceedings of International Conference on Complex, Intelligent and Software Intensive Systems, 2010.

Kwok Y K., Hwang K., and Song S, Selfish Grids: Game-Theoretic Modeling and NAS/PSA Benchmark Evaluation, IEEE Transactions on Parallel and Distributing Systems, 2007.

Monir Abdullah, Mohamed Othman, Hamidah Ibrahim, Shamala Subramaniam, Optimal Workload Allocation Model for Scheduling Divisible Data Grid Applications, Future Generation Computer Systems, 2010.

Y C Cheng, T G Robertazzi, Distributed Computation with Communication Delays, IEEE Transactions on Aerospace and Electronic Systems, 1988.

S Kim, J B Weissman, A Genetic Algorithm Based Approach for Scheduling Decomposable Data Grid Applications, IEEE Proceeding of the International Conference on Parallel Processing, 2004.

Monir Abdullah, Mohamed Othman, Hamidah Ibrahim, Shamala Subramaniam, Adaptive Divisible Load Model for Scheduling Data-intensive Grid Applications in Computational Science, Lecture Notes in Computer Science, Springer Verlag, 2007.

Monir Abdullah, Mohamed Othman, Hamidah Ibrahim, Shamala Subramaniam, A2DLT: Divisible Load Balancing Model for Scheduling Communication-intensive Grid Applications, Lecture Notes in Computer Science, Springer Verlag, 2008.

Chao Chin Wu, Ren Yi Sun, An Integrated Security-aware Job Scheduling Strategy for Large-scale Computational Grids, Future Generation Computer Systems, 2010.

M Srinivas, L M Patnaik, Genetic Algorithms: A Survey, IEEE Transactions on Computers, 1994.

Song S, Kwok Y K, Hwang K, Risk-resilient Heuristics and Genetic Algorithms for Security-assured Grid Job Scheduling, IEEE Transactions on Computers, 2006.

Xin Liu, Chunming Qiao, Wei Wei, Xiang Yu, Ting Wang, Weisheng Hu, Wei Guo, and Min-You Wu, Task Scheduling and Light Path Establishment in Optical Grids, Journal of Light Wave Technology, 2009.

Taiwan Unigrid project portal site, http://www.unigrid.org.tw.

GlobusToolkit-v4, http://www.globus.org/toolkit/downloads/4.0.4/.

B.T. Benjamin Khoo, Bharadwaj Veeravalli, Pro-active Failure Handling Mechanisms for Scheduling in Grid Computing Environments, Journal of Parallel Distributed Computing, 2010.

Hamid Mohammadi Fard,Hossein Deldari, An Economic Approach for Scheduling Dependent Tasks in Grid Computing, The 11th IEEE International Conference on Computational Science and Engineering, 2008.

O Sinnen, A To, M Kaur , Contention-Aware Scheduling with Task Duplication, Journal of Parallel and Distributed Computing, 2011.

Luiz Meyer, Doug Scheftner, Jens Vöckler, Marta Mattoso, Mike Wilde, Ian Foster,An Opportunistic Algorithm for Scheduling Workflows on Grids, High Performance Computing for Computational Science, 2006.

Weizhe Zhang, Cheng, A M K, Mingzeng Hu, Multisite Co-Allocation Algorithms for Computational Grid, 20th International Parallel and Distributed Processing Symposium, 2006.

D I George Amalarethinam, F Kurus Malai Selvi, A Task Duplication Based Efficient Multi-Objective Workflow Scheduling Algorithm, International Journal of Advanced Research in Computer Science, 2012.

D I George Amalarethinam, F Kurus Malai Selvi, An Efficient Dual Objective Grid Workflow Scheduling Algorithm, International Journal of Computer Applications, 2011.

Vydyanathan N, Catalyurek U, Kurc T, Sadayappan, P, A Duplication Based Algorithm for Optimizing Latency Under Throughput Constraints for Streaming Workflows, 37th International Conference on Parallel Processing, 2008.

Vydyanathan N, Catalyurek U, Kurc T, Sadayappan, P, Saltz J, Toward Optimizing Latency Under Throughput Constraints for Application Workflows on Clusters, 13th International European Conference on Parallel and Distributed Computing, 2007.

K Asakura, B Shao, T Watanabe, A Task Duplication Based Scheduling Algorithm for Avoiding Useless Duplication, PDPTA, 2006.

Dang Minh Quan, Yang, L T, Parallel Mapping with Time Optimization for SLA-aware Compositional Services in the Business Grid, IEEE Transactions on Services Computing, 2011.

Suchang Guo, Hong-Zhong Huang, Zhonglai Wang, Min Xie, Grid Service Reliability Modeling and Optimal Task Scheduling Considering Fault Recovery, IEEE Transactions on Reliability, 2011.

Prodan R, Wieczorek M, Bi-Criteria Scheduling of Scientific Grid Workflows, IEEE Transactions on Automation Science and Engineering, 2010.

Bozdag D, Catlyurek U, Ozguner F,A Task Duplication Based Bottom-Up Scheduling Algorithm for Heterogeneous Environments, 20th International Parallel and Distributed Processing Symposium, 2006.

Yiming Tan,Guosun Zeng,Shuixia Hao, Performance Analysis for Heterogeneous & Reconfigurable Computing Based on Scheduling, International Journalof Education and Management Engineering, 2011.

Mohammad Sadeq Garshasbi, Mehdi Effatparvar,High Performance Scheduling in Parallel Heterogeneous Multiprocessor Systems Using Evolutionary Algorithms, International Journal of Intelligent Systems and Applications, 2013.

Saeed Molaiy,Mehdi Effatparvar,Scheduling in Grid Systems using Ant Colony Algorithm, International Journal of Computer Network and Information Security, 2014.

Reza Fotohi, Mehdi Effatparvar,A Cluster Based Job Scheduling Algorithm for Grid Computing, International Journal of Information Technology and Computer Science, 2013.

Y. Xu et al., A genetic algorithm for task scheduling on heterogeneous computing systems using multiple priority queues, Information. Sciences, 2014.

Haluk Topcuoglu, Salim Hariri, Min-You Wu, Performance-Effective and Low-Complexity Task Scheduling for Heterogeneous Computing, IEEE Transactions on Parallel and Distributed Systems, 2002.

Dipti Sharma and Pradeep Mittal, Job Scheduling Algorithm for Computational Grid in Grid Computing Environment, International Journal of Advanced Research in Computer Science and Software Engineering, 2013.

P. Keerthika and N. Kasthuri, An Efficient Grid Scheduling Algorithm with Fault Tolerance and User Satisfaction, Mathematical Problems in Engineering, 2013.

Sanjeev Puri,Harsh Dev,Deliberate, Secure Grid Computing Blueprint Design in Indian Context, International Journal of Computer Network and Information Security, 2012.

Rajabioun. R, Cuckoo optimization algorithm. Applied soft computing, 2011.

Saurabh Kumar Garg, Srikumar Venugopal, James Brober, Rajkumar Buyya, Double auction-inspired meta-scheduling of parallel applications on global grids, Journal of Parallel and Distributed Computing, 2013.

Lizhe Wang, Samee U. Khan, Dan Chen, Joanna Kołodziej, Rajiv Ranjan, Cheng-zhong Xu, Albert Zomaya, Energy-aware parallel task scheduling in a cluster, Future Generation Computer Systems, 2013.

Chung-Hsing Hsu, Wu chun Feng, A feasibility analysis of power awareness in commodity-based high-performance clusters, CLUSTER, 2005.

Xiaomin Zhu, Rong Ge, Jinguang Sun, Chuan He, 3E: Energy-efficient elastic scheduling for independent tasks in heterogeneous computing systems, The Journal of Systems and Software, 2013.

Ye Huang, Nik Bessis, Peter Norrington, Pierre Kuonen, Beat Hirsbrunner, Exploring decentralized dynamic scheduling for grids and clouds using the community-aware scheduling algorithm, Future Generation Computer Systems, 2013.

Wei Liu, Wei Du, Jing Chen, Wei Wang, Guo Sun Zeng, Adaptive energy-efficient scheduling algorithm for parallel tasks on homogeneous clusters, Journal of Network and Computer Applications, 2014.

Rajni, Inderveer Chana, Bacterial foraging based hyper-heuristic for resource scheduling in grid computing, Future Generation Computer Systems, 2013.

K.M. Passino, Biomimicry of bacterial foraging for distributed optimization and control, IEEE Control Systems Magazine, 2002.

Sucha Smanchat, Maria Indrawan, Sea Ling, Colin Enticott, David Abramson, Scheduling parameter sweep workflow in the Grid based on resource competition, Future Generation Computer Systems, 2013.

Ramya R and Shalini Thomas, An Optimal Job Scheduling Algorithm in Computational Grids, Special Issue of International Journal of Computer Applications, 2012.

Anis Gharbi et al, An Effective Genetic Algorithm for a Complex Real-World Scheduling Problem, International Journal of Mechanical, Industrial Science and Engineering, 2013.

Bsoul, M. , Phillips, I. , Hinde, C. , MICOSim: A simulator for modelling economic scheduling in Grid computing, World Academy of Science, Engineering and Technology, International Science Index 68, 2012.

Maryam Rabiee and Hedieh Sajedi, Job Scheduling in Grid Computing with Cuckoo Optimization Algorithm, International Journal of Computer Applications, 2013.

M. C. Lee, F. Y. Leu, and Y. Chen, PFRF: An adaptive data replication algorithm based on star topology Data Grids, Future Generation Computer Systems, 2012.

J. Taheri, Y. C. Lee, A. Y. Zomaya and H. J. Siegel, A Bee Colony based optimization approach for simultaneous job scheduling and data replication in Grid environments, Computers & Operations Research, 2013.

N. Saadat and A. M. Rahmani, PDDRA: A new pre-fetching based dynamic data replication algorithm in Data Grids, Future Generation Computer Systems, 2012.

N. Mansouri and Gh. Dastghaibyfard, Improving Data Grids Performance by using Modified Dynamic Hierarchical Replication Strategy, Iranian Journal of Electrical & Electronic Engineering, 2014.

N. Mansouri and G. H. Dastghaibyfard, A dynamic replica management strategy in Data Grid, Journal of Network and Computer Applications, 2012.

V. Andronikou, K. Mamouras, K. Tserpes, D. Kyriazis and T. Varvarigou, Dynamic QoS aware data replication in Grid environments based on data importance, Future Generation Computer Systems, 2012.

Kamalam, G.K. and V.Murali Bhaskaran, Novel adaptive job scheduling algorithm on heterogeneous grid resources, American Journal Applied Sciences, 2012.

Keerthika, P. and N. Kasthuri, An efficient fault tolerant scheduling approach for computational grid, American Journal of Applied Sciences, 2012.

P. Linberg, J. Leingang, D. Lysaker, S. Khan, J. Li, Comparison and analysis of eight scheduling heuristics for the optimization of energy consumption and makespan in large-scale distributed systems, The Journal of Supercomputing, 2012.


Refbacks

  • There are currently no refbacks.



Please send any question about this web site to info@praiseworthyprize.com
Copyright © 2005-2019 Praise Worthy Prize