Kuberina: Maritime Stowage-Inspired Combinatorial Optimization for Pre-deployment Scheduling in Heterogeneous Kubernetes Clusters

The default Kubernetes scheduler ( kube-scheduler ) makes millisecond-latency placement decisions using a first-come, first-served heuristic optimized for homogeneous, stateless microservices. As clusters become increasingly heterogeneous - incorporating GPUs, TPUs, and memory-optimized nodes - this reactive approach produces severe resource fragmentation, with industry analyses consistently reporting 30–40% average CPU utilization across cloud environments. Existing solutions such as Volcano, Kueue, and Google Autopilot address scheduling fairness or vertical scaling but do not solve the underlying combinatorial packing problem offline. We present Kuberina, an offline, pre-deployment CLI engine that reformulates Kubernetes pod scheduling as a Multi-Dimensional Bin Packing Problem (MDBP) - drawing a structural isomorphism from the Container Stowage Planning Problem (CSPP) used by mega-vessel shipping lines. Kuberina employs a three-phase hybrid pipeline: (1) Vector Packing First-Fit Decreasing (FFD) warm-start, (2) Genetic Algorithm (GA) optimization with gang-aware repair, and (3) Constraint Satisfaction Problem (CSP) enforcement with Forward Checking - all integrated tightly rather than executed sequentially. On asynthetic benchmark modeled after the MSC Irina mega-vessel (186 nodes, 2,714 pods, 5,128 affinity constraints), Kuberina achieves 100% scheduling success with zero constraint violations, consolidates workloads onto 152 of 186 nodes (18.3% node reduction), reaches 88.7% average CPU utilization, and produces a α = 1.34 relative mathematically verified feasible solution with approximation ratio α to the LP lower bound - all computed in under 44 seconds. Monte Carlo testing confirms the result is statistically significant (p < 10−4). The output is a declarative YAML blueprint that can be reviewed, version-controlled, and applied via kubectl without touching the live cluster.