Task Scheduling in Multi-Cloud Environments: A Graph Partitioning Approach Enhanced by Nested Genetic Algorithms

In today’s rapidly evolving cloud computing and IoT landscape, efficiently managing tasks across multiple cloud environments or IoT layers is essential for optimising resource utilisation, monitoring performance requirements, and meeting deadlines. To address this challenge, we present a methodology that merges graph partitioning with nested genetic algorithms (GAs) to optimise task allocation while prioritising to meet the deadlines. Our approach focuses on optimising partitions to ensure efficient and secure task execution across multi-cloud environments. Using the inherent structure of task dependencies and resource constraints depicted as a directed graph, we employ graph partitioning techniques to distribute tasks across available cloud or IoT resources while ensuring the task dependencies, thereby minimising makespan, optimising partitions and meeting the timing. To fortify our optimisation framework, various experiments were conducted. The results showcase our approach’s efficacy in achieving superior task scheduling efficiency, reductions in execution times, and optimisation of partitions, all while ensuring the strict timing requirements of critical systems.