Abstract: A customer centric strategy leads companies to accentuate business drivers through reliable Customer Relationship Management (CRM) software, which is maintained with efficient decision making processes, especially the process of release planning (RP). To improve the decision quality of the maintenance release planning process, we have proposed in our previous paper a S-TRPM, a Strategic RP model for Third-Party Application Maintenance (TPM) projects. This Integer linear programming model supports, in a systematic way, TPM manager decisions of when to deliver customer change requests, increases the customer satisfaction, and respects the contractual commitment in terms of service level agreements (SLAs). Furthermore, we have validated the application of our model in a real CRM project that was managed using an ad hoc RP approach and we have produced an automatic roadmap with better SLAs compared to the ad hoc RP SLAs. In this paper, we aim to extend our model to address efficiently change requests (CRs) with an exceeded SLA through the minimization of CR penalties. This extension involves a multi-objective approach that adds a new objective function and adapts the existing SLA constraint of our S-TRPM. Then, we apply this multi-objective model in the same CRM project by means of the NSGA-II genetic algorithm. The resulting roadmap is constructed automatically in an iterative and incremental way, based on non-dominated solutions, and then compared to the ad hoc RP ones and previous work results.