Release planning takes place (1) on the strategic level where the overall goal is to prioritize (high-level) requirements and (2) on the operational level where the major focus is to de ne more detailed implementation plans, i.e., the assignment of requirements to speci c releases and often the assignment of stakeholders to requirements. In this paper, we show how release planning can be represented as a con guration task and how re-con guration tasks can be supported. Thus we advance the state-of-the-art in software release planning by introducing technologies that support the handling of inconsistencies in already existing plans.
Higher exibility of software development and better
satised customer requirements can be achieved by developing
and delivering software in an incremental fashion [
Figure 1 depicts an overview of a release planning process.
First, requirements are prioritized on the basis of a utility
analysis [
The major contributions of this paper are the following.
First, we show how to represent a release planning problem
as a con guration task. In this context, we also show how
recon guration can be supported on the basis of con guration
1 Graz University of Technology, Graz, Austria email:
ffelfernig,spoecklberger,samer,stettinger,atasg@ist.tugraz.at
2 University of Helsinki, Finland email:
fjuha.tiihonen,mikko.raatikaineng@helsinki.
3 We interpret pro t as the value of a requirement for the user [
The remainder of this paper is organized as follows. In Section 2, we sketch how utility analysis can be performed on the basis of a given set of requirements. Thereafter, in Section 3 we show how release planning can be represented as a conguration task and how re-con guration can be supported in this context. In Section 4, we report the results of an evaluation of the proposed approach. The paper is concluded with a discussion of issues for future work. 2
The prioritization of requirements can be performed on the
basis of a utility analysis, i.e., the evaluation and ranking of
requirements with regard to a prede ned set of interest
dimensions such as pro t, e ort, and risk [
Prioritization with Aggregated Utilities. In this context, multi-attribute utility theory can be applied to determine a ranking (prioritization) of a given set of requirements (see Table 1). First, each stakeholder si evaluates each individual requirement with regard to interest dimensions. In our example, we use the interest dimensions pro t, e ort, and risk, which are typical interest dimensions in release planning. Interest dimensions can have an assigned weight, for example, it is more important to avoid risky release plans than maximizing the potential pro t.
In such a setting, the distribution of weights could be similar to the one de ned in Table 2. Second, on the basis of a given set of evaluations and a speci cation of the importance of individual interest dimensions, requirements can be ranked according to Formula 1 where imp(d) denotes the importance of interest dimension d and contrib(r; d) denotes the contri
When applying Formula 1 to the entries in Table 1 and Table 2, we are able to derive a ranking of the requirements R = fr1; r2; ::; rng as depicted in Table 3.
In this paper, we directly evaluate requirements with regard to interest dimensions (on a rating scale [1..10]). Especially for the dimensions e ort and pro t, alternative evaluation scales can be de ned which are then mapped to a utility scale (e.g., [1..10]). For example, instead of evaluating e ort directly on a scale [1..10], e ort could be speci ed in man-months which are then translated into a corresponding utility scale. In the context of our examples, high values for pro t denote a high associated pro t, whereas high values for e ort and risk denote low associated e ort and risk estimates.
Prioritization with Aggregated Prioritizations. First, multiattribute utility theory can be applied to determine stakeholder-individual requirement utilities (priorities) (see Table 4). Each stakeholder si evaluates individual requirements with regard to the pre-de ned interest dimensions. Alternatively, stakeholders can specify prioritizizations "directly", i.e., without a utility-based pre-evaluation. Second, requirement utilities can be determined on the basis of Formula 2 where s represents a stakeholder, d 2 Dim represents an interest dimension, and r is a requirement. We assume a globally de ned speci c weight for the individual interest dimensions (see Table 2).
utility(r; s) = d2Dimimp(d) contrib(r; d; s) (2)
Stakeholder-individual prioritizations (see Table 4) have to be aggregated. One approach to support this aggregation is to apply basic social choice based preference aggregation functions such as Borda Count where the winner is the requirement with the best total ranking score where each requirement rank is associated with a score 0 .. #requirements-1 (see Table 6).4
Testing Prioritizations. A prioritization derived on the basis
of a utility analysis can be tested for plausibility. For
example, stakeholders can specify speci c prioritization constraints
that have to hold in the nal prioritization. Such tests could
4 For an overview of di erent types of preference aggregation
functions we refer to [
De nition 1: Consistent Prioritization : given a prioritization P = fp1 : r1 = v1; p2 : r2 = v2; ::; pn : rn = vng for requirements REQ = fr1; r2; ::; rng (vi 2 domain(ri)) and a set of test cases T = ft1; t2; ::; tkg. Then P is a consistent prioritization if P [ ti is consistent 8ti 2 T .
Consistent prioritizations determined on the basis of a utility analysis can be regarded as input for release planning. In the following, we show how prioritizations can be exploited in the context of release planning and how release planning can be represented as a constraint-based con guration task. 3
Constraints ri = vi (vi 2 domain(ri)) representing
individual requirement prioritizations can be used as one input of a
release con guration problem [
De nition 2: Constraint-based Release Con guration Task : a constraint-based release con guration task can be de ned as a tuple (R; P C; RC) where R = frelr1; relr2; ::; relrng is a set of variables representing potential assignments of requirements to releases (domain(relri)=[0..n] { 0 refers to requirements not assigned to a release), P C = fpc1; pc2; ::; pcmg represents a set of prioritization constraints 5, and RC = frc1; rc2; ::; rclg is a set of release constraints.
Examples of typically used release constraints are given in Table 5. Further release constraints that will not be taken into account in our working example are release capacity in hours, total capacity in hours, release costs, total costs, assignment of stakeholders to requirements, average risk level per release, minimum market value per release, and further optimization 5 Hard prioritization constraints are often too strict in practice.
They can also be interpreted as preferences, i.e., solvers should
take these into account as much as possible.
s1
s2
s3
average(AV G)
pro t
3
5
6
4.67
risk
1
3
4
2.67
criteria such as maximum pro t, maximum customer value,
and minimum risk. For simplicity, Table 5 contains only
binary constraints, however, these are generalizable to
higherorder constraints [
An example of a constraint-based release con guration task is the following. This task includes the three requirements from Section 2. Furthermore, three releases are available.
R = frelr1; relr2; relr3g domain(relri) = [1::3] P C = fpc1 : relr2 relr1; pc2 : relr2 relr3g RC = frc1 : relr1 = relr2 ; rc2 : relr1 = 1g relr3; pc3 : relr1
De nition 3: Constraint-based Release Con guration : A constraint-based release con guration (solution) for a constraint-based release con guration task can be represented by a complete assignment RP = frelra = va; relrb = vb; ::; relrk = vkg where vk is the release number of requirement rk such that RP [ P C [ RC is consistent.
In the context of our working example, an example of a constraint-based release con guration is RP = frelr1 = 1; relr2 = 1; relr3 = 2g.
As it is often the case, prioritization as well as release
planning is an iterative process [
De nition 4: Release Recon guration Task : A release recon guration task can be de ned by a tuple (RP; P C0; RC0) where P C0 represents a set of adapted prioritization constraints, RC0 a set of adapted release constraints, and RP [ P C0 [ RC0 is assumed to be inconsistent. The underlying task is to identify a minimal set of constraints RP such that RP [ P C0 [ RC0 is consistent. If parts of RP have already been implemented, we can assume RP = RPcompleted [ RPopen and the task is to identify a diagnosis with RPopen [ RPcompleted [ P C0 [ RC0 is consistent.
A recon guration for a given release recon guration task can be de ned as follows (see De nition 5).
De nition 5: Release Recon guration: A release recon guration (solution) for a release recon guration task can be represented by an assignment RECON F = frelra = va0; relrb = vb0; ::; relrk = vk0g where relri = vi0 2 RECON F ! relri = vi 2 and vi 6= vi0.
In this context, represents a diagnosis, i.e., a minimal set of constraints that, if deleted from RP (RPopen), help to restore consistency, i.e., RP [ P C0 [ RC0 is consistent.
The set can be determined on the basis of a model-based
diagnosis algorithm such as FastDiag [
One could also be interested in identifying minimal sets of changes in given prioritizations P C such that P C [RC is consistent. Table 7 provides an overview of example (re)con guration services that can be provided in release con guration scenarios. (1) proposed prioritizations (P C) have to be checked with regard to their consistency with a de ned set of release constraints (RC). (2) Assuming the consistency of RC s1 s2 s3 pro t 3 5 6 utility (prio) 68 (1) 46 (1) 62 (1) pro t 1 3 4 utility (prio) 13 (3) 33 (3) 31 (2) and the inconsistency of P C [ RC, a minimal set of elements in P C has to be identi ed such that P C [RC is consistent. (3) Assuming the consistency of P C0 [ RC0, a minimal set of elements in RP has to be identi ed (i.e., a potential change of the current release plan) such that RP [ P C0 [ RC0 is consistent. (4) Given a diagnosis for RP (with regard to P C0 [ RC0), a constraint solver can determine a solution for RP [ P C0 [ RC0. (5) If there exists a test case t 2 T with inconsistent(t [ P C), a diagnosis represents a minimal set of elements in P C such that P C [ t is consistent 8t 2 T . Beside performance analyses, there are di erent alternative ways to evaluate the release planning related services mentioned in Table 7.
Release plans as outcome of a con guration process can be evaluated with regard to di erent interest dimensions such as pro t, risk, and e ort. The corresponding utility function is the following (see Formula 3).
utility(RP ) = relr2RP d2Dim contrib(r;d) imp(d)
relr jrelr 2 RP j (3)
An evaluation of the utility of release plans generated with the Choco constraint solver6 is depicted in Table 8. A corresponding performance evaluation is depicted in Table 9. For each combination of jRCj #releases, we randomly generated jRCj release constraints 10 times. In this context, we did not optimize solution search on the basis of search heuristics { this is regarded as a major task of our future work. In Table 8, we can observe a decreasing utility of release plans along with an increasing size of RC. Table 9 shows increasing runtimes with an increasing size of RC and an increasing number of releases. 6 choco-solver.org
Recon gurations of release plans can be evaluated with regard to the similarity between the new con guration and the old con guration where a(S) denotes the set of variable assignments contained in solution S.
similarity(Sold; Snew) = a(Sold) \ a(snew) a(Sold) [ a(snew) (4)
An evaluation of the similarity between recon gurations and original release plans is depicted in Table 10. For each combination of jRCj #releases, we randomly generated jRCj release constraints and a corresponding release plan 10 times, randomly changed 10% of the (original) release constraints and determined a recon guration (for the given release plan). We can observe a decreasing similarity with a corresponding increasing number of release constraints.
Diagnoses can be evaluated with regard to their degree of conservativism (see Formula 5), i.e., the number of changes needed in a constraint set C compared to the overall number of elements in C. Furthermore, diagnoses can be evaluated with regard to their relevance: the lower the total relevance of constraints contained in a diagnosis (represented as the sum of the individual relevances (rel( i)) of constraints in ), the higher the relevance of the (see Formula 6). relevance( = f 1; 2; ::; qg) = j j jCj i2 (6)
An evaluation of conservativism and relevance of generated
diagnoses is depicted in Table 11. For each combination of
jRCj #releases, we randomly generated jRCj release
constraints 10 times, assigned importance values to these
constraints, and randomly changed 10% of the constraints. The
resulting (inconsistent) constraint sets were diagnosed with
FastDiag [
jRCj 5
In this paper, we have shown how to represent release
planning as a con guration problem. This representation is a
major basis for supporting re-planning tasks, i.e., the adaptation
of plans that become inconsistent due to changing constraints
(e.g., a changing availability of resources). In this context, we
also focused on introducing concepts that support the
automated adaptation of release plans (recon guration of release
plans) and di erent variants thereof such as the diagnosis of
release constraints and prioritization constraints. To show the
applicability of the presented concepts, we have presented
initial evaluation results based on a couple of evaluation metrics.
Future work will include the development and evaluation of
di erent types of preference aggregation functions (see
Section 2) with regard to their capability of generating relevant
prioritizations. Furthermore, we will optimize the
determination of release plans, recon gurations, and diagnoses by
integrating intelligent search heuristics that help to improve the
quality of identi ed solutions. In this context, we will
compare constraint-based reasoning approaches with local search
based ones [
The work presented in this paper has been conducted within the scope of the Horizon 2020 project OpenReq (732463).