Jaya algorithm has gained considerable attention lately due to its simplicity and requiring no control parameters (i.e. parameter free). Despite its potential, Jaya algorithm is inherently designed for single objective problems. Additionally, Jaya is limited by the intense conflict between exploration (i.e. roams the random search space at the global scale) and exploitation (i.e. neighborhood search by exploiting the current good solution). Thus, Jaya requires better control for exploitation and exploration in order to prevent premature convergence and avoid being trapped in local optima. Addressing these issues, this paper proposes a new multi-objective Jaya variant with a multi-start adaptive capability and Cuckoo search like elitism scheme, called MS-Jaya, to enhance its exploitation and exploration allowing good convergence while permitting more diverse solutions. To assess its performances, we adopt MS-Jaya for the software module clustering problem. Experimental results reveal that MS-Jaya exhibits competitive performances against the original Jaya and state-of-the-art parameter free meta-heuristic counterparts consisting of Teaching Learning based Optimization (TLBO), Global Neighborhood Algorithm (GNA), Symbiotic Optimization Search (SOS), and Sine Cosine Algorithm (SCA).