Exact algorithms for integrated facility location and production planning problems

We consider a class of facility location problems with a time dimension, which requires assigning every customer to a supply facility in each of a finite number of periods. Each facility must meet all assigned customer demand in every period at a minimum cost via its production and inventory decisions. We provide exact branch‐and‐price algorithms for this class of problems and several important variants. The corresponding pricing problem takes the form of an interesting class of production planning and order selection problems. This problem class requires selecting a set of orders that maximizes profit, defined as the revenue from selected orders minus production‐planning‐related costs incurred in fulfilling the selected orders. We provide polynomial‐time dynamic programming algorithms for this class of pricing problems, as well as for generalizations thereof. Computational testing indicates the advantage of our branch‐and‐price algorithm over various approaches that use commercial software packages. These tests also highlight the significant cost savings possible from integrating location with production and inventory decisions and demonstrate that the problem is rather insensitive to forecast errors associated with the demand streams. © 2011 Wiley Periodicals, Inc. Naval Research Logistics, 2011     

On the first come–first served rule in multi‐echelon inventory control

A two‐echelon distribution inventory system with a central warehouse and a number of retailers is considered. The retailers face stochastic demand and replenish from the warehouse, which, in turn, replenishes from an outside supplier. The system is reviewed continuously and demands that cannot be met directly are backordered. Standard holding and backorder costs are considered. In the literature on multi‐echelon inventory control it is standard to assume that backorders at the warehouse are served according to a first come–first served policy (FCFS). This allocation rule simplifies the analysis but is normally not optimal. It is shown that the FCFS rule can, in the worst case, lead to an asymptotically unbounded relative cost increase as the number of retailers approaches infinity. We also provide a new heuristic that will always give a reduction of the expected costs. A numerical study indicates that the average cost reduction when using the heuristic is about two percent. The suggested heuristic is also compared with two existing heuristics. © 2007 Wiley Periodicals, Inc. Naval Research Logistics, 2007     

Performance evaluation of a production/inventory system with periodic review and endogenous lead times

This paper considers a discrete time, single item production/inventory system with random period demands. Inventory levels are reviewed periodically and managed using a base‐stock policy. Replenishment orders are placed with the production system which is capacitated in the sense that there is a single server that sequentially processes the items one at a time with stochastic unit processing times. In this setting the variability in demand determines the arrival pattern of production orders at the queue, influencing supply lead times. In addition, the inventory behavior is impacted by the correlation between demand and lead times: a large demand size corresponds to a long lead time, depleting the inventory longer. The contribution of this paper is threefold. First, we present an exact procedure based on matrix‐analytic techniques for computing the replenishment lead time distribution given an arbitrary discrete demand distribution. Second, we numerically characterize the distribution of inventory levels, and various other performance measures such as fill rate, base‐stock levels and optimal safety stocks, taking the correlation between demand and lead times into account. Third, we develop an algorithm to fit the first two moments of the demand and service time distribution to a discrete phase‐type distribution with a minimal number of phases. This provides a practical tool to analyze the effect of demand variability, as measured by its coefficient of variation, on system performance. We also show that our model is more appropriate than some existing models of capacitated systems in discrete time. © 2007 Wiley Periodicals, Inc. Naval Research Logistics, 2007     

The continuous‐time single‐sourcing problem with capacity expansion opportunities

This paper develops a new model for allocating demand from retailers (or customers) to a set of production/storage facilities. A producer manufactures a product in multiple production facilities, and faces demand from a set of retailers. The objective is to decide which of the production facilities should satisfy each retailer's demand, in order minimize total production, inventory holding, and assignment costs (where the latter may include, for instance, variable production costs and transportation costs). Demand occurs continuously in time at a deterministic rate at each retailer, while each production facility faces fixed‐charge production costs and linear holding costs. We first consider an uncapacitated model, which we generalize to allow for production or storage capacities. We then explore situations with capacity expansion opportunities. Our solution approach employs a column generation procedure, as well as greedy and local improvement heuristic approaches. A broad class of randomly generated test problems demonstrates that these heuristics find high quality solutions for this large‐scale cross‐facility planning problem using a modest amount of computation time. © 2005 Wiley Periodicals, Inc. Naval Research Logistics, 2005.     

Operations sequencing for a multi‐stage production inventory system

This article studies operations sequencing for a multi‐stage production inventory system with lead times under predictable (deterministic) yield losses and random demand. We consider various cases with either full or partial release of work‐in‐process inventories, for either pre‐operation or post‐operation cost structures, and under either the total discounted or average cost criteria. We derive necessary and sufficient criteria for the optimal sequence of operations in all cases. While the criteria differ in their specific forms, they all lead to the same principal: those operations with (1) lower yields, (2) lower processing costs, (3) longer lead times, and (4) lower inventory holding costs should be placed higher upstream in the system.Copyright © 2014 Wiley Periodicals, Inc. Naval Research Logistics 61: 144–154, 2014     

