Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
This paper empirically evaluates quantum-inspired Quadratic Unconstrained Binary Optimization (QUBO) methods for heterogeneous HPC workflow scheduling against classical solvers like MILP, CP-SAT, GA, and HEFT. They tested single-run simulated annealing, multi-attempt annealing, and a layered QAOA-inspired schedule on both validation and synthetic scaling instances, tracking feasibility, makespan, and resource utilization. Results show that while QUBO variants achieve optimal makespan on small validation instances, they exhibit feasibility degradation as problem size and constraint complexity increase, with classical solvers remaining more robust.
Quantum-inspired QUBO methods for HPC scheduling falter in feasibility as problem complexity grows, revealing that classical solvers still reign supreme for realistic workflow sizes.
Heterogeneous HPC workflow scheduling under multiple hard constraints poses a challenging combinatorial optimization problem. Classical exact solvers guarantee optimality but face scalability limits, motivating interest in quantum-inspired Quadratic Unconstrained Binary Optimization (QUBO) as an alternative optimization paradigm. This work presents a systematic empirical evaluation of QUBO-based scheduling methods against classical baselines including MILP, CP-SAT, GA, and HEFT. We evaluate three QUBO variants, single-run simulated annealing, multi-attempt annealing, and a layered QAOA-inspired schedule, with hybrid enhancement strategies on validation workflows (3-4 tasks) and synthetic scaling instances (5-20 tasks). All solvers are assessed through a unified pipeline tracking feasibility, makespan, and resource utilization under progressive constraint activation and controlled penalty sweeps. All approaches recover the expected optimal makespan on validation instances, confirming formulation correctness. However, feasibility degradation emerges for specific QUBO variants as constraint interactions intensify, particularly when communication costs are introduced. Penalty analysis reveals a sharp feasibility threshold for QUBO-SA, where insufficient penalties consistently fail and moderate-to-strong penalties restore feasibility. Scaling experiments show that classical solvers remain robust across all tested sizes, while QUBO-SA loses feasibility beyond 15 tasks and the QAOA-inspired variant beyond 10 tasks. The study provides a clear empirical characterization of the reliability boundaries of quantum-inspired QUBO formulations for HPC scheduling and identifies regimes where classical approaches remain preferable under current solver capabilities.