Dynamic Multi-Objective Workflow Scheduling in Cloud Computing


Thesis Type: Postgraduate

Institution Of The Thesis: Marmara University, Institute for Graduate Studies in Pure and Applied Sciences, Turkey

Approval Date: 2019

Thesis Language: English

Student: GOSHGAR ISMAYILOV

Supervisor: Haluk Rahmi Topcuoğlu

Abstract:

BULUT HESAPLAMA İÇİN DİNAMİK ÇOK-AMAÇLI İŞ AKIŞI ÇİZELGELENMESİ Bulut hesaplama, isteğe bağlı olarak farklı düzeylerde hizmetler sunan, heterojen ve dağıtık bir hesaplama sistemidir. Bulut sistemlerdeki mevcut kaynakların iş akışlarının yürütülmesi için, her bir iş akışının servis kalitesinde belirtilen hedefleri gözeterek etkin kullanımını amaçlayan iş akışı çizelgeleme problemi, üzerinde çokça çalışılmış araştırma problemlerinden biridir. Zaman içerisindeki kaynak arızalanmalarını ve iş akışı amaçlarının zaman içerisindeki değişimini göz önüne alan dinamik iş akışı çizelgeleme problemi, bu tez kapsamında, bir dinamik çok amaçlı eniyileme problemi olarak modellenmiştir. Yazılımsal veya donanımsal hatalar, ilk türdeki dinamik ögeye yönelik başlıca nedenler arasında sayılabilir. Değişen hizmet kalitesi gibi bulut sistemlerinde rastlanan farklı gerçek hayat senaryolarının bir iş akışının yürütülmesi sırasında eniyileme amaçlarının sayısını değiştirebilmesi, ikinci türdeki devingenliğe yönelik temel motivasyon kaynağı olarak düşünülebilir. Bu tezde, dinamik iş akışı çizelgeleme problemi için iki farklı çözüm geliştirilmiştir. İlk çözümde, literatürden seçilen, tahmine dayalı olmayan beş öncü çok-amaçlı evrimsel algoritma, bu problem için uyarlanmıştır. İkincil çözümde ise, çok amaçlı eniyileme problemleri için yoğun olarak kullanılan NSGA-II algoritmasını yapay sinir ağları ile birleştirerek, tahmine dayalı yeni bir dinamik çok amaçlı eniyileme algoritması (NN-DNSGA-II algoritması) önerilmiştir. Bu problem için çözümler, altı farklı amaç fonksiyonu arasındaki ödünleşim göz önünde bulundurularak oluşturulmuştur. Bu amaç fonksiyonları, iş akışının yürütülmesi için gerekli sürenin, maliyetin, enerjinin ve kaynaklar arası iş yükü dengesizliklerinin minimizasyonu, ve güvenilirliğin ve kaynaklardan faydalanma oranının maksimizasyonudur. Pegasus iş akışı yönetim sistemindeki uygulamalar ve Amazon EC2 sistemindeki kaynaklar kullanılarak deneysel çalışma gerçeklenmiştir. NN-DNSGA-II algoritması, domine edilmeyen çözümlerin sayısı, Schott aralığı ve Hiper-hacim metriklerine göre, diğer alternatiflerden belirgin olarak daha iyi sonuçlar verdiği gözlemlenmiştir. -------------------- DYNAMIC MULTI-OBJECTIVE WORKFLOW SCHEDULING IN CLOUD COMPUTING Cloud computing is a heterogeneous and distributed computing platform that delivers various levels of on-demand services to the customers. Workflow scheduling is one of the research challenges, which is largely addressed by cloud computing in the literature, where efficient utilization of cloud resources for workflow executions is targeted by considering the objectives specified in QoS requirements. In this thesis, the dynamic workflow scheduling problem is modelled as a dynamic multi-objective optimization problem (DMOP) where the source of dynamism is based on both resource failures and the number of objectives which may change over time. Software faults and/or hardware faults can be listed among the motivations for the first type of the dynamism. On the other hand, several real-life scenarios confronted in cloud computing such as changing in QoS requirements may change number of objectives at runtime during the execution of a workflow, which is the main motivation for the second type of dynamism. In this thesis, two different solutions are proposed for the dynamic workflow scheduling problem. In the first solution, five non-prediction based multi-objective evolutionary algorithms from the literature are adapted for the problem. In the second solution, a novel prediction-based dynamic multi-objective evolutionary algorithm (NN-DNSGA-II) is presented, where it incorporates neural networks with the NSGA-II algorithm. Trade-offs between six different objectives are considered while scheduling, which are minimization of makespan, cost, energy and degree of imbalance; and maximization of reliability and utilization. The empirical study is based on real-world applications from the Pegasus workflow management system and resource specifications from Amazon EC2. It reveals that our NN-DNSGA-II algorithm significantly outperforms the other alternatives in most cases with respect to three different metrics used for DMOPs with unknown true Pareto-optimal front, consisting of the number of non-dominated solutions, the Schott's spacing and the Hypervolume indicator.