Nothing Special   »   [go: up one dir, main page]
Skip to main content

Advertisement

Springer Nature Link
Log in

Multi-objective workflow scheduling in Amazon EC2

  • Published:
Cluster Computing Aims and scope Submit manuscript

Abstract

Nowadays, scientists and companies are confronted with multiple competing goals such as makespan in high-performance computing and economic cost in Clouds that have to be simultaneously optimised. Multi-objective scheduling of scientific applications in these systems is therefore receiving increasing research attention. Most existing approaches typically aggregate all objectives in a single function, defined a-priori without any knowledge about the problem being solved, which negatively impacts the quality of the solutions. In contrast, Pareto-based approaches having as outcome a set of (nearly) optimal solutions that represent a tradeoff among the different objectives, have been scarcely studied. In this paper, we analyse MOHEFT, a Pareto-based list scheduling heuristic that provides the user with a set of tradeoff optimal solutions from which the one that better suits the user requirements can be manually selected. We demonstrate the potential of our method for multi-objective workflow scheduling on the commercial Amazon EC2 Cloud. We compare the quality of the MOHEFT tradeoff solutions with two state-of-the-art approaches using different synthetic and real-world workflows: the classical HEFT algorithm for single-objective scheduling and the SPEA2* genetic algorithm used in multi-objective optimisation problems. The results demonstrate that our approach is able to compute solutions of higher quality than SPEA2*. In addition, we show that MOHEFT is more suitable than SPEA2* for workflow scheduling in the context of commercial Clouds, since the genetic-based approach is unable of dealing with some of the constraints imposed by these systems.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Algorithm 1
Algorithm 2
Algorithm 3
Algorithm 4
Algorithm 5
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9

Similar content being viewed by others

Notes

  1. These prices only refer to the Standard On-Demand Instances (September 2013).

