Many computing workloads in big data and machine learning applications are structured as directed acyclic graphs (DAG) and deployed on PC clusters for parallel execution using multiple physical or virtual machines. The scheduling of such workloads is critical to the application performance such as execution time and a plethora of techniques have been developed, taking into account various aspects such as data locality, network bandwidth, and server capability. We formulate DAG-structured workload scheduling as a nonlinear integer programming (NIP) problem and prove it to be NP-complete. Our empirical study reveals a positive correlation between scheduling plan distance (SPD) and finish time gap (FTG), and based on this finding, we propose a running time gap strategy (RTGS) to tackle this scheduling problem in multiprocessor environments. RTGS follows the main optimization strategy in the family of whale optimization algorithm (WOA). We derive a new function and use a greedy algorithm to generate an effective scheduling plan in RTGS. Extensive experiments with real production traces from Alibaba on simulation environments and realistic Hadoop environments show that our approach significantly improves the stability of WOA when applied to the scheduling problem of DAG-structured workloads, and also reduces the workload completion time by up to $$93\%$$ 93 % in comparison with seven state-of-the-art baseline algorithms.

On GPU-based clusters, the training workloads of machine learning (ML) models, particularly neural networks (NNs), are often structured as Directed Acyclic Graphs (DAGs) and typically deployed for parallel execution across heterogeneous GPU resources. Efficient scheduling of these workloads is crucial for optimizing performance metrics such as execution time, under various constraints including GPU heterogeneity, network capacity, and data dependencies. DAG-structured ML workload scheduling could be modeled as a Nonlinear Integer Program (NIP) problem, and is shown to be NP-complete. By leveraging a positive correlation between Scheduling Plan Distance (SPD) and Finish Time Gap (FTG) identified through an empirical study, we propose to develop a Running Time Gap Strategy for scheduling based on Whale Optimization Algorithm (WOA) and Reinforcement Learning, referred to as WORL-RTGS. The proposed method integrates the global search capabilities of WOA with the adaptive decision-making of Double Deep Q-Networks (DDQN). Particularly, we derive a novel function to generate effective scheduling plans using DDQN, enhancing adaptability to complex DAG structures. Comprehensive evaluations on practical ML workload traces collected from Alibaba on simulated GPU-enabled platforms demonstrate that WORL-RTGS significantly improves WOA’s stability for DAG-structured ML workload scheduling and reduces completion time by up to 66.56% compared with five state-of-the-art scheduling algorithms.