Heuristic Approaches to the Container Scaling Problem in Kubernetes Orchestrators

This work proposes heuristics for the container scheduling problem in Kubernetes orchestrators, modeled as an Integer Programming problem inspired by the Capacitated Facility Location Problem (CFLP). The proposal aims to minimize infrastructure costs by considering node opening costs, pod allocation, and error penalties. A greedy constructive heuristic, a best-improvement local search, and a GRASP metaheuristic were developed. Experiments demonstrated cost reductions of over 90% compared to Kube-scheduler on instances with 5000 pods and 200 nodes, with computational times shorter than exact methods.