Robust tower location for code division multiple access networks

Designing Code Division Multiple Access networks includes determining optimal locations of radio towers and assigning customer markets to the towers. In this paper, we describe a deterministic model for tower location and a stochastic model to optimize revenue given a set of constructed towers. We integrate these models in a stochastic integer programming problem with simple recourse that optimizes the location of towers under demand uncertainty. We develop algorithms using Benders' reformulation, and we provide computational results. © 2006 Wiley Periodicals, Inc. Naval Research Logistics, 2007     

A general strategic capacity planning model under demand uncertainty

Capacity planning decisions affect a significant portion of future revenue. In equipment intensive industries, these decisions usually need to be made in the presence of both highly volatile demand and long capacity installation lead times. For a multiple product case, we present a continuous‐time capacity planning model that addresses problems of realistic size and complexity found in current practice. Each product requires specific operations that can be performed by one or more tool groups. We consider a number of capacity allocation policies. We allow tool retirements in addition to purchases because the stochastic demand forecast for each product can be decreasing. We present a cluster‐based heuristic algorithm that can incorporate both variance reduction techniques from the simulation literature and the principles of a generalized maximum flow algorithm from the network optimization literature. © 2005 Wiley Periodicals, Inc. Naval Research Logistics, 2006     

Integrated capacity,demand, and production planning with subcontracting and overtime options

Models for integrated production and demand planning decisions can serve to improve a producer's ability to effectively match demand requirements with production capabilities. In contexts with price‐sensitive demands, economies of scale in production, and multiple capacity options, such integrated planning problems can quickly become complex. To address these complexities, this paper provides profit‐maximizing production planning models for determining optimal demand and internal production capacity levels under price‐sensitive deterministic demands, with subcontracting and overtime options. The models determine a producer's optimal price, production, inventory, subcontracting, overtime, and internal capacity levels, while accounting for production economies of scale and capacity costs through concave cost functions. We use polyhedral properties and dynamic programming techniques to provide polynomial‐time solution approaches for obtaining an optimal solution for this class of problems when the internal capacity level is time‐invariant. © 2007 Wiley Periodicals, Inc. Naval Research Logistics, 2007     

A continuous‐time strategic capacity planning model

Capacity planning decisions affect a significant portion of future revenue. In the semiconductor industry, they need to be made in the presence of both highly volatile demand and long capacity installation lead‐times. In contrast to traditional discrete‐time models, we present a continuous‐time stochastic programming model for multiple resource types and product families. We show how this approach can solve capacity planning problems of reasonable size and complexity with provable efficiency. This is achieved by an application of the divide‐and‐conquer algorithm, convexity, submodularity, and the open‐pit mining problem. © 2005 Wiley Periodicals, Inc. Naval Research Logistics, 2005.     

Robust capacity planning in semiconductor manufacturing

We present a stochastic programming approach to capacity planning under demand uncertainty in semiconductor manufacturing. Given multiple demand scenarios together with associated probabilities, our aim is to identify a set of tools that is a good compromise for all these scenarios. More precisely, we formulate a mixed‐integer program in which expected value of the unmet demand is minimized subject to capacity and budget constraints. This is a difficult two‐stage stochastic mixed‐integer program which cannot be solved to optimality in a reasonable amount of time. We instead propose a heuristic that can produce near‐optimal solutions. Our heuristic strengthens the linear programming relaxation of the formulation with cutting planes and performs limited enumeration. Analyses of the results in some real‐life situations are also presented. © 2005 Wiley Periodicals, Inc. Naval Research Logistics, 2005.     

Capacity investment decisions under risk aversion

