Queue-Theoretic Admission Control for Multi-Tenant GPU Clusters

Problem: GPU cluster operators cannot predict workload admission wait times, and existing greedy heuristics lack formal guarantees. Method: We formalize admission as a multi-class, multi-resource queueing network, prove a structural decomposition into quotable and unfeasible workloads, and model quotable queues as M/G/k systems with effective server count from vector packing. Finding: We prove optimal admission ordering is NP-hard via vector bin packing, and validation on Kueue shows the vector k_eff identifies bottleneck resources, Little's Law holds exactly, and Erlang-C overestimates wait times conservatively. Why it matters: This provides the first formal wait-time bounds for multi-tenant GPU clusters, enabling predictable admission control despite NP-hard optimality.