Budget-constraint workflow scheduling for cloud computing using evolutionary algorithm

Abstract

BULUT HESAPLAMA İÇİN EVRİMSEL ALGORİTMA KULLANARAK BÜTÇE KISITLAMALI İŞ AKIŞI PLANLAMASI 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 algoritma tabanlı bir yöntem önerilmiştir. Bu çalışmanın temel amacı, bütçe kısıtlamasına uyarak programın çalışma süresini en aza indirmektir. Bu amaca ulaşmak için, evrimsel algoritmada probleme özel çaprazlama operatörü ve yerel arama teknikleri ö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.

BUDGET-CONSTRAINT WORKFLOW SCHEDULING FOR CLOUD COMPUTING USING EVOLUTIONARY ALGORITHM 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, we propose an evolutionary algorithm to solve workflow scheduling problem. The main objective of this work is to minimize the makespan of the schedule while obeying budget constraints. To achieve this goal, problem specific crossover operator and local search techniques 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.