This is a work in progress…

A Computational Approach for the Product Backlog Prioritization Problem

Abstract
In Scrum and similar Agile product development frameworks, backlog prioritization is one of the principal duties of the Product Owner and determines the order in which product features are developed and ultimately delivered. Despite its obvious significance, current methods of backlog prioritization suffer from one or more of the following shortcomings: failure to elevate risk to the same level of consideration as business value, measurement of business value using metrics that are not as useful or even available at the start of a project, and largely intuitive or sub-optimal approaches to ordering. Although backlog prioritization is the responsibility of the Product Owner, it is nonetheless a collaborative effort. As such, the demands of the business should be balanced against the concerns of the development team. The predominant approach to measuring business value is via a priori financial metrics (NPV, ROI, IRR) or market research (Kano analysis). It is simpler and just as credible and accurate to use a relative business value to rank features and defer financial analyses until after the first release, when the results of sales and customer feedback are actually known. When sorting backlog items, much of the Scrum literature either prescribes a consensus approach (Delphi method) or pairwise comparison (bubble sort). I present an alternate approach that formulates the problem as an iterated 0-1 Multi-Objective Knapsack Problem (MOKP). By incorporating risk as a separate objective and making use of readily obtainable input parameters such as relative business value, this approach addresses the shortcomings cited above. I propose exact, heuristic, stochastic, and approximation methods to find optimal or near optimal solutions for the MOKP with reasonable computational effort for one or more teams assigned to a single product backlog.

1 Introduction

The product backlog prioritization problem (PBPP) is one of the core problems that has to be addressed when developing a product using Agile principles. Product Owners (POs) are tasked with ordering a set of features so as to deliver as much business value as possible subject to the following constraints:

• Precedence - some features have to be worked on before others
• Resource - teams have different capacities (steady-state velocities) and sizes (collaborative overhead)
• Risk - the risks inherent to software product development can have a material impact on business value delivery

1.1 Precedence

Precedence constraints impose an ordering on the set of all backlog items. Subsets of all independent or dependency-satisfied items within this ordered set are referred to as DSPBI (Dependency-Satisfied Product Backlog Item) sets.

1.2 Resource

Resource constraints restrict the amount of work that can be accomplished within a given time period to the smallest DSPBI set that meets or exceeds the combined capacity of all teams. If this DSPBI set exceeds the combined team capacity, it is known as the APBI (Available Product Backlog Item) set.

1.3 Risk

Risk constraints can influence which elements of the APBI set are selected before others for inclusion into the sprint backlog (Scrum) or to do queue (Kanban). Ceteris paribus, riskier items should be worked on earlier since their business values could be impacted due to delay (cost of delay). There are two kinds of risk: systematic and non-systematic. Systematic risk is risk inherent to the entire project and non-systematic risk is risk inherent to a particular backlog item. For our purposes, we shall call the set of individual systematic risks the PR (Project Risk)¹ set and the set of individual non-systematic risks the TR (Technical Risk) ² set. In some Scrum projects, item size and technical risk are conflated. If we then use item size as a substitute for the technical risk, we get a bias towards "heavier" backlog items. Therefore, it is recommended that item size and technical risk be evaluated separately. Both project and technical risk are mitigated by the agility³ of the team working on the items and the amount of time the team has left to complete the items without incurring material (noticeable) loss (delay duration).

1.3.1 Scrum

In Scrum, the time period allotted for completing the sprint backlog is always fixed and time-boxed. If there is more than one team, the bipartite graph of teams to sprint backlog items is called the project sprint backlog:

The actual amount of work completed by a team at the end of their sprint is called the sprint velocity (measured in story points). Note that a sprint is an indivisible unit and is therefore not amenable to more granular productivity measurements often seen in Kanban (see below).

The emphasis is on ensuring that planning, development, and inspection events are grouped in sequence together, hence the use of time-boxed iterations. While this approach is more business-friendly due to its serial nature, it suffers from the formation of internal bottlenecks that can hamper developer productivity over time. These bottlenecks can be attributed to the disparate completion rates of programmers, testers, analysts, and other members of the development team.

