Transcript Slides - Crest

Search-Based Software Project
Staffing: Challenges, Solutions,
Promises, and Limitations
Massimiliano Di Penta
[email protected]
Ack
 This work has been carried out together
with:
 Giulio Antoniol
 Mark Harman
 Fahim Qureshi
Motivations
 Project planning is a crucial task for software
maintenance projects
 Poor planning can cause unacceptable costs and
delays
 Main causes of many software project failures
Project staffing/scheduling
modeled as a search problem
Search-based staffing approach
 Search problem:
 Determine the (near) optimal WP ordering in the
queue and the people distribution across teams
 Objective: minimize the project completion time
provided that precedence constraints are satisfied
 Fitness function: completion time obtained by
simulating the queuing model
 Further details:
 Massimiliano Di Penta, Mark Harman, Giuliano
Antoniol, "The use of Search-Based Optimization
Techniques to Schedule and Staff Software Projects:
an Approach and an Empirical Study", Software:
Practice and Experience, (to appear), 2010, Wiley
Representation
WP
Ordering
4
2
1
3
WP1 WP2 WP3 WP4
Maintainers
Allocation
T2 T2 T3 T1
D1
D2
D3
D4
Team 1
D4
Team 2
D1
WP1 WP4 WP2 WP3
Team 3
D3
D2
How long does it take a team of n
persons to complete a task requiring
e person/months?
The Mythical Man Month
 Famous book by Frederick Brooks, firstly
published in 1975
 Brooks’ Law:
“Adding manpower to a late software
project makes it later”
 However, the sentence before says:
“Oversimplifying outrageously, we state Brooks’
Law”
 Brooks also makes the observation:
“there is no simple linear conversion between
person–months and staff levels”
Search based analysis of communication
overhead
 Explore the impact of communication overhead
over:
 Project completion time
 Maintainers distribution across teams
 What happens when increasing the staffing levels
 Different communication overhead models are
formalized and simulated
 Further details:
 Massimiliano Di Penta, Mark Harman, Giuliano
Antoniol, Fahim Qureshi: The Effect of
Communication Overhead on Software Maintenance
Project Staffing: a Search-Based Approach. ICSM
2007: 315-324
Communication overhead models
Communication overhead
months
months
Perfectly partitionable task
persons
Task not partitionable
months
months
Complex communication overhead
persons
persons
persons
Formally…
e
t
n
Perfectly partitionable task
(Brooks’ Law does not apply)
e
t   ce  n(n  1) / 2 Communication involving
pairs
n
e
 ce  n(n  1) / 2  n(n  1)(n  2) / 3!...  n(n  1)...(n  k  1) / k!
n
e
k n
Complex Communication
  ce   j 1  
n
 j
t
e
t   ce  n
n
t
e
 ce  log(n)
n
Linear communication overhead
(some structure of communication)
Logarithmic communication overhead
(good communication structure)
Empirical Study
 Objective: analyze the effect of different staffing levels
and of communication overhead models on the
completion time and on the resource assignment to
teams when staffing and scheduling a software
maintenance project using a search-based approach
 Communication models considered in the study: log
(structured communication), quadratic (pair
communication), cubic (up to 3 people communication)
 Context: data from 2 industrial projects
 Project A: Massive Y2K remedial project
– 84 WPs
– No dependencies
 Project B: Evolution of a multiplatform system
– 108 WPs
– 102 WP dependencies
Research questions
 RQ1: what’s the project completion time for
different staffing levels
 RQ2: would it be possible to handle
handling specialized teams?
 RQ3: what’s the effect of communication
overhead?
Completion time for different staffing levels
Project A
Above a certain staffing level benefits result reduced…
Completion time for different staffing levels
Project B
…even more when there are complex dependencies…
Tradeoff between completion time and
staffing level
 Multi-objective optimization using NSGA-II
Handling specialized teams
Database
70 12
58
56
53
Networking
Middleware
Core
Compl. Time
(person months)
49
48
Staffing
Staffing
60 10
50
8
40
30 6
GUI
40
39
6
7
8
7
8
37
20 4
10
2
0
0
1
2
1
3
2
4
3
5
4
5
Configuration
Configuration
6
Effect of communication overhead
Quadratic
Cubic
Log
190
170
150
130
110
0
1
2
3
4
5
6
7
8
9
% of communication overhead
Project A
10
Completion time
[days]
Completion time
[days]
Log
Quadratic
Cubic
600
500
400
300
200
0
1
2
3
4
5
6
7
8
9
% of communication overhead
Project B
 Significant difference among different models for any
