More Web Proxy on the site http://driver.im/

article

A genetic algorithm for multi-objective optimisation in workflow scheduling with hard constraints

Authors:

Jérémie Sublime,

Rachid Chelouah,

Bertrand GranadoAuthors Info & Claims

International Journal of Metaheuristics, Volume 2, Issue 4

Pages 415 - 433

https://doi.org/10.1504/IJMHEUR.2013.058475

Published: 01 December 2013 Publication History

Abstract

Cloud computing is a fast growing technology allowing companies to use on-demand computation, and data services for their everyday needs. The main contribution of this work is to propose a new model of genetic algorithm for the workflow scheduling problem. The algorithm must be capable of: 1 dealing with the multi-objective problem of optimising several quality of service QoS variables, namely: computation time, cost, reliability or security; 2 handling a large number of workflow scheduling aspects such as adding constraints on QoS variables deadlines and budgets; 3 handling hard constraints such as restrictions on task scheduling that the previous algorithms have not addressed. Using data from Amazon elastic compute cloud EC2 and workflows from the London e-Science Centre; we have compared our algorithm with other scheduling algorithms. Simulation results indicate the efficiency of the proposed metaheuristic both in terms of solution quality and computational time.

References

[1]

Abrishami, S. and Naghibzadeh, M. (2012), 'Deadline-constrained workflow scheduling in software as a service cloud', Scientia Iranica, Vol. 19, No. 3, pp. 680-689.

[2]

Amazon EC2 website, pricing page, UE (Ireland) pricing [online] http://aws.amazon.com/en/ec2/pricing/ (accessed January 2013).

[3]

Brucker, P. (2004) Scheduling Algortihms, Springer-Verlag, Berlin Heidelberg.

[4]

Hollinsworth, D, (1994) 'The workflow reference model', Workflow Management Coalition, TC00-1003.

[5]

Kanoh, H., Hasegawa, K., Matsumoto, M., Kato, N. and Nishihara, S. (1997) 'Solving constraint satisfaction problems by a genetic algorithm adopting viral infection', Engineering Application of Artificial Intelligence, Vol. 10, No. 6, pp. 531-537.

[6]

Lenstra, J.K. and. Rinnooy Kan, A.H.G. (1978) 'Complexity of scheduling under precedence constraints', Operations Research, January-February, Vol. 26, No. 1, pp. 22-35.

[7]

Liu, K., Jin, H., Chen, J., Liu, X., Yuan, D. and Yang, Y. (2010) 'A compromised-time-cost scheduling algorithm in SwinDeW-C for instance-intensive cost-constrained workflows on cloud computing platform', International Journal of High Performance Computing Applications, Vol. 24, No. 4, pp. 445-456.

Digital Library

[8]

Mezmaz, M., Melab, N., Kessaci, Y., Lee, Y.C., Talbi, E-G., Zomaya, A.Y. and Tuyttens, D. (2011) 'A parallel bi-objective hybrid metaheuristic for energy-aware scheduling for cloud computing systems', Journal of Parallel and Distributed Computing, Vol. 71, No. 11, pp. 1497-1508.

Digital Library

[9]

O'Brien, A., Newhouse, S. and Darlington, J. (2004) 'Mapping of scientific workflow within the e-protein project to distributed resources', in UK e-Science All Hands Meeting, Nottingham, UK, September.

[10]

Pandey, S., Wu, L., Guru, S.M. and Buyya, R. (2010) 'A particle swarm optimization-based heuristic for scheduling workflow applications in cloud computing environments', 24th IEEE Int'l Conference on Advanced Information Networking and Applications (AINA), pp. 400-407.

[11]

Sarda, K., Sanghrajka, S. and Sion, R. (2011) Cloud Performance Benchmark Series : Amazon EC2 CPU Speed Benchmarks, Technical Report, Cloud Computing Center & Network Security and Applied Cryptography Lab, Stony Brook University, New York, USA.

[12]

Selvarani, S. and Sadhasivam, G.S. (2010) 'Improved cost-based algorithm for task scheduling in Cloud computing', Computational Intelligence and Computing Research (ICCIC), pp. 1-5.

[13]

Topcuoglu, H., Hariri, S. and Wu, M. (2002) 'Performance-effective and low-complexity task scheduling for heterogeneous computing', in IEEE Transactions on Parallel and Distributed Systems, Vol. 13, No. 3, pp. 260-274.

Digital Library

[14]

Vaquero, L.M., Rodero-Merino, L., Caceres, J. and Lindner, M. (2008) 'A break in the clouds: towards a cloud definition', ACM SIGCOMM Computer Communication Review, Vol. 39, No. 1, pp. 50-55.

Digital Library

[15]

Verma, A. and Kaushal, S. (2012) 'Deadline and budget distribution based cost-time optimization workflow scheduling algorithm for cloud', IJCA Proceedings on International Conference on Recent Advances and Future Trends in Information Technology (iRAFIT 2012), iRAFIT(7), pp. 1-4, April 2012.

[16]

Wang, X., Yeo, C.S., Buyya, R. and Su, J. (2011) 'Optimizing the Makespan and reliability for workflow applications with reputation and a look-ahead genetic algorithm', ELSEVIER Future Generation Computer Systems, Vol. 27, p1124-1134.

Digital Library

[17]

