Group testing procedures with quantitative features and incomplete identification

We present a group testing model for items characterized by marker random variables. An item is defined to be good (defective) if its marker is below (above) a given threshold. The items can be tested in groups; the goal is to obtain a prespecified number of good items by testing them in optimally sized groups. Besides this group size, the controller has to select a threshold value for the group marker sums, and the target number of groups which by the tests are classified to consist only of good items. These decision variables have to be chosen so as to minimize a cost function, which is a linear combination of the expected number of group tests and an expected penalty for missing the desired number of good items, subject to constraints on the probabilities of misclassifications. We treat two models of this kind: the first one is based on an infinite population size, whereas the second one deals with the case of a finite number of available items. All performance measures are derived in closed form; approximations are also given. Furthermore, we prove monotonicity properties of the components of the objective function and of the constraints. In several examples, we study (i) the dependence of the cost function on the decision variables and (ii) the dependence of the optimal values of the decision variables (group size, group marker threshold, and stopping rule for groups classified as clean) and of the target functionals (optimal expected number of tests, optimal expected penalty, and minimal expected cost) on the system parameters.© 2011 Wiley Periodicals, Inc. Naval Research Logistics, 2011     

Warehouse sizing to minimize inventory and storage costs

This paper considers a warehouse sizing problem whose objective is to minimize the total cost of ordering, holding, and warehousing of inventory. Unlike typical economic lot sizing models, the warehousing cost structure examined here is not the simple unit rate type, but rather a more realistic step function of the warehouse space to be acquired. In the cases when only one type of stock‐keeping unit (SKU) is warehoused, or when multiple SKUs are warehoused, but, with separable inventory costs, closed form solutions are obtained for the optimal warehouse size. For the case of multi‐SKUs with joint inventory replenishment cost, a heuristic with a provable performance bound of 94% is provided. © 2001 John Wiley & Sons, Inc. Naval Research Logistics 48: 299–312, 2001     

Yield randomness,cost tradeoffs,and diversification in the EOQ model

Existing production/inventory models with random (variable) yield take the yield distribution as given. This work takes a step towards selecting the optimal yield randomness, jointly with lot sizing decisions. First, we analyze an EOQ model where yield variance and lot size are to be selected simultaneously. Two different cost structures are considered. Secondly, we consider source diversification (‘second sourcing’) as a means of reducing effective yield randomness, and trade its benefits against its costs. Conditions for the superiority of diversification between two sources with distinct yield distributions over a single source are derived. The optimal number of identical sources is also analyzed. Some comments on the congruence of the results with recent JIT practices are provided.     

Optimal replacement under additive damage and other failure models

A machine or production system is subject to random failure. Upon failure the system is replaced by a new one, and the process repeats. A cost is associated with each replacement, and an additional cost is incurred at each failure in service. Thus, there is an incentive for a controller to attempt to replace before failure occurs. The problem is to find an optimal control strategy that balances the cost of replacement with the cost of failure and results in a minimum total long-run average cost per unit time. We attack this problem under the cumulative damage model for system failure. In this failure model, shocks occur to the system in accordance with a Poisson process. Each shock causes a random amount of damage or wear and these damages accumulate additively. At any given shock, the system fails with a known probability that depends on the total damage accumulated to date. We assume that the cumulative damage is observable by the controller and that his decisions may be based on its current value. Supposing that the shock failure probability is an increasing function of the cumulative damage, we show that an optimal policy is to replace either upon failure or when this damage first exceeds a critical control level, and we give an equation which implicitly defines the optimal control level in terms of the cost and other system parameters. Also treated are some more general models that allow for income lost during repair time and other extensions.     

Selection of the optimal setup policy

A model is developed taking into consideration all the costs (namely cost of sampling, cost of not detecting a change in the process, cost of a false indication of change, and the cost of readjusting detected changes) incurred when a production process, using an unscheduled setup policy, utilizes fraction-defective control charts to control current production. The model is based on the concept of the expected time between detection of changes calling for setups. It is shown that the combination of unscheduled setups and control charts can be utilized in an optimal way if those combinations of sample size, sampling interval, and extent of control limits from process average are used that provide the minimum expected total cost per unit of time. The costs of a production process that uses unscheduled setups in conjunction with the appropriate optimal control charts are compared to the costs of a production process that uses scheduled setups at optimum intervals in conjunction with its appropriate control charts. This comparison indicates the criteria for selecting production processes with scheduled setups using optimal setup intervals over unscheduled setups. Suggestions are made to evaluate the optimal process setup strategy and the accompanying optimal decision parameters, for any specific cost data, by use of computer enumeration. A numerical example for assumed cost and process data is provided.     

