Scheduling Algorithms in Parallel Processing: A Survey

Parallel processing is vital in modern computing, as it distributes complex tasks across multiple processors or cores, significantly improving performance and efficiency. The effectiveness of such systems is significantly influenced by scheduling algorithms that optimize execution time, load balancing, and resource utilization. An overview of scheduling for parallel processing is provided by this survey, with a focus on static, dynamic, heuristic, and hybrid algorithms. Special attention is given to Directed Acyclic Graph (DAG)-based algorithms, which addresses task dependencies and precedence constraints in real world systems. As scheduling problems are typically NP-Complete, various algorithms have been designed to address these challenges. This review paper provides a comprehensive analysis of various DAG-based scheduling algorithms, including list-based, task duplication, and clustering methods. These algorithms are evaluated in terms of their ability to minimize task execution time, improve resource utilization, and handle task dependencies. Additionally, this review examines the limitations of existing algorithms and highlights areas where additional research is necessary to tackle the increasing complexity of contemporary parallel computing systems.