Two-Layer Evolutionary Scheduling for Machine Learning Jobs in Multi-Cluster Environments

JOURNAL OF LATEX CLASS FILES, VOL. 14, NO. 8, AUGUST 2021

1

Two-Layer Evolutionary Scheduling for Machine Learning Jobs in Multi-Cluster Environments

arXiv:2611.09093v1 [cs.NE] 6 Nov 2026

Jingyuan Xu, Changwu Huang, Member, IEEE, Lemeng Pan, Ke Tang Fellow, IEEE and Xin Yao Fellow, IEEE

Abstract—The rapid growth of large-scale machine learning (ML) workloads has led to unprecedented demands on GPU cluster scheduling systems. However, existing heuristic schedulers struggle to handle the complexity and dynamics of multicluster GPU environments, often leading to load imbalance, long queuing delays, and poor alignment to business objectives. This paper formulates the ML scheduling problem in multi-cluster GPU environments as online multi-objective optimization that minimizes the average and maximum weighted queuing times while maximizing GPU time utilization. To solve this optimization problem, we propose EVO-GP, a two-layer evolutionary online scheduling method that decouples global job-to-cluster allocation from intra-cluster GPU resource allocation. At the job-to-cluster allocation layer, an evolutionary algorithm assigns arriving jobs to feasible clusters to promote load balance across clusters. At the resource allocation layer, a priority function automatically learned offline via genetic programming is used to rank jobs and guide GPU allocation within each cluster. Extensive experiments on both real-world data and simulated workloads demonstrate that the proposed EVO-GP method consistently outperforms state-of-the-art baselines, while maintaining superior adaptability and scalability. Index Terms—Machine learning job scheduling, multi-cluster scheduling, job allocation, resource allocation, evolutionary computation.

I. I NTRODUCTION

I

N recent years, machine learning (ML) techniques, particularly deep learning, have achieved remarkable success across various domains, including speech recognition, robotic control, and medical diagnostics [1], [2]. To meet the growing computational demands associated with ML model training, many leading technology companies have deployed large-scale GPU clusters [3], [4], [5]. However, the inherent complexity and distinctive characteristics of ML jobs often lead to low resource utilization and high operational costs under conventional scheduling strategies [6], [7]. Consequently, designing efficient scheduling strategies for GPU clusters has become a critical research challenge. Existing GPU cluster schedulers can be broadly classified into three categories. The first category is heuristic schedJingyuan Xu and Ke Tang is with the Guangdong Provincial Key Laboratory of Brain-inspired Intelligent Computation, Department of Computer Science and Engineering of Southern University of Science and Technology, Shenzhen, China. Changwu Huang is with the School of AI and Liberal Arts, Beijing NormalHong Kong Baptist University, Zhuhai, China. Lemeng Pan is with the Huawei Technologies Company, Ltd., Shenzhen, China. Xin Yao is with the School of Data Science, Lingnan University, Hong Kong SAR, China. Corresponding authors: Changwu Huang (changwuhuang@bnbu.edu.cn) and Xin Yao (xinyao@ln.edu.hk).

ulers [8], [9], [10], [11], [12], which rely on predefined rules (such as First-In First-Out (FIFO) [8], [9], Shortest Job First (SJF) [10]) to schedule jobs. While simple, these manually designed heuristics lack flexibility and generalization, making them difficult to adapt to dynamic workloads or changing business objectives. The second category consists of Integer Linear Programming (ILP)-based schedulers [13], [14], [15]. However, the strict requirement for linear objectives and constraints restricts their modeling flexibility and scalability in complex real-world environments. The third category encompasses reinforcement learning (RL)-based schedulers [16], [17], [18], [19], which learn scheduling policies from historical data or online interactions. While RL can capture dynamic patterns, the resulting policies lack sufficient interpretability and controllability, hindering the incorporation of domain expertise and making system behaviors difficult to explain [20]. From the perspective of scheduling scenarios, most existing GPU cluster schedulers focus on job scheduling within a single cluster. In real-world operations, however, large-scale GPU clusters often suffer from severe inter-job interference caused by resource contention [21], which can make shared clusters less efficient than dedicated private clusters [22]. Consequently, many systems adopt a cluster partitioning strategy, dividing a single large cluster into several logically isolated virtual clusters (VCs) to reduce management complexity and improve resource utilization [3], [5]. While this approach mitigates interference, it can lead to load imbalance across clusters: when some VCs experience serious queuing delays due to job backlogs, other VCs may remain underutilized, causing resource wastage. A common remedy is to periodically adjust the size of each VC, scaling down those under low loads and scaling up those under high demands [3]. However, such reconfigurations are typically performed only every few days [3], which is insufficient to respond to real-time workload fluctuations and limits the benefit of multi-cluster coordination. These observations reveal two key research gaps. From the method perspective, existing schedulers are either rigid (heuristics and ILP approaches) or opaque (RL-based methods), making them difficult to jointly optimize multiple objectives while retaining interpretability and ability to incorporate domain knowledge. From the scenario perspective, most work either focused on single-cluster environments or handle multicluster settings in an ad hoc and coarse-grained manner, lacking principled mechanisms for online, fine-grained coordination across clusters. To address these challenges, this paper formulates ML job scheduling in multi-cluster GPU environments as a multiobjective optimization problem that minimizes the average

JOURNAL OF LATEX CLASS FILES, VOL. 14, NO. 8, AUGUST 2021

and maximum weighted queuing times while maximizing GPU time utilization. Then, we propose EVO-GP, a twolayer evolutionary online scheduling framework for the formulated ML training job scheduling in multi-cluster GPU environments. This new framework adopts a collaborative optimization mechanism that decouples global job allocation from local resource allocation. At the job allocation layer, an evolutionary algorithm dynamically assigns incoming jobs to suitable clusters to ensure global load balance across clusters. At the resource allocation layer, a priority function is automatically learned by genetic programming (GP) and used to determine job priorities and guide GPU allocation within each cluster. Such a framework combines the global search capability of evolutionary algorithms with the interpretability of GP-learned rules. The main contributions of this paper include: • Problem formulation for multi-cluster ML job scheduling. Unlike existing scheduling models that are confined to a single cluster, we explicitly formulate the scheduling problem for rigid ML jobs in heterogeneous multi-cluster environments. The objectives minimize average and maximum weighted queuing times while maximizing resource utilization, aligning with both efficiency and practical requirements. • Two-layer evolutionary online scheduling method. We propose EVO-GP, a novel two-layer evolutionary online ML job scheduling method that performs job allocation and resource allocation. The upper layer handles global load balancing via evolutionary search, while the lower layer manages local resource allocation using a learned priority function. • Priority function automatically learned by GP. We employ a GP-based approach to automatically discover high-quality, human-interpretable priority functions. This offline learning process reduces reliance on humandesigned heuristics and improves adaptability to varying optimization preferences. • Comprehensive evaluation and generalization. Extensive experiments on both real-world traces and simulated workloads, in both multi-cluster and single-cluster settings, demonstrate that the proposed EVO-GP consistently outperforms state-of-the-art baselines according to commonly used key metrics. It balances multiple objectives and generalizes well across different cluster environments. The remainder of this paper is organized as below. Section II formalizes the multi-cluster ML job scheduling problem and briefly reviews the related work. Section III introduces our proposed EVO-GP framework, detailing the evolutionary job allocation algorithm and the GP-based priority function learning method. Section IV presents the experimental setup and analyzes the results. Finally, Section V concludes the paper. II. BACKGROUND In this section, we first formalize the online ML job scheduling problem in a multi-cluster GPU environment. We then review existing scheduling methods for ML workloads

2