Optimal machine capacity expansions with nested limitations under stochastic demand

This paper studies capacity expansions for a production facility that faces uncertain customer demand for a single product family. The capacity of the facility is modeled in three tiers, as follows. The first tier consists of a set of upper bounds on production that correspond to different resource types (e.g., machine types, categories of manpower, etc.). These upper bounds are augmented in increments of fixed size (e.g., by purchasing machines of standard types). There is a second‐tier resource that constrains the first‐tier bounds (e.g., clean room floor space). The third‐tier resource bounds the availability of the second‐tier resource (e.g., the total floor space enclosed by the building, land, etc.). The second and third‐tier resources are expanded at various times in various amounts. The cost of capacity expansion at each tier has both fixed and proportional elements. The lost sales cost is used as a measure for the level of customer service. The paper presents a polynomial time algorithm (FIFEX) to minimize the total cost by computing optimal expansion times and amounts for all three types of capacity jointly. It accommodates positive lead times for each type. Demand is assumed to be nondecreasing in a “weak” sense. © 2003 Wiley Periodicals, Inc. Naval Research Logistics, 2004.     

A probabilistic analysis of a fixed partition policy for the inventory‐routing problem

We consider the Inventory‐Routing Problem (IRP) where n geographically dispersed retailers must be supplied by a central facility. The retailers experience demand for the product at a deterministic rate, and incur holding costs for keeping inventory. Distribution is performed by a fleet of capacitated vehicles. The objective is to minimize the average transportation and inventory costs per unit time over the infinite horizon. We focus on the set of Fixed Partition Policies (FPP). In an FPP, the retailers are partitioned into disjoint and collectively exhaustive sets. Each set of retailers is served independently of the others and at its optimal replenishment rate. Previous research has measured the effectiveness of an FPP solution relative to a lower bound over all policies. We propose an additional measure that is relative to the optimal FPP. In this paper we construct a polynomial‐time partitioning scheme that is shown to yield an FPP whose cost is asymptotically within 1.5% + ? of the cost of an optimal FPP, for arbitrary ? > 0. In addition, in some cases, our polynomial‐time scheme yields an FPP whose cost is asymptotically within 1.5% + ? of the minimal policy's cost (over all feasible policies). © 2004 Wiley Periodicals, Inc. Naval Research Logistics, 2004     

Inventory policies with quantized ordering

This article studies (nQ, r) inventory policies, under which the order quantity is restricted to be an integer multiple of a base lot size Q. Both Q and r are decision variables. Assuming the one-period expected holding and backorder cost function is unimodal, we develop an efficient algorithm to compute the optimal Q and r. The algorithm is facilitated by simple observations about the cost function and by tight upper bounds on the optimal Q. The total number of elementary operations required by the algorithm is linear in these upper bounds. By using the algorithm, we compare the performance of the optimal (nQ, r) policy with that of the optimal (s, S) policy through a numerical study, and our results show that the difference between them is small. Further analysis of the model shows that the cost performance of an (nQ, r) policy is insensitive to the choice of Q. These results establish that (nQ, r) models are potentially useful in many settings where quantized ordering is beneficial.     

Fluctuations of the optimal advertising and inventory policy: A qualitative analysis

This paper discusses the properties of the inventory and advertising policy minimizing the expected discounted cost over a finite horizon in a dynamic nonstationary inventory model with random demand which is influenced by the level of promotion or goodwill. Attention is focused on the relation between the fluctuations over time of the optimal policies and the variations over time of the factors involved, i.e., demand distributions and various costs. The optimal policies are proved to be monotone in the various factors. Also, three types of fluctuations over time of the optimal policies are discussed according to which factor varies over time. For example, if over a finite interval, the random demand increases (stochastically) from one period to the next, reaches a maximum and then decreases, then the optimal inventory level will do the same. Also the period of maximum of demand never precedes that of maximum inventory. The optimal advertising behaves in the opposite way and its minimum will occur at the same time as the maximum of the inventory. The model has a linear inventory ordering cost and instantaneous delivery of stocks; many results, however, are extended to models with a convex ordering cost or a delivery time lag.     

Outsourcing warranty repairs: Dynamic allocation