communication overhead percentage
 Log model introduces a significantly lower overhead
 For 4%≤overhead%≤8% (Project A) and
2%≤overhead%≤9% (Project B) cubic model significantly
increases the completion time with a high effect size
 By using team re-balancing, the manager can minimize the
impact of communication overhead
10
Varying staffing and communication
Quadratic
Cubic
No overhead
170.0
153.0
150.0
130.0
145.4
131.5
142.0
132.8
134.8
126.7
122.4
110.0
126.1
113.8
35
40
45
50
Staffing level
Project A
55
Log
Completion time
[days]
Completion time
[days]
Log
Quadratic
Cubic
No overhead
500
400
300
200
10
15
20
25
30
Staffing level
Project B
 Project A: significant differences among models
– All models able to benefit for increasing staffing level up to
46 (optimal staffing we found in [TSE 2004])
– Different models benefit in different measures
 more evident gain for log model
 Project B: benefits less evident above 20 (actual staffing)
– Even some increase…
35
Limitations and Risks of SBSE planning
and scheduling
 SBSE scheduling/staffing is not going to
solve all your problems
 Modeling expertises:
 WPs often require specific expertises, even
multiple ones
 Depending on the skills, performances of
people on specific tasks can vary
– I could be able to develop a network module, but
an expert would do it in 50% of my time
 How to evaluate it? How to model it?
Limitations and Risks of SBSE planning
and scheduling
 Dealing with uncertainty
 Effort estimation is imprecise
 Unexpected activities can arise
– E.g. unexpected requirements, re-development of some
modules
 Project managers might want to build a robust
schedule such that:
– The project is staffed in a way to ensuring missing deadlines
even in presence of unexpected events or bad estimations
 Details:
 S. Gueorguiev, M. Harman, and G. Antoniol, ‘Software
project planning for robustness and completion time
in the presence of uncertainty using multi objective
search based software engineering’, in Genetic and
Evolutionary Computation Conference, GECCO 2009,
Proceedings, Montreal, Quebec, Canada, July 8-12,
2009, pp. 1673–1680. ACM, (2009).
Limitations and Risks of SBSE planning
and scheduling
 Dealing with project dynamics
 Simple SBSE approaches could assume a (fairly) fixed
team staffing
 This is not the case in reality
– Staffing is re-distributed among teams during the project
 Possible solution: combine search-based methods and
simulation
– Determine a sequence of events over time
– See the racing game simulation challenge at GECCO 2009
Example







T1:
T1:
…
T4:
…
T7:
…
assign Person 1 to Team A
assign Person 1 to Team B
dispatch WP1 to Team A
move Person 1 to Team B
Application to FLOSS
 FLOSS projects have, wrt. industrial
projects, a more self-organizing nature
 Cathedral vs. Bazaar projects
 Activities are entirely based on a voluntary
basis
 Thus, no real project scheduling
 Everybody works whenever has time
However…
 Also in FLOSS, change requests (bug fixing)
cannot be handled in any order
 There are complex dependency relations among
bugs
 Some of them blocking relations
 Empirical studies have indicated a significant
correlation between change entropy and faultproneness [Hassan, 2009]
 Changes performed on many files
 Files touched by many developers
How SBSE could play a role here…
 It could help the project core team to assign
bugs to contributors
 Inputs:
 Developer expertise (from previous tasks, see [Anvik
et al. 2006])
 Availability for a given time period
 Bug dependencies/blocking relations (from BTS)
 Bug priorities (from BTS)
 Objective: support bug triaging
 Assign bugs to developer such that they will be fixed
in the shortest time possible
 Keep into account bug priorities
SBSE Challenges
 Search-based techniques could be used to aid
the project manager
 But should not replace her!
 In principle models could incorporate many
parameters
 Expertise, communication overhead, training,
uncertainty
 Too many variables, however…
 Work-in-progress:
 Can SBSE be applied to support coordination in FLOSS
projects?
Thank you!
Questions?