Real Relative Encoding Genetic Algorithm for Workflow Scheduling in Heterogeneous Distributed Computing Systems

Abstract

This paper introduces a novel Real Relative encoding Genetic Algorithm (R<inline-formula><tex-math notation="LaTeX">$^{2}$</tex-math></inline-formula>GA) to tackle the workflow scheduling problem in heterogeneous distributed computing systems (HDCS). R<inline-formula><tex-math notation="LaTeX">$^{2}$</tex-math></inline-formula>GA employs a unique encoding mechanism, using real numbers to represent the relative positions of tasks in the schedulable task set. Decoding is performed by interpreting these real numbers in relation to the directed acyclic graph (DAG) of the workflow. This approach ensures that any sequence of randomly generated real numbers, produced by cross-over and mutation operations, can always be decoded into a valid solution, as the precedence constraints between tasks are explicitly defined by the DAG. The proposed encoding and decoding mechanism simplifies genetic operations and facilitates efficient exploration of the solution space. This inherent flexibility also allows R<inline-formula><tex-math notation="LaTeX">$^{2}$</tex-math></inline-formula>GA to be easily adapted to various optimization scenarios in workflow scheduling within HDCS. Additionally, R<inline-formula><tex-math notation="LaTeX">$^{2}$</tex-math></inline-formula>GA overcomes several issues associated with traditional genetic algorithms (GAs) and existing real-number encoding GAs, such as the generation of chromosomes that violate task precedence constraints and the strict limitations on gene value ranges. Experimental results show that R<inline-formula><tex-math notation="LaTeX">$^{2}$</tex-math></inline-formula>GA consistently delivers superior performance in terms of solution quality and efficiency compared to existing techniques.