Uncertainty-aware online deadline-constrained scheduling of parallel applications in distributed heterogeneous systems

Parallel application scheduling with deadline constraints is a crucial area in distributed heterogeneous systems, and various methodologies have been proposed. However, these approaches overlook the uncertainty of task execution times and the randomness of application arrivals. Therefore, this study aims to solve the online scheduling problem of parallel applications with deadline constraints by introducing a novel algorithm that addresses uncertainties. We develop a model for randomly arriving applications and introduce a dynamic task prioritization strategy to mitigate uncertainty. Additionally, we augment with a discard mechanism to bolster application success rates. We conducted nine groups of experiments using both randomly generated applications and real-world applications. Simulation results demonstrate that the proposed algorithm significantly outperforms three similar algorithms in terms of enhancing DAG success rate, resource utilization, and runtime efficiency.