Multi-objective scheduling model for the next release problem with precedence constraints

The Next Release Problem (NRP) seeks to select software requirements that maximize stakeholder satisfaction subject to requirements precedence constraints. This work extends the classical NRP with an explicit temporal scheduling layer, producing executable development plans within a discrete planning time horizon T. Two NRP variant model formulations are proposed and evaluated: NRP-S, with an aggregated big-M temporal precedence constraint, and NRP-S*, a tighter disaggregated reformulation motivated by a runtime anomaly observed on larger instances. Experiments on five benchmark instances with time horizons T in {40, 80, 120, 160} and a team of three developers show that all configurations are solved to global optimality. NRP-S* achieves better runtime results over NRP-S when the root LP relaxation is loose, yet neither formulation dominates the other: on instances where the relaxation is naturally tight, NRP-S solves faster than NRP-S*, while both variants consistently recover the same optimal objectives as the selection-only baseline.