On the uncapacitated K‐commodity network design problem with zero flow‐costs

Extending Sastry's result on the uncapacitated two‐commodity network design problem, we completely characterize the optimal solution of the uncapacitated K‐commodity network design problem with zero flow costs for the case when K = 3. By solving a set of shortest‐path problems on related graphs, we show that the optimal solutions can be found in O(n³) time when K = 3, where n is the number of nodes in the network. The algorithm depends on identifying a list of “basic patterns”; the number of basic patterns grows exponentially with K. We also show that the uncapacitated K‐commodity network design problem can be solved in O(n³) time for general K if K is fixed; otherwise, the time for solving the problem is exponential. © 2004 Wiley Periodicals, Inc. Naval Research Logistics, 2004     

A general approach to the shape of failure rate and MRL functions

Failure rate and mean residual life are two important characteristics for studying reliability of products. In literature, some work studied the shape of failure rate function based on the knowledge of the associated probability density function; some other work investigated the shape of mean residual life function based on the shape of the associated failure rate function separately for continuous case and discrete case. In this article, a general approach is developed which can be applied to the aforementioned studies. © 2004 Wiley Periodicals, Inc. Naval Research Logistics, 2004     

Higher‐order Markov chain models for categorical data sequences*

In this paper we study higher‐order Markov chain models for analyzing categorical data sequences. We propose an efficient estimation method for the model parameters. Data sequences such as DNA and sales demand are used to illustrate the predicting power of our proposed models. In particular, we apply the developed higher‐order Markov chain model to the server logs data. The objective here is to model the users' behavior in accessing information and to predict their behavior in the future. Our tests are based on a realistic web log and our model shows an improvement in prediction. © 2004 Wiley Periodicals, Inc. Naval Research Logistics, 2004     

Optimization of schedule stability and efficiency under processing time variability and random machine breakdowns in a job shop environment

The ability to cope with uncertainty in dynamic scheduling environments is becoming an increasingly important issue. In such environments, any disruption in the production schedule will translate into a disturbance of the plans for several external activities as well. Hence, from a practical point of view, deviations between the planned and realized schedules are to be avoided as much as possible. The term stability refers to this concern. We propose a proactive approach to generate efficient and stable schedules for a job shop subject to processing time variability and random machine breakdowns. In our approach, efficiency is measured by the makespan, and the stability measure is the sum of the variances of the realized completion times. Because the calculation of the original measure is mathematically intractable, we develop a surrogate stability measure. The version of the problem with the surrogate stability measure is proven to be NP‐hard, even without machine breakdowns; a branch‐and‐bound algorithm is developed for this problem variant. A tabu search algorithm is proposed to handle larger instances of the problem with machine breakdowns. The results of extensive computational experiments indicate that the proposed algorithms are quite promising in performance. © 2011 Wiley Periodicals, Inc. Naval Research Logistics, 2011     

A spatial rank‐based multivariate EWMA control chart

Nonparametric control charts are useful in statistical process control when there is a lack of or limited knowledge about the underlying process distribution, especially when the process measurement is multivariate. This article develops a new multivariate self‐starting methodology for monitoring location parameters. It is based on adapting the multivariate spatial rank to on‐line sequential monitoring. The weighted version of the rank‐based test is used to formulate the charting statistic by incorporating the exponentially weighted moving average control scheme. It is robust to non‐normally distributed data, easy to construct, fast to compute and also very efficient in detecting multivariate process shifts, especially small or moderate shifts which occur when the process distribution is heavy‐tailed or skewed. As it avoids the need for a lengthy data‐gathering step before charting and it does not require knowledge of the underlying distribution, the proposed control chart is particularly useful in start‐up or short‐run situations. A real‐data example from white wine production processes shows that it performs quite well. © 2012 Wiley Periodicals, Inc. Naval Research Logistics 59: 91–110, 2012     

Optimal pricing for a short life‐cycle product when customer price‐sensitivity varies over time

Technology products often experience a life‐cycle demand pattern that resembles a diffusion process, with weak demand in the beginning and the end of the life cycle and high demand intensity in between. The customer price‐sensitivity also changes over the life cycle of the product. We study the prespecified pricing decision for a product that exhibits such demand characteristics. In particular, we determine the optimal set of discrete prices and the times to switch from one price to another, when a limited number of price changes are allowed. Our study shows that the optimal prices and switching times show interesting patterns that depend on the product's demand pattern and the change in the customers' price sensitivity over the life cycle of the product. © 2012 Wiley Periodicals, Inc. Naval Research Logistics, 2012     