in both single-cluster and multi-cluster settings, highlighting their design principles and limitations. This background lays the foundation for our proposed scheduling framework and clarifies how it differs from and advances prior work. A. Problem Formulation In this subsection, we formalize the online ML job scheduling problem in a multi-cluster GPU environment. We first present the system model and job attributes, then describe the online scheduling dynamics, and finally define the performance objectives and constraints that together constitute our problem formulation. 1) System Model: We consider a GPU system that consists of P clusters, denoted as P = {1, 2, . . . , P }. Each cluster p ∈ P contains Np homogeneous nodes, denoted as Np = {1, 2, . . . , Np }, each equipped with Gp GPUs. Thus, the total number of GPUs in cluster p is Np × Gp . This multi-cluster GPU environment serves as the foundational resource substrate for ML job scheduling [3], [12]. The set of jobs is denoted as J = {1, 2, . . . , J}. Each job j ∈ J is characterized by its arrival time aj , a userspecified cluster sj to which it is initially submitted, and an (estimated) training time or duration dj , the required number of workers rj and a total GPU demand gj , and a user-defined priority uj , where a larger uj indicates a more urgent job. Here, a worker represents an execution unit (e.g., a process in a virtual machine or container) on a compute node that executes a portion of the distributed training workload [14]. Following prior works [10], [19], we assume that the training time dj of each job j is known. In practical applications, dj can be replaced by an estimated duration of the job [23]. g Each worker of job j is assumed to consume rjj GPUs. These attributes jointly determine the resource demand and urgency of each job, and are crucial for designing effective scheduling strategies. When the scheduler performs a scheduling operation, it involves two key decisions: (1) Job allocation across clusters. For each cluster p, the set of jobs tentatively assigned to cluster p is denoted by Yp . To balance load, a job j may be reassigned to a cluster different from its user-specified cluster sj ; the actual allocated cluster is denoted by cj . (2) Resource allocation within clusters. For each cluster p, this decision jointly determines: (i) Priority ordering within a cluster. For each cluster p, the relative priority of jobs in Yp is represented by a permutation (vector) yp . A job that appears earlier in yp is assigned a higher “relative priority”. We use “relative priority” to denote the ordering produced by a scheduling rule (e.g., FIFO, SJF) or a learned priority function, so as to distinguish it from the user-defined priority uj . (ii) Worker placement on nodes. Let xj,n ∈ {0, 1, . . . , rj } denote the number of workers of job j placed on node n. If xj,n = 0, then job j is not executed on node n. The placement variables xj,n must satisfy both job-level and node-level capacity constraints. 2) Online ML Job Scheduling in a Multi-Cluster Environment: We now describe the online scheduling problem in a dynamic setting. Before making a scheduling decision at time t, the scheduler must obtain both static and dynamic information about jobs. In addition to the static attributes introduced in

JOURNAL OF LATEX CLASS FILES, VOL. 14, NO. 8, AUGUST 2021

3

Section II-A1, at time t, each job j is associated with a remain(t) ing training time dj and an already accumulated queuing time (t) qj . Thus, in the dynamic model, a ML job can be represented (t) (t) as an octuple j = ⟨aj , sj , dj , rj , gj , uj , dj , qj ⟩, where the first six components are static and the last two capture the current execution state. Let J (t) denote the set of jobs that have arrived by time t but have not yet completed. This set is partitioned into running jobs Je and queued jobs Jq . For each running job j ∈ Je , let wj,n denote the number of workers of job j placed on node n before the scheduling operation at time t. Given a scheduling decision at time t—including the job-tocluster assignment {Yp }, the relative priority order yp within each cluster, and the worker placement {xj,n }—we can derive the start time of each job. Let Sj denote the start time of job j ∈ YpP , where Sj ≥ t. If the resources are sufficient at time g t, i.e., j∈Yp,≤j xj,n · rjj ≤ Gp holds for all n ∈ Np (where Yp,≤j is the set containing job j and all jobs in Yp that have a higher relative priority than j), then job j can start immediately and thus Sj = t. Otherwise, job j must wait until some higherpriority jobs complete and release sufficient resources. In this case, the start time of job j is X gk (xk,n · · 1Fk >Fw ) Sj = min {Fw | w∈Yp,<j rk k∈Yp,≤j (1) ≤ Gp , ∀n ∈ Np },

c) GPU Time Utilization: To reduce resource fragmentation and improve GPU resource efficiency, we define GPU time utilization as the ratio between the total GPU hours requested by jobs and the total GPU capacity over the planning horizon: P (t) j∈J (t) gj · dj  Cu =  (4)   P G · N · max F − t p p j p∈P j∈J (t)

d) Combined Objective Function of Online MultiObjective Scheduling Problem: We combine the three objectives via weighted-sum and formulate the following minimization problem: minimize

ω1 · Cq,avg + ω2 · Cq,max + ω3 · (1 − Cu ) (5)

subject to Y1 ∩ Y2 ∩ ... ∩ YP = ∅

(6) (t)

Y1 ∪ Y2 ∪ ... ∪ YP = J X xj,n = rj , ∀p ∈ P, ∀j ∈ Yp

(7) (8)

n∈Np

X j∈Yp

xj,n ×

gj ≤ Gp , ∀p ∈ P, ∀j ∈ Yp rj

 Gp × r j × Np ≥ rj , ∀p ∈ P, ∀n ∈ Np , ∀j ∈ Yp gj Sj = t ∧ xj,n = wj,n , ∀p ∈ P, ∀n ∈ Np , ∀j ∈ Jn

(9)



(10) (11)

(t)

where Fw = Sw + dw denotes the completion time of job w, 1Fk >Fw is an indicator function that takes the value 1 if Fk > Fw and 0 otherwise, and w ∈ Yp,<j denotes the set of jobs in Yp that have a higher relative priority than j. The queuing time of job j under the current scheduling scheme is (t) (t) denoted by qj = qj + Sj − t, which consists of the time job j has already spent waiting before time t plus the additional waiting time from t until its start time Sj . 3) Objective Functions: We consider three objectives, and the specific calculation methods for each objective are as follows. a) Average Weighted Queuing Time: Following [14], we define the average weighted queuing time as X 1 (t) Cq,avg = uj · qj (2) (t) |J | (t) j∈J

Here, the user priority uj serves as a weight for the queuing time of job j. This metric encourages earlier execution of jobs with a higher user priority. b) Maximum Weighted Queuing Time: Classical heuristic algorithms, such as the Shortest Remaining Service First (SRSF) algorithm [10], can achieve favorable performance in terms of average job completion time. However, they tend to prioritize jobs with shorter remaining times and lower resource requirements, which may cause large jobs to experience excessively long queuing delays, degrading user experience. To alleviate this issue and avoid starvation, we introduce the maximum weighted queuing time: (t)

Cq,max = max uj · qj j∈J (t)

(3)

We employ weighted-sum scalarization to integrate the objectives into a single optimization target. Constraints (6) and (7) enforce unique job allocation, i.e., each job is assigned to exactly one cluster and cannot simultaneously occupy resources in multiple clusters. Constraint (8) ensures that the number of workers placed for each job equals its required worker count. Constraint (9) is the node capacity constraint, requiring that the total number of GPUs used by all jobs on any node does not exceed the node’s GPU capacity. Constraint (10) is the cluster capacity constraint, ensuring that the number of workers required by a job j does not exceed the maximum number j kof workers that cluster p can host for that job. Here, Gp ×rj denotes the maximum number of workers of job j gj that a single node in cluster p can accommodate. Constraint (11) defines the preemption constraint for jobs. Specifically, a non-preemptive job refers to one whose allocated resources remain unchanged under the new scheduling scheme and does not need to re-enter the queue. The set Jn denotes the set of non-preemptive jobs. In practice, whether a job can be preempted is determined by specific rules, which may vary across different business scenarios. In this paper, we employ a simple rule to define the set of non-preemptive jobs as Jn = {j ∈ Je | sj = cj }, which implies that jobs currently running in the user-specified cluster cannot be preempted. Our work focuses on the scheduling decision process rather than the system-level overhead associated with job preemption. Therefore, we assume that preempted jobs can be resumed without any loss of progress. These definitions complete our formulation of the online multi-cluster ML job scheduling problem. We next review

