Genetic Algorithm and Reinforcement Learning for ETL Pipeline Task Prioritization Under Limited Parallelism

Abstract

List-scheduling heuristics such as the critical-path (CP) rule are effective for minimizing makespan in DAG-structured ETL pipelines, but they provide no direct control over task waiting time. This study evaluates whether learned priority functions can approach CP performance while enabling a tunable trade-off between makespan and waiting time. We compare a genetic algorithm (GA) that optimizes a compact linear priority function and a reinforcement-learning (RL) policy with classical and previously proposed heuristics, including FIFO, CP, shortest processing time, weighted critical path, maximum dependencies, LJF, a hybrid slot-splitting method, and an optimized linear combination. Experiments use 112 test DAGs with 300-600 tasks generated from seven topology classes and four slot configurations. Learned policies are trained with five random seeds, and significance is assessed using the paired Wilcoxon signed-rank test. CP achieves the best makespan and is not surpassed by the learned methods. However, GA remains within 0.8% of CP and RL within about 2%, both with low across-seed variance. Under the scalarized objective $T_{\text{total}}+\lambda \cdot w_{\text{avg}}, \text{GA}$ and RL trace a makespan-waiting-time frontier. At $N=8$, GA reduces average waiting time by up to 29% relative to CP and RL by up to 43%, while keeping the makespan penalty below 3%. Additional median, 95th-percentile, and starvation metrics show that GA provides the most balanced reduction in waiting time while maintaining starvation close to CP.