1.3.2 Kanban

In Kanban, the time period is called a cycle. Unlike a sprint, a cycle can vary in duration depending on the type of WIP limit imposed. The APBI subset would be added to an existing To Do queue and the WIP limit would constrain the size (in traditional Kanban) or capacity (in Scrumban) of the queue.

Since prioritization is optional in Kanban, we could constrain the APBI set in FIFO (First In First Out) fashion. However, given the high degree of heterogeneity and risk inherent to software development, we would likely mandate prioritization. If the constraint is by size (cardinality), then cycle times are likely to vary from cycle to cycle. If the constraint is by capacity, however, cycle times are expected to be relatively consistent across cycles, mirroring what we see in Scrum. Since the intended aim is to achieve a steady-state velocity, we make use of a capacity-based WIP limit in our analysis.

The amount of work completed within a cycle is called the total throughput (measured in number of items or story points) and is analogous to the sprint velocity discussed above. Throughput, then, is the amount of work completed per unit of cycle time (per day, per week, etc).

The emphasis is on ensuring the steady flow of work items through the queues, hence the use of WIP limits and cadences to ease bottlenecks. This leads to a more efficient use of resources than Scrum due to the parallel nature of development. However, this also makes it more difficult to coordinate effort and achieve steady-state velocities, particularly when there are multiple teams working on the same backlog.

2 Problem Definition

2.1 Problem Description

We can formulate this problem as an iterated 0-1 MOKP[1][2][3] with three objectives:

1. Maximizing the risk absorption (Minimizing the deferred risk)
2. Maximizing the business value
3. Maximizing the capacity utilization

In order to deal with the possible trade-offs across the different objectives, we introduce two perspectives:

1. Technical Perspective - From the vantage point of the Development Team (DT) and other technical stakeholders, any solution that reduces the risk absorption (thereby increasing the deferred risk) in favor of higher business value or capacity utilization is not desirable. This perspective is similar in aim to the Markowitz Model[4] in that it attempts to maximize the benefit without affecting the minimal possible deferred risk (maximal possible risk absorption).
2. Business Perspective - From the vantage point of the Product Owner (PO) and other business stakeholders, any solution that reduces business value in favor of higher risk absorption or capacity utilization is not desirable. This perspective is identical in aim to a weighted shortest job first (WSJF) scheduling discipline with preemption commonly applied in CPU scheduling[5] in that it attempts to minimize the deferred risk (maximize the risk absorption) without affecting the maximal possible benefit (business value).

The parameters and variables are as follows:

1. $ c_j $: item size (in story points)
2. $ v_j $: business value (in business value points)
3. $ t_j $ : delay duration (in number of sprints)
4. $ l $ : team size (number of developers)
5. $ c $ : team capacity / WIP limit (in story points)
6. \( r^p_j \): project risk (systematic risk)
7. \( r^t_j \): technical risk (non-systematic risk)

Item size and technical risk are determined by the DT while business value and project risk are determined by the PO in conjunction with other stakeholders.

If multiple teams are assigned to the same product backlog, then there are three variants:

1. If the team-item assignments do not result in different sizes, risk absorptions, and business values (that is, all three remain the same regardless of which team is assigned to an item), then we have an iterated Multi-Objective Multiple Knapsack Problem[6].
2. If the team-item assignments do result in different sizes, risk absorptions, or business values (that is, any of the three change depending on which team is assigned to an item), then we have a Generalized Assignment Problem[7]. It is possible to minimize or even eliminate the variances in size and business value across teams through standardization of story points and proper team formation, respectively. Indeed, this practice is encouraged and explored further here. Variances in risk absorption, however, are difficult to minimize or eliminate since different teams tend to have different risk profiles.
3. If certain items can only be assigned to a particular team or teams, then we have an iterated Multi-Objective Multiple Knapsack Problem with Assignment Restriction. As can be surmised, assignment restriction simplifies the problem, particularly if a set of items can only be assigned to a single team (MOKP).