JOURNAL OF LATEX CLASS FILES, VOL. 14, NO. 8, AUGUST 2021

4

existing scheduling methods in both single-cluster and multicluster environments.

adaptive performance while retaining explicit and controllable scheduling policies in multi-cluster GPU environments.

B. Related Work

III. T WO - LAYER E VOLUTIONARY S CHEDULING FOR ML J OBS IN M ULTI -C LUSTER E NVIRONMENTS

In this subsection, we review existing scheduling methods for ML workloads that are most relevant to our problem. Most existing studies focus on single-cluster scheduling. They employ heuristic rules [10], [9], [11], [12], mathematical programming [14], [13], [15], or reinforcement learning [24], [18], [19], [16] to resolve resource contention within a single cluster. Despite their effectiveness, these classical scheduling methods become increasingly inadequate as cluster scale grows. As cluster size expands, contention on shared resources (e.g., network and storage) can significantly degrade training performance [21], and a single shared cluster may even underperform dedicated clusters [22]. Accordingly, several works propose unified schedulers for large-scale clusters [4], [19], [25], [21]. In industry, large clusters are often partitioned into multiple isolated virtual clusters (VCs) to simplify management and mitigate interference [3], [5]. This partitioning introduces a key challenge: load imbalance across VCs, which can cause resource idleness in some VCs and long queuing delays in others [3]. Dynamic VC resizing can partially mitigate imbalance [3], but it is typically performed on multi-day cycles and thus cannot respond to short-term demand fluctuations. Lyra [11] addresses imbalance via resource loaning between an inference and a training cluster, but its mechanism is tailored to a two-cluster setting and does not directly generalize to many training clusters. In a multi-cloud task scheduling scenario, Panda et al. [26] adopts a heuristic Minimum Completion Time (MCT) policy, which assigns each task to the cluster that yields the smallest predicted completion time. Similarly, MAST [27] globally schedules large-scale ML training jobs across geo-distributed datacenters by jointly optimizing placement and data transfer under WAN constraints. However, these approaches are limited by their focus on specific infrastructure constraints and lack the generality and automated policy-discovery capabilities. In summary, existing scheduling methods either operate within a single cluster or handle multi-cluster environments in a coarse-grained manner, typically through infrequent mechanisms such as cluster resizing or limited resource borrowing. Such approaches react to load imbalance only at a coarse time scale and are unable to cope with highly dynamic workload variations. In contrast, we address multi-cluster scheduling by directly and online assigning each arriving job to an appropriate cluster, enabling fine-grained and immediate responses to dynamic load changes. Moreover, existing methods are methodologically either human-designed with limited adaptability (heuristics and ILP approaches) or black-box (RL-based methods). This paper formulates multi-cluster ML job scheduling as an online multiobjective optimization problem, jointly considering average and maximum weighted queuing times while maximizing GPU time utilization. Building on this formulation, we propose a two-layer evolutionary scheduling framework with GP-learned, human-interpretable priority functions, providing

This section presents our proposed two-layer evolutionary online scheduling framework for the formulated ML training jobs in multi-cluster GPU environments. The framework, termed EVO-GP, adopts a collaborative optimization mechanism that explicitly decouples global job allocation from local resource allocation. At the job allocation layer, an evolutionary algorithm dynamically assigns incoming jobs to suitable clusters to ensure global load balance across clusters. At the resource allocation layer, a priority function is automatically learned offline by GP and used to determine job priorities and guide GPU allocation within each cluster. Section III-A presents the overall framework of the EVO-GP. Section III-B describes the implementation details of the evolutionary job allocation, and Section III-C introduces the implementation details of the resource allocation procedure and offline learned priority function using GP. A. Algorithm Overview EVO-GP is a two-layer evolutionary online scheduling framework that decouples global job allocation from local resource allocation in multi-cluster GPU environments. As shown in Fig. 1, the upper layer (Evolutionary Job Allocation) decides which cluster each job should run on, while the lower layer (Resource Allocation with a GP-learned priority function) decides how to allocate GPUs within each cluster. This separation addresses the combinatorial complexity of multi-cluster scheduling by (i) searching over job-to-cluster mappings under cluster-level feasibility constraints and (ii) applying a reusable intra-cluster allocation policy. Meanwhile, the priority function used in the resource allocation layer is learned offline by GP, thereby reducing reliance on handcrafted heuristics and enabling adaptation to multi-objective requirements such as delay, fairness, and utilization.

Fig. 1. Overall illustration of EVO-GP.

At the job allocation layer, EVO-GP employs an evolutionary algorithm in which each individual represents a

JOURNAL OF LATEX CLASS FILES, VOL. 14, NO. 8, AUGUST 2021

complete job-to-cluster assignment. Starting from a feasibilityaware randomized initialization, the algorithm repeatedly applies crossover and mutation to generate new assignments that satisfy cluster feasibility constraints. For each candidate assignment, the lower-layer resource allocation procedure constructs a feasible schedule and evaluates its fitness using the scalarized multi-objective function (Eq. (5)). Through environmental selection, high-quality assignments are retained and guide subsequent search. In this way, the evolutionary job allocation layer intelligently explores the combinatorial space of job–cluster assignments under complex constraints, while remaining agnostic to the internal details of the resource allocation policy. At the resource allocation layer, EVO-GP performs resource allocation with a GP-learned priority function. Given a fixed job-to-cluster assignment from the upper layer, this module first respects non-preemptive jobs by keeping their current placements and assigning them the highest priority, and then uses the learned priority function f (·) to rank the remaining jobs within each cluster. Jobs are scheduled in the order determined by f (·), and their workers are placed using a Best Fit strategy based on the earliest start time and residual GPU capacity, turning a job allocation plan into a complete executable schedule. The priority function f (·) is obtained offline by GP, which searches the space of interpretable expressions over key job features (e.g., remaining duration, queuing time, user priority, GPU demand) to find a suitable priority for the scheduling goal. During online scheduling, the evolutionary job allocation layer and the priority-based resource allocation layer collaborate as follows: the upper layer proposes different job-to-cluster mappings, the lower layer realizes these mappings into concrete schedules, and the resulting objective values feed back to the evolutionary search. This collaborative mechanism enables joint optimization of global load balancing and local scheduling quality, while preserving flexibility and interpretability (via a pluggable f (·) in human-readable GP expression). The implementation details of EVO-GP are shown in Algorithm 1. The inputs include the set of unfinished jobs J (t) , the non-preemptive job set Jn , the cluster set P, the population size n, the mutation rate r, and the priority function f (·). The algorithm first identifies schedulable jobs Js = J (t) \ Jn (line 1) and encodes them for compact representation (line 2). It then initializes a feasible population (line 3) and iteratively generates offspring via crossover and mutation (lines 5–13). Each offspring individual is evaluated by invoking the resource allocation procedure to construct a complete schedule and compute its fitness, where Xi records the worker placements and Yi records the intra-cluster job orderings. (lines 14–17). The best n individuals are selected to form the next generation (line 18). After termination, the best individual is decoded and passed to the resource allocation procedure to output the final schedule (lines 20–22). B. Details for Evolutionary Job Allocation This subsection details evolutionary job allocation components, including the individual representation, population

5

