Feature assignment in multi-release work plan: Accelerating optimization using gene clustering

This paper presents a novel method for solving the previously un-researched problem of multi-release work plan (MRWP). The research also suggests a technique for improving the run-time of metaheuristic search optimizations for this problem. The MRWP is required for many products and R&D projects that are characterized by a long-term planning horizon, spaced by intermediate releases. The intermediate releases enable the organization to keep its liquidity and survive and materialize the value for a given investment. The inclusion of features in a certain release impacts the value of the release, impacts the required workload, and impacts future development of other features. This problem is NP-hard. Thus, practical instances of this problem cannot be solved optimally in polynomial time. In this paper, we apply a clustering algorithm, based on novel similarity coefficients to reduce complexity and accelerate the convergence of a clonal selection search algorithm. Our goal is to provide a near-optimal yet simple method for quantitatively determining the feature content of all project releases. The four versions of the proposed algorithms are tested on a newly-developed set of instances and the results show the advantages of the combination of clustering mutations and random mutations over the pure cluster-based search. To examine the optimality-gap, a sample of benchmark MRWP solutions was generated. These solutions were obtained by a specially developed branch and bound algorithm developed for this study. The comparison of the optimal results to the metaheuristic results, proved that the metaheuristic yields optimal solutions in small problems, and their performance deteriorates slightly as the problem grows.