The main focus of this study is on the survey of parallelization strategies for the Variable Neighborhood Search (VNS) metaheuristic, covering 58 publications spanning the period 2001--2025. Parallelization is a widely-used tool to enhance the efficiency of various algorithms. When stochastic algorithms such as metaheuristics are considered, the expectation is that engaging multiple processing units improves solution quality within the same or even reduced running time. However, achieving this objective is typically a demanding task. Various aspects of parallel computing must be carefully examined, including the identification of parallelizable parts, distribution granularity, load balancing, synchronization, and communication overhead. Moreover, it is important to consider the compatibility between the available hardware resources and the computational requirements. A parallel metaheuristic represents an entirely new algorithm that may significantly differ from the original sequential variant, which additionally motivates the need for a structured classification framework. We propose such a framework for the existing parallel VNS literature, organizing proposed implementations according to two complementary and non-overlapping layers. The first layer adopts the existing high-level algorithmic taxonomy (HTPM), which captures the decomposition strategy, search control, communication pattern, and solution diversity. The second layer introduces a novel implementation-level taxonomy (ITPM), proposed here for the first time, characterizing hardware architecture, communication topology, granularity, load balancing, and parallel programming model. Neither layer alone is sufficient to interpret reported performance differences across implementations: two algorithms sharing an identical HTPM classification may perform very differently in practice, and without systematically documenting both layers such differences cannot be reliably attributed to algorithmic design choices rather than implementation-specific factors. The dual classification framework is applied consistently to all reviewed publications, accompanied by a bibliometric analysis of the field's evolution and a structured identification of open challenges specific to parallel VNS. The resulting classification provides researchers with a solid foundation to design and compare new parallel VNS implementations and to advance the parallelization of metaheuristics in general, while also laying the groundwork for a predictive understanding of parallel metaheuristic performance.