This article studies the optimal capacity investment problem for a risk‐averse decision maker. The capacity can be either purchased or salvaged, whereas both involve a fixed cost and a proportional cost/revenue. We incorporate risk preference and use a consumption model to capture the decision maker's risk sensitivity in a multiperiod capacity investment model. We show that, in each period, capacity and consumption decisions can be separately determined. In addition, we characterize the structure of the optimal capacity strategy. When the parameters are stationary, we present certain conditions under which the optimal capacity strategy could be easily characterized by a static two‐sided (s, S) policy, whereby, the capacity is determined only at the beginning of period one, and held constant during the entire planning horizon. It is purchased up to B when the initial capacity is below b, salvaged down to Σ when it is above σ, and remains constant otherwise. Numerical tests are presented to investigate the impact of demand volatility on the optimal capacity strategy. © 2016 Wiley Periodicals, Inc. Naval Research Logistics 63: 218–235, 2016     

Capacity expansion and cost efficiency improvement in the warehouse problem

The warehouse problem with deterministic production cost, selling prices, and demand was introduced in the 1950s and there is a renewed interest recently due to its applications in energy storage and arbitrage. In this paper, we consider two extensions of the warehouse problem and develop efficient computational algorithms for finding their optimal solutions. First, we consider a model where the firm can invest in capacity expansion projects for the warehouse while simultaneously making production and sales decisions in each period. We show that this problem can be solved with a computational complexity that is linear in the product of the length of the planning horizon and the number of capacity expansion projects. We then consider a problem in which the firm can invest to improve production cost efficiency while simultaneously making production and sales decisions in each period. The resulting optimization problem is non‐convex with integer decision variables. We show that, under some mild conditions on the cost data, the problem can be solved in linear computational time. © 2016 Wiley Periodicals, Inc. Naval Research Logistics 63: 367–373, 2016     

Capacity expansion under a service‐level constraint for uncertain demand with lead times

For a service provider facing stochastic demand growth, expansion lead times and economies of scale complicate the expansion timing and sizing decisions. We formulate a model to minimize the infinite horizon expected discounted expansion cost under a service‐level constraint. The service level is defined as the proportion of demand over an expansion cycle that is satisfied by available capacity. For demand that follows a geometric Brownian motion process, we impose a stationary policy under which expansions are triggered by a fixed ratio of demand to the capacity position, i.e., the capacity that will be available when any current expansion project is completed, and each expansion increases capacity by the same proportion. The risk of capacity shortage during a cycle is estimated analytically using the value of an up‐and‐out partial barrier call option. A cutting plane procedure identifies the optimal values of the two expansion policy parameters simultaneously. Numerical instances illustrate that if demand grows slowly with low volatility and the expansion lead times are short, then it is optimal to delay the start of expansion beyond when demand exceeds the capacity position. Delays in initiating expansions are coupled with larger expansion sizes. © 2009 Wiley Periodicals, Inc. Naval Research Logistics, 2009     

Stochastic production capacity: A bane or a boon for quick response supply chains?

The quick response (QR) system that can cope with demand volatility by shortening lead time has been well studied in the literature. Much of the existing literature assumes implicitly or explicitly that the manufacturers under QR can always meet the demand because the production capacity is always sufficient. However, when the order comes with a short lead time under QR, availability of the manufacturer's production capacity is not guaranteed. This motivates us to explore QR in supply chains with stochastic production capacity. Specifically, we study QR in a two-echelon supply chain with Bayesian demand information updating. We consider the situation where the manufacturer's production capacity under QR is uncertain. We first explore how stochastic production capacity affects supply chain decisions and QR implementation. We then incorporate the manufacturer's ability to expand capacity into the model. We explore how the manufacturer determines the optimal capacity expansion decision, and the value of such an ability to the supply chain and its agents. Finally, we extend the model to the two-stage two-ordering case and derive the optimal ordering policy by dynamic programming. We compare the single-ordering and two-ordering cases to generate additional managerial insights about how ordering flexibility affects QR when production capacity is stochastic. We also explore the transparent supply chain and find that our main results still hold.     

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     

Coordinated pricing and inventory control problems with capacity constraints and fixed ordering cost