In this paper we consider the problem of minimizing the costs of outsourcing warranty repairs when failed items are dynamically routed to one of several service vendors. In our model, the manufacturer incurs a repair cost each time an item needs repair and also incurs a goodwill cost while an item is awaiting and undergoing repair. For a large manufacturer with annual warranty costs in the tens of millions of dollars, even a small relative cost reduction from the use of dynamic (rather than static) allocation may be practically significant. However, due to the size of the state space, the resulting dynamic programming problem is not exactly solvable in practice. Furthermore, standard routing heuristics, such as join‐the‐shortest‐queue, are simply not good enough to identify potential cost savings of any significance. We use two different approaches to develop effective, simply structured index policies for the dynamic allocation problem. The first uses dynamic programming policy improvement while the second deploys Whittle's proposal for restless bandits. The closed form indices concerned are new and the policies sufficiently close to optimal to provide cost savings over static allocation. All results of this paper are demonstrated using a simulation study. © 2005 Wiley Periodicals, Inc. Naval Research Logistics, 2005     

Dynamic pricing and replenishment: Optimality,bounds, and asymptotics

In many applications, managers face the problem of replenishing and selling products during a finite time horizon. We investigate the problem of making dynamic and joint decisions on product replenishment and selling in order to improve profit. We consider a backlog scenario in which penalty cost (resulting from fulfillment delay) and accommodation cost (resulting from shortage at the end of the selling horizon) are incurred. Based on continuous‐time and discrete‐state dynamic programming, we study the optimal joint decisions and characterize their structural properties. We establish an upper bound for the optimal expected profit and develop a fluid policy by resorting to the deterministic version of the problem (ie, the fluid problem). The fluid policy is shown to be asymptotically optimal for the original stochastic problem when the problem size is sufficiently large. The static nature of the fluid policy and its lack of flexibility in matching supply with demand motivate us to develop a “target‐inventory” heuristic, which is shown, numerically, to be a significant improvement over the fluid policy. Scenarios with discrete feasible sets and lost‐sales are also discussed in this article.     

The fixed charge problem

The fixed charge problem is a nonlinear programming problem of practical interest in business and industry. Yet, until now no computationally feasible exact method of solution for large problems had been developed. In this paper an exact algorithm is presented which is computationally feasible for large problems. The algorithm is based upon a branch and bound approach, with the additional feature that the amount of computer storage required remains constant throughout (for a problem of any given size). Also presented are three suboptimal heuristic algorithms which are of interest because, although they do not guarantee that the true optimal solution will be found, they usually yield very good solutions and are extremely rapid techniques. Computational results are described for several of the heuristic methods and for the branch and bound algorithm.     

基于灰色决策原理的导弹核武器最佳配置模型

核武器是国家军事战略的基石,其配置的合理性直接影响核力量作战运用的成效.分析了影响导弹核武器配置的因素,将导弹核武器划分为平时和战时两种状态,构建了导弹核武器最佳配置的灰色规划模型计算结果验证了模型的正确性.研究表明:基于灰色规划原理构建的最佳配置模型在解的稳定性、模型的适应性上要优于同类线性规划模型.核武器最佳配置问题一直是核作战运用研究的重要内容.研究成果可为导弹武器的订购、存贮、阵地配置及作战运用提供理论决策依据.     

Deterministic inventory lot‐size models under inflation with shortages and deterioration for fluctuating demand

In this paper, we extend the inventory lot‐size models to allow for inflation and fluctuating demand (which is more general than constant, increasing, decreasing, and log‐concave demand patterns). We prove that the optimal replenishment schedule not only exists but is also unique. Furthermore, we show that the total cost associated with the inventory system is a convex function of the number of replenishments. Hence, the search for the optimal number of replenishments is simplified to finding a local minimum. Finally, several numerical examples are provided to illustrate the results. © 2001 John Wiley & Sons, Inc. Naval Research Logistics 48: 144–158, 2001     

A comparative study of three tool replacement/operation sequencing strategies in a flexible manufacturing system

This paper studies three tool replacement/operation sequencing strategies for a flexible manufacturing system over a finite time horizon: (1) failure replacement—replace the tool only upon failure, (2) optimal preventive tool replacement for a fixed sequence of operations, and (3) joint scheduling of the optimal preventive tool replacement times and the optimal sequence of operations. Stochastic dynamic decision models are used for strategies 2 and 3. The optimization criterion for strategies 2 and 3 is the minimization of the total expected cost over the finite time horizon. We will show through numerical studies that, with the same amount of information, the total expected costs can be reduced considerably by choosing an optimal strategy. Our conclusion is that in flexible manufacturing, optimal tool replacement and optimal operations sequencing are not separate issues. They should be considered jointly to minimize the expected total cost. © 2000 John Wiley & Sons, Inc. Naval Research Logistics 47: 479–499, 2000     