Algorithm 1: Pseudo-code of the Proposed Two-layer Evolutionary Scheduling Method (EVO-GP) Input : Job set J (t) , Non-preemptive job set Jn , Cluster set P, Population size n, Mutation rate r, Priority function f (·). Output: Solution s. (t) 1 Js ← J \ Jn ; 2 Encode the jobs in Js ; 3 I ← Population Initialization; 4 while termination conditions are not met do 5 N ← ∅; // Job Allocation 6 while |N | < n do 7 p1 , p2 ← Randomly select two individuals from I; 8 o1 , o2 ← Perform crossover between p1 and p2 ; 9 if rand(0, 1) < r then 10 Apply mutation to individuals o1 and o2 ; 11 end 12 N ← N ∪ {o1 , o2 }; 13 end // Resource Allocation 14 for i ∈ N do 15 (Xi , Yi ) ← ResourceAllocation(i, Js , Jn , P, f (·)); 16 end 17 Evaluate the fitness of all individuals in N ; 18 I ← Select n best individuals from N ∪ I; 19 end 20 o ← The optimal individual from I; 21 (X , Y) ← ResourceAllocation(o, Js , Jn , P, f (·)); 22 s ← (X , Y)

initialization, crossover and mutation operators, and fitness evaluation. 1) Individual Representation: We represent an individual as a one-dimensional vector of length |Js |, where each index corresponds to a job and the value denotes the assigned cluster ID. Fig. 2 illustrates an example. Since each job index appears exactly once, the representation satisfies the unique allocation constraints in Eqs. (6)–(7). 2) Population Initialization: We employ randomized initialization; however, purely random assignments may violate constraint (10) (e.g., assigning a large job to an incapable cluster). Such infeasible individuals may prevent the construction of a valid schedule and hinder search. Therefore, when initializing the assigned cluster for job j j, wek first compute the G ×r feasible cluster set Pf,j = {p ∈ P| pgj j × Np ≥ rj }, and then randomly select a cluster from Pf,j . 3) Crossover and Mutation Operators: During offspring generation, adopt a single-point crossover operator [28]. For mutation, we use two complementary strategies: (i) singlejob mutation, which reassigns one randomly selected job to another feasible cluster, and (ii) swap-based mutation, which exchanges the assigned clusters of two jobs. One strategy is selected uniformly at random each time mutation is applied.

JOURNAL OF LATEX CLASS FILES, VOL. 14, NO. 8, AUGUST 2021

Fig. 2. An example of an individual encoding and its corresponding scheduling.

The mutation operator must preserve feasibility with respect to (10). For the single-job mutation, the new cluster is sampled from the job’s feasible set. For the swap mutation, given a solution, we randomly select a job j with current cluster p and its feasible cluster set Pf,j . Let Ja denote the set of jobs assigned to clusters in Pf,j . We then filter Jaj to obtain k jobs that can Gp ×rw × Np ≥ rw }. run on cluster p: Jf = {w ∈ Ja | gw Finally, we randomly select one job from Jf and swap its cluster assignment with that of job j, ensuring the resulting solution remains feasible. 4) Fitness Evaluation: Each individual encodes only a jobto-cluster mapping; thus, we invoke the resource allocation procedure to construct a complete schedule before computing the objective value. We use Eq. (5) as the fitness function, so the evolutionary job allocation directly optimizes the scalarized multi-objective formulation. C. Details for Resource Allocation with Priority Function Learned by GP (RAPFTGP) When GPU resources are insufficient to satisfy concurrent job demands, the scheduler must resolve contention by prioritizing jobs. Such policies can be expressed as a priority function, which maps job features to a scalar score used for ranking. Prior work shows that priority function design critically affects ML scheduling performance [10]. To automatically derive effective and interpretable rules, we use GP to learn a priority function offline. Algorithm 2 describes the resource allocation procedure. The inputs include an individual c (job-to-cluster mapping), the schedulable job set Js , the non-preemptive job set Jn , the cluster set P, and the priority function f (·). The algorithm initializes X to record worker placements and Y to record intra-cluster job orderings. It then processes clusters sequentially. For each cluster, it first fixes non-preemptive jobs by preserving their placements and placing them at the front of the ordering. Note that the relative order among nonpreemptive jobs does not affect the scheduling outcome, since they are already running at time t and their resource allocations are fixed (lines 5–12). For schedulable jobs, it ranks jobs using f (·) and allocates resources in that order (line 14). For each

6

Algorithm 2: Resource Allocation Input : Individual i, The set of jobs to be scheduled Js , non-preemptive job set Jn , cluster set P, Priority function f (·). Output: Solution s. 1 X ← ∅, Y ← ∅; 2 for p ∈ P do 3 Jp,n ← {j ∈ Jn |cj = p}; 4 Jp,s ← {j ∈ Js |i[j.id] = p}; 5 yp ← An empty list; // Handling Non-preemptive Jobs 6 for j ∈ Jp,n do 7 for n ∈ Np do 8 xj,n ← wj,n ; 9 X ← X ∪ {xj,n }; 10 end 11 Append j to yp ; 12 end // Handling Schedulable Jobs 13 while |Jp,s | > 0 do 14 j ← The job with the minimum f (j) in Jp,s ; 15 tj,s ← Find the earliest feasible start time of j based on already scheduled jobs; // Best Fit Allocation 16 for each worker of job j do g 17 n ← arg min {σ(n, tj,s )|σ(n, tj,s ) ≥ rjj }; n∈Np

xj,n ← xj,n + 1; 19 X ← X ∪ {xj,n } 20 end 21 Append j to yp ; 22 Jp,s ← Jp,s \ {j}; 23 end 24 Y ← Y ∪ {yp }; 25 end 26 s ← (X , Y); 18

job, it computes the earliest feasible start time and then applies Best Fit to place each worker (lines 15–20). The earliest start time of job j is computed according to Eq. (12).

tj,s = min

  

tj,s ∈ T

X  σ(n, tj,s )  n∈Np

gj /rj

≥ rj

 

,



(12)

T = {t} ∪ {Fw | w ∈ Yp,<j }. where Yp,<j denotes the set of jobs in cluster p that have already been scheduled before job j according to the priority order (i.e., the jobs that have already been added into yp when job j is being scheduled), and the candidate time set T consists of the current time t and the completion times of these jobs, since resource availability only changes at these time instants. For each job w, its completion time is given by (t) Fw = tw,s + dw . Moreover, σ(n, tj,s ) denotes the remaining capacity of node n ∈ Np at time tj,s under the current scheduling decision.

JOURNAL OF LATEX CLASS FILES, VOL. 14, NO. 8, AUGUST 2021

The remaining capacity of node n at time tj,s can be calculated as  X  gw σ(n, tj,s ) = Gp − xw,n · 1Fw >tj,s · . (13) rw w∈Yp.<j

After completing the resource allocation for all clusters, (X , Y) is output as the complete solution (line 26). Algorithm 3 presents the GP procedure for learning the priority function. The inputs include a training problem instance set D, a validation problem instance set V, population size n, mutation rate r, and training subset size α. Both D and V consist of multiple problem instances, where each instance composed of a set of machine learning jobs and a set of clusters. In each generation of GP, a subset Dsub is sampled for fitness evaluation [29]; offspring are generated via subtree crossover and mutation; and the best individuals are selected for the next generation. After termination, individuals are evaluated on V and the best one is converted into a humanreadable expression, yielding the priority function f (·) used in Algorithm 2. The detailed implementation for learning the priority function with GP is presented below. Algorithm 3: Priority Function Learning with GP Input : Training problem instance set D, Validation problem instance set V, Population size n, Mutation rate r, The size of the training subset α. Output: Score Function f (·) 1 I ← Initialize population; 2 while termination conditions are not met do 3 O ← ∅; 4 Dsub ← Randomly select α instances from D; 5 for |O| < n do 6 p1 , p2 ← Select from I with k-tournament selection approach; 7 c1 , c2 ← Offspring generated by crossover of p1 and p2 ; 8 if rand(0, 1) < r then 9 Apply the mutation operation to individual c1 and c2 . 10 end 11 O ← O ∪ {c1 , c2 }; 12 end 13 for i ∈ I ∪ O do 14 Evaluate the fitness of i with Dsub ; 15 end 16 I ← Select n individuals with the best fitness; 17 end 18 for i ∈ I do 19 Evaluate the fitness of i with V; 20 end 21 rbest ← Select the best individual; 22 f (·) ← Convert individual rbest into priority function; 1) Individual Representation: In the algorithm, individuals are represented using a tree structure (binary tree), where the internal nodes are selected from the function set, and the leaf

