Optimal capacity in a coordinated supply chain

We consider a supply chain in which a retailer faces a stochastic demand, incurs backorder and inventory holding costs and uses a periodic review system to place orders from a manufacturer. The manufacturer must fill the entire order. The manufacturer incurs costs of overtime and undertime if the order deviates from the planned production capacity. We determine the optimal capacity for the manufacturer in case there is no coordination with the retailer as well as in case there is full coordination with the retailer. When there is no coordination the optimal capacity for the manufacturer is found by solving a newsvendor problem. When there is coordination, we present a dynamic programming formulation and establish that the optimal ordering policy for the retailer is characterized by two parameters. The optimal coordinated capacity for the manufacturer can then be obtained by solving a nonlinear programming problem. We present an efficient exact algorithm and a heuristic algorithm for computing the manufacturer's capacity. We discuss the impact of coordination on the supply chain cost as well as on the manufacturer's capacity. We also identify the situations in which coordination is most beneficial. © 2008 Wiley Periodicals, Inc. Naval Research Logistics, 2008     

Discrete stochastic optimization using variants of the stochastic ruler method

We present two random search methods for solving discrete stochastic optimization problems. Both of these methods are variants of the stochastic ruler algorithm. They differ from our earlier modification of the stochastic ruler algorithm in that they use different approaches for estimating the optimal solution. Our new methods are guaranteed to converge almost surely to the set of global optimal solutions under mild conditions. We discuss under what conditions these new methods are expected to converge faster than the modified stochastic ruler algorithm. We also discuss how these methods can be used for solving discrete optimization problems when the values of the objective function are estimated using either transient or steady‐state simulation. Finally, we present numerical results that compare the performance of our new methods with that of the modified stochastic ruler algorithm when applied to solve buffer allocation problems. © 2005 Wiley Periodicals, Inc. Naval Research Logistics, 2005.     

Minimizing mean absolute deviation of completion times about a common due date

We consider a single machine scheduling problem in which the objective is to minimize the mean absolute deviation of job completion times about a common due date. We present an algorithm for determining multiple optimal schedules under restrictive assumptions about the due date, and an implicit enumeration procedure when the assumptions do not hold. We also establish the similarity of this problem to the two parallel machines mean flow time problem.     

Revenue maximization in two-station tandem queueing systems

We study optimal pricing for tandem queueing systems with finite buffers. The service provider dynamically quotes prices to incoming price sensitive customers to maximize the long-run average revenue. We present a Markov decision process model for the optimization problem. For systems with two stations, general-sized buffers, and two or more prices, we describe the structure of the optimal dynamic pricing policy and develop tailored policy iteration algorithms to find an optimal pricing policy. For systems with two stations but no intermediate buffer, we characterize conditions under which quoting either a high or a low price to all customers is optimal and provide an easy-to-implement algorithm to solve the problem. Numerical experiments are conducted to compare the developed algorithms with the regular policy iteration algorithm. The work also discusses possible extensions of the obtained results to both three-station systems and two-station systems with price and congestion sensitive customers using numerical analysis.     

Minimizing the false alarm rate in systems with transient abnormality

We consider a stochastic partially observable system that can switch between a normal state and a transient abnormal state before entering a persistent abnormal state. Only the persistent abnormal state requires alarms. The transient and persistent abnormal states may be similar in appearance, which can result in excess false alarms. We propose a partially observable Markov decision process model to minimize the false alarm rate, subject to a given upper bound on the expected alarm delay time. The cost parameter is treated as the Lagrange multiplier, which can be estimated from the bound of the alarm delay. We show that the optimal policy has a control‐limit structure on the probability of persistent abnormality, and derive closed‐form bounds for the control limit and present an algorithm to specify the Lagrange multiplier. We also study a specialized model where the transient and persistent abnormal states have the same observation distribution, in which case an intuitive “watchful‐waiting” policy is optimal. © 2016 Wiley Periodicals, Inc. Naval Research Logistics 63: 320–334, 2016     

Dynamic inventory management with cash flow constraints

In this article, we consider a classic dynamic inventory control problem of a self‐financing retailer who periodically replenishes its stock from a supplier and sells it to the market. The replenishment decisions of the retailer are constrained by cash flow, which is updated periodically following purchasing and sales in each period. Excess demand in each period is lost when insufficient inventory is in stock. The retailer's objective is to maximize its expected terminal wealth at the end of the planning horizon. We characterize the optimal inventory control policy and present a simple algorithm for computing the optimal policies for each period. Conditions are identified under which the optimal control policies are identical across periods. We also present comparative statics results on the optimal control policy. © 2008 Wiley Periodicals, Inc. Naval Research Logistics 2008     

A bounded dual (all-integer) integer programming algorithm with an objective cut

