Search-Based Software Engineering is a research area that aims to tackle software engineering tasks as optimization problems. Among the problems in this area, we can find the Software Module Clustering Problem (SMCP). This problem, which has been proved to be $$backslashmathcalNbackslashmathcalP$$NP-hard, focuses on finding the best organization of a software project in terms of modularity. Since modular code is easier to understand, the result is an increase of the quality of software projects and thus a reduction of the costs associated to their maintenance. To tackle the SMCP, software projects are often modeled as graphs that represent the dependencies between different components. In this work, we study two well-known multi-objective approaches for the SMCP: the Maximizing Cluster Approach (MCA) and the Equal-size Cluster Approach (ECA). Each of these variants is composed of 5 different objectives. We propose a heuristic algorithm based on the Multi-Objective Variable Neighborhood Descent (MO-VND) schema to tackle the aforementioned variants and we introduce three neighborhoods to be explored within the algorithm. Finally, we compare the performance of our proposal with the performance of NSGA-III over a dataset of real software projects. The results show that the proposed algorithm is competitive when tackling the MCA, and some ideas are given to increase its efficiency when tackling the ECA.