7

nodes are selected from the terminal set. This representation can be directly converted into prefix, infix, or postfix expressions, yielding an interpretable priority function [30]. 2) Function Set and Terminal Set: Table I summarizes the (t) terminal and function sets. We include remaining duration dj and total GPU demand gj to capture temporal and resource (t) dimensions [10], and include queuing time qj and user priority uj to align with the optimization objectives. The function set is {+, −, ×, %}, where % denotes protected division [31]. If the denominator is zero, the numerator is returned directly; otherwise, the division operation is performed. TABLE I F UNCTION AND T ERMINAL SETS OF GP Terminal Set

Description

(t) dj (t) qj uj

The remaining duration of job j.

gj

The length of time that job j has been queued. The priority defined by the user for job j. The total number of GPUs required by job j.

Function Set

+, −, ×, % (protected division)

3) Fitness Evaluation: The fitness of a GP individual should reflect the scheduling quality induced by its priority function. Thus, for each problem instance (jobs and cluster resources), we construct a schedule using Algorithm 2 with the candidate priority function and compute the resulting objective value. To reduce learning cost, we use the Minimum Completion Time (MCT) heuristic [26] for job-to-cluster assignment during priority function learning, while keeping the intra-cluster resource allocation identical. This choice avoids the large computational overhead of running evolutionary job allocation for each GP fitness evaluation, while still exposing GP to representative scheduling dynamics. In the fitness evaluation process of GP, a common method is to evaluate each individual on all training problem instances [30]. However, when the training problem instance set is large, this becomes expensive. Inspired by [29], we construct a compact training subset in each generation for fitness evaluation (Fig. 3).

Fig. 3. A training subset is constructed within each generation for fitness evaluation.

The fitness of an individual is computed as the sum of its scores over instances in Tsub : f itness(c) =

X i∈Tsub

score(c, i)

(14)

JOURNAL OF LATEX CLASS FILES, VOL. 14, NO. 8, AUGUST 2021

8

where score(c, i) represents the score of individual c on the training instance i. To reduce variance across instances, we normalize objective values [30], score(c, i) =

Oc,i Obase,i

the given mean. The simulator uses a 1-second time unit (fractional seconds are discarded). The last column “Weight” specifies the relative sampling probability of each job type in the workload simulator, reflecting its occurrence frequency in the production traces. For each cluster, the simulator first filters out infeasible job types and then samples types according to their weights. Job priorities are sampled uniformly from {1, 2, 3}. Job arrivals follow a Poisson process with rate λ. In our simulations, the total number of arrivals per cluster is set to 10 × Np [32], where Np denotes the number of nodes in cluster p. For each cluster p, λ is sampled N ×G uniformly from [λmin , λmax ], where λmax = E[dpj ×gpj ] and λmin = λmax [32], [33]. 4

(15)

where Oc,i is the objective value on problem instance i using the priority function of individual c, and Obase,i is the objective value using a baseline priority function. We use SRSF [10] as the baseline, whose priority function is denoted (t) by f (j) = gj · dj (smaller values indicate higher priority), based on its stable performance across workload pressures observed in our experiments. IV. E XPERIMENTAL S TUDIES In this section, we empirically evaluate EVO-GP in both multi-cluster and single-cluster GPU environments. Although the primary focus of this paper is multi-cluster scheduling, we additionally include single-cluster experiments to demonstrate that EVO-GP can be adapted beyond the specific objective set and environment considered in this work. We first describe the experimental settings, including workloads, cluster configurations, performance metrics, and baselines. We then present results in three aspects: (i) overall performance in multi-cluster scenarios, (ii) performance and adaptability in single-cluster scenarios, and (iii) robustness under varying load pressures. Finally, we conduct ablation studies to quantify the contribution of each component in our proposed framework and report the online running time overhead of EVO-GP. Unless otherwise stated, all experimental results reported in this section are obtained by averaging over 15 independent runs with different random seeds. A. Experimental Setting 1) Workload Types: We conduct experiments on two types of workloads: (i) real-world job traces collected from SenseTime’s production cluster [3], and (ii) a workload simulator constructed through trajectory analysis of Huawei’s production cluster. Both workloads correspond to online settings, where jobs arrive sequentially and the scheduler is triggered upon each job arrival. • SenseTime Traces [3]: To evaluate generality of our framework on real traces and conventional objectives, we use data from SenseTime’s Venus cluster. Specifically, we use a two-week snapshot containing 9,281 jobs on a cluster with 1,064 GPUs as the test set, and the preceding two-week snapshot containing 9,820 jobs as the training set. • Workload simulator: We employ the simulator provided by Huawei to evaluate EVO-GP under controllable multicluster configurations. The simulator models 21 job types, summarized in Table II. The first two columns specify the required number of workers and GPUs for each type. We consider synchronous data-parallel training, where GPUs GPU Num per worker are fixed as Worker Num . The third column reports the mean training time (hours); for each type, training times follow an exponential distribution with

TABLE II T YPES OF M ACHINE L EARNING J OBS AND T HEIR C HARACTERISTICS Worker Num 1 1 1 1 2 2 2 2 3 4 4 6 8 8 10 12 16 16 16 24 32

GPU Num

Avg. Training Hours

Weight

1 2 4 8 2 4 8 16 24 4 32 48 8 64 80 96 16 64 128 192 256

1.499136 0.906435 1.050502 3.285060 1.701724 1.348965 0.167778 6.448247 0.277222 0.039333 4.548746 5.659565 0.751250 11.871677 6.448889 0.449074 0.135417 0.036111 12.898697 0.198611 12.730382

2.44 × 10−1 1.23 × 10−1 8.20 × 10−2 4.29 × 10−1 3.00 × 10−2 1.00 × 10−3 1.80 × 10−4 2.40 × 10−2 3.70 × 10−4 2.64 × 10−4 2.90 × 10−2 3.30 × 10−3 4.00 × 10−4 1.93 × 10−2 8.50 × 10−4 1.70 × 10−4 1.00 × 10−3 5.30 × 10−5 3.91 × 10−2 5.30 × 10−5 8.60 × 10−4

2) Cluster Resource Model: In multi-cluster experiments, each test instance consists of multiple clusters with varying numbers of nodes. The number of clusters is sampled from [2, 26], following the virtual-cluster settings reported in SenseTime [3]. The number of nodes per cluster is sampled from [10, 100], and each node is equipped with 8 GPUs. For the SenseTime Venus trace, we follow [12], [34] and scale down the cluster capacity to 800 GPUs to reduce the impact of CPUintensive workloads. 3) Performance Metric: To evaluate the effectiveness of our algorithm, we conduct experiments in two parts. The first part uses the simulator to test multi-cluster scheduling under the objectives defined in Eqs. (2)–(4). The second part uses the SenseTime trace to evaluate EVO-GP in a single-cluster setting under commonly used metrics, demonstrating that our approach can be adapted beyond the specific objective set used in the simulator. For multi-cluster experiments, we report: •

Average Weighted Queuing Time (Eq. (2)): encourages shorter waiting times, especially for high-priority jobs.

JOURNAL OF LATEX CLASS FILES, VOL. 14, NO. 8, AUGUST 2021