Are non‐lethal weapons a viable military option to strengthen the hearts and minds approach in Afghanistan?

Commanders of the International Security Assistance Force (ISAF) have repeatedly stressed the hearts and minds approach in Afghanistan, in saying that the human terrain is decisive for a successful outcome of the mission. Avoidance of civilian casualties is considered of strategic importance, and by nature highly dependent on the management of tactical level Escalation of Force (EoF) situations. Non‐lethal weapons (NLWs) are expected to enable tactical commanders to avoid innocent civilian casualties in such situations. This article considers a selected NLW on its potential to accomplish this requirement. It uses a defence technology assessment approach to analyse EoF situations experienced by Dutch ISAF forces in which the NLW is inserted. The analysis demonstrates that a range of contextual factors in the Afghanistan high‐risk environment tend to narrow down the window of opportunity for the NLW to help defuse the risk of unintended civil casualties.     

Approximation results for min‐max path cover problems in vehicle routing

This article studies a min‐max path cover problem, which is to determine a set of paths for k capacitated vehicles to service all the customers in a given weighted graph so that the largest path cost is minimized. The problem has wide applications in vehicle routing, especially when the minimization of the latest service completion time is a critical performance measure. We have analyzed four typical variants of this problem, where the vehicles have either unlimited or limited capacities, and they start from either a given depot or any depot of a given depot set. We have developed approximation algorithms for these four variants, which achieve approximation ratios of max{3 ‐ 2/k,2}, 5, max{5 ‐ 2/k,4}, and 7, respectively. We have also analyzed the approximation hardness of these variants by showing that, unless P = NP , it is impossible for them to achieve approximation ratios less than 4/3, 3/2, 3/2, and 2, respectively. We have further extended the techniques and results developed for this problem to other min‐max vehicle routing problems.© 2010 Wiley Periodicals, Inc. Naval Research Logistics, 2010     

Dynamic capacity reservation and due date quoting in a make‐to‐order system

We consider a make‐to‐order manufacturer facing random demand from two classes of customers. We develop an integrated model for reserving capacity in anticipation of future order arrivals from high priority customers and setting due dates for incoming orders. Our research exhibits two distinct features: (1) we explicitly model the manufacturer's uncertainty about the customers' due date preferences for future orders; and (2) we utilize a service level measure for reserving capacity rather than estimating short and long term implications of due date quoting with a penalty cost function. We identify an interesting effect (“t‐pooling”) that arises when the (partial) knowledge of customer due date preferences is utilized in making capacity reservation and order allocation decisions. We characterize the relationship between the customer due date preferences and the required reservation quantities and show that not considering the t‐pooling effect (as done in traditional capacity and inventory rationing literature) leads to excessive capacity reservations. Numerical analyses are conducted to investigate the behavior and performance of our capacity reservation and due date quoting approach in a dynamic setting with multiple planning horizons and roll‐overs. One interesting and seemingly counterintuitive finding of our analyses is that under certain conditions reserving capacity for high priority customers not only improves high priority fulfillment, but also increases the overall system fill rate. © 2008 Wiley Periodicals, Inc. Naval Research Logistics, 2008     

A generic model of motor‐carrier fuel optimization

Fuel optimizers are decision models (software products) that are increasingly recognized as effective fuel management tools by U.S. truckload carriers. Using the latest price data of every truck stop, these models calculate the optimal fueling schedule for each route that indicates: (i) which truck stop(s) to use, and (ii) how much fuel to buy at the chosen truck stop(s) to minimize the refueling cost. In the current form, however, these models minimize only the fuel cost, and ignore or underestimate other costs that are affected by the models' decision variables. On the basis of the interviews with carrier managers, truck drivers, and fuel‐optimizer vendors, this article proposes a comprehensive model of motor‐carrier fuel optimization that considers all of the costs that are affected by the model's decision variables. Simulation results imply that the proposed model not only attains lower vehicle operating costs than the commercial fuel optimizers, but also gives solutions that are more desirable from the drivers' viewpoint. © 2008 Wiley Periodicals, Inc. Naval Research Logistics, 2008