A location‐inventory model with lateral transshipments

We study an infinite horizon periodic stochastic inventory system consisting of retail outlets and customers located on a homogenous line segment. In each period, the total demand, generated by the customers on the line, is normally distributed. To better match supply and demand, we incorporate lateral transshipments. We propose a compact model in which the strategic decisions—the number and locations of retail outlets—are determined simultaneously with the operational decisions—the inventory replenishment and transshipment quantities. We find the optimal balance between the risk‐pooling considerations, which drive down the optimal number of retail outlets, and lateral transshipments, which drive up the optimal number of retail outlets. We also explore the sensitivity of the optimal number of retail outlets to various problem parameters. This article presents a novel way of integrating lateral transshipments in the context of an inventory‐location model. © 2011 Wiley Periodicals, Inc. Naval Research Logistics, 2011     

Optimal FCFS allocation rules for periodic‐review assemble‐to‐order systems

In Assemble‐To‐Order (ATO) systems, situations may arise in which customer demand must be backlogged due to a shortage of some components, leaving available stock of other components unused. Such unused component stock is called remnant stock. Remnant stock is a consequence of both component ordering decisions and decisions regarding allocation of components to end‐product demand. In this article, we examine periodic‐review ATO systems under linear holding and backlogging costs with a component installation stock policy and a First‐Come‐First‐Served (FCFS) allocation policy. We show that the FCFS allocation policy decouples the problem of optimal component allocation over time into deterministic period‐by‐period optimal component allocation problems. We denote the optimal allocation of components to end‐product demand as multimatching. We solve the multi‐matching problem by an iterative algorithm. In addition, an approximation scheme for the joint replenishment and allocation optimization problem with both upper and lower bounds is proposed. Numerical experiments for base‐stock component replenishment policies show that under optimal base‐stock policies and optimal allocation, remnant stock holding costs must be taken into account. Finally, joint optimization incorporating optimal FCFS component allocation is valuable because it provides a benchmark against which heuristic methods can be compared. © 2015 Wiley Periodicals, Inc. Naval Research Logistics 62: 158–169, 2015     

Optimal control of a production‐inventory system with both backorders and lost sales

We consider the optimal control of a production inventory‐system with a single product and two customer classes where items are produced one unit at a time. Upon arrival, customer orders can be fulfilled from existing inventory, if there is any, backordered, or rejected. The two classes are differentiated by their backorder and lost sales costs. At each decision epoch, we must determine whether or not to produce an item and if so, whether to use this item to increase inventory or to reduce backlog. At each decision epoch, we must also determine whether or not to satisfy demand from a particular class (should one arise), backorder it, or reject it. In doing so, we must balance inventory holding costs against the costs of backordering and lost sales. We formulate the problem as a Markov decision process and use it to characterize the structure of the optimal policy. We show that the optimal policy can be described by three state‐dependent thresholds: a production base‐stock level and two order‐admission levels, one for each class. The production base‐stock level determines when production takes place and how to allocate items that are produced. This base‐stock level also determines when orders from the class with the lower shortage costs (Class 2) are backordered and not fulfilled from inventory. The order‐admission levels determine when orders should be rejected. We show that the threshold levels are monotonic (either nonincreasing or nondecreasing) in the backorder level of Class 2. We also characterize analytically the sensitivity of these thresholds to the various cost parameters. Using numerical results, we compare the performance of the optimal policy against several heuristics and show that those that do not allow for the possibility of both backordering and rejecting orders can perform poorly.© 2010 Wiley Periodicals, Inc. Naval Research Logistics 2010     

Optimization of order-up-to-s policies in two-echelon inventory systems with periodic review

We consider an inventory system with one warehouse and N retailers. Transportation times are constant and the retailers face independent Poisson demand. Each facility applies a periodic review order-up-to-S policy. In case of shortages at the warehouse, orders for individual units are filled in the same order as the original demand at the retailers, i.e., according to a so-called virtual allocation scheme. Using that the considered policy is very similar to a continuous review one-for-one ordering policy, we are able to provide simple recursive procedures for exact evaluation of holding and shortage costs. © 1993 John Wiley & Sons, Inc.     

Optimal base stock policies and truck capacity in a two-echelon system