2.2 Problem Formulation

In the iterated 0-1 MOKP, at each iteration, or sprint, we are given an APBI set $ N = \{1,…,n\} $ and a team with positive capacity $ c $, size $ l $, and remaining sprints $ t $. APBI element $j$ has positive size $c_j$, business value $v_j$, delay duration $t_j$, technical risk set \(TR_j = \{1,...,r\}\), and project risk set \(PR_j = \{1,...,s\}\), $j = 1,…,n$. TR element $ u $ and PR element $ v $ have positive risk value \(r^t_u\) and \(r^p_v\), respectively, $u = 1,…,r$ and $v = 1,…,s$.

We define risk absorption $r_j$ as follows:

\[ r_j = \frac{(r^t_j + r^p_j) l}{c t_j}, r_j \in \mathbb{R}_{\ge0} \hspace{20 mm} (1.1)\]

where

\[ r^t_j = \sum_{u=1}^r r^t_u \hspace{20 mm} r^t_u \in \mathbb{N}^1_{\le25} \]

\[ r^p_j = \sum_{v=1}^s r^p_v \hspace{20 mm} r^p_v \in \mathbb{N}^1_{\le25} \]

\[ t_j \in \mathbb{N}^1_{\le t} \]

Let $ X $ denote the finite set of feasible solutions. A feasible solution is represented by a vector $ x = (x_1,…,x_n) $ of binary decision variables $x_j$, such that $x_j$ = 1 if APBI item $j$ is included in the solution and 0 otherwise, which satisfies the capacity constraint \( \sum_{j=1}^n c_j x_j \leq c \). Each such solution \( x \in X \) is represented in the objective space by its corresponding objective vector:

\[ f(x) = ( f_r(x), f_v(x), f_c(x) ) \hspace{20 mm} (1.2)\]

where

\[ f_r(x) = \sum_{j=1}^n r_j x_j \] \[ f_v(x) = \sum_{j=1}^n v_j x_j \] \[ f_c(x) = \sum_{j=1}^n c_j x_j \]