In this article, we describe a new algorithm for solving all-integer, integer programming problems. We generate upper bounds on the decision variables, and use these bounds to create an advanced starting point for a dual all-integer cutting plane algorithm. In addition, we use a constraint derived from the objective function to speed progress toward the optimal solution. Our basic vehicle is the dual all-integer algorithm of Gomory, but we incorporate certain row- and column-selection criteria which partially avoid the problem of dual-degenerate iterations. We present the results of computational testing.     

A branch-and-bound algorithm to minimize total flow time with unequal release dates

This article examines the single-machine scheduling problem to minimize total flow time with unequal release dates. This problem has been proven to be NP-hard. We present a necessary and sufficient condition for local optimality which can also be considered as a priority rule. On the basis of this condition, we then define a class of schedules which contains all optimal solutions. We present some efficient heuristic algorithms using the previous condition to build a schedule belonging to this subset. We also prove some new dominance theorems, discuss the results found in the literature for this problem, and propose a branch-and-bound algorithm in which the heuristics are used to provide good upper bounds. We compare this new algorithm with existing algorithms found in the literature. Computational results on problems with up to 100 jobs indicate that the proposed branch-and-bound algorithm is superior to previously published algorithms. © 1992 John Wiley & Sons. Inc.     

An assumption-free convergence analysis for a perturbation of the scaling algorithm for linear programs,with application to the L1 estimation problem

This article is concerned with the scaling variant of Karmarkar's algorithm for linear programming problems. Several researchers have presented convergence analyses for this algorithm under various nondegeneracy types of assumptions, or under assumptions regarding the nature of the sequence of iterates generated by the algorithm. By employing a slight perturbation of the algorithm, which is computationally imperceptible, we are able to prove without using any special assumptions that the algorithm converges finitely to an ε-optimal solution for any chosen ε > 0, from which it can be (polynomically) rounded to an optimum, for ε > 0 small enough. The logarithmic barrier function is used as a construct for this analysis. A rounding scheme which produces an optimal extreme point solution is also suggested. Besides the non-negatively constrained case, we also present a convergence analysis for the case of bounded variables. An application in statistics to the L₁ estimation problem and related computational results are presented.     

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     

整数线性规划问题的一个新算法

本文给出求解整数线性规划问题的一个算法。基本思想是通过求出其伴随线性规划问题的最优单纯形表,把整数线性规划化成正整数系数的不定方程,然后从不定方程的非负整数解集中选取一组满足整数线性规划的约束条件的解,作为整数线性规划的最优解。     

Exact analysis of (R,s, S) inventory control systems with lost sales and zero lead time

We study an (R, s, S) inventory control policy with stochastic demand, lost sales, zero lead‐time and a target service level to be satisfied. The system is modeled as a discrete time Markov chain for which we present a novel approach to derive exact closed‐form solutions for the limiting distribution of the on‐hand inventory level at the end of a review period, given the reorder level (s) and order‐up‐to level (S). We then establish a relationship between the limiting distributions for adjacent values of the reorder point that is used in an efficient recursive algorithm to determine the optimal parameter values of the (R, s, S) replenishment policy. The algorithm is easy to implement and entails less effort than solving the steady‐state equations for the corresponding Markov model. Point‐of‐use hospital inventory systems share the essential characteristics of the inventory system we model, and a case study using real data from such a system shows that with our approach, optimal policies with significant savings in inventory management effort are easily obtained for a large family of items.     

An interactive optimization system for bulk-cargo ship scheduling

This article considers the efficient scheduling of a fleet of ships engaged in pickup and delivery of bulk cargoes. Our optimization system begins by generating a menu of candidate schedules for each ship. This menu can contain all feasible solutions, which guarantees we will find an optimal solution or can be heuristically limited to contain only those schedules likely to be in an optimal solution. The problem of choosing from this menu an optimal schedule for the fleet is formulated as a set-packing problem and solved with a dual algorithm. Computational experience is presented based on real data obtained from the Military Sealift Command of the U. S. Navy. Run times for this data were reasonable and solutions were generated with the potential of saving up to about $30 million per year over the manual system currently in place. We also describe a color-graphics interface developed to facilitate interaction with the optimization system.     

The transportation paradox

A paradox arises when a transportation problem admits to a total cost solution which is lower than the optimum and is attainable by shipping larger quantities of goods over the same routes that were previously designated as optimal. That is, falling total costs are present in moving to the greater shipment quantities. Necessary conditions for this to occur are established and an algorithm for solving this expanded transportation problem is supplied.     

A finite algorithm for concave minimization over a polyhedron

We present a new algorithm for solving the problem of minimizing a nonseparable concave function over a polyhedron. The algorithm is of the branch-and-bound type. It finds a globally optimal extreme point solution for this problem in a finite number of steps. One of the major advantages of the algorithm is that the linear programming subproblems solved during the branch-and-bound search each have the same feasible region. We discuss this and other advantages and disadvantages of the algorithm. We also discuss some preliminary computational experience we have had with our computer code for implementing the algorithm. This computational experience involved solving several bilinear programming problems with the code.     

An analysis of single item inventory systems with returns

Inventory systems with returns are systems in which there are units returned in a repairable state, as well as demands for units in a serviceable state, where the return and demand processes are independent. We begin by examining the control of a single item at a single location in which the stationary return rate is less than the stationary demand rate. This necessitates an occasional procurement of units from an outside source. We present a cost model of this system, which we assume is managed under a continuous review procurement policy, and develop a solution method for finding the policy parameter values. The key to the analysis is the use of a normally distributed random variable to approximate the steady-state distribution of net inventory. Next, we study a single item, two echelon system in which a warehouse (the upper echelon) supports N(N ? 1) retailers (the lower echelon). In this case, customers return units in a repairable state as well as demand units in a serviceable state at the retailer level only. We assume the constant system return rate is less than the constant system demand rate so that a procurement is required at certain times from an outside supplier. We develop a cost model of this two echelon system assuming that each location follows a continuous review procurement policy. We also present an algorithm for finding the policy parameter values at each location that is based on the method used to solve the single location problem.     

A single-machine replacement model with learning

The replacement or upgrade of productive resources over time is an important decision for a manufacturing organization. The type of technology used in the productive resources determines how effectively the manufacturing operations can support the product and marketing strategy of the organization. Increasing operating costs (cost of maintenance, labor, and depreciation) over time force manufacturing organizations to periodically consider replacement or upgrade of their existing productive resources. We assume that there is a setup cost associated with the replacement of a machine, and that the setup cost is a nonincreasing function of the number of replacements made so far due to learning in setups. The operating cost of a newer machine is assumed to be lower than the operating cost of an older machine in any given period, except perhaps in the first period of operation of the new machine when the cost could be unusually high due to higher initial depreciation. A forward dynamic programming algorithm is developed which can be used to solve finite-horizon problems. We develop procedures to find decision and forecast horizons such that choices made during the decision horizon based only on information over the forecast horizon are also optimal for any longer horizon problem. Thus, we are able to obtain optimal results for what is effectively an infinite-horizon problem while only requiring data over a finite period of time. We present a numerical example to illustrate the decision/forecast horizon procedure, as well as a study of the effects of considering learning in making a series of machine replacement decisions. © 1993 John Wiley & Sons. Inc.     

Multiproduct dynamic lot-sizing model with coordinated replenishments

In this article we consider a multiproduct dynamic lot-sizing model. In addition to a separate setup cost for each product ordered, a joint setup cost is incurred when at least one product is ordered. We formulate the model as a concave minimization problem over a compact polyhedral set and present a finite branch and bound algorithm for finding an optimal ordering schedule. Superiority of the branch and bound algorithm to the existing exact procedures is demonstrated. We report computational experience with problems whose dimensions render the existing procedures computationally infeasible.     

Sensor placement in active multistatic sonar networks

The idea of deploying noncollocated sources and receivers in multistatic sonar networks (MSNs) has emerged as a promising area of opportunity in sonar systems. This article is one of the first to address point coverage problems in MSNs, where a number of points of interest have to be monitored in order to protect them from hostile underwater assets. We consider discrete “definite range” sensors as well as various diffuse sensor models. We make several new contributions. By showing that the convex hull spanned by the targets is guaranteed to contain optimal sensor positions, we are able to limit the solution space. Under a definite range sensor model, we are able to exclude even more suboptimal solutions. We then formulate a nonlinear program and an integer nonlinear program to express the sensor placement problem. To address the nonconvex single‐source placement problem, we develop the Divide Best Sector (DiBS) algorithm, which quickly provides an optimal source position assuming fixed receivers. Starting with a basic implementation of DiBS, we show how incorporating advanced sector splitting methods and termination conditions further improve the algorithm. We also discuss two ways to use DiBS to find multiple source positions by placing sensors iteratively or simultaneously. © 2017 Wiley Periodicals, Inc. Naval Research Logistics 64: 287–304, 2017     

Aggregating courier deliveries

We consider the problem of efficiently scheduling deliveries by an uncapacitated courier from a central location under online arrivals. We consider both adversary‐controlled and Poisson arrival processes. In the adversarial setting we provide a randomized (3βΔ/2δ ? 1) ‐competitive algorithm, where β is the approximation ratio of the traveling salesman problem, δ is the minimum distance between the central location and any customer, and Δ is the length of the optimal traveling salesman tour overall customer locations and the central location. We provide instances showing that this analysis is tight. We also prove a 1 + 0.271Δ/δ lower‐bound on the competitive ratio of any algorithm in this setting. In the Poisson setting, we relax our assumption of deterministic travel times by assuming that travel times are distributed with a mean equal to the excursion length. We prove that optimal policies in this setting follow a threshold structure and describe this structure. For the half‐line metric space we bound the performance of the randomized algorithm in the Poisson setting, and show through numerical experiments that the performance of the algorithm is often much better than this bound.