With the recent trend toward just-in-time deliveries and reduction of inventories, many firms are reexamining their inventory and logistics policies. Some firms have dramatically altered their inventory, production, and shipping policies with the goal of reducing costs and improving service. Part of this restructuring may involve a specific contract with a trucking company, or it may entail establishing in-house shipping capabilities. This restructuring, however, raises new questions regarding the choice of optimal trucking capacity, shipping frequency, and inventory levels. In this study, we examine a two-level distribution system composed of a warehouse and a retailer. We assume that demand at the retailer is random. Since the warehouse has no advance notice of the size of the retailer order, inventory must be held there as well as at the retailer. We examine inventory policies at both the warehouse and the retailer, and we explicitly consider the trucking capacity, and the frequency of deliveries from the warehouse to the retailer. Both linear and concave fixed transportation costs are examined. We find the optimal base stock policies at both locations, the optimal in-house or contracted regular truck capacity, and the optimal review period (or, equivalently, delivery frequency). For the case of normally distributed demand we provide analytical results and numerical examples that yield insight into systems of this type. Some of our results are counterintuitive. For instance, we find some cases in which the optimal truck capacity decreases as the variability of demand increases. In other cases the truck capacity increases with variability of demand. © 1993 John Wiley & Sons, Inc.     

Effectiveness of (R,Q) policies in one‐warehouse multiretailer systems with deterministic demand and backlogging

Consider a distribution system with a central warehouse and multiple retailers. Customer demand arrives at each of the retailers continuously at a constant rate. The retailers replenish their inventories from the warehouse which in turn orders from an outside supplier with unlimited stock. There are economies of scale in replenishing the inventories at both the warehouse and the retail level. Stockouts at the retailers are backlogged. The system incurs holding and backorder costs. The objective is to minimize the long‐run average total cost in the system. This paper studies the cost effectiveness of (R, Q) policies in the above system. Under an (R, Q) policy, each facility orders a fixed quantity Q from its supplier every time its inventory position reaches a reorder point R. It is shown that (R, Q) policies are at least 76% effective. Numerical examples are provided to further illustrate the cost effectiveness of (R, Q) policies. © 2000 John Wiley & Sons, Inc. Naval Research Logistics 47: 422–439, 2000     

Inventory models with nonlinear shortage costs and stochastic lead times; applications of shape properties of randomly stopped counting processes

In this article, we study generalizations of some of the inventory models with nonlinear costs considered by Rosling in (Oper. Res. 50 (2002) 797–809). In particular, we extend the study of both the periodic review and the compound renewal demand processes from a constant lead time to a random lead time. We find that the quasiconvexity properties of the cost function (and therefore the existence of optimal (s, S) policies), holds true when the lead time has suitable log‐concavity properties. The results are derived by structural properties of renewal delayed processes stopped at an independent random time and by the study of log‐concavity properties of compound distributions. © 2015 Wiley Periodicals, Inc. Naval Research Logistics 62: 345–356, 2015     

The economic lot scheduling problem with finite backorder costs

We are concerned with the problem of scheduling m items, facing constant demand rates, on a single facility to minimize the long-run average holding, backorder, and setup costs. The inventory holding and backlogging costs are charged at a linear time weighted rate. We develop a lower bound on the cost of all feasible schedules and extend recent developments in the economic lot scheduling problem, via time-varying lot sizes, to find optimal or near-optimal cyclic schedules. The resulting schedules are used elsewhere as target schedules when demands are random. © 1992 John Wiley & Sons, Inc.     

Distribution free bounds for service constrained (Q,r) inventory systems

A classical and important problem in stochastic inventory theory is to determine the order quantity (Q) and the reorder level (r) to minimize inventory holding and backorder costs subject to a service constraint that the fill rate, i.e., the fraction of demand satisfied by inventory in stock, is at least equal to a desired value. This problem is often hard to solve because the fill rate constraint is not convex in (Q, r) unless additional assumptions are made about the distribution of demand during the lead‐time. As a consequence, there are no known algorithms, other than exhaustive search, that are available for solving this problem in its full generality. Our paper derives the first known bounds to the fill‐rate constrained (Q, r) inventory problem. We derive upper and lower bounds for the optimal values of the order quantity and the reorder level for this problem that are independent of the distribution of demand during the lead time and its variance. We show that the classical economic order quantity is a lower bound on the optimal ordering quantity. We present an efficient solution procedure that exploits these bounds and has a guaranteed bound on the error. When the Lagrangian of the fill rate constraint is convex or when the fill rate constraint does not exist, our bounds can be used to enhance the efficiency of existing algorithms. © 2000 John Wiley & Sons, Inc. Naval Research Logistics 47: 635–656, 2000     

On the (S − 1, S) lost sales inventory model with priority demand classes

In this paper an inventory model with several demand classes, prioritised according to importance, is analysed. We consider a lot‐for‐lot or (S ? 1, S) inventory model with lost sales. For each demand class there is a critical stock level at and below which demand from that class is not satisfied from stock on hand. In this way stock is retained to meet demand from higher priority demand classes. A set of such critical levels determines the stocking policy. For Poisson demand and a generally distributed lead time, we derive expressions for the service levels for each demand class and the average total cost per unit time. Efficient solution methods for obtaining optimal policies, with and without service level constraints, are presented. Numerical experiments in which the solution methods are tested demonstrate that significant cost reductions can be achieved by distinguishing between demand classes. © 2002 Wiley Periodicals, Inc. Naval Research Logistics 49: 593–610, 2002; Published online in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/nav.10032     

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     

