Variable Neighbourhood Search (VNS) is used to optimize the solutions for heuristic problems. Solutions are based on neighboring solution systematic changes. The changes are made during the ascending phase to get local optimum and the perturbation phase to gain the global optimum solutions. Exploration and Exploitation procedures are made through various mutation step-size. The objective function to choose the best offspring to be move to the next evolving generation. Thus, this paper uses two variations of VNS based on four random probability distributions for adapting the Offspring solution in the next iteration. The first variant generates each Offspring ranking model solution from one probability distribution in the whole mutation procedure (all mutation step-sizes made by only one probability distribution for each Neighbourhood candidate). On the contrary, the second variant of VNS perturbed each Offspring Neighbourhood solution by a random choice of the probability distribution in each mutation step size. From the obtained results, we can conclude that the second VNS method outperformed the first variant and recent research. In the experiments, we used Yahoo, Microsoft Bing Search (MSLR-WEB10K) and LETOR 4 (MQ2008, MQ2007) datasets.