Cluster Computing Journal: "FUGE: A joint meta-heuristic approach to cloud job scheduling algorithm using fuzzy theory and a genetic method"

Job scheduling is one of the most important research problems in distributed systems, particularly cloud environments/computing. The dynamic and heterogeneous nature of resources in such distributed systems makes optimum job scheduling a non-trivial task. Maximal resource utilization in cloud computing demands/necessitates an algorithm that allocates resources to jobs with optimal execution time and cost. The critical issue for job scheduling is assigning jobs to the most suitable resources, considering user preferences and requirements. In this paper, we present a hybrid approach called FUGE that is based on fuzzy theory and a genetic algorithm (GA) that aims to perform optimal load balancing considering execution time and cost. We modify the standard genetic algorithm (SGA) and use fuzzy theory to devise a fuzzy-based steady-state GA in order to improve SGA performance in term of makespan. In details, the FUGE algorithm assigns jobs to resources by considering virtual machine (VM) processing speed, VM memory, VM bandwidth, and the job lengths. We mathematically prove our optimization problem which is convex with well-known analytical conditions (specifically, Karush–Kuhn–Tucker conditions). We compare the performance of our approach to several other cloud scheduling models. The results of the experiments show the efficiency of the FUGE approach in terms of execution time, execution cost, and average degree of imbalance.

作业调度（Job scheduling）是分布式系统，尤其是云环境与云计算领域中最为关键的研究问题之一。此类分布式系统的资源兼具动态性与异构性，这使得实现最优作业调度成为一项颇具挑战的非平凡任务。若要在云计算场景下达成资源的最大化利用，亟需一种能够以最优执行时长与成本为作业分配资源的算法。作业调度的核心问题在于，需结合用户偏好与实际需求，将作业分配至最适配的资源。
本文提出一种名为FUGE的混合调度方法，该方法基于模糊理论与遗传算法（Genetic Algorithm，GA），旨在兼顾执行时长与执行成本以实现最优负载均衡。具体而言，我们对标准遗传算法（Standard Genetic Algorithm，SGA）进行改进，并结合模糊理论设计出基于模糊逻辑的稳态遗传算法，以提升标准遗传算法在总完工时间（makespan）维度上的性能表现。
详细来说，FUGE算法会综合考量虚拟机（Virtual Machine，VM）的处理速率、内存容量、网络带宽以及作业长度，完成作业到资源的分配工作。我们针对该优化问题开展了数学推导与证明，该问题属于凸优化问题，且满足经典解析条件（特指卡鲁什-库恩-塔克（Karush–Kuhn–Tucker）条件）。我们将所提方法的性能与多款其他云调度模型进行了对比实验。实验结果表明，FUGE方法在执行时长、执行成本以及平均负载不平衡度三个维度上均展现出优异的性能。