On the value of information in dynamic production/inventory problems under forecast evolution

In this article we explore how total system costs and inventory positions are affected when forecasts are incorporated explicitly in production/inventory systems. We assume that forecasts for demand of a certain item are available in each period, and they evolve from one period to the next in accordance with an additive evolution model. In order to analyze the effects of the forecasts on the production/inventory system we compare the optimal ordering policy and the expected costs of the model that keeps forecasts with that of a comparable standard inventory model. We show that under mild assumptions the former yields lower expected costs and inventory levels than the latter. © 1996 John Wiley & Sons, Inc.     

Optimal control policies for a periodic review inventory system with emergency orders

We describe a periodic review inventory system where emergency orders, which have a shorter supply lead time but are subject to higher ordering cost compared to regular orders, can be placed on a continuous basis. We consider the periodic review system in which the order cycles are relatively long so that they are possibly larger than the supply lead times. Study of such systems is important since they are often found in practice. We assume that the difference between the regular and emergency supply lead times is less than the order-cycle length. We develop a dynamic programming model and derive a stopping rule to end the computation and obtain optimal operation parameters. Computational results are included that support the contention that easily implemented policies can be computed with reasonable effort. © 1998 John Wiley & Sons, Inc. Naval Research Logistics 45: 187–204, 1998     

Capacitated warehouse location model with risk pooling

In this article, we introduce the capacitated warehouse location model with risk pooling (CLMRP), which captures the interdependence between capacity issues and the inventory management at the warehouses. The CLMRP models a logistics system in which a single plant ships one type of product to a set of retailers, each with an uncertain demand. Warehouses serve as the direct intermediary between the plant and the retailers for the shipment of the product and also retain safety stock to provide appropriate service levels to the retailers. The CLMRP minimizes the sum of the fixed facility location, transportation, and inventory carrying costs. The model simultaneously determines warehouse locations, shipment sizes from the plant to the warehouses, the working inventory, and safety stock levels at the warehouses and the assignment of retailers to the warehouses. The costs at each warehouse exhibit initially economies of scale and then an exponential increase due to the capacity limitations. We show that this problem can be formulated as a nonlinear integer program in which the objective function is neither concave nor convex. A Lagrangian relaxation solution algorithm is proposed. The Lagrangian subproblem is also a nonlinear integer program. An efficient algorithm is developed for the linear relaxation of this subproblem. The Lagrangian relaxation algorithm provides near‐optimal solutions with reasonable computational requirements for large problem instances. © 2008 Wiley Periodicals, Inc. Naval Research Logistics, 2008     

Optimal outbound dispatch policies: Modeling inventory and cargo capacity

In this paper, we present an optimization model for coordinating inventory and transportation decisions at an outbound distribution warehouse that serves a group of customers located in a given market area. For the practical problems which motivated this paper, the warehouse is operated by a third party logistics provider. However, the models developed here may be applicable in a more general context where outbound distribution is managed by another supply chain member, e.g., a manufacturer. We consider the case where the aggregate demand of the market area is constant and known per period (e.g., per day). Under an immediate delivery policy, an outbound shipment is released each time a demand is realized (e.g., on a daily basis). On the other hand, if these shipments are consolidated over time, then larger (hence more economical) outbound freight quantities can be dispatched. In this case, the physical inventory requirements at the third party warehouse (TPW) are determined by the consolidated freight quantities. Thus, stock replenishment and outbound shipment release policies should be coordinated. By optimizing inventory and freight consolidation decisions simultaneously, we compute the parameters of an integrated inventory/outbound transportation policy. These parameters determine: (i) how often to dispatch a truck so that transportation scale economies are realized and timely delivery requirements are met, and (ii) how often, and in what quantities, the stock should be replenished at the TPW. We prove that the optimal shipment release timing policy is nonstationary, and we present algorithms for computing the policy parameters for both the uncapacitated and finite cargo capacity problems. The model presented in this study is considerably different from the existing inventory/transportation models in the literature. The classical inventory literature assumes that demands should be satisfied as they arrive so that outbound shipment costs are sunk costs, or else these costs are covered by the customer. Hence, the classical literature does not model outbound transportation costs. However, if a freight consolidation policy is in place then the outbound transportation costs can no longer be ignored in optimization. Relying on this observation, this paper models outbound transportation costs, freight consolidation decisions, and cargo capacity constraints explicitly. © 2002 Wiley Periodicals, Inc. Naval Research Logistics 49: 531–556, 2002; Published online in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/nav.10030