Maximum Weighted Queuing Time (Eq. (3)): captures worst-case delay and mitigates starvation. • GPU Time Utilization (Eq. (4)): measures the efficiency of GPU-time usage. For the single-cluster experiments, we report: • Average Job Completion Time (AvgJCT): a conventional metric for ML cluster scheduling. • Maximum Queuing Time (MaxJCT): reflects tail latency in waiting time; it often conflicts with optimizing Average Job Completion Time because policies favoring short jobs can delay large jobs. 4) Baselines and Implementation Details: We compare EVO-GP with widely used schedulers, including (i) Spark [8], (ii) Liquid [9], (iii) Tiresias [10], and (iv) Lyra [11]. Spark uses Round Robin for placement, while the other methods use Best Fit placement. Spark [8] and Liquid [9] apply FIFO ordering. When job durations are known, Tiresias [10] uses SRSF to rank jobs; Lyra applies Best-Fit Decreasing. Since dedicated multi-cluster allocation baselines are limited, we additionally use the heuristic Minimum Completion Time (MCT) method [26] as a baseline cluster-allocation strategy. The specific parameter configurations for EVO-GP are set as follows. For the evolutionary job allocation layer, we set the population size to 100, the maximum number of generations to 200, and the mutation rate to 0.1. For GP-based priority function learning, we initialize the population using the ramped half-and-half method [35]. The training set contains 50 simulator-generated instances, and the per-generation training subset size is set to 3. The remaining GP hyperparameters follow [30]: population size 512, maximum generations 100, mutation rate 0.1, and maximum tree depth 7.

9

•

B. Performance of the Algorithm in a Multi-Cluster Scenario We compare EVO-GP against the baselines in multi-cluster settings. We use Eq. (5) (weighted sum of the three objectives) as the primary evaluation metric, with equal weights (ω1 = ω2 = ω3 = 1). Fig. 4 reports the ranking results on 30 test instances. We denote by MCT-LIQUID, MCTTIRESIAS, MCT-SPARK, and MCT-LYRA the combinations of MCT job allocation with each single-cluster scheduler. MCT-GP uses MCT for job allocation and the GP-learned priority function for intra-cluster resource allocation. EVO-GP uses evolutionary job allocation with the GP-learned priority function for resource allocation. We rank all algorithms on 30 instances. As shown in Fig. 4, with MCT allocation, the GP-learned priority function achieves the best performance on 25 instances, second on 3 instances, and third on 2 instances. When both allocation and resource scheduling are optimized by EVO-GP, our method achieves the best performance across all instances. Experimental results indicate that scheduling algorithms such as Spark [8] and Liquid [9], which rely on FIFO-based strategies with relative priority ordering, exhibit larger performance variance under the given workload. This is primarily because FIFO considers only arrival time and ignores other job characteristics, making it sensitive to workload composition and burstiness. In contrast, Tiresias [10] incorporates both

Fig. 4. Ranking of scheduling algorithms under the scalarized multi-objective metric on 30 test instances

resource demand and execution time in its scheduling decisions, leading to more stable performance and overall stronger effectiveness. However, it strongly favors short jobs, which can starve large jobs and increase the maximum queuing time, thereby degrading the scalarized objective when the tail delay is weighted. Lyra [11] favors jobs with larger per-worker GPU demand. Its performance is inferior to ours, because Lyra [11] is designed to exploit job elasticity, whereas we focus on rigid jobs that cannot make progress without receiving their full requested workers (Constraint (8)). To further analyze why GP-learned priorities perform well, we conducted simulation experiments on multiple instances and recorded job waiting times across different user-priority levels. Fig. 5 shows the density distribution of job queuing times on a representative instance with 10 clusters, where the x-axis denotes queuing time and the y-axis denotes probability density. It can be clearly observed that the GP-learned function more aggressively serves higher-priority jobs, yielding a distribution with more probability mass concentrated at smaller queuing times for high-priority classes.

(a) Priority Function Learned by GP

(b) Tiresias Priority Function

Fig. 5. Job Queuing Time Distributions under GP-Learned and Tiresias Priority Functions.

Fig. 6 reports objective breakdowns on representative instances. When all objectives are equally weighted, the maximum weighted queuing time (Cq,max ) often dominates the scalarized objective. The GP-learned priority function therefore emphasizes reducing Cq,max while still improving the other objectives when possible. Tiresias [10] achieves strong performance on the average weighted queuing time (Cq,avg ) and GPU time utilization (Cu ) but suffers from a larger Cq,max . In contrast, the GP-learned function trades off some average weighted queuing time and GPU time utilization

JOURNAL OF LATEX CLASS FILES, VOL. 14, NO. 8, AUGUST 2021

10

to substantially reduce Cq,max , leading to a better overall scalarized objective.

(a) Avg. Weighted Queuing Time

business scenarios by customizing the objective function, making it more flexible than expert heuristic methods.

(b) Max Weighted Queuing Time

Fig. 7. Results of AvgJCT (Average Job Completion Time) and MaxQT (Maximum Queuing Time) from various algorithms.

(c) GPU Time Utilization

(d) Scalarized Objective Value

Fig. 6. Different objective values of each algorithm on a representative test instance.

C. Performance of the Algorithm in a Single-Cluster Scenario In the previous subsection, we demonstrated that the proposed algorithm performs well in scenarios involving multiple clusters with user-specified priorities. In this subsection, we conduct experiments using real-world traces, according to the classical objective of minimizing average job completion time and the objective of minimizing maximum completion time. This aims to verify the flexibility of the proposed algorithm across different objectives and scheduling scenarios. The following scalarized objective is used to learn the priority function, minimize

ω · AvgJCT + (1 − ω) · M axQT

(16)

where ω ∈ [0, 1] controls the trade-off. Larger ω places more emphasis on AvgJCT, while smaller ω emphasizes MaxQT. Fig. 7 shows the results of various algorithms. Tiresias performs well on AvgJCT but yields large MaxQT due to its preference for short jobs. Lyra shows a similar tail-delay issue. Spark and Liquid reduce MaxQT by FIFO ordering but underperform on AvgJCT because they ignore job characteristics. In contrast, the GP-learned priority function adapts to different ω values and achieves improved trade-offs between AvgJCT and MaxQT. Fig. 8 shows that the optimization behavior of EVO-GP changes under different values of ω. As ω decreases, the learned priority function places more emphasis on reducing MaxQT, reflecting a controllable and smooth trade-off. From the experimental results, we can observe that the priority function learned by GP exhibits superior performance compared to expert heuristic rules. This is because GP, as a data-driven approach, can consider problem information more comprehensively and design finer-grained scheduling rules. Additionally, this method can more flexibly adapt to different

(a) AvgJCT

(b) MaxQT

Fig. 8. AvgJCT and MaxQT of the proposed EVO-GP under different values of ω.

D. The Impact of Load Pressure The level of load pressure also affects the performance of the algorithms. To study robustness under different load pressures, we further conduct experiments under different load pressure in both multi-cluster and single-cluster scenarios. We first conduct a performance comparison of the algorithm in a multi-cluster environment. To better control the load pressure, we assume that the job arrivals follow a uniform distribution [16]. The load pressure is adjusted by varying the inter-job arrival interval [36]. A smaller interval corresponds to higher load pressure, while a larger interval indicates lower load pressure. A total of five clusters are set up, with each cluster containing 40 nodes, and each node equipped with 8 GPUs. Fig. 9(a) presents the experimental results with simulated workloads. It can be observed that EVO-GP consistently outperforms baseline methods under varying load pressures. Moreover, the objective function values achieved by EVO-GP exhibit the minimal fluctuation as the load changes, demonstrating a greater stability compared to other scheduling algorithms. We then conducted experiments in a single-cluster environment, using the classic objective of AvgJCT for comparison. Following the approach described in [12], we controlled the cluster size to adjust the load pressure: a larger cluster corresponds to lower load pressure, while a smaller cluster indicates higher load pressure. During the priority function learning process, we construct 10 training instances with

