Hybrid Multi-Objective Relinked GRASP for the constrained Next Release Problem

Release planning is a critical step in the development of a software product, and it involves many factors. Deciding what to build for the next software release requires taking into account not only the cost of building a subset of software features, but also the expected satisfaction of the clients, as well as the dependencies that the features might have among them. This problem, called Next Release Problem, can be difficult to tackle by expert judge, or even intractable if the number of requirements, dependencies and clients to consider is very large. In the literature, this problem has been approached from the so-called search-based software engineering field, introducing a variety of metaheuristic algorithms to obtain a subset of release proposals that simultaneously optimise both cost and satisfaction. In this work, we present a GRASP-based advanced method, and evaluate it against other families of algorithms commonly applied to this problem, using two public and four synthetic datasets for the evaluation. Results show that solutions obtained by our proposal are superior to those of other algorithms in terms of quality indicators and speed of execution. Algorithms, datasets and evaluation framework have been made available to the research community.