References

  1. Alexandru, I., Ostermann, S., Yigitbasi, M., Prodan, R., Fahringer, T., Epema, D.: Performance analysis of cloud computing services for many-tasks scientific computing. IEEE Trans. Parallel Distrib. Syst. 22(6), 931–945 (2010)

    Google Scholar 

  2. Assayad, I., Girault, A., Kalla, H.: A bi-criteria scheduling heuristics for distributed embedded systems under reliability and real-time constraints. In: International Conference on Dependable Systems and Networks (DSN’04), Firenze, Italy. IEEE Press, New York (2003)

    Google Scholar 

  3. Blaha, P., Schwarz, K., Madsen, G., Kvasnicka, D., Luitz, J.: Wien2k: an augmented plane wave plus local orbitals program for calculating crystal properties. Tech. rep., Institute of Physical and Theoretical Chemistry, TU Vienna (2001)

  4. Blum, C., Roli, A.: Metaheuristics in combinatorial optimization: overview and conceptual comparison. ACM Comput. Surv. 35(3), 268–308 (2003)

    Article  Google Scholar 

  5. Canon, L.C., Emmanuel, E.: MO-Greedy: an extended beam-search approach for solving a multi-criteria scheduling problem on heterogeneous machines. In: International Heterogeneity in Computing (2011)

    Google Scholar 

  6. Coello, C.A.C., Lamont, G.B., Van Veldhuisen, D.A.: Evolutionary Algorithms for Solving Multi-Objective Problems. Springer, Berlin (2007)

    MATH  Google Scholar 

  7. Deb, K., Pratap, A., Agarwal, S., Meyarivan, T.: A fast elitist multi-objective genetic algorithm: NSGA-II. IEEE Trans. Evol. Comput. 6, 182–197 (2000)

    Article  Google Scholar 

  8. Durillo, J., Fard, H., Prodan, R.: Moheft: a multi-objective lilst-based method for workflow scheduling. In: 4th IEEE International Conference on Cloud Computing Technology and Science (2012)

    Google Scholar 

  9. Durillo, J.J., Nebro, A.J.: jMetal: a Java framework for multi-objective optimization. Adv. Eng. Softw. 42, 760–771 (2011)

    Article  Google Scholar 

  10. Fard, H., Prodan, R., Barrionuevo, J., Fahringer, T.: A multi-objective approach for workflow scheduling in heterogeneous environments. In: 12th IEEE/ACM International Symposium on Cluster, Cloud and Grid Computing (CCGrid), pp. 300–309 (2012). doi:10.1109/CCGrid.2012.114

    Google Scholar 

  11. Garg, R., Singh, A.K.: Reference point based multi-objective optimization to workflow grid scheduling. Int. J. Appl. Evol. Comput. 3(1), 80–99 (2012)

    Article  Google Scholar 

  12. Garg, S.K., Buyya, R., Siegel, H.J.: Scheduling parallel applications on utility grids: time and cost trade-off management. In: Proceedings of the Thirty-Second Australasian Conference on Computer Science (ACSC ’09), Darlinghurst, Australia, vol. 91, pp. 151–160. Australian Computer Society, Sydney (2009)

    Google Scholar 

  13. Hakem, M., Butelle, F.: Reliability and scheduling on systems subject to failures. In: Proceedings of the 2007 International Conference on Parallel Processing (ICPP ’07), p. 38. IEEE Comput. Soc., Washington (2007)

    Chapter  Google Scholar 

  14. Ilavarsan, E., Thambidurai, P.: Low complexity performance effective task scheduling algorithm for heterogeneous computing environments. J. Comput. Sci. 3(2), 94–103 (2007)

    Article  Google Scholar 

  15. Mezmaz, M., Melab, N., Kessaci, Y., Lee, Y., Albi, E.G.T., Zomaya, A.Y., Tuyttens, D.: A parallel bi-objective hybrid metaheuristic for energy-aware scheduling for cloud computing systems. J. Parallel Distrib. Comput. 71, 1497–1508 (2011)

    Article  Google Scholar 

  16. Plachetka, T.: POVRAY—persistence of vision parallel raytracer. In: Proceedings of Computer Graphics International ’98, pp. 123–129 (1998)

    Google Scholar 

  17. Sakellariou, R., Zhao, H., Tsiakkouri, E., Dikaiakos, M.D.: Scheduling workflows with budget constraints. In: Gorlatch, S., Danelutto, M. (eds.) Integrated Research in Grid Computing. CoreGrid Series. Springer, Berlin (2007)

    Google Scholar 

  18. Singh, D., Garg, R.: A robust multi-objective optimization to workflow scheduling for dynamic grid. In: Proceedings of the International Conference on Advances in Computing and Artificial Intelligence (ACAI ’11), pp. 183–188. ACM, New York (2011)

    Chapter  Google Scholar 

  19. Singh, M.P., Vouk, M.A.: Scientific Workflows: Scientific Computing Meets Transactional Workflows (1996)

  20. Talukder, A.K.M.K.A., Kirley, M., Buyya, R.: Multiobjective differential evolution for scheduling workflow applications on global grids. Evolution 21(13), 1742–1756 (2009)

    Google Scholar 

  21. Taylor, I.J., Deelman, E., Gannon, D.B., Shields, M.: Workflows for e-Science: Scientific Workflows for Grids. Springer, New York (2006)

    Google Scholar 

  22. Topcuoglu, H., Hariri, S., Wu, M.Y.: Performance-effective and low-complexity task scheduling for heterogeneous computing. IEEE Trans. Parallel Distrib. Syst. 13(3), 260–274 (2002)

    Article  Google Scholar 

  23. Ullman, J.: Np-complete scheduling problems. J. Comput. Syst. Sci. 10(3), 384–393 (1975)

    Article  MATH  MathSciNet  Google Scholar 

  24. Yu, J., Buyya, R., Ramamohanarao, K.: Workflow scheduling algorithms for grid computing. In: Xhafa, F., Abraham, A. (eds.) Metaheuristics for Scheduling in Distributed Computing Environments, pp. 109–153. Springer, Berlin (2008)

    Google Scholar 

  25. Yu, J., Kirley, M., Buyya, R.: Multi-objective planning for workflow execution on grids. In: Proceedings of the 8th IEEE/ACM International Conference on Grid Computing (GRID ’07), pp. 10–17. IEEE Comput. Soc., Washington (2007)

    Chapter  Google Scholar 

  26. Zeng, J.t., Xia, J.w., Li, J.z., Li, M.h.: Multi-objective optimal grid workflow scheduling with qos constraints. In: Cao, B., Li, T.F., Zhang, C.Y. (eds.) Fuzzy Information and Engineering, Volume 2. Advances in Intelligent and Soft Computing, vol. 62, pp. 839–847. Springer, Berlin (2009)

    Chapter  Google Scholar 

  27. Zitzler, E., Laumanns, M., Thiele, L.: Spea2: improving the strength pareto evolutionary algorithm. Tech. rep. 103, Gloriastrasse 35, CH-8092 Zurich, Switzerland (2001)

Download references

Author information

Authors and Affiliations

  1. University of Innsbruck, Innsbruck, Tirol, Austria

    Juan J. Durillo & Radu Prodan

Authors
  1. Juan J. Durillo
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Radu Prodan
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Juan J. Durillo.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Durillo, J.J., Prodan, R. Multi-objective workflow scheduling in Amazon EC2. Cluster Comput 17, 169–189 (2014). https://doi.org/10.1007/s10586-013-0325-0

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10586-013-0325-0

Keywords

Search

Navigation