JOURNAL OF LATEX CLASS FILES, VOL. 14, NO. 8, AUGUST 2021

11

different cluster size (shown in Fig. 9(b)), each subjected to identical workloads. The training subset size was set to 1, while all other parameters remained consistent with previous settings. To clearly highlight the differences in results, Fig. 9(b) only presents a comparison between Tiresias and the proposed method (as both outperform other methods). The results indicate that the priority function learned by GP surpasses that of Tiresias under all load pressure conditions, and this advantage becomes more pronounced as the load increases.

Fig. 10. Example of the learned priority function by GP with workload simulator.

(a) Simulated workloads

F. Ablation Study

(b) Venus trace

Fig. 9. Impact of load pressure on different algorithms.

E. Insight on the Learned Priority Function Fig. 10 illustrates the tree structure of the priority function learned by GP after simplification. It can be represented as the following mathematical expression: (t)

qj +gj (t)

f (j) =

qj

− uj

(t)

2qj

(t)

dj

× (t)

qj +

(t) dj +gj −uj (t) (qj )2

.

(17)

It is worth noting that a smaller value of f (j) indicates a higher relative priority of job j; accordingly, jobs with lower f (j) values are scheduled earlier. As can be observed, the priority function is expressed as the product of two components. The left component favors jobs with longer queuing times, smaller GPU demands, and higher user-defined priorities, thereby promoting their earlier execution. The right component favors jobs with shorter remaining execution times, longer queuing times, and higher user-defined priorities. These two components preserve the principle of favoring small and short jobs while further incorporating the effects of user-defined priority and queuing time, yielding scheduling decisions that more effectively balance urgency and fairness. When the queuing time is zero, due to the presence of protected division, Eq. (18) can be further simplified as: (gj − uj ) × dj (t)

dj + gj − uj

(a) Effectiveness of Evolutionary Job Allocation

(b) Effectiveness of GP-learned priority function

Fig. 11. Ablation experiments: (a) job allocation methods (b) resource allocation methods.

G. Algorithm Running Time

(t)

(t)

f (j|qj = 0) =

To quantify the contribution of each component of EVO-GP, we conduct ablation studies in the multi-cluster setting with the same configuration as in Section IV-D. Fig. 11(a) compares the performance of job allocation using the evolutionary algorithm and the MCT method under different load pressures. The job allocation using evolutionary algorithm consistently outperforms the MCT method across all load pressures and exhibits smoother trends. Fig. 11(b) compares different intracluster resource allocation strategies. It can be observed that when using the GP-learned priority function achieves the best performance with lower variance, especially under heavier load. These results confirm that both the evolutionary allocation layer and the GP-learned priority layer contribute to the overall gains.

(18)

where the numerator enhances SRSF (i.e., jobs with smaller (t) gj × dj are scheduled earlier) by explicitly incorporating user-defined priority, thereby strengthening the scheduler’s ability to favor high-priority jobs. This term jointly captures a job’s remaining duration, resource demand, and user-defined priority, extending SRSF from a purely efficiency-driven rule to one that simultaneously accounts for urgency and service differentiation.

We evaluated the execution time of a single scheduling operation of the EVO-GP online algorithm implemented in JAVA. The experiments were conducted on a desktop computer (Apple M4 Pro, 24 GB RAM) to measure the algorithm’s performance when handling different numbers of jobs. As shown in Fig. 12, the execution time increases with the number of jobs but still remains at a relatively low level (< 7 seconds). Considering that ML training jobs typically run for hours or even days, this overhead is acceptable for practical online scheduling.

JOURNAL OF LATEX CLASS FILES, VOL. 14, NO. 8, AUGUST 2021

Fig. 12. Running time of EVO-GP to handle different numbers of jobs.

V. C ONCLUSION This paper proposes EVO-GP, a two-layer evolutionary scheduling framework designed to address the challenges of ML job scheduling in multi-cluster GPU environments. By introducing a two-layer optimization mechanism, the framework decouples global job allocation from local resource scheduling to achieve both efficiency and adaptability. At the job allocation layer, the proposed evolutionary job allocation algorithm dynamically assigns jobs to appropriate clusters to maintain global load balance. At the resource allocation layer, the resource allocation with priority function learned by GP module automatically learns interpretable and effective priority functions that guide GPU allocation decisions under contention. By integrating evolutionary search at the global layer with data-driven, GP-learned heuristics at the local layer, EVO-GP can flexibly adapt to varying workload characteristics and support different multi-objective formulations (e.g., delay, fairness, and utilization). Extensive experiments on both realworld and simulated workloads demonstrate that EVO-GP consistently outperforms state-of-the-art scheduling algorithms in minimizing both average and maximum (weighted) queuing times while maximizing GPU utilization, thereby confirming its effectiveness, scalability, and general applicability in diverse ML job scheduling tasks. ACKNOWLEDGMENTS This work was supported by the National Natural Science Foundation of China (Grant No. 62250710682), the Guangdong Provincial Key Laboratory (Grant No. 2020B121201001), the Program for Guangdong Introducing Innovative and Entrepreneurial Teams (Grant No. 2017ZT07X386), and an internal grant from Lingnan University. R EFERENCES [1] Y. LeCun, Y. Bengio, and G. Hinton, “Deep learning,” Nature, vol. 521, no. 7553, pp. 436–444, 2015. [2] Z. Ye, W. Gao, Q. Hu, P. Sun, X. Wang, Y. Luo, T. Zhang, and Y. Wen, “Deep learning workload scheduling in GPU datacenters: A survey,” ACM Computing Surveys, vol. 56, no. 6, pp. 1–38, 2024. [3] Q. Hu, P. Sun, S. Yan, Y. Wen, and T. Zhang, “Characterization and prediction of deep learning workloads in large-scale GPU datacenters,” in Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis, 2021, pp. 1–15.

12

