CFP last date
20 January 2025
Reseach Article

A Taxonomy and Survey of Scheduling Algorithms in Cloud: Based on task dependency

by Ruby Annette. J, Aisha Banu. W, Shriram
International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Volume 82 - Number 15
Year of Publication: 2013
Authors: Ruby Annette. J, Aisha Banu. W, Shriram
10.5120/14240-2389

Ruby Annette. J, Aisha Banu. W, Shriram . A Taxonomy and Survey of Scheduling Algorithms in Cloud: Based on task dependency. International Journal of Computer Applications. 82, 15 ( November 2013), 20-26. DOI=10.5120/14240-2389

@article{ 10.5120/14240-2389,
author = { Ruby Annette. J, Aisha Banu. W, Shriram },
title = { A Taxonomy and Survey of Scheduling Algorithms in Cloud: Based on task dependency },
journal = { International Journal of Computer Applications },
issue_date = { November 2013 },
volume = { 82 },
number = { 15 },
month = { November },
year = { 2013 },
issn = { 0975-8887 },
pages = { 20-26 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume82/number15/14240-2389/ },
doi = { 10.5120/14240-2389 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-02-06T21:57:50.179355+05:30
%A Ruby Annette. J
%A Aisha Banu. W
%A Shriram
%T A Taxonomy and Survey of Scheduling Algorithms in Cloud: Based on task dependency
%J International Journal of Computer Applications
%@ 0975-8887
%V 82
%N 15
%P 20-26
%D 2013
%I Foundation of Computer Science (FCS), NY, USA
Abstract

Cloud computing has made the dream of scalability of resources on demand come true. As the usage of the resources on the cloud involves cost, their optimal utilization is vital. Various scheduling algorithms are being designed and implemented seamlessly to achieve this goal. One of the factors that have a high impact on the scheduling algorithm design is the dependency of the tasks. Dependency implies that the tasks are executed in some precedence order. This survey provides a review of the various scheduling algorithms in cloud mainly from the perspective of task dependency. The broad categorization, advantages and the disadvantages of the various scheduling algorithms available for both dependent and independent tasks are discussed. Based on a comprehensive understanding of the challenges and the current research trends, some open issues worthy of further exploration are proposed.

References
  1. M. Armbrust et al., Above the Clouds: A Berkeley View of Cloud Computing, tech. report UCB/EECS-2009-28, EECS Dept., Univ. of California, Berkeley, Feb. 2009.
  2. Salesforce.com
  3. Google App Engine: http://www.google.com/apps
  4. Amazon EC2: http://aws.amazon.com/ec2
  5. Eucalyptus http://eucalyptus.com
  6. T. Casavant, and J. Kuhl, A Taxonomy of Scheduling in General-purpose Distributed Computing Systems, in IEEE Trans. on Software Engineering Vol. 14, No.2, pp.141--154, February 1988.
  7. F. Dong and S. G. Akl, Scheduling algorithm for grid computing: state of the art and open problems, Technical Report of the Open Issues in Grid Scheduling Workshop, School of Computing, University Kingston, Ontario, January, 2006.
  8. M. Dias de Assunção, A. di Costanzo, and R. Buyya, “Evaluating the Cost-Benefit of Using Cloud Computing to Extend the Capacity of Clusters,” Proc. Int’l Symp.
  9. Haluk Topcuoglo, Salim Hariri, Min-You Wu, Performance-effective and low-complexity task scheduling for heterogeneous computing, IEEE Transactions on parallel and distributed systems, No.3, March 2002.
  10. A. Abraham, R. Buyya and B. Nath, Nature's Heuristics for Scheduling Jobs on Computational Grids, in Proc. of 8th IEEE International Conference on Advanced Computing and Communications (ADCOM 2000), pp. 45-52, Cochin, India, December 2000.
  11. N. Muthuvelu, J. Liu, N. L. Soe, S.rVenugopal, A. Sulistio and R. Buyya, A Dynamic Job Grouping-Based Scheduling for Deploying Applications with Fine-Grained Tasks on Global Grids, Proceedings of the 3rd Australasian Workshop on Grid Computing and e-Research (AusGrid 2005), Newcastle, Australia, January 30 – February 4, 2005.
  12. Quan Liu, Yeqing Liao, “Grouping based Fine-Grained job Scheduling in Grid Computing”, First International Workshop on Education Technology and Computer Science, Vol.1,pp. 556-559, IEEE, 2009.
  13. R. Braun, H. Siegel, N. Beck, L. Boloni, M. Maheswaran, A. Reuther, J. Robertson,M. Theys, B. Yao, D. Hensgen and R. Freund, A Comparison of Eleven Static Heuristics for Mapping a Class of Independent Tasks onto Heterogeneous Distributed Computing Systems, in J. of Parallel and Distributed Computing, vol.61, No. 6, pp. 810-837, 2001.
  14. R.Armstrong, D.Hensgen, and T.Kidd, “The relative performance of various mapping algorithms is independent of sizable variance in run-time predictions,” 7th IEEE Heterogeneous Computing Workshop (HCW’98), March. 1998, pp.79 87
  15. 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 HeterogeneousComputing Ubrkshop (HCW '98), Mar. 1998, pp. 184-199.
  16. 0. H. Sbarra and C. E. Kim, "Heuristic algorithms for scheduling independent tasks on nonidentical processors," Journal of the ACM, Vol. 24, No. 2, Apr. 1977, pp. 280-259.
  17. X. He, X. Sun and G. Laszewski, A QoS Guided Min-Min Heuristic for Grid Task Scheduling, in J. of Computer Science and Technology, Special Issue on Grid Computing, Vol.18, No.4, pp.442--451, July 2003.
  18. M. Wu, W. Shu and H. Zhang, Segmented Min-Min: A Static Mapping Algorithm for Meta-Tasks on Heterogeneous Computing Systems, in Proc. of the 9th Heterogeneous Computing Workshop (HCW'00), pp. 375--385, Cancun, Mexico, May 2000.
  19. 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, in J. of Parallel and Distributed Computing, Vol. 59, No. 2,pp.107--131, November 1999.
  20. H. Casanova, A. Legrand, D. Zagorodnov and F. Berman, Heuristics for Scheduling Parameter Sweep Applications in Grid Environments, in Proc. of the 9th Heterogeneous Computing Workshop (HCW'00), pp. 349-363, Cancun, Mexico, May 2000.
  21. Mu’alem, A.W., Feitelson, D.G.: Utilization, predictability, workloads, and user runtime estimates in scheduling the IBM SP2 with backfilling. IEEE Trans. Parallel Distrib. Syst. 12(6), 529–543 (2001)
  22. Lifka, D.A.: The ANL/IBM SP scheduling system. In: Workshop on Job Scheduling Strategies for Parallel Processing (IPPS’95), London, UK, 1995, pp. 295–303. Springer, Berlin (1995)
  23. Srinivasan, S., Kettimuthu, R., Subramani, V., Sadayappan, P.: Selective Reservation strategies for backfill job scheduling. In: 8th International Workshop on Job Scheduling Strategies for Parallel Processing (JSSPP ’02), London, UK, 2002. LNCS, vol. 2537, pp.55–71. Springer, Berlin/Heidelberg (2002)
  24. S. Song, Y. Kwok, and K. Hwang, Security-Driven Heuristics and A Fast Genetic Algorithm for Trusted Grid Job Scheduling, in Proc. of 19th IEEE International Parallel and Distributed Processing Symposium (IPDPS'05), pp.65-74, Denver, Colorado USA, April 2005.
  25. Y. Liu, Survey on Grid Scheduling (for Ph.D Qualifying Exam), Department of Computer Science, University of Iowa, http://www.cs.uiowa.edu/~yanliu/, April 2004.
  26. M. M. Shoukat, M. Maheswaran, S. Ali, H. J. Siegel, D. Hensgen, and R. F. Freund. “Dynamic mapping of a class of independent tasks onto heterogeneous computing systems”. Journal of Parallel and Distributed Computing, 59:107–131, 1999.
  27. Haluk Topcuoglo, Salim Hariri, Min-You Wu, Performance-effective and low-complexity task scheduling for heterogeneous computing, IEEE Transactions on parallel and distributed systems, No.3, March 2002.
  28. J. Yu, R. Buyya, and C. K. Tham, “Cost-based scheduling of scientific workflow applications on utility grids,” in International Conference on e-Science and Grid Computing, Jul. 2005, pp. 140–147.
  29. S. Abrishami, M. Naghibzadeh, and D. Epema, “Cost-driven scheduling of grid workflows using partial critical paths,” in 11th IEEE/ACM International Conference on Grid Computing (GRID), Oct. 2010, pp. 81 –88.
  30. S. Pandey, L. Wu, S. Guru, and R. Buyya, “A particle swarm optimization-based heuristic for scheduling workflow applications in cloud Computing environments,” in 24th IEEE International Conference on Advanced Information Networking and Applications (AINA), Apr. 2010, pp. 400 –407.
  31. L. F. Bittencourt and E. R. M. Madeira, “HCOC: a cost optimization algorithm for workflow scheduling in hybrid clouds,” Journal of Internet Services and Applications, vol. 2, no. 3, Dec 2011, pp. 207–227.
  32. Tianchi Ma and Rajkumar Buyya, Critical-Path and Priority based Algorithms for Scheduling Workflows with Parameter Sweep Tasks on Global Grids, in Proc. of the 17th International Symposium on Computer Architecture and High Performance Computing, Rio de Janeiro, Brazil, October 2005.
  33. M. Iverson and F. Ozguner, Dynamic, Competitive Scheduling of Multiple DAGs in a Distributed Heterogeneous Environment, in Proc. of Seventh Heterogeneous Computing Workshop, pp. 70-78, Orlando, Florida USA, March 1998.
Index Terms

Computer Science
Information Sciences

Keywords

Resource scheduling Scheduling algorithms Hybrid cloud Task dependency IaaS