This article addresses a single‐item, finite‐horizon, periodic‐review coordinated decision model on pricing and inventory control with capacity constraints and fixed ordering cost. Demands in different periods are random and independent of each other, and their distributions depend on the price in the current period. Each period's stochastic demand function is the additive demand model. Pricing and ordering decisions are made at the beginning of each period, and all shortages are backlogged. The objective is to find an optimal policy that maximizes the total expected discounted profit. We show that the profit‐to‐go function is strongly CK‐concave, and the optimal policy has an (s,S,P) ‐like structure. © 2012 Wiley Periodicals, Inc. Naval Research Logistics, 2012     

A single‐period inventory placement problem for a serial supply chain

This article addresses the inventory placement problem in a serial supply chain facing a stochastic demand for a single planning period. All customer demand is served from stage 1, where the product is stored in its final form. If the demand exceeds the supply at stage 1, then stage 1 is resupplied from stocks held at the upstream stages 2 through N, where the product may be stored in finished form or as raw materials or subassemblies. All stocking decisions are made before the demand occurs. The demand is nonnegative and continuous with a known probability distribution, and the purchasing, holding, shipping, processing, and shortage costs are proportional. There are no fixed costs. All unsatisfied demand is lost. The objective is to select the stock quantities that should be placed different stages so as to maximize the expected profit. Under reasonable cost assumptions, this leads to a convex constrained optimization problem. We characterize the properties of the optimal solution and propose an effective algorithm for its computation. For the case of normal demands, the calculations can be done on a spreadsheet. © 2001 John Wiley & Sons, Inc. Naval Research Logistics 48:506–517, 2001     

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     

Economic ordering decisions with market choice flexibility

Standard approaches to classical inventory control problems treat satisfying a predefined demand level as a constraint. In many practical contexts, however, total demand is comprised of separate demands from different markets or customers. It is not always clear that constraining a producer to satisfy all markets is an optimal approach. Since the inventory‐related cost of an item depends on total demand volume, no clear method exists for determining a market's profitability a priori, based simply on per unit revenue and cost. Moreover, capacity constraints often limit a producer's ability to meet all demands. This paper presents models to address economic ordering decisions when a producer can choose whether to satisfy multiple markets. These models result in a set of nonlinear binary integer programming problems that, in the uncapacitated case, lend themselves to efficient solution due to their special structure. The capacitated versions can be cast as nonlinear knapsack problems, for which we propose a heuristic solution approach that is asymptotically optimal in the number of markets. The models generalize the classical EOQ and EPQ problems and lead to interesting optimization problems with intuitively appealing solution properties and interesting implications for inventory and pricing management. © 2003 Wiley Periodicals, Inc. Naval Research Logistics, 2004.     

Newsvendor problems with sequentially revealed demand information

This article analyzes a capacity/inventory planning problem with a one‐time uncertain demand. There is a long procurement leadtime, but as some partial demand information is revealed, the firm is allowed to cancel some of the original capacity reservation at a certain fee or sell off some inventory at a lower price. The problem can be viewed as a generalization of the classic newsvendor problem and can be found in many applications. One key observation of the analysis is that the dynamic programming formulation of the problem is closely related to a recursion that arises in the study of a far more complex system, a series inventory system with stochastic demand over an infinite horizon. Using this equivalence, we characterize the optimal policy and assess the value of the additional demand information. We also extend the analysis to a richer model of information. Here, demand is driven by an underlying Markov process, representing economic conditions, weather, market competition, and other environmental factors. Interestingly, under this more general model, the connection to the series inventory system is different. © 2012 Wiley Periodicals, Inc. Naval Research Logistics 2012     

The (s,Q) inventory model with Erlang lead time and deterministic demand

We develop a simple, approximately optimal solution to a model with Erlang lead time and deterministic demand. The method is robust to misspecification of the lead time and has good accuracy. We compare our approximate solution to the optimal for the case where we have prior information on the lead‐time distribution, and another where we have no information, except for computer‐generated sample data. It turns out that our solution is as easy as the EOQ's, with an accuracy rate of 99.41% when prior information on the lead‐time distribution is available and 97.54–99.09% when only computer‐generated sample information is available. Apart from supplying the inventory practitioner with an easy heuristic, we gain insights into the efficacy of stochastic lead time models and how these could be used to find the cost and a near‐optimal policy for the general model, where both demand rate and lead time are stochastic. © 2004 Wiley Periodicals, Inc. Naval Research Logistics, 2004     