[4] Q. Weng, W. Xiao, Y. Yu, W. Wang, C. Wang, J. He, Y. Li, L. Zhang, W. Lin, and Y. Ding, “MLaaS in the wild: Workload analysis and scheduling in large-scale heterogeneous GPU clusters,” in 19th USENIX Symposium on Networked Systems Design and Implementation (NSDI 22), 2022, pp. 945–960. [5] M. Jeon, S. Venkataraman, A. Phanishayee, J. Qian, W. Xiao, and F. Yang, “Analysis of Large-Scale Multi-Tenant GPU clusters for DNN training workloads,” in 2019 USENIX Annual Technical Conference (USENIX ATC 19), 2019, pp. 947–960. [6] B. Hindman, A. Konwinski, M. Zaharia, A. Ghodsi, A. D. Joseph, R. Katz, S. Shenker, and I. Stoica, “Mesos: A platform for Fine-Grained resource sharing in the data center,” in 8th USENIX Symposium on Networked Systems Design and Implementation (NSDI 11), 2011, p. 295–308. [7] V. K. Vavilapalli, A. C. Murthy, C. Douglas, S. Agarwal, M. Konar, R. Evans, T. Graves, J. Lowe, H. Shah, S. Seth et al., “Apache hadoop yarn: Yet another resource negotiator,” in Proceedings of the 4th annual Symposium on Cloud Computing, 2013, pp. 1–16. [8] M. Zaharia, M. Chowdhury, M. J. Franklin, S. Shenker, and I. Stoica, “Spark: Cluster computing with working sets,” in 2nd USENIX Workshop on Hot Topics in Cloud Computing (HotCloud 10), 2010, pp. 1–10. [9] R. Gu, Y. Chen, S. Liu, H. Dai, G. Chen, K. Zhang, Y. Che, and Y. Huang, “Liquid: Intelligent resource estimation and network-efficient scheduling for deep learning jobs on distributed GPU clusters,” IEEE Transactions on Parallel and Distributed Systems, vol. 33, no. 11, pp. 2808–2820, 2021. [10] J. Gu, M. Chowdhury, K. G. Shin, Y. Zhu, M. Jeon, J. Qian, H. Liu, and C. Guo, “Tiresias: A GPU cluster manager for distributed deep learning,” in 16th USENIX Symposium on Networked Systems Design and Implementation (NSDI 19), 2019, pp. 485–500. [11] J. Li, H. Xu, Y. Zhu, Z. Liu, C. Guo, and C. Wang, “Lyra: Elastic scheduling for deep learning clusters,” in Proceedings of the Eighteenth European Conference on Computer Systems, 2023, pp. 835–850. [12] Z. Ye, P. Sun, W. Gao, T. Zhang, X. Wang, S. Yan, and Y. Luo, “Astraea: A fair deep learning scheduler for multi-tenant GPU clusters,” IEEE Transactions on Parallel and Distributed Systems, vol. 33, no. 11, pp. 2781–2793, 2021. [13] S. Jayaram Subramanya, D. Arfeen, S. Lin, A. Qiao, Z. Jia, and G. R. Ganger, “Sia: Heterogeneity-aware, goodput-optimized ml-cluster scheduling,” in Proceedings of the 29th Symposium on Operating Systems Principles, 2023, pp. 642–657. [14] R. Zhou, J. Pang, Q. Zhang, C. Wu, L. Jiao, Y. Zhong, and Z. Li, “Online scheduling algorithm for heterogeneous distributed machine learning jobs,” IEEE Transactions on Cloud Computing, vol. 11, no. 2, pp. 1514– 1529, 2022. [15] M. Yu, Y. Tian, B. Ji, C. Wu, H. Rajan, and J. Liu, “Gadget: Online resource optimization for scheduling ring-all-reduce learning jobs,” in IEEE INFOCOM 2022-IEEE Conference on Computer Communications. IEEE, 2022, pp. 1569–1578. [16] Y. Peng, Y. Bao, Y. Chen, C. Wu, C. Meng, and W. Lin, “DL2: A deep learning-driven scheduler for deep learning clusters,” IEEE Transactions on Parallel and Distributed Systems, vol. 32, no. 8, pp. 1947–1960, 2021. [17] Y. Bao, Y. Peng, and C. Wu, “Deep learning-based job placement in distributed machine learning clusters,” in IEEE INFOCOM 2019-IEEE Conference on Computer Communications. IEEE, 2019, pp. 505–513. [18] Y. Luan, X. Chen, H. Zhao, Z. Yang, and Y. Dai, “Sched2 : Scheduling deep learning training via deep reinforcement learning,” in 2019 IEEE Global Communications Conference (GLOBECOM). IEEE, 2019, pp. 1–7. [19] H. Wang, Z. Liu, and H. Shen, “Job scheduling for large-scale machine learning clusters,” in Proceedings of the 16th International Conference on emerging Networking EXperiments and Technologies, 2020, pp. 108– 120. [20] R. S. Sutton, A. G. Barto et al., Reinforcement learning: An introduction. MIT press Cambridge, 1998, vol. 1, no. 1. [21] X. Zhao and C. Wu, “Large-scale machine learning cluster scheduling via multi-agent graph reinforcement learning,” IEEE Transactions on Network and Service Management, vol. 19, no. 4, pp. 4962–4974, 2021. [22] H. Zhao, Z. Han, Z. Yang, Q. Zhang, F. Yang, L. Zhou, M. Yang, F. C. Lau, Y. Wang, Y. Xiong et al., “HiveD: Sharing a GPU cluster for deep learning with guarantees,” in 14th USENIX Symposium on Operating Systems Design and Implementation (OSDI 20), 2020, pp. 515–532. [23] Y. Peng, Y. Bao, Y. Chen, C. Wu, and C. Guo, “Optimus: an efficient dynamic resource scheduler for deep learning clusters,” in Proceedings of the Thirteenth EuroSys Conference, 2018, pp. 1–14.

JOURNAL OF LATEX CLASS FILES, VOL. 14, NO. 8, AUGUST 2021

[24] H. Mao, M. Alizadeh, I. Menache, and S. Kandula, “Resource management with deep reinforcement learning,” in Proceedings of the 15th ACM Workshop on Hot Topics in Networks, 2016, pp. 50–56. [25] D. Narayanan, F. Kazhamiaka, F. Abuzaid, P. Kraft, A. Agrawal, S. Kandula, S. Boyd, and M. Zaharia, “Solving large-scale granular resource allocation problems efficiently with pop,” in Proceedings of the ACM SIGOPS 28th Symposium on Operating Systems Principles, 2021, pp. 521–537. [26] S. K. Panda and P. K. Jana, “Efficient task scheduling algorithms for heterogeneous multi-cloud environment,” The Journal of Supercomputing, vol. 71, no. 4, pp. 1505–1533, 2015. [27] A. Choudhury, Y. Wang, T. Pelkonen, K. Srinivasan, A. Jain, S. Lin, D. David, S. Soleimanifard, M. Chen, A. Yadav et al., “MAST: Global scheduling of ML training across Geo-Distributed datacenters at hyperscale,” in 18th USENIX Symposium on Operating Systems Design and Implementation (OSDI 24), 2024, pp. 563–580. [28] G. Pavai and T. Geetha, “A survey on crossover operators,” ACM Computing Surveys (CSUR), vol. 49, no. 4, pp. 1–43, 2016. [29] C. Gathercole and P. Ross, “Dynamic training subset selection for supervised learning in genetic programming,” in International Conference on Parallel Problem Solving from Nature. Springer, 1994, pp. 312–321. [30] B. Tan, H. Ma, Y. Mei, and M. Zhang, “A cooperative coevolution genetic programming hyper-heuristics approach for on-line resource allocation in container-based clouds,” IEEE Transactions on Cloud Computing, vol. 10, no. 3, pp. 1500–1514, 2020. [31] J. R. Koza, “Genetic programming: on the programming of computers by means of natural selection cambridge,” MA: MIT Press, 1992. [32] F. Filippini, J. Anselmi, D. Ardagna, and B. Gaujal, “A stochastic approach for scheduling ai training jobs in GPU-based systems,” IEEE Transactions on Cloud Computing, vol. 12, no. 1, pp. 53–69, 2023. [33] V. Saxena, K. Jayaram, S. Basu, Y. Sabharwal, and A. Verma, “Effective elastic scaling of deep learning workloads,” in 2020 28th International Symposium on Modeling, Analysis, and Simulation of Computer and Telecommunication Systems (MASCOTS). IEEE, 2020, pp. 1–8. [34] A. Tumanov, T. Zhu, J. W. Park, M. A. Kozuch, M. Harchol-Balter, and G. R. Ganger, “Tetrisched: global rescheduling with adaptive plan-ahead in dynamic heterogeneous clusters,” in Proceedings of the Eleventh European Conference on Computer Systems, 2016, pp. 1–16. [35] J. R. Koza, Genetic Programming: On the Programming of Computers by Means of Natural Selection. Cambridge, MA: MIT Press, 1992. [36] W. Li, S. Chen, K. Li, H. Qi, R. Xu, and S. Zhang, “Efficient online scheduling for coflow-aware machine learning clusters,” IEEE Transactions on Cloud Computing, vol. 10, no. 4, pp. 2564–2579, 2020.

13

Related documents

• SAGA: Workflow-Atomic Scheduling for AI Agent Inference on GPU Clusters#151760
• Agentic CPU-GPU Scheduling for Heterogeneous AI Workloads#405626
• Heddle: Learning Structural Templates for Parallelism Planning on Heterogeneous GPU Clusters#1319186
• Accelerating Dynamic Graph Clustering on GPU Architectures with cuGraph#429327
• Power- and Fragmentation-aware Online Scheduling for GPU Datacenters#1447989