Presenting the several-release-problem and its cluster-based solution accelartion
本文提出一种利用聚类技术加速元启发式搜索的新方法，应用于现代工业中常见的多次发布问题，帮助企业在多个版本中决定包含哪些功能，以最大化投资价值。
This paper presents a novel technique for improving the runtime of metaheuristic search optimisations. The technique was applied on a new practical problem: several-release-problem (SRP) that characterises the modern industry. Many modern products are replaced by their next version due to incessant R&D activity, resulting in a short marketable life length. There are numerous such examples including the automotive industry, electronic devices and software products. These intermediate releases enable organisations to maximise their value for a given investment. The challenge faced by the industry is to decide which features to include in which version. The paper proves that SRP is NP-hard, thus cannot be solved practically using analytical approaches. A near-optimal, simple technique for determining the feature content of all version releases of the planning horizon is presented. The innovative approach utilises techniques adopted from the clustering domain to enhance the optimisation. The clustering enables skipping significant amounts of unattractive zones of the space. Verification and validation of the proposed technique are presented. The paper compares different heuristics and the shows that embedding the suggested clustering into general methods, yields significantly shorter runtime, and improves the solution’s quality. The enhancement technique can be applied to other combinatorial problems and metaheuristics.