Balancing and optimizing a portfolio of R&D projects

A mathematical formulation of an optimization model designed to select projects for inclusion in an R&D portfolio, subject to a wide variety of constraints (e.g., capital, headcount, strategic intent, etc.), is presented. The model is similar to others that have previously appeared in the literature and is in the form of a mixed integer programming (MIP) problem known as the multidimensional knapsack problem. Exact solution of such problems is generally difficult, but can be accomplished in reasonable time using specialized algorithms. The main contribution of this paper is an examination of two important issues related to formulation of project selection models such as the one presented here. If partial funding and implementation of projects is allowed, the resulting formulation is a linear programming (LP) problem which can be solved quite easily. Several plausible assumptions about how partial funding impacts project value are presented. In general, our examples suggest that the problem might best be formulated as a nonlinear programming (NLP) problem, but that there is a need for further research to determine an appropriate expression for the value of a partially funded project. In light of that gap in the current body of knowledge and for practical reasons, the LP relaxation of this model is preferred. The LP relaxation can be implemented in a spreadsheet (even for relatively large problems) and gives reasonable results when applied to a test problem based on GM's R&D project selection process. There has been much discussion in the literature on the topic of assigning a quantitative measure of value to each project. Although many alternatives are suggested, no one way is universally accepted as the preferred way. There does seem to be general agreement that all of the proposed methods are subject to considerable uncertainty. A systematic way to examine the sensitivity of project selection decisions to variations in the measure of value is developed. It is shown that the solution for the illustrative problem is reasonably robust to rather large variations in the measure of value. We cannot, however, conclude that this would be the case in general. © 2001 John Wiley & Sons, Inc. Naval Research Logistics 48: 18–40, 2001     

Economic design of a two-stage control chart based on both performance and surrogate variables

The traditional approach to economic design of control charts is based on the assumption that a process is monitored using only a performance variable. If, however, the performance variable is costly to measure and a less expensive surrogate variable is available, the process may be more efficiently controlled by using both performance and surrogate variables. In this article we propose a model for economic design of a two-stage control chart which uses a highly correlated surrogate variable together with a performance variable. The process is assumed to be monitored by the surrogate variable until it signals out-of-control behavior, then by the performance variable until it signals out-of-control behavior or maintains in-control signals for a prespecified amount of time, and the two variables are used in alternating fashion. An algorithm based on the direct search method of Hooke and Jeeves [6] is used to find the optimum values of design parameters. The proposed model is applied to the end-closure welding process for nuclear fuel to compute the amount of reduction in cost compared with the current control procedure. © 1999 John Wiley & Sons, Inc. Naval Research Logistics 46: 958–977, 1999     

Decomposition algorithms for the maximum-weight connected graph problem

Given a positive integer R and a weight for each vertex in a graph, the maximum-weight connected graph problem (MCG) is to find a connected subgraph with R vertices that maximizes the sum of their weights. MCG has applications to communication network design and facility expansion. The constrained MCG (CMCG) is MCG with a constraint that one predetermined vertex must be included in the solution. In this paper, we introduce a class of decomposition algorithms for MCG. These algorithms decompose MCG into a number of small CMCGs by adding vertices one at a time and building a partial graph. They differ in the ordering of adding vertices. Proving that finding an ordering that gives the minimum number of CMCGs is NP-complete, we present three heuristic algorithms. Experimental results show that these heuristics are very effective in reducing computation and that different orderings can significantly affect the number of CMCGs to be solved. © 1998 John Wiley & Sons, Inc. Naval Research Logistics 45: 817–837, 1998     

Open shop scheduling to minimize the number of late jobs

We develop polynomial algorithms for several cases of the NP-hard open shop scheduling problem of minimizing the number of late jobs by utilizing some recent results for the open shop makespan problem. For the two machine common due date problem, we assume that either the machines or the jobs are ordered. For the m machine common due date problem, we assume that one machine is maximal and impose a restriction on its load. © 1998 John Wiley & Sons, Inc. Naval Research Logistics 45: 525–532, 1998     

Operating characteristics of a two-echelon inventory system for repairable and consumable items under batch ordering and shipment policy

