In this article, the design of a quality control network is considered in an entire supply chain, in the context of an international food and beverage company, denoted as ABC. For each possible control point of the network, two decisions have to be made: (1) establish a monitoring activity or not; (2) if a monitoring activity is placed, determine its acceptance level with a well-adjusted sampling plan. The objective function to minimize consists of a weighted sum of two conflicting components, namely risk (of having bad units) and processing time (to control the product batch itself). Indeed, for each control point, an accurate monitoring activity reduces risk but augments processing time. Each monitoring activity has a specific cost (if selected) and a budget constraint has to be satisfied for the entire network. Various solutions methods are proposed to tackle this NP-hard problem, ranging from a basic greedy heuristic to advanced metaheuristics involving tabu search as an internal procedure. CPLEX can be used for very small instances (with less than 20 control points), for which a basic tabu search can obtain similar results much quicker (in a fraction of second). The experiments for larger instances highlight the importance of having a good control (in terms of the involved search trajectory in the solution space) on the search process, as the methods with well-tuned diversification mechanisms perform best.