Kevin’s R&D Planning Blog

Research and Development Planning: Selecting and Scheduling Projects with Approximate Solutions to a Markov Decision Model Dissertation Executive Summary 

Kevin Gormley, 4/26/07

Committee: Professor William Scherer (Advisor), Professor K.P. White (Chair), Professor Peter Beling, Professor Robert Carraway; Dr. Patricia Massimini

This research investigated approximate solution methods for solving the Research and Development (R&D) project selection and scheduling problem. Globally, industry and government invested a projected one trillion dollars in 2006, (Duga and Studt 2005)[1] yet detailed decision models have not been widely used. (Henriksen and Traynor 1999; Raynor and Leroux 2004) The key research contributions were 1) a comprehensive survey of the R&D planning research literature, 2) a Markov decision model based on the R&D planning tool of “technology roadmaps,” and 3) an extensive evaluation of approximate solution methods for solving different types of project networks.

Over decades of research in R&D project selection, many models and solution approaches have been created including scorecards, linear programs, dynamic programs and various heuristics. (Heidenberger and Stummer 1999) The use of technology roadmaps or networks of projects that lead to technology goals has increased over the past several years. (Radnor and Probert 2004) Unlike models of serial or parallel sets of projects often seen in the literature (Chun 1994; Subramanian et al. 2000), these technology roadmaps may take more complex forms with complicated project precedence relationships. To capture the complexity of technology roadmaps, a model was designed (“PRIORITY”), which is shown in context of the existing literature in Figure 1.

Figure 1 Map of the R&D Planning Research Literature[2]

This research (labeled “PRIORITY” to the right of the center) focused on an R&D planning model that 1) considers both project selection and scheduling, 2) uses both formal optimization and heuristic methods for obtaining solutions, and 3) allows for project failure and a complex network structure.

The problem was formulated as a discrete, dynamic sequential stochastic program using a Markov decision model. Due to the “curse of dimensionality” (Bertsekas 2000), models of sufficiently large and complex project networks cannot be solved with dynamic programming in a reasonable time. (Jones 2006) Recently, researchers have proposed genetic algorithms for near-optimal solutions to project selection and scheduling problems. (Jong and Schonfeld 2001; Brown and Sumichrast 2003; McConnell 2003) Unlike some other methods, the genetic algorithm (GA) was easily adapted into the proposed model formulation.

Three approximate solution methods were tested against the GA benchmark for sets of random project networks and a case study. This research focused on parts 5, 6a and 6b in the R&D planning process shown in Figure 2.

Figure 2 R&D Planning Process

Three approaches were examined: state aggregation, problem decomposition, and heuristic methods. For state aggregation, the system states were aggregated by grouping project states (funded for one period, funded for two periods, etc.) together into one state (“in progress”). In problem decomposition, a project network with several goals was split into one sub-network for each goal. Each sub-network was individually solved and all the sub-network solutions were combined into an overall funding solution. The most effective heuristic was the “goal contribution” heuristic where projects were selected based on how much each project contributed towards estimated expected utility.

An integrated heuristic combined state aggregation and the goal contribution heuristic for an overall recommendation. When the problem was too large to be solved optimally with a full dynamic program, the goal contribution and integrated heuristic were often the best of the approximate solution methods. In empirical results, both the goal contribution and integrated heuristic had a statistically significant higher utility than the GA benchmark.

Figure 3 shows the range of utility for solving ten complex networks of thirty projects.

Figure 3 Utility by Solution Approach for 10 Large, Complex Project Networks

The Integrated Heuristic and Goal Contribution performed significantly better than the Genetic Algorithm for networks 3, 4, 7, 8, 9 and 10 (for the Integrated Heuristic) with separation between the +/- one standard deviation ranges. The two heuristics performed at least as well as the Genetic Algorithm for the other project networks. A Student’s t test comparing the difference in mean utility on the large, complex project networks found that the Goal Contribution and Integrated Heuristic had greater utility than the Genetic Algorithm with a p value of <0.0001. The Goal Contribution and Integrated Heuristic both had a mean utility of about 3.9, nearly tripling the utility of the Genetic Algorithm. See Table 1 for a comparison of the approximate solutions methods.

Table 1 Summary of Solution Approaches for R&D Project Networks

Figure 4 shows the proposed use of solution approaches by project networks size.

Figure 4 Use of Solution Approaches and Project Network Size

In summary, the research literature was categorized, a model for R&D planning using technology roadmaps was formulated, and approximate solution approaches were evaluated for a variety of project networks. The categorization of the literature suggested that new R&D models were needed to capture the complexity of technology roadmaps. The proposed Markov decision model formulation considered the selection and scheduling of R&D projects given the inputs of project costs, probability of success, goal utility, resource constraints, and precedent relationships. Through extensive empirical tests, the Goal Contribution and the Integrated Heuristic were shown to achieve significantly higher utilities than the Genetic Algorithm benchmark.

Future research may examine the relaxation of assumptions such as the certainty of precedent relationships, the property of unfunded projects to remain in the same state, and project costs not changing in time periods. In addition, modeling can be done in competitive R&D planning where rival organizations strive to be the first to achieve breakthroughs and to patent technologies.

[1] References are listed in the full dissertation.

[2] Acronyms in diagram are as follows: Program Evaluation and Review Technique (PERT), Critical Path Method (CPM), and Graphical Evaluation and Review Technique (GERT).