<p>This paper focuses on the micro-service allocation problem with affinity, a new challenge emerging in the cloud computing industry. The objective is to efficiently allocate a set of micro-services with asymmetric invoking flow onto heterogeneous physical machines, which is mathematically formulated as the vector cutting stock problem with affinity (VCSPA). Two mathematical models are introduced: Generalized Kantorovic model and Set Partitioning model. A symmetry-breaking strategy is presented to reduce the symmetry in solutions of the Generalized Kantorovich model. A column generation-based diving heuristic (CGDH) is employed to address the proposed problem. An affinity-based segmentation is leveraged the computational efficiency of CGDH. Extensive experimental studies are executed to evaluate the proposed models and CGDH. We compare the Rounding strategy of CGDH with two other strategies. The affinity-based segmentation strategy is evaluated in different scenarios. We also compare CGDH with three baseline algorithms: neighborhood search (NS), Ant Colony Optimization (ACO), and the iterative heuristic from ByteDance (IH). The results on the real clusters from ByteDance indicate that CGDH achieves an average increase of 19.03% in the invoking flow and 22.20% in the revenue. The proposed problem is further extended to the resource contention scenario to verify the impacts of the uncertain utilization of micro-services.</p>