Context A software system's structure often degrades due to repetitive maintenance. To make a sustainable evolution of such systems, it becomes mandatory to improve their modular structure after a certain time. Many remodularization approaches Were proposed to improve the modular structure of software systems. Most of the existing approaches rely on structural or lexical dependencies. However, there is a lack of research that distinguishes different types of structural (e.g., inheritance, method calls, references, etc.) or lexical (Name of classes, methods, variables, etc.) dependencies, but assumes that they are equivalent, which is illogical from a software developer's point of view. Objective: In this paper, we propose an approach that considers various types of structural as well as lexical dependencies along with their relative importance to remodularize the Object-Oriented (00) systems. The main goal of the paper is to generate remodularization solutions that can reflect the developers' perspective (as visible in the well-modularized software system) of remodularization, which is highly desirable in software evolution. Method: The paper computes coupling strength among classes using different weights (computed on basis of well-modularized software system) in terms of various mechanisms of structural and lexical dependencies. Software remodularization problem is formulated as a single and multi-objective optimization problem and solved using Genetic Algorithnis (GA). Based on the different types of structural and lexical dependencies and as per their un-weighted/weighted variants, we have designed following 24 coupling schemes: structural-based (i.e., SBUW, SBW, SAUW, SAW, STFUW, STFW, STFIDFUW, and STFIDFW), lexical based (i.e., LBUW, LBW, LAUW, LAW, LTFUW, LTFW, LTFIDFUW, and LTFIDFW), and combined structural lexical based (i.e., SLBUW, SLBW, SLAUW, SLAW, SLTFUW, SLTFW, SLTFIDFUW, and SLTFIDFW). Values obtained through these coupling schemes are used in coupling and cohesion objective function of the GA. Along with this objective, some supportive objective functions such as MCI and MSI have been used to drive the optimization process towards a good quality modularization solution. Results: We assess the effectiveness of our proposed remodularization approach over eight real-world object-oriented software systems in terms of original design of the experimented software systems and modularization decisions provided by the developers. Results indicate that TFIDF based weighted variants (i.e. STFIDFW, LTFIDFW, and SLTFIDFW) of each broad three categories outperformed rest of variants within each category. However, TFIDF weighted variant in the third broad category (i.e., SLTFIDFW) outperformed all others. Conclusion: Our combined lexical-structural approach (SLTFIDFW) considering various types of dependencies along with their relative weights performs well and results into better remodularization compared to rest of considered alternates. It also shows significant improvement over techniques based on only lexical or structural information. Thus this approach can be very useful to improve the quality of the software whose remodularization quality deteriorates beyond accepted level. (C) 2016 Elsevier B.V. All rights reserved.