Yu, J. and Buyya, R. (2006) 'A budget constrained scheduling of workflow applications on utility grids using genetic algorithms', Proceedings of the 15th IEEE International Symposium on High Performance Distributed Computing, HPDC 2006, IEEE, IEEE CS Press, Paris, France.

[18]

Yu, J., Kirley, M. and Buyya, R. (2007) 'Multi-objective planning for workflow execution on grids', in Proceedings of the 8th IEEE/ACM International Conference on Grid Computing (Grid 2007), IEEE CS Press, IEEE, Los Alamitos, CA, USA, June.

[19]

Zhao, Y., Wilde, M., Foster, I., Voeckler, J., Jordan, T., Quigg, E. and Dobson, J. (2004) 'Grid middleware services for virtual data discovery, composition, and integration', in 2nd Workshop on Middleware for Grid Computing, Toronto, Ontario, Canada, October 18.

Digital Library

Cited By

Shukla PPandey S(2024)MOTORS: multi-objective task offloading and resource scheduling algorithm for heterogeneous fog-cloud computing scenarioThe Journal of Supercomputing10.1007/s11227-024-06315-280:15(22315-22361)Online publication date: 1-Oct-2024
https://dl.acm.org/doi/10.1007/s11227-024-06315-2
Marwa MHajlaoui JSonia YOmri MRachid C(2023)Multi-agent system-based fuzzy constraints offer negotiation of workflow scheduling in Fog-Cloud environmentComputing10.1007/s00607-022-01148-4105:7(1361-1393)Online publication date: 1-Jul-2023
https://dl.acm.org/doi/10.1007/s00607-022-01148-4
(2019)Executing time and cost-aware task scheduling in hybrid cloud using a modified DE algorithmInternational Journal of Computational Science and Engineering10.5555/3337494.333749618:3(217-226)Online publication date: 25-May-2019
https://dl.acm.org/doi/10.5555/3337494.3337496
Show More Cited By

A genetic algorithm for multi-objective optimisation in workflow scheduling with hard constraints
1. Computing methodologies
  1. Artificial intelligence
    1. Search methodologies

Recommendations

Cloud workflow scheduling algorithm based on multi-objective particle swarm optimisation

Owing to the characteristics of market-oriented cloud computing, the objective function of cloud workflow scheduling algorithm should not only consider the running time, but also consider the running costs. The nature of cloud workflow scheduling is to ...
Evolutionary Multi-Objective Workflow Scheduling in Cloud

Cloud computing provides promising platforms for executing large applications with enormous computational resources to offer on demand. In a Cloud model, users are charged based on their usage of resources and the required quality of service (QoS) ...
A hybrid multi-objective Particle Swarm Optimization for scientific workflow scheduling

A heuristic is used to initialize the population of Particle Swarm Optimization.Based upon the heuristic, hybrid multi-objective Particle Swarm Optimization (HPSO) is proposed.Multi-objective optimization workflow scheduling problem in IaaS cloud ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image International Journal of Metaheuristics

International Journal of Metaheuristics Volume 2, Issue 4

December 2013

101 pages

ISSN:1755-2176

EISSN:1755-2184

Issue’s Table of Contents

Publisher

Inderscience Publishers

Geneva 15, Switzerland

Publication History

Published: 01 December 2013

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

6
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 31 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Shukla PPandey S(2024)MOTORS: multi-objective task offloading and resource scheduling algorithm for heterogeneous fog-cloud computing scenarioThe Journal of Supercomputing10.1007/s11227-024-06315-280:15(22315-22361)Online publication date: 1-Oct-2024
https://dl.acm.org/doi/10.1007/s11227-024-06315-2
Marwa MHajlaoui JSonia YOmri MRachid C(2023)Multi-agent system-based fuzzy constraints offer negotiation of workflow scheduling in Fog-Cloud environmentComputing10.1007/s00607-022-01148-4105:7(1361-1393)Online publication date: 1-Jul-2023
https://dl.acm.org/doi/10.1007/s00607-022-01148-4
(2019)Executing time and cost-aware task scheduling in hybrid cloud using a modified DE algorithmInternational Journal of Computational Science and Engineering10.5555/3337494.333749618:3(217-226)Online publication date: 25-May-2019
https://dl.acm.org/doi/10.5555/3337494.3337496
Powell CMiura KMunetomo M(2019)Constrained Multi-objective Optimization Method for Practical Scientific Workflow Resource SelectionEvolutionary Multi-Criterion Optimization10.1007/978-3-030-12598-1_54(683-694)Online publication date: 10-Mar-2019
https://dl.acm.org/doi/10.1007/978-3-030-12598-1_54
Nesmachnow S(2018)An overview of metaheuristicsInternational Journal of Metaheuristics10.1504/IJMHEUR.2014.0689143:4(320-347)Online publication date: 13-Dec-2018
https://dl.acm.org/doi/10.1504/IJMHEUR.2014.068914
(2018)Labelled evolutionary Petri nets/genetic algorithm based approach for workflow scheduling in cloud computingInternational Journal of Grid and Utility Computing10.1504/IJGUC.2018.0917219:2(157-169)Online publication date: 17-Dec-2018
https://dl.acm.org/doi/10.1504/IJGUC.2018.091721
(2018)An evolutionary approach to schedule deadline constrained bag of tasks in a cloudInternational Journal of Bio-Inspired Computation10.1504/IJBIC.2018.09279911:4(229-238)Online publication date: 21-Dec-2018
https://dl.acm.org/doi/10.1504/IJBIC.2018.092799

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents