We address a variant of the Capacitated Facility Location Problem in which each customer can be assigned to multiple facilities, subject to customer incompatibility constraint where, specifically, no two incompatible customers may be served by the same facility. In this paper, we extend the model by introducing a maximum budget service constraint, requiring that each customer must be assigned only to facilities within a predefined maximum unitary cost. This variant has practical applications where proximity and compatibility are critical, such as emergency logistics, last-miler delivery, and distribution of social services. Given the \(\mathcal{N}\mathcal{P}\) -hard nature of the problem, we propose a metaheuristic based on General Variable Neighborhood Search (GVNS), which integrates adaptive neighborhood structures and efficient local search procedures. Extensive computational experiments confirm the robustness and efficiency of the proposed method, particularly in scenarios with tight budget service restrictions.