In this article we have generalized previous models on multiechelon recoverable inventory systems to cover the cases of batch ordering and shipment policy, and when items can either be repaired or condemned. The batch ordering and shipment policy is appropriate when the setup cost for shipment and order and/or the demand rates of the items are relatively high. The operating characteristics of such a system have been studied. Specifically, the probability distribution of backorder levels at the bases are analyzed for different repair-time distributions. An approximation scheme is proposed for this distribution, and is evaluated using extensive simulation results. The results indicate that the scheme is very effective in providing near-optimal stocking levels in such a system.     

Global planning of accelerated degradation tests based on exponential dispersion degradation models

The accelerated degradation test (ADT) is an efficient tool for assessing the lifetime information of highly reliable products. However, conducting an ADT is very expensive. Therefore, how to conduct a cost-constrained ADT plan is a great challenging issue for reliability analysts. By taking the experimental cost into consideration, this paper proposes a semi-analytical procedure to determine the total sample size, testing stress levels, the measurement frequencies, and the number of measurements (within a degradation path) globally under a class of exponential dispersion degradation models. The proposed method is also extended to determine the global planning of a three-level compromise plan. The advantage of the proposed method not only provides better design insights for conducting an ADT plan, but also provides an efficient algorithm to obtain a cost-constrained ADT plan, compared with conventional optimal plans by grid search algorithms.     

Callable products with dependent demands

Capacity providers such as airlines often sell the same capacity to different market segments at different prices to improve their expected revenues. The absence of a secondary market, due to the nontransferability of airline tickets, gives rise to an opportunity for airlines to broker capacity between consumers with different willingness to pay. One way to broker capacity is by the introduction of callable products. The idea is similar to callable bonds where the issuer has the right, but not the obligation, to buy back the bonds at a certain price by a certain date. The idea of callable products was introduced before under the assumption that the fare-class demands are all independent. The independent assumption becomes untenable when there is significant demand recovery (respectively, demand cannibalization) when lower fares are closed (respectively, opened). In this case, consumer choice behavior should be modeled explicitly to make meaningful decisions. In this paper, we consider a general consumer choice model and develop the optimal strategy for callable products. Our numerical study illustrates how callable products are win-win-win, for the capacity provider and for both high and low fare consumers. Our studies also identify conditions for callable products to result in significant improvements in expected revenues.     

An analytic basis for decision support in negotiations

Mediators increase the effectiveness of negotiation processes. The art of mediation includes interpersonal skills, ability to convince, and proficiency in argumentation. The science of mediation represents an analytical approach to problem solving, a systematic analysis of the process, of players' positions, and of their goals, aspirations, and concessions. Analytical tools for mediation can be used by mediators, but these tools can also support negotiators in their analysis, verification of their positions, and choices. The knowledge of effective and safe alternatives, of sets of compromises, and the knowledge of the possible outcomes of concessions may be used to develop an effective strategy and to increase a negotiator's bargaining power. Models to analyze alternatives, to verify concessions made by the opponents, to determine effective alternatives, and to search for solutions that yield mutual gains, to aggregate opponents' proposals, to look for coalition members, and to simulate some of the actions of a mediator are discussed in the article.     

Tests for transient means in simulated time series

We present a family of tests to detect the presence of a transient mean in a simulation process. These tests compare variance estimators from different parts of a simulation run, and are based on the methods of batch means and standardized time series. Our tests can be viewed as natural generalizations of some previously published work. We also include a power analysis of the new tests, as well as some illustrative examples. © 1994 John Wiley & Sons, Inc.     

Algorithms for the constrained maximum-weight connected graph problem

Given a positive integer R and a weight for each vertex in a graph, the maximum-weight connected graph (MCG) problem is to find a connected subgraph with R vertices that maximizes the sum of the weights. The MCG problem is strongly NP-complete, and we study a special case of it: the constrained MCG (CMCG) problem, which is the MCG problem with a constraint of having a predetermined vertex included in the solution. We first show that the Steiner tree problem is a special case of the CMCG problem. Then we present three optimization algorithms for the CMCG problem. The first two algorithms deal with special graphs (tree and layered graphs) and employ different dynamic programming techniques, solving the CMCG problem in polynomial times. The third one deals with a general graph and uses a variant of the Balas additive method with an imbedded connectivity test and a pruning method. We also present a heuristic algorithm for the CMCG problem with a general graph and its bound analysis. We combine the two algorithms, heuristic and optimization, and present a practical solution method to the CMCG problem. Computational results are reported and future research issues are discussed. © 1996 John Wiley & Sons, Inc.