Attribute reduction is a basic issue in knowledge representation and data mining. It simplifies an information system by discarding some redundant attributes. In this paper, we present a hybrid approach that combines the nature of variable neighbourhood search in the first phase with an iterated local search in the second phase that always accepts best solutions. The approach is tested over 13 well-known established datasets. The results demonstrate that the variable neighbourhood search approach is able to produce solutions that are competitive with those state-of-the-art techniques from the literature in terms of minimal reducts.