.png){kind=icon}
.png){kind=icon}
Return
Real Relative Encoding Genetic Algorithm for Workflow Scheduling in Heterogeneous Distributed Computing Systems
.png){kind=icon}
PRE
AI
DOI：10.1109/TPDS.2024.3492210.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
This paper introduces a novel Real Relative encoding Genetic Algorithm (R(2)GA) to tackle the workflow scheduling problem in heterogeneous distributed computing systems (HDCS). R(2)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(2)GA to be easily adapted to various optimization scenarios in workflow scheduling within HDCS. Additionally, R(2)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(2)GA consistently delivers superior performance in terms of solution quality and efficiency compared to existing techniques.
Keywords:
Genetic algorithms
Encoding
Scheduling
Processor scheduling
Biological cells
Metaheuristics
Quality of service
Heuristic algorithms
Genetic operators
Distributed computing
Candidate task set
directed acyclic graph (DAG)
genetic algorithm
real encoding
workflow scheduling
Journal
IF:
6
Papers:
5.2K
Citations:
1.1W
Organization
View more organizations