Nonperiodic preventive maintenance for repairable systems

As a complex system with multiple components usually deteriorates with age, preventive maintenance (PM) is often performed to keep the system functioning in a good state to prolong its effective age. In this study, a nonhomogeneous Poisson process with a power law failure intensity is used to describe the deterioration of a repairable system, and the optimal nonperiodic PM schedule can be determined to minimize the expected total cost per unit time. However, since the determination of such optimal PM policies may involve numerous uncertainties, which typically make the analyses difficult to perform because of the scarcity of data, a Bayesian decision model, which utilizes all available information effectively, is also proposed for determining the optimal PM strategies. A numerical example with a real failure data set is used to illustrate the effectiveness of the proposed approach. The results show that the optimal schedules derived by Bayesian approach are relatively more conservative than that for non‐Bayesian approach because of the uncertainty of the intensity function, and if the intensity function are updated using the collected data set, which indicates more severe deterioration than the prior belief, replacing the entire system instead of frequent PM activities before serious deterioration is suggested. © 2010 Wiley Periodicals, Inc. Naval Research Logistics, 2010     

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     

A dual criteria sequencing problem with earliness and tardiness penalties

We consider the problem of sequencing n jobs on a single machine, with each job having a processing time and a common due date. The common due date is assumed to be so large that all jobs can complete by the due date. It is known that there is an O(n log n)‐time algorithm for finding a schedule with minimum total earliness and tardiness. In this article, we consider finding a schedule with dual criteria. The primary goal is to minimize the total earliness and tardiness. The secondary goals are to minimize: (1) the maximum earliness and tardiness; (2) the sum of the maximum of the squares of earliness and tardiness; (3) the sum of the squares of earliness and tardiness. For the first two criteria, we show that the problems are NP‐hard and we give a fully polynomial time approximation scheme for both of them. For the last two criteria, we show that the ratio of the worst schedule versus the best schedule is no more than . © 2002 Wiley Periodicals, Inc. Naval Research Logistics 49: 422–431, 2002; Published online in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/nav.10020     

On labeling the vertices of products of complete graphs with distance constraints

Variations of Hale's channel assignment problem, the L(j, k)‐labeling problem and the radio labeling problem require the assignment of integers to the vertices of a graph G subject to various distance constraints. The λ_j,k‐number of G and the radio number of G are respectively the minimum span among all L(j, k)‐labelings, and the minimum span plus 1 of all radio labelings of G (defined in the Introduction). In this paper, we establish the λ_j,k‐number of ∏ K for pairwise relatively prime integers t₁ < t₂ < … < t_q, t₁ ≥ 2. We also show the existence of an infinite class of graphs G with radio number |V(G)| for any diameter d(G). © 2003 Wiley Periodicals, Inc. Naval Research Logistics, 2005     

Dynamic pricing under first order Markovian competition

We evaluate the effect of competition on prices, profits, and consumers' surplus in multiperiod, finite horizon, dynamic pricing settings. In our base model, a single myopic consumer visits two competing retailers, who offer identical goods, in a (first order Markovian) probabilistic fashion—if the posted price exceeds the consumer's valuation for the good, he returns to the same store in the following period with a certain probability. We find that even a small reduction in the return probability from one—which corresponds to the monopoly case at which prices decline linearly—is sufficient to revert the price decline from a linear into an exponential shape. Each retailer's profit is particularly sensitive to changes in his return probability when it is relatively high, and is maximized under complete loyalty behavior (i.e., return probability is one). On the other hand, consumer surplus is maximized under complete switching behavior (i.e., return probability is zero). In the presence of many similar consumers, the insights remain valid. We further focus on the extreme scenario where all consumers follow a complete switching behavior, to derive sharp bounds, and also consider the instance where, in this setting, myopic consumers are replaced with strategic consumers. © 2011 Wiley Periodicals, Inc. Naval Research Logistics, 2011     

Batch scheduling on a two‐machine jobshop with machine‐dependent setup times

The problem of minimum makespan on an m machine jobshop with unit execution time (UET) jobs (m ≥ 3) is known to be strongly NP‐hard even with no setup times. We focus in this article on the two‐machine case. We assume UET jobs and consider batching with batch availability and machine‐dependent setup times. We introduce an efficient \begin{align*}(O(\sqrt{n}))\end{align*} algorithm, where n is the number of jobs. We then introduce a heuristic for the multimachine case and demonstrate its efficiency for two interesting instances. © 2011 Wiley Periodicals, Inc. Naval Research Logistics, 2011     

Constrained minimax optimization of continuous search efforts for the detection of a stationary target

Analytical resolution of search theory problems, as formalized by B.O. Koopman, may be applied with some model extension to various resource management issues. However, a fundamental prerequisite is the knowledge of the prior target density. Though this assumption has the definite advantage of simplicity, its drawback is clearly that target reactivity is not taken into account. As a preliminary step towards reactive target study stands the problem of resource planning under a min–max game context. This paper is related to Nakai's work about the game planning of resources for the detection of a stationary target. However, this initial problem is extended by adding new and more general constraints, allowing a more realistic modeling of the target and searcher behaviors. © 2007 Wiley Periodicals, Inc. Naval Research Logistics, 2007     

Untruthful probabilistic demand forecasts in vendor‐managed revenue‐sharing contracts: Coordinating the chain

Vendor‐managed revenue‐sharing arrangements are common in the newspaper and other industries. Under such arrangements, the supplier decides on the level of inventory while the retailer effectively operates under consignment, sharing the sales revenue with his supplier. We consider the case where the supplier is unable to predict demand, and must base her decisions on the retailer‐supplied probabilistic forecast for demand. We show that the retailer's best choice of a distribution to report to his supplier will not be the true demand distribution, but instead will be a degenerate distribution that surprisingly induces the supplier to provide the system‐optimal inventory quantity. (To maintain credibility, the retailer's reports of daily sales must then be consistent with his supplied forecast.) This result is robust under nonlinear production costs and nonlinear revenue‐sharing. However, if the retailer does not know the supplier's production cost, the forecast “improves” and could even be truthful. That, however, causes the supplier's order quantity to be suboptimal for the overall system. © 2007 Wiley Periodicals, Inc. Naval Research Logistics, 2007     

Production to order and off‐line inspection when the production process is partially observable

This study combines inspection and lot‐sizing decisions. The issue is whether to INSPECT another unit or PRODUCE a new lot. A unit produced is either conforming or defective. Demand need to be satisfied in full, by conforming units only. The production process may switch from a “good” state to a “bad” state, at constant rate. The proportion of conforming units in the good state is higher than in the bad state. The true state is unobservable and can only be inferred from the quality of units inspected. We thus update, after each inspection, the probability that the unit, next candidate for inspection, was produced while the production process was in the good state. That “good‐state‐probability” is the basis for our decision to INSPECT or PRODUCE. We prove that the optimal policy has a simple form: INSPECT only if the good‐state‐probability exceeds a control limit. We provide a methodology to calculate the optimal lot size and the expected costs associated with INSPECT and PRODUCE. Surprisingly, we find that the control limit, as a function of the demand (and other problem parameters) is not necessarily monotone. Also, counter to intuition, it is possible that the optimal action is PRODUCE, after revealing a conforming unit. © 2007 Wiley Periodicals, Inc. Naval Research Logistics, 2007