Probabilistic solution and bounds for serial inventory systems with discounted and average costs

We consider the infinite horizon serial inventory system with both average cost and discounted cost criteria. The optimal echelon base‐stock levels are obtained in terms of only probability distributions of leadtime demands. This analysis yields a novel approach for developing bounds and heuristics for optimal inventory control polices. In addition to deriving the known bounds in literature, we develop several new upper bounds for both average cost and discounted cost models. Numerical studies show that the bounds and heuristic are very close to optimal.© 2007 Wiley Periodicals, Inc. Naval Research Logistics, 2007     

Jointly constrained order quantities with all-units discounts

In this article we investigate situations where the buyer is offered discounted price schedules from alternative vendors. Given various discount schedules, the buyer must make the best buying decision under a variety of constraints, such as limited storage space and restricted inventory budgets. Solutions to this problem can be utilized by the buyer to improve profitability. EOQ models for multiple products with all-units discounts are readily solvable in the absence of constraints spanning the products. However, constrained discounted EOQ models lack convenient mathematical properties. Relaxing the product-spanning constraints produces a dual problem that is separable, but lack of convexity and smoothness opens the door for duality gaps. In this research we present a set of algorithms that collectively find the optimal order vector. Finally, we present numerical examples using actual data. to illustrate the application of the algorithms. © 1993 John Wiley & Sons, Inc.     

Technical note: A computationally efficient algorithm for undiscounted Markov decision processes with restricted observations

We present a computationally efficient procedure to determine control policies for an infinite horizon Markov Decision process with restricted observations. The optimal policy for the system with restricted observations is a function of the observation process and not the unobservable states of the system. Thus, the policy is stationary with respect to the partitioned state space. The algorithm we propose addresses the undiscounted average cost case. The algorithm combines a local search with a modified version of Howard's (Dynamic programming and Markov processes, MIT Press, Cambridge, MA, 1960) policy iteration method. We demonstrate empirically that the algorithm finds the optimal deterministic policy for over 96% of the problem instances generated. For large scale problem instances, we demonstrate that the average cost associated with the local optimal policy is lower than the average cost associated with an integer rounded policy produced by the algorithm of Serin and Kulkarni Math Methods Oper Res 61 (2005) 311–328. © 2008 Wiley Periodicals, Inc. Naval Research Logistics 2009     

Natural gas storage valuation and optimization: A real options application

In this article, we present an algorithm for the valuation and optimal operation of natural gas storage facilities. Real options theory is used to derive nonlinear partial‐integro‐differential equations (PIDEs), the solution of which give both valuation and optimal operating strategies for these facilities. The equations are designed to incorporate a wide class of spot price models that can exhibit the same time‐dependent, mean‐reverting dynamics, and price spikes as those observed in most energy markets. Particular attention is paid to the operational characteristics of real storage units. These characteristics include working gas capacities, variable deliverability and injection rates, and cycling limitations. We illustrate the model with a numerical example of a salt cavern storage facility that clearly shows how a gas storage facility is like a financial straddle with both put and call properties. Depending on the amount of gas in storage the relative influence of the put and call components vary. © 2009 Wiley Periodicals, Inc. Naval Research Logistics 2009     

A note on parallel machine replacement

Jones, Zydiak, and Hopp [1] consider the parallel machine replacement problem (PMRP), in which there are both fixed and variable costs associated with replacing machines. Increasing maintenance cost motivates replacements, and a fixed replacement cost provides incentive for replacing machines of the same age in clusters. They prove two intuitive but important results for finite- or infinite-horizon PMRPs, which significantly reduce the size of the linear programming (LP) formulation of the problem and computing efforts required to obtain an optimal replacement policy. Their results are the no-splitting rule (NSR) and the older cluster replacement rule (OCRR). Under a slightly weaker set of assumptions, we prove a third rule, the all-or-none rule (AONR), which states that in any period, an optimal policy is to keep or to replace all the machines regardless of age. This result further reduces the size of the LP formulation of the PMRP. © 1993 John Wiley & Sons, Inc.