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.     

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     

Optimal control policies for a periodic review inventory system with emergency orders

We describe a periodic review inventory system where emergency orders, which have a shorter supply lead time but are subject to higher ordering cost compared to regular orders, can be placed on a continuous basis. We consider the periodic review system in which the order cycles are relatively long so that they are possibly larger than the supply lead times. Study of such systems is important since they are often found in practice. We assume that the difference between the regular and emergency supply lead times is less than the order-cycle length. We develop a dynamic programming model and derive a stopping rule to end the computation and obtain optimal operation parameters. Computational results are included that support the contention that easily implemented policies can be computed with reasonable effort. © 1998 John Wiley & Sons, Inc. Naval Research Logistics 45: 187–204, 1998     

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.     

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.     

Approximation schemes for single‐machine scheduling with a fixed maintenance activity to minimize the total amount of late work

We consider the problem of scheduling n independent and simultaneously available jobs without preemption on a single machine, where the machine has a fixed maintenance activity. The objective is to find the optimal job sequence to minimize the total amount of late work, where the late work of a job is the amount of processing of the job that is performed after its due date. We first discuss the approximability of the problem. We then develop two pseudo‐polynomial dynamic programming algorithms and a fully polynomial‐time approximation scheme for the problem. Finally, we conduct extensive numerical studies to evaluate the performance of the proposed algorithms. © 2016 Wiley Periodicals, Inc. Naval Research Logistics 63: 172–183, 2016     

Algorithm to solve a chance‐constrained network capacity design problem with stochastic demands and finite support

We consider the problem of determining the capacity to assign to each arc in a given network, subject to uncertainty in the supply and/or demand of each node. This design problem underlies many real‐world applications, such as the design of power transmission and telecommunications networks. We first consider the case where a set of supply/demand scenarios are provided, and we must determine the minimum‐cost set of arc capacities such that a feasible flow exists for each scenario. We briefly review existing theoretical approaches to solving this problem and explore implementation strategies to reduce run times. With this as a foundation, our primary focus is on a chance‐constrained version of the problem in which α% of the scenarios must be feasible under the chosen capacity, where α is a user‐defined parameter and the specific scenarios to be satisfied are not predetermined. We describe an algorithm which utilizes a separation routine for identifying violated cut‐sets which can solve the problem to optimality, and we present computational results. We also present a novel greedy algorithm, our primary contribution, which can be used to solve for a high quality heuristic solution. We present computational analysis to evaluate the performance of our proposed approaches. © 2016 Wiley Periodicals, Inc. Naval Research Logistics 63: 236–246, 2016