The dominance relation defined on $X$, denoted by \( \underline{\Delta} \) , states that a feasible solution $ x $ dominates a feasible solution $ x' $, \( x \underline{\Delta} x' \) , \( \iff f_r(x) \geq f_r(x') \land f_v(x) \geq f_v(x') \land f_c(x) \geq f_c(x') \). We denote by \( \Delta \) the asymmetric part of \( \underline{\Delta} \). A solution $ x $ is efficient \( \iff \) there is no other feasible solution \( x' \in X \) such that \( x' \Delta x \), and its corresponding objective vector \( f(x) \) is said to be non-dominated. Thus, the efficient set is defined as \( E(X) = \{ x \in X : \forall x' \in X\), not \((x' \Delta x)\} \). The set of non-dominated objective vectors, which corresponds to the image of the efficient set in the objective space, is denoted by $ND$. Since the efficient set can contain different solutions corresponding to the same objective vector, any subset of $E(X)$ that contains one and only one solution for every non-dominated objective vector is called a reduced efficient set denoted by \( \hat{E(X)} \). We aim at determining the set of non-dominated objective vectors, $ND$, and the reduced efficient set \( \hat{E(X)} \).

3 Heuristic Results

Before proceeding with solving the MOKP, we take a look at a simple heuristic that attempts to maximize all three objectives based on whether items are on the critical path or not.

3.1 Heuristic

1. Items must be added such that the running story point total does not exceed the commitment
2. Items must be independent⁴ except when there are no other items remaining to be worked on
3. Items on the critical path take precedence
4. Items not on the critical path must be chosen such that those that have the earliest critical path dependencies take precedence, with story points and business value (if present) following suit - i.e., earliest critical path dependency > story points > business value

If more than one team

5. Items must be chosen based on the degree of team specialization⁵, agility³, and number of remaining sprints, in order of decreasing precedence. For example, a product backlog item that is database-specific/heavy would be assigned to the most database specialized team, if one exists⁶. Otherwise, it would be assigned to the team with the highest agility⁶. If two or more teams have equal agility, then the item would be assigned to the team with the greatest number of remaining sprints.

3.2 Algorithm

TODO: Write algorithm in pseudocode

3.3 Rationale

Work is assigned with project¹ and technical risk² in mind first, and then business value. Larger⁷, specialized⁸, rapidly changing⁹, and emergent¹⁰ items, or any combination thereof, are deemed to be riskier and should be tackled first.

Since agility³ is basically a corollary of quality¹¹ which itself is a measure of resource utilization or efficiency, it naturally follows that teams with greater agility can respond to change more quickly or accomplish more with less since they tend to be smaller and/or more capable. Thus, riskier items are assigned to such teams in order to incur less project and/or technical risk.

Business value is only used to break ties when items are of the same size or degree of specialization.

3.4 Input

1. Dependency-Ordered Product Backlog (DOPB)
2. Critical Path (CP)
3. Business points attained per release or backlog item cutoffs (optional)

3.5 Output

1. Priority-Ordered Product Backlog (POPB)
2. Release plan (if Input 2. is provided)

3.6 Example

Input:

Srinj DOPB and CP

Output:

1. Textual

   Srinj Priority-Ordered Product Backlog
   
   ---------------------------------------------------
   Product Backlog items available to be worked on:
   
   USRREG - 28 3000 (CP)
   COMINS - 10 2000
   DREQAL - 15 2000
   PATCON - 15 3000
   PATSER - 28 1200
   
   Team SproutCore KL (45) (0)
   Sprint 1 (38):
   USRREG - on critical path
   COMINS - earliest dependency
   ---------------------------------------------------
   Product Backlog items available to be worked on:
   
   USRPRO - 13 1200  (CP)
   DREQAL - 15 2000
   PATCON - 15 3000
   PATSER - 28 1200
   
   Team SproutCore KL (45) (38)
   Sprint 2 (41):
   USRPRO - on critical path
   PATSER - earliest dependency, maximum size
   -----------------------------------------------------
   Product Backlog items available to be worked on:
   
   PATVIS - 26 3000 (CP)
   DREQAL - 15 2000
   PATCON - 15 3000
   PEPALO - 20 1200
   
   Team SproutCore KL (45) (79)
   Sprint 3 (41):
   PATVIS - on critical path
   PATCON - earliest dependency
   -----------------------------------------------------
   Product Backlog items available to be worked on:
   
   PATEXA - 23 (CP)
   DREQAL - 15
   PEPALO - 20
   EDICPC - 25
   PATSCH - 10
   
   Team SproutCore KL (45) (120)
   Sprint 4 (38):
   PATEXA - on critical path
   DREQAL - earliest dependency
   -----------------------------------------------------
   Product Backlog items available to be worked on:
   
   PATTRE - 25 (CP)
   SUPCLI - 25
   PEPALO - 20
   EDICPC - 25
   PATSCH - 10
   
   Team SproutCore KL (45) (158)
   Sprint 5 (45):
   PATTRE - on critical path
   PEPALO - earliest dependency, maximum allowable size
   -----------------------------------------------------
   Product Backlog items available to be worked on:
   
   ROLES  - 13
   SUPCLI - 25
   EDICPC - 25
   PATSCH - 10
   
   Team SproutCore KL (45) (203)
   Sprint 6 (38):
   SUPCLI - earliest dependency
   ROLES  - earliest dependency, maximum allowable size 
   -----------------------------------------------------
   Product Backlog items available to be worked on:
   
   EDPACS - 45
   EDICPC - 25
   PATSCH - 10
   
   Team SproutCore KL (45) (241)
   Sprint 7 (45):
   EDPACS - earliest dependency
   -----------------------------------------------------
   Product Backlog items available to be worked on:
   
   
   ORDINV - 26
   EDICPC - 25
   PATSCH - 10
   
   Team SproutCore KL (45) (286)
   Sprint 8 (36):
   ORDINV - earliest dependency
   PATSCH - maximum allowable size
   -----------------------------------------------------
   Product Backlog items available to be worked on:
   
   
   ACCTNG - 40 (CP)
   EDICPC - 25
   
   Team SproutCore KL (45) (322)
   Sprint 9 (40):
   ACCTNG - on critical path
   -----------------------------------------------------
   Product Backlog items available to be worked on:
   
   
   REPLOG - 40 (CP)
   EDICPC - 25
   
   Team SproutCore KL (45) (362)
   Sprint 10 (40):
   REPLOG - on critical path
   -----------------------------------------------------
   Product Backlog items available to be worked on:
   
   
   EDICPC - 25
   NOFNRQ - 8
   
   Team SproutCore KL (45) (402)
   Sprint 11 (33):
   EDICPC - earliest dependency
   NOFNRQ - on critical path (no other items, so exclusivity doesn't apply)
   
   

2. Graphical

Srinj Theme Feature Map

4 Computational Results

4.1 MOKP

If a set of items is assigned to a single team, then a dynamic programming or stochastic algorithm is needed.

4.2 MOMKP

If a set of items is assigned to teams of equal capacity (MOMKP-I), then an approximation[8] or any-time algorithm is needed.

If a set of items is assigned to teams of disparate capacities (MOMKP-D), then a greedy approximation algorithm[9] is needed.

4.3 GAP

If a set of items is assigned to teams where team-item assignments can result in different values for the objective vector, then a stochastic algorithm is needed.

4.4 MOMKPAR

If a set of items can only be assigned to one or more teams, then the problem reduces to MOKP or MOMKP.

5 Future Work

TODO: Add areas to explore here

6 Bibliography

References

1. ^ Knapsack problem,
   http://en.wikipedia.org/wiki/Knapsack_problem
2. ^ Knapsack Problems,
   http://books.google.com.my/books?id=u5DB7gck08YC
3. ^ Multi-objective optimization,
   http://en.wikipedia.org/wiki/Multi-objective_optimization
4. ^ Markowitz Model,
   http://en.wikipedia.org/wiki/Harry_Markowitz#Harry_Markowitz_Model
5. ^ CPU Scheduling,
   http://www.scs.stanford.edu/09wi-cs140/notes/l5-print.pdf
6. ^ List of Knapsack problems,
   http://en.wikipedia.org/wiki/List_of_knapsack_problems
7. ^ Generalized Assignment Problem,
   http://en.wikipedia.org/wiki/Generalized_assignment_problem
8. ^ Approximation Algorithm,
   http://en.wikipedia.org/wiki/Approximation_algorithm
9. ^ Greedy Algorithm,
   http://en.wikipedia.org/wiki/Greedy_algorithm

---

1. 1. Project Risk = schedule overrun risk + cost overrun risk + scope creep risk + quality reduction risk + change risk
2. 2.  Technical Risk = aptitude risk + feasibility risk
3. 3. Agility = Velocity / Resources
4. 4. There does not exist a directed path between any 2 items selected from the set of chosen items
5. 5. Degree of Specialization = Specialized Resources / Total Resources
6. 6. Cross-functional teams are preferred
7. 7. Larger ⇒ schedule overrun risk
8. 8. Specialized ⇒ technical risk
9. 9. Rapidly Changing ⇒ scope creep risk
10. 10. Emergent ⇒ scope creep risk
11. 11. Quality = Result of Work Effort / Total Cost, as defined by  Deming

Child Pages:

• BacklogPrioritization
  • GAP
  • MOKP
  • MOMKP

© 2011-2012 Tarun Sukhani. All Rights Reserved