Bulut Hesaplama İçin Evrimsel Algoritma Kullanarak İş Akışı Planlaması

Öz

Bulut bilişim, gerçek dünya uygulamaları için güçlü, yüksek düzeyde ölçeklenebilir, esnek kaynaklar sağlar. Maliyet ve işletme giderlerini de azaltır. Bulut bilişimde daha yüksek performans elde etmek, maliyeti düşürmek ve kaynakları daha verimli kullanmak için iş akışı planlaması önemlidir. Bulut sistemlerinde iş akışı çizelgeleme, işleri sistemde bulunan kaynaklara atar ve iş akışının süresini azaltarak bulut kaynaklarından etkin bir şekilde yararlanmayı amaçlar. Bu çalışmada, iş akışı çizelgeleme problemini çözmek için evrimsel bir algoritma önerilmiştir. Bu çalışmanın temel amacı, programın çalışma süresini en aza indirmektir. Bu amaca ulaşmak için, evrimsel algoritmada probleme özel çaprazlama operatörü ve mutasyon operatörleri önerilmiştir. Çaprazlama operatörü, yeni bir birey oluşturmak için her iki ebeveynde depolanan bilgileri birleştirmektedir. Mutasyon operatörleri, bazı akıllı arama mekanizmalarını kullanarak komşu çözümleri keşfetmektedir. Operatörlerin bu özgün tasarımı, arama uzayının çeşitliliğini ve çözümlerin kalitesini arttırmaktadır. Sonuç olarak, evrimsel algoritmadan elde edilen iş akışı çizelgeleri, bulut sistemindeki iş akışının tamamlanma süresini azaltır. Önerilen çalışmanın performansı, iyi bilinen bilimsel iş akışları kullanılarak ölçüldü ve literatürdeki algoritmalarla karşılaştırıldı. Önerilen çalışma, yapılan testlerin %67'sinde ilgili tüm algoritmalardan daha iyi performans gösterirken, diğer testlerde literatürdeki çalışmalar ile aynı sonuçları elde etmiştir.

Anahtar Kelimeler

• İş Akışı Planlaması
• Bulut Bilişim
• Evrimsel Algoritma

Workflow Scheduling for Cloud Computing Using Evolutionary Algorithm

Abstract

Cloud computing provides powerful, highly scalable, flexible resources for real world applications. It also reduces the cost and operation expenses. Workflow scheduling is important for getting higher performance, reducing cost and using resources more efficiently in cloud computing. Workflow scheduling in cloud systems assigns tasks to resources available in the system and aims to utilize cloud resources by decreasing makespan of the workflow. In this study, an evolutionary algorithm is proposed to solve workflow scheduling problem. The main objective of this work is to minimize the makespan of the schedule. To achieve this goal, problem specific crossover operator and mutation operators are proposed in the evolutionary algorithm. The crossover operator will combine the problem-specific information stored in both parents to create a new individual. The mutation operators will explore neighbor solutions using some intelligent search mechanisms. This unique design of the operators increases the diversity of the search space and the quality of the solutions. As a result, the workflow schedules obtained from the evolutionary algorithm decreases the makespan of the workflow in the cloud system. The performance of the proposed study is measured using well-known scientific workflows and is compared with the algorithms from the literature. The proposed study outperforms all related algorithms in 67% of the test cases and obtains the same results in the remaining test cases.

Keywords

• Workflow Scheduling
• Cloud Computing
• Evolutionary Algorithm

Kaynakça

1. [1] E. H. Houssein, A. G. Gad, Y. M. Wazery, and P. N. Suganthan, “Task Scheduling in Cloud Computing based on Meta-heuristics: Review, Taxonomy, Open Challenges, and Future Trends”, Swarm and Evolutionary Computation, 2021, 62.
2. [2] M. R. Garey and D. S. Johnson, “A guide to the theory of np-completeness”, Computers and intractability, 1979, pp. 641–650.
3. [3] R. Zarrouk, I. E. Bennour, and A. Jemai, “A two-level particle swarm optimization algorithm for the flexible job shop scheduling problem”, Swarm Intelligence, 2019, pp. 1–24.
4. [4] N. Sadashiv, and S. D. Kumar, “Cluster, grid and cloud computing: A detailed comparison”, 2011 6th International Conference on Computer Science & Education (ICCSE), 2011, pp. 477–482.
5. [5] S. H. H Madni, Latiff, M. S. A. Abdullahi, M., Abdulhamid, and M. Usman, “Performance comparison of heuristic algorithms for task scheduling in iaas cloud computing environment”, PLoS ONE, 2017, 12: 5.
6. [6] A. Brandwajn, and T. Begin, “First-come-first-served queues with multiple servers and customer classes”, Performance Evaluation, 2019; 130, pp. 51–63.
7. [7] H. Topcuoglu, S. Hariri, and M. Wu, “Performance-effective and low-complexity task scheduling for heterogeneous computing”, IEEE transactions on parallel and distributed systems, 2002, 13(3), pp. 260-274.
8. [8] B. Li, L. Niu, X. Huang, H. Wu, and Y. Pei, “Minimum completion time offloading algorithm for mobile edge computing”, IEEE 4th International Conference on Computer and Communications (ICCC), IEEE, 2018, pp. 1929–1933.

9. [9] F. Yao, C. Pu, and Z. Zhang, “Task Duplication-Based Scheduling Algorithm for Budget-Constrained Workflows in Cloud Computing”, IEEE Access, 2021, 9, pp. 37262-37272.
10. [10] H. Aziza and S. Krichen, “A hybrid genetic algorithm for scientific workflow scheduling in cloud environment”, Neural Computing & Applications, 2020, 32(18).
11. [11] M. Zhang, H. Li, L. Liu and R. Buyya, “An adaptive multi-objective evolutionary algorithm for constrained workflow scheduling in Clouds”, Distributed and Parallel Databases, 2018, 36(2), pp. 339-368.
12. [12] G. Ismayilov and H. Topcuoglu, “Neural network based multi-objective evolutionary algorithm for dynamic workflow scheduling in cloud computing”, Future Generation computer systems, 2020, 102, pp. 307-322.
13. [13] W. Chen and E. Deelman, “WorkflowSim: A toolkit for simulating scientific workflows in distributed environments”, 2012 IEEE 8th International Conference on E-Science, Chicago, IL, USA, pp. 1-8. doi: 10.1109/eScience.2012.6404430.
14. [14] E. Deelman, K. Vahi, G. Juve, M. Rynge, S. Callaghan, P. J. Maechling, R. Mayani, W. Chen, R. Ferreira da Silva, M. Livny, and K. Wenger, “Pegasus, a workflow management system for science automation”, Future Generation Computer Systems, 2015, 46, pp. 17-35.
15. [15] S. Bharathi, A. Chervenak, E. Deelman, G. Mehta, M. -H. Su and K. Vahi, "Characterization of scientific workflows", 2008 Third Workshop on Workflows in Support of Large-Scale Science, Austin, TX, USA, 2008, pp. 1-10, doi: 10.1109/WORKS.2008.4723958.