Risk‐sensitive sizing of responsive facilities

We develop a risk‐sensitive strategic facility sizing model that makes use of readily obtainable data and addresses both capacity and responsiveness considerations. We focus on facilities whose original size cannot be adjusted over time and limits the total production equipment they can hold, which is added sequentially during a finite planning horizon. The model is parsimonious by design for compatibility with the nature of available data during early planning stages. We model demand via a univariate random variable with arbitrary forecast profiles for equipment expansion, and assume the supporting equipment additions are continuous and decided ex‐post. Under constant absolute risk aversion, operating profits are the closed‐form solution to a nontrivial linear program, thus characterizing the sizing decision via a single first‐order condition. This solution has several desired features, including the optimal facility size being eventually decreasing in forecast uncertainty and decreasing in risk aversion, as well as being generally robust to demand forecast uncertainty and cost errors. We provide structural results and show that ignoring risk considerations can lead to poor facility sizing decisions that deteriorate with increased forecast uncertainty. Existing models ignore risk considerations and assume the facility size can be adjusted over time, effectively shortening the planning horizon. Our main contribution is in addressing the problem that arises when that assumption is relaxed and, as a result, risk sensitivity and the challenges introduced by longer planning horizons and higher uncertainty must be considered. Finally, we derive accurate spreadsheet‐implementable approximations to the optimal solution, which make this model a practical capacity planning tool.© 2008 Wiley Periodicals, Inc. Naval Research Logistics, 2008     

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     

An integer programming model for the weekly tour scheduling problem

We study a workforce planning and scheduling problem in which weekly tours of agents must be designed. Our motivation for this study comes from a call center application where agents serve customers in response to incoming phone calls. Similar to many other applications in the services industry, the demand for service in call centers varies significantly within a day and among days of the week. In our model, a weekly tour of an agent consists of five daily shifts and two days off, where daily shifts within a tour may be different from each other. The starting times of any two consecutive shifts, however, may not differ by more than a specified bound. Furthermore, a tour must also satisfy constraints regarding the days off, for example, it may be required that one of the days off is on a weekend day. The objective is to determine a collection of weekly tours that satisfy the demand for agents' services, while minimizing the total labor cost of the workforce. We describe an integer programming model where a weekly tour is obtained by combining seven daily shift scheduling models and days‐off constraints in a network flow framework. The model is flexible and can accommodate different daily models with varying levels of detail. It readily handles different days‐off rules and constraints regarding start time differentials in consecutive days. Computational results are also presented. © 2001 John Wiley & Sons, Inc. Naval Research Logistics 48: 607–624, 2001.     

The stochastic single resource service‐provision problem

The service‐provision problem described in this paper comes from an application of distributed processing in telecommunications networks. The objective is to maximize a service provider's profit from offering computational‐based services to customers. The service provider has limited capacity and must choose which of a set of software applications he would like to offer. This can be done dynamically, taking into consideration that demand for the different services is uncertain. The problem is examined in the framework of stochastic integer programming. Approximations and complexity are examined for the case when demand is described by a discrete probability distribution. For the deterministic counterpart, a fully polynomial approximation scheme is known 2 . We show that introduction of stochasticity makes the problem strongly NP‐hard, implying that the existence of such a scheme for the stochastic problem is highly unlikely. For the general case a heuristic with a worst‐case performance ratio that increases in the number of scenarios is presented. Restricting the class of problem instances in a way that many reasonable practical problem instances satisfy allows for the derivation of a heuristic with a constant worst‐case performance ratio. Worst‐case performance analysis of approximation algorithms is classical in the field of combinatorial optimization, but in stochastic programming the authors are not aware of any previous results in this direction. © 2003 Wiley Periodicals, Inc. Naval Research Logistics, 2003