[Discussion] Metaheuristic-based Global Batch Optimization (GA+VNS) for Heterogeneous Clusters

[kinhluan]

Hi Volcano community,

I'm researching hybrid metaheuristic scheduling (GA + VNS) for Unrelated Parallel Machine Scheduling (UPMS) in heterogeneous clusters (e.g., mixed CPU/GPU generations, ARM/x86). Our current simulations on the standard Braun et al. benchmark suite show that this approach significantly outperforms classic heuristics (HEFT, MinMin) in both Makespan and Resource Utilization.

Since Volcano is the industry standard for high-performance batch scheduling (AI/ML/HPC), I'm exploring whether a global metaheuristic optimizer could be integrated into the Volcano ecosystem to provide near-optimal placement for large batches of jobs.

The Concept

Conventional schedulers often make pod-by-pod or small-batch greedy decisions. Metaheuristics (Genetic Algorithms + Variable Neighborhood Search) allow for a global view of the cluster and the pending queue, finding a mapping that optimizes for the overall batch completion time.

Proposed Architecture (Asynchronous Background Loop):

1. Background Optimizer: A controller that continuously observes the cluster state and the pending queue. It runs the GA+VNS algorithm asynchronously to compute a globally "ideal" mapping state.
2. Guided Scheduling: Volcano's scheduling actions (Enqueue, Allocate) are guided by this cached ideal state, effectively steering greedy sequential decisions toward a globally optimal configuration.

Key Benefits for Volcano Workloads

• Performance: Significant makespan reduction for complex AI training pipelines.
• Multi-objective: Ability to optimize for both performance and energy consumption (Energy-Aware Scheduling).
• Heterogeneity: Handles cases where node performance isn't a simple scalar multiplier (mixed architectures).

Questions for the Community

1. Architectural Fit: Is there interest in incorporating search-based metaheuristics (beyond simple heuristics) for global batch placement within Volcano?
2. Integration Path: Would this be better as a custom Action/Plugin within the Volcano controller or as an external Optimization Service providing advice to the scheduler?
3. Benchmarking: We are happy to share our methodology and results (512 tasks × 16 machines, 12 instance types, 30 seeds, Friedman test p < 0.001) if there's interest in a deeper dive.

I've initiated related technical discussions in the K8s ecosystem here:

• kubernetes-sigs/scheduler-plugins#948
• sustainable-computing-io/kepler#2436

Looking forward to hearing your thoughts on how this could enhance Volcano's scheduling capabilities!

[JesseStutler]

Yes of course! We'd like to any see performance improvements for volcano scheduler! However, I personally have no experience with GA+VNS. I look forward to your proposal and seeing the performance test results. Do you want to initiate the proposal directly in the Volcano main repo?

[kinhluan]

Yes of course! We'd like to any see performance improvements for volcano scheduler! However, I personally have no experience with GA+VNS. I look forward to your proposal and seeing the performance test results. Do you want to initiate the proposal directly in the Volcano main repo?

Hi @JesseStutler,

Yes, I'm definitely interested in initiating a proposal in the Volcano main repository.

Since my current findings are based on simulations, I'm eager to discuss how to bridge the gap toward a real-world implementation in Volcano. I am also currently preparing to run more benchmarks on real cluster trace datasets (Google/Azure logs) to strengthen the results.

Could you please provide some guidance on the preferred proposal process or a template I should follow?

Thanks for the feedback and the guidance!

[JesseStutler]

Yes of course! We'd like to any see performance improvements for volcano scheduler! However, I personally have no experience with GA+VNS. I look forward to your proposal and seeing the performance test results. Do you want to initiate the proposal directly in the Volcano main repo?

Hi @JesseStutler,

Yes, I'm definitely interested in initiating a proposal in the Volcano main repository.

Since my current findings are based on simulations, I'm eager to discuss how to bridge the gap toward a real-world implementation in Volcano. I am also currently preparing to run more benchmarks on real cluster trace datasets (Google/Azure logs) to strengthen the results.

Could you please provide some guidance on the preferred proposal process or a template I should follow?

Thanks for the feedback and the guidance!

Are you a graduate student and currently conducting thesis experiments, or is your company in need of this?

You can learn from the concepts from volcano website and use tools like AI agent or deepwiki to learn the concept and architecture of volcano( also directly reading on your own is ok ), about the proposal process there is no standard, but you can refer to KEP template, KEP is the standard proposal doc in the kubernetes ecosystem

[kinhluan]

Yes of course! We'd like to any see performance improvements for volcano scheduler! However, I personally have no experience with GA+VNS. I look forward to your proposal and seeing the performance test results. Do you want to initiate the proposal directly in the Volcano main repo?

Hi @JesseStutler,
Yes, I'm definitely interested in initiating a proposal in the Volcano main repository.
Since my current findings are based on simulations, I'm eager to discuss how to bridge the gap toward a real-world implementation in Volcano. I am also currently preparing to run more benchmarks on real cluster trace datasets (Google/Azure logs) to strengthen the results.
Could you please provide some guidance on the preferred proposal process or a template I should follow?
Thanks for the feedback and the guidance!

Are you a graduate student and currently conducting thesis experiments, or is your company in need of this?

You can learn from the concepts from volcano website and use tools like AI agent or deepwiki to learn the concept and architecture of volcano( also directly reading on your own is ok ), about the proposal process there is no standard, but you can refer to KEP template, KEP is the standard proposal doc in the kubernetes ecosystem

My research is motivated by actual scheduling issues encountered in my company with highly heterogeneous hardware.

Thank you for the guidance! I will dive into the Volcano architecture and start drafting a proposal following the KEP template. I'll explore how to integrate these metaheuristic patterns as a pluggable optimization component for Volcano.

I'll keep you updated once the draft is ready for review.