Dependency-Aware Microservice Deployment Optimization via Neural Heuristic Learning

Microservice deployment should consider dependency constraints and resource requirements while minimizing deployment costs. There are various dependencies among microservices, and such intricate dependencies bring great difficulties to efficient deployment. Despite significant progress, existing deep learning-based methods are not expressive enough to capture the complexity of microservice dependencies. Meanwhile, metaheuristic methods encode such dependencies into problem-specific heuristics through explicit formulae, yet such formulations remain static and inherently limited. This paper addresses these issues by formulating the microservice deployment problem (MSDP) as a variable-sized bin packing problem. We first introduce a heterogeneous graph neural network to effectively represent the complex dependencies of MSDP. Based on this representation, we propose a novel reinforcement learning policy to design heuristics without the need to derive explicit formulae. Guided by the learned heuristics, we further devise a parallel ant colony optimization algorithm to accelerate solution construction. Experimental results from three representative microservice applications demonstrate that our method obtains near-optimal solutions while significantly outperforming the state-of-the-art methods in computational efficiency.