Selection of the requirements for the next release of a software product is a inherently complex task due to the high volume of intricate requirements and to the varied interests of the stake holders involved. In this paper we apply integer linear programming techniques to aid requirements managers of product software companies in release planning. The applied techniques take candidate requirements, estimated revenue per requirement (or combination of requirements), and available resources as input. Planning suppleness is added by way of allowing flexibility in team composition, team transfers, extension of deadlines and hiring external resources. Through experiments the application of the proposed approach is demonstrated with real life data. Future additions to the model are identified, as well as improved validation.
by the software vendor. Release initiation is a formal document triggering the release of a development project. The release definition contains the list of product requirements to be developed in the upcoming release. Conceptual solutions in requirements management are used to sketch the business context of one or more product requirements, and help developers to view the ‘big picture’ of the development of a product requirement. Finally, the selected product requirements will be developed into software components.
Provided the set of all product requirements, many aspects influence the definition of an optimal set of requirements for a next release. For example, the importance or business value of the requirement, personal preference of certain customers and other stake holders, penalty if not developed, cost of development in man-days, development lead-time, requirement volatility, requirement dependencies, ability to reuse, and requirements quality (e.g. Berander and Andrews (2005); Firesmith (2004); Ruhe et al. (2003); Natt och Dag et al. (2004); Natt och Dag et al. (2005)). So we address what an adequate set of product requirements is for an upcoming release of the software, in the context of business continuity of the product software company.
We develop and demonstrate an optimization technique, based on Integer Linear Programming (ILP) (see e.g. Wolsey (1998) for a general introduction on ILP; see e.g. Van den Akker, et al. (1999A) and Van den Akker, et al. (1999B) for application of ILP in the area of scheduling), to support software vendors in determining the next release of product software. Our technique is based on the assumption that a release’s best set of requirements is the set that results maximum projected revenue against available resources in a given time period. We take into account practical aspects, including the total list of requirements, whether or not requirements are dependent on one another, a requirement’s projected revenue, and a requirements resource claim per development team. To further increase its application in practice, we enhance our technique with managerial steering mechanisms, i.c. enabling of team transfers, conceding release deadline extension, allowing extra resources, and more. By introducing these aspects and managerial steering mechanisms into ILP models for the release composition process we extend the work of Jung (1998), who also applied linear programming techniques in the context of release planning.
Our approach is original in three ways. Firstly, we include a unique set of aspects, among others needed team capacity per requirement. Secondly, we introduce unique yet practical managerial steering mechanisms that can help product managers and development project managers in release planning: enabling of team transfers, and deadlines and extra resources. Thirdly, we apply ILP techniques in a unique way. 2
Integer linear programming models for release planning Let {R1, R2, . . . , Rn} be the set of candidate requirements. For each requirement Rj we assume we can estimate its revenue vj. Further assume that we have a fixed development period. We have to find the subset of requirements for the next release such that the revenue is maximal and the available capacity is not exceeded. We denote our development period by T and define d(T ) as the number of working days in the development period. Moreover, let Q be the number of persons working in the development teams of the company. Then, the available capacity equals d(T )Q man-days. Moreover, we have an estimate aj of the amount of man days needed for the implementation of requirement Rj. We model the requirements selection problem in terms of binary variables xj (j = 1, . . . , n), where xj = 1 if requirement Rj is selected; 0 otherwise.
The problem can be modeled as an ILP problem in the following way: max
vjxj n j=1 If the company decides that, in any case, some of the requirements have to be included in the new release, this can be achieved by fixing the corresponding variables xj at 1, i.e. adding the equation xj = 1 to the above model. If the number of working days in the planning period is different for different persons the total capacity is given by dp(T ), where dp(T ) is the number of working days of person p in period T and the sum is over all persons in the company.
Especially in larger product software companies there are different development teams, each with their own specialization. Let m be the number of teams and suppose team Gi (i = 1, . . . , m) consists of Qi persons. We assume that the implementation of requirement Rj needs a given amount aij of man days from team Gi (i = 1, . . . , m). Now the team capacities can be included by replacing constraint 1 by:
aij xj ≤ d(T )Qi, for i = 1, . . . , m.
Note that for m = 1, this coincides with the model for one pool of developers.
By allowing people to work in a different team, there is more flexibility that
can increase revenue. We assume that if a person from team Gi works in another
team Gk his contribution in terms of man days is multiplied by αik, i.e. if the
person works one day this contributes only αik to the work delivered by team
Gk. Besides the variables xj , we now define the variables yik as the number
mandays from team Gi deployed in team Gk. Let mi be the number of man-days in
team Gi. Including transfers results in the following model:
(
vj xj k:k=i yik = mi, xj ∈ {0, 1}, yik nonnegative and integral, for , i = 1, . . . , m, for i = 1, . . . , m, for j = 1, . . . , n, for j = 1, . . . , n. As a proof-of-concept we implemented a prototype of a requirements selection system. For testing the program different data sets were used. The different sets were: small with 9 requirements and 3 teams, AA, BB, CC with 24 requirements and 17 teams and different ratios of available and total required capacity and master with 99 requirements and 17 teams. All of the used data sets are available online for research purposes at http://www.cs.uu.nl/~diepen/ReqMan.
The following table presents the total revenues for the optimal requirement selection for the different problems that were tested.
The first column in Table 1 represents the scenario of a development organization consisting of one big pool of developers. In practice, however, there will be different teams (especially with larger development organizations); the second column therefore depicts the scenario with multiple teams in the development organization (with no transfers allowed). The last column depicts the scenario with multiple teams, and team transfers allowed (αik = 0.7 for all i = k). The case with one big pool of developers leads to the highest revenue. Introducing multiple teams will decrease total revenue. From the theory this is explained by the fact that this model imposes stricter conditions in assigning labor to requirements. However, allowing transfers between teams (for αik = 0.7 for all i = k) again increases flexibility and hence revenue. 4
Until now we have assumed that all requirements can be implemented independently Suppose that the functionality imposed by a certain requirement can only be effective if one or more other requirements are also implemented, say if we select requirement Rj we also have to select Rk. In the model, we have to ensure that
xj = 1 ⇒ xk = 1.
This can be done by extending our model with the linear inequality
xj ≤ xk.
(
Until now, we assumed that the total revenue of a release is the sum of the revenues of the individual requirements included in the release. However, the revenue may be larger if some collection of requirements is completely realized. A typical example is when these requirements together provide a ‘package’ in some area within the software product. We can include this in our model by using a binary variable xS indicating if the set S is completely realized. Further details are omitted for reasons of brevity.
To increase the capacity for the development of the next release, the company
may consider to hire external personnel in some of the development teams. In our
model, this can be included by to adding the external capacity to the right-hand
side of constraints (
We have shown that ILP models and methods can be used in flexible release planning by implementing a subset of the managerial steering mechanisms in a prototype tool. ILP techniques can be used to help product and requirements managers in software release planning. In this paper we specifically optimized revenues against available resources in a given time period. Scenarios dealing with one pool of developers, different development teams, including the possibility of transfer of developers between teams are discussed and demonstrated through experimentation. Moreover a number of extensions were modeled.
Our approach simplified the task of computing the set of release requirements to a great extend. We aim for more support during release development as in the dynamics of the project workload turns out to be overestimated or underestimated, and that the revenue projections are changing due to a changing market. We further plan to test the validity of our model through multiple business cases. In such cases an appropriate approach is to use our model for release planning on the one hand, and compare its outcome with the company’s proprietary way of release planning. We finally note that our approach supports the release planning at the start of the release planning process. In practice the value of requirements may evolve over time, as the release is being developed; dealing with this is a further extension of our current approach.