Heuristics for Base‐Stock Levels in Multi‐Echelon Distribution Networks

We study inventory optimization for locally controlled, continuous‐review distribution systems with stochastic customer demands. Each node follows a base‐stock policy and a first‐come, first‐served allocation policy. We develop two heuristics, the recursive optimization (RO) heuristic and the decomposition‐aggregation (DA) heuristic, to approximate the optimal base‐stock levels of all the locations in the system. The RO heuristic applies a bottom‐up approach that sequentially solves single‐variable, convex problems for each location. The DA heuristic decomposes the distribution system into multiple serial systems, solves for the base‐stock levels of these systems using the newsvendor heuristic of Shang and Song (2003), and then aggregates the serial systems back into the distribution system using a procedure we call “backorder matching.” A key advantage of the DA heuristic is that it does not require any evaluation of the cost function (a computationally costly operation that requires numerical convolution). We show that, for both RO and DA, changing some of the parameters, such as leadtime, unit backordering cost, and demand rate, of a location has an impact only on its own local base‐stock level and its upstream locations’ local base‐stock levels. An extensive numerical study shows that both heuristics perform well, with the RO heuristic providing more accurate results and the DA heuristic consuming less computation time. We show that both RO and DA are asymptotically optimal along multiple dimensions for two‐echelon distribution systems. Finally, we show that, with minor changes, both RO and DA are applicable to the balanced allocation policy.     

Coordination in a Single‐Supplier,Multi‐Retailer Distribution System: Supplier‐Facilitated Transshipments

We consider supplier‐facilitated transshipments for achieving supply chain coordination in a single supplier, multi‐retailer distribution system with non‐cooperative retailers. The previous transshipment literature has focused on coordination through retailer‐negotiated transshipments and thus does not consider the supplier's decision‐making. In contrast, in this study, we assume the supplier is an active participant in the system and we seek to understand how the supplier can facilitate the implementation of coordinating transshipments. We study a two‐period model with wholesale orders at the start of the first period and preventive transshipments performed at the start of the second period. Inspired by a supplier‐facilitated transshipment scheme observed in practice, we assume the supplier implements transshipments through a bi‐directional adjustment contract. Under this contract, each retailer can either buy additional inventory from, or sell back excess inventory to, the supplier. We show that coordination can be achieved through carefully designed contracts with state‐dependent adjustment prices and a wholesale price menu. We demonstrate that the supplier's role in facilitating coordinating transshipments is critical. In addition, we use our understanding of the coordinating contract form to derive some simpler and easier‐to‐implement heuristic contracts. We use a numerical study to demonstrate the value, to the supplier, of using the coordinating adjustment and wholesale prices, and to evaluate the heuristics’ performance.     

Multiple In‐Cycle Transshipments with Positive Delivery Times

We study a centralized inventory sharing system of two retailers that are replenished periodically. Between two replenishments, a unit can be transshipped to a stocked‐out retailer from the other. It arrives a transshipment time later, during which the stocked‐out retailer incurs backorder cost. Without transshipment, backorder cost is incurred until the next replenishment. Since the transshipment time is shorter than the time between two replenishments, transshipments can reduce the backorder cost at the stocked‐out retailer and the holding costs at the other retailer. The system is directed by a centralized inventory manager, who minimizes the long‐run average cost consisting of replenishment, holding, backorder, and transshipment costs. The transshipment policy is characterized by hold‐back inventory levels, which are nonincreasing in the remaining time until the next replenishment. The transshipment policy differs from those in the literature because we allow for multiple transshipments between replenishments, positive transshipment times, and backorder costs. We also discuss the challenges associated with positive replenishment time and develop upper and lower bounds of average cost in this case. Bounds are numerically shown to have an average gap of 1.1%. A heuristic solution is based on the upper bound and differs from the optimal cost by at most this gap.     

Experimental Results Indicating Lattice‐Dependent Policies May Be Optimal for General Assemble‐To‐Order Systems

We consider an assemble‐to‐order (ATO) system with multiple products, multiple components which may be demanded in different quantities by different products, possible batch ordering of components, random lead times, and lost sales. We model the system as an infinite‐horizon Markov decision process under the average cost criterion. A control policy specifies when a batch of components should be produced, and whether an arriving demand for each product should be satisfied. Previous work has shown that a lattice‐dependent base‐stock and lattice‐dependent rationing (LBLR) policy is an optimal stationary policy for a special case of the ATO model presented here (the generalized M‐system). In this study, we conduct numerical experiments to evaluate the use of an LBLR policy for our general ATO model as a heuristic, comparing it to two other heuristics from the literature: a state‐dependent base‐stock and state‐dependent rationing (SBSR) policy, and a fixed base‐stock and fixed rationing (FBFR) policy. Remarkably, LBLR yields the globally optimal cost in each of more than 22,500 instances of the general problem, outperforming SBSR and FBFR with respect to both objective value (by up to 2.6% and 4.8%, respectively) and computation time (by up to three orders and one order of magnitude, respectively) in 350 of these instances (those on which we compare the heuristics). LBLR and SBSR perform significantly better than FBFR when replenishment batch sizes imperfectly match the component requirements of the most valuable or most highly demanded product. In addition, LBLR substantially outperforms SBSR if it is crucial to hold a significant amount of inventory that must be rationed.     

Unsold Versus Unbought Commitment: Minimum Total Commitment Contracts with Nonzero Setup Costs

We study a minimum total commitment (MTC) contract embedded in a finite‐horizon periodic‐review inventory system. Under this contract, the buyer commits to purchase a minimum quantity of a single product from the supplier over the entire planning horizon. We consider nonstationary demand and per‐unit cost, discount factor, and nonzero setup cost. Because the formulations used in existing literature are unable to handle our setting, we develop a new formulation based on a state transformation technique using unsold commitment instead of unbought commitment as state variable. We first revisit the zero setup cost case and show that the optimal ordering policy is an unsold‐commitment‐dependent base‐stock policy. We also provide a simpler proof of the optimality of the dual base‐stock policy. We then study the nonzero setup cost case and prove a new result, that the optimal solution is an unsold‐commitment‐dependent (s, S) policy. We further propose two heuristic policies, which numerical tests show to perform very well. We also discuss two extensions to show the generality of our method's effectiveness. Finally, we use our results to examine the effect of different contract terms such as duration, lead time, and commitment on buyer's cost. We also compare total supply chain profits under periodic commitment, MTC, and no commitment.     

Joint Initial Stocking and Transshipment—Asymptotics and Bounds

A common problem faced by many firms in their supply chains can be abstracted as follows. Periodically, or at the beginning of some selling season, the firm needs to distribute finished goods to a set of stocking locations, which, in turn, supply customer demands. Over the selling season, if and when there is a supply‐demand mismatch somewhere, a re‐distribution or transshipment will be needed. Hence, there are two decisions involved: the one‐time stocking decision at the beginning of the season and the supply/transshipment decision throughout the season. Applying a stochastic dynamic programming formulation to a two‐location model with compound Poisson demand processes, we identify the optimal supply/transshipment policy and show that the optimal initial stocking quantities can be obtained via maximizing a concave function whereas the contribution of transshipment is of order square‐root‐of T. Hence, in the context of high‐volume, fast‐moving products, the initial stocking quantity decision is a much more important contributor to the overall profit. The bounds also lead to a heuristic policy, which exhibits excellent performance in our numerical study; and we further prove both the bounds and the heuristic policy are asymptotically optimal when T approaches infinity. Extension to multiple locations is also discussed.     

Scheduling of Multi‐skilled Staff Across Multiple Locations

We address the problem of assigning airline customer service agents (CSAs) to tasks related to departing flights, such as selling tickets and collecting boarding cards, at an international terminal of a large airport. The airline specifies minimum and target levels of staff and required (or desired) types and levels of skills for each location in each time period. The assignment problem is complicated by staff heterogeneity, time required for moves between locations, and lunch and rest‐break requirements. We present a mixed‐integer formulation that considers both staffing shortages and skills mismatches and show that the problem is NP‐hard. We derive valid inequalities that tighten the bounds within a branch‐and‐cut procedure, enabling us to obtain near‐optimal solutions for problems of realistic size very quickly. We also present a generalization to simultaneously optimize shift starting times and task assignments, which can aid in longer term workforce planning. Finally, we utilize our procedure to obtain managerial insights regarding the benefits of flexibility derived from more highly skilled staff, allowing more frequent moves, and choices of shift starting times. We also demonstrate the benefits of our procedure vs. a heuristic that mimics what an experienced scheduler might choose.     

Lowest Cost May Not Lower Total Cost: Using “Spackling” to Smooth Mass‐Customized Production

Consider a manufacturer who mass customizes variants of a product in make‐to‐order fashion, and also produces standard variants as make‐to‐stock. A traditional manufacturing strategy would be to employ two separate manufacturing facilities: a flexible plant for mass‐customized items and an efficient plant for standard items. We contrast this traditional focus strategy with an alternative that better utilizes capacity by combining production of mass‐customized and standard items in one of two alternate spackling strategies: (1) a pure‐spackling strategy, where the manufacturer produces everything in a (single) flexible plant, first manufacturing custom products as demanded each period, and then filling in the production schedule with make‐to‐stock output of standard products; or (2) a layered‐spackling strategy, which uses an efficient plant to make a portion of its standard items and a separate flexible plant where it spackles. We identify the optimal production strategy considering the tradeoff between the cost premium for flexible (versus efficient) production capacity and the opportunity costs of idle capacity. Spackling amortizes fixed costs of capacity more effectively and thus can increase profits from mass customization vis‐à‐vis a focus strategy, even with higher cost production for the standard goods. We illustrate our framework with data from a messenger bag manufacturer.     

考虑多种安全库存策略的选址-库存问题研究

考虑多种安全设置策略的物流网络的选址-库存问题,不仅是选址、订货、运输和库存的集成优化,还需要考虑多种不同的安全库存设置和转运策略。因此,本文深入讨论了二级物流网络中的六种安全库存设置策略,构建了六种考虑不同安全库存设置的选址-库存模型。在考虑集中设置安全库存时,集中安全库存需要通过转载运输实现,因此需要将转载运输成本引入选址-库存模型之中,使新的选址-库存模型更加科学合理。另外,针对六种新的选址-库存模型,提出了基于个体成本差异分配的遗传算法,迭代搜索选址、分配、库存设置策略的优化组合。最后,通过数据实验验证了模型的有效性：（1）安全库存与转载运输之间存在此消彼长的背反关系;（2）安全库存设置和转载运输策略对总成本的影响取决于两种费率权重情况。本文的研究可以为二级物流网络的选址、订货和安全库存策略集成优化决策提供参考依据。     

The Role of Contract Expirations in Service Parts Management

The majority of after‐sales service providers manage their service parts inventory by focusing on the availability of service parts. This approach, combined with automatic replenishment systems, leads to reactive inventory control policies where base stock levels are adjusted only after a service contract expires. Consequently, service providers often face excess stock of critical service parts that are difficult to dispose due to their specificity. In this study, we address this problem by developing inventory control policies taking into account contract expirations. Our key idea is to reduce the base stock level of the one‐for‐one policy before obsolescence (a full or partial drop in demand rate) occurs and let demand take away excess stock. We refer to this policy as the single‐adjustment policy. We benchmark the single‐adjustment policy with the multiple‐adjustment policy (allowing multiple base stock adjustments) formulated as a dynamic program and verify that for a wide range of instances the single‐adjustment policy is an effective heuristic for the multiple‐adjustment policy. We also compare the single‐adjustment policy with the world‐dependent base stock policy offered by Song and Zipkin (1993) and identify the parameter combinations where both policies yield similar costs. We consider two special cases of the single‐adjustment policy where the base stock level is kept fixed or the base stock adjustment is postponed to the contract expiration time. We find that the initial demand rate, contract expiration time, and size of the drop in demand rate are the three key parameters driving the choice between the single‐adjustment policy and its special cases.     

Optimal Ordering Policies for Inventory Problems With Dynamic Information Delays

Information delays exist when the most recent inventory information available to the Inventory Manager (IM) is dated. In other words, the IM observes only the inventory level that belongs to an earlier period. Such situations are not uncommon, and they arise when it takes a while to process the demand data and pass the results to the IM. We introduce dynamic information delays as a Markov process into the standard multiperiod stochastic inventory problem with backorders. We develop the concept of a reference inventory position. We show that this position along with the magnitude of the latest observed delay and the age of this observation are sufficient statistics for finding the optimal order quantities. Furthermore, we establish that the optimal ordering policy is of state‐dependent base‐stock type with respect to the reference inventory position (or state‐dependent (s, S) type if there is a fixed ordering cost). The optimal base stock and (s, S) levels depend on the magnitude of the latest observed delay and the age of this observation. Finally, we study the sensitivity of the optimal base stock and the optimal cost with respect to the sufficient statistics.     

Coordinated Logistics: Joint Replenishment with Capacitated Transportation for a Supply Chain

In this study, we consider the integrated inventory replenishment and transportation operations in a supply chain where the orders placed by the downstream retailer are dispatched by the upstream warehouse via an in‐house fleet of limited size. We first consider the single‐item single‐echelon case where the retailer operates with a quantity based replenishment policy, (r,Q), and the warehouse is an ample supplier. We model the transportation operations as a queueing system and derive the operating characteristics of the system in exact terms. We extend this basic model to a two‐echelon supply chain where the warehouse employs a base‐stock policy. The departure process of the warehouse is characterized in distribution, which is then approximated by an Erlang arrival process by matching the first two moments for the analysis of the transportation queueing system. The operating characteristics and the expected cost rate are derived. An extension of this system to multiple retailers is also discussed. Numerical results are presented to illustrate the performance and the sensitivity of the models and the value of coordinating inventory and transportation operations.     

Addressing Supply–Demand Imbalance: Designing Efficient Remanufacturing Strategies

The management of remanufacturing inventory system is often challenged by mismatched supply (i.e., returned units, called cores) and demand. Typically, the demand for remanufactured units is high and exceeds the supply early in a product's lifetime, and drops below the supply late in the lifetime. This supply–demand imbalance motivates us to study a switching strategy to facilitate the decision‐making process. This strategy deploys a push mode at the early stage of a product's lifetime, which remanufactures scarce cores to stock to responsively satisfy the high demand, and switches to a pull mode as the product approaches obsolescence to accurately match the low demand with supply. In addition, the strategy further simplifies the decision‐making process by ignoring the impact of leftover cores at the end of each decision period. We show that the optimal policy of the switching strategy possesses a simple, multi‐dimensional base‐stock structure, which aims to remanufacture units from the i best‐quality categories up to the ith state‐independent base‐stock level. An extensive numerical study shows that the switching strategy delivers close‐to‐optimal and robust performance: the strategy only incurs an average profit loss of 1.21% and a maximum of 2.27%, compared with the optimal one. The numerical study also shows when a pure push or pull strategy, a special case of the switching strategy, delivers good performance. The study offers the managerial insight that firms can use simple, easy‐to‐implement strategies to efficiently manage the remanufacturing inventory system.     

Joint Inventory and Pricing Coordination with Incomplete Demand Information

In retailing operations, retailers face the challenge of incomplete demand information. We develop a new concept named K‐approximate convexity, which is shown to be a generalization of K‐convexity, to address this challenge. This idea is applied to obtain a base‐stock list‐price policy for the joint inventory and pricing control problem with incomplete demand information and even non‐concave revenue function. A worst‐case performance bound of the policy is established. In a numerical study where demand is driven from real sales data, we find that the average gap between the profits of our proposed policy and the optimal policy is 0.27%, and the maximum gap is 4.6%.     

Priority Rules for Multi‐Task Due‐Date Scheduling under Varying Processing Costs

We study the scheduling of multiple tasks under varying processing costs and derive a priority rule for optimal scheduling policies. Each task has a due date, and a non‐completion penalty cost is incurred if the task is not completely processed before its due date. We assume that the task arrival process is stochastic and the processing rate is capacitated. Our work is motivated by both traditional and emerging application domains, such as construction industry and freelance consulting industry. We establish the optimality of Shorter Slack time and Longer remaining Processing time (SSLP) principle that determines the priority among active tasks. Based on the derived structural properties, we also propose an effective cost‐balancing heuristic policy and demonstrate the efficacy of the proposed policy through extensive numerical experiments. We believe our results provide operators/managers valuable insights on how to devise effective service scheduling policies under varying costs.     

Replenishment Policies for Multi‐Product Stochastic Inventory Systems with Correlated Demand and Joint‐Replenishment Costs

This study analyzes optimal replenishment policies that minimize expected discounted cost of multi‐product stochastic inventory systems. The distinguishing feature of the multi‐product inventory system that we analyze is the existence of correlated demand and joint‐replenishment costs across multiple products. Our objective is to understand the structure of the optimal policy and use this structure to construct a heuristic method that can solve problems set in real‐world sizes/dimensions. Using an MDP formulation we first compute the optimal policy. The optimal policy can only be computed for problems with a small number of product types due to the curse of dimensionality. Hence, using the insight gained from the optimal policy, we propose a class of policies that captures the impact of demand correlation on the structure of the optimal policy. We call this class (s, c, d, S)‐policies, and also develop an algorithm to compute good policies in this class, for large multi‐product problems. Finally using an exhaustive set of computational examples we show that policies in this class very closely approximate the optimal policy and can outperform policies analyzed in prior literature which assume independent demand. We have also included examples that illustrate performance under the average cost objective.     

Approximation algorithms for multicast routing in ad hoc wireless networks

Energy efficient multicast problem is one of important issues in ad hoc networks. In this paper, we address the energy efficient multicast problem for discrete power levels in ad hoc wireless networks. The problem of our concern is: given n nodes deployed over 2-D plane and each node v has l(v) transmission power levels and a multicast request (s,D) (clearly, when D is V∖{s}, the multicast request is a broadcast request), how to find a multicast tree rooted at s and spanning all destinations in D such that the total energy cost of the multicast tree is minimized. We first prove that this problem is NP-hard and it is unlikely to have an approximation algorithm with performance ratio ρlnn(ρ<1). Then, we propose a general algorithm for the multicast/broadcast tree problem. And based on the general algorithm, we propose an approximation algorithm and a heuristics for multicast tree problem. Especially, we also propose an efficient heuristic for broadcast tree problem. Simulations ensure our algorithms are efficient.     

Information‐Sensitive Replenishment when Inventory Records Are Inaccurate

Inspired by recent empirical work on inventory record inaccuracy, we consider a periodic review inventory system with imperfect inventory records and unobserved lost sales. Record inaccuracies are assumed to arrive via an error process that perturbs physical inventory but is unobserved by the inventory manager. The inventory manager maintains a probability distribution around the physical inventory level that he updates based on sales observations using Bayes Theorem. The focus of this study is on understanding, approximating, and evaluating optimal forward‐looking replenishment in this environment. By analyzing one‐ and two‐period versions of the problem, we demonstrate several mechanisms by which the error process and associated record inaccuracy can impact optimal replenishment. Record inaccuracy generally brings an incentive for a myopic manager to increase stock to buffer the added uncertainty. On the other hand, a forward‐looking manager will stock less than a myopic manager, in part to improve information content for future decisions. Using an approximate partially observed dynamic programming policy and associated bound, we numerically corroborate our analytical findings and measure the effectiveness of an intelligent myopic heuristic. We find that the myopic heuristic is likely sufficiently good in practical settings targeting high service levels.     

Dynamic Supply Risk Management with Signal‐Based Forecast,Multi‐Sourcing,and Discretionary Selling

We examine the critical role of advance supply signals—such as suppliers’ financial health and production viability—in dynamic supply risk management. The firm operates an inventory system with multiple demand classes and multiple suppliers. The sales are discretionary and the suppliers are susceptible to both systematic and operational risks. We develop a hierarchical Markov model that captures the essential features of advance supply signals, and integrate it with procurement and selling decisions. We characterize the optimal procurement and selling policy, and the strategic relationship between signal‐based forecast, multi‐sourcing, and discretionary selling. We show that higher demand heterogeneity may reduce the value of discretionary selling, and that the mean value‐based forecast may outperform the stationary distribution‐based forecast. This work advances our understanding on when and how to use advance supply signals in dynamic risk management. Future supply risk erodes profitability but enhances the marginal value of current inventory. A signal of future supply shortage raises both base stock and demand rationing levels, thereby boosting the current production and tightening the current sales. Signal‐based dynamic forecast effectively guides the firm's procurement and selling decisions. Its value critically depends on supply volatility and scarcity. Ignoring advance supply signals can result in misleading recommendations and severe losses. Signal‐based dynamic supply forecast should be used when: (a) supply uncertainty is substantial, (b) supply‐demand ratio is moderate, (c) forecast precision is high, and (d) supplier heterogeneity is high.     

Optimal Policies for Selling New and Remanufactured Products

Because of environmental and economic reasons, an increasing number of original equipment manufacturers (OEMs) nowadays sell both new and remanufactured products. When both products are available, customers will buy the one that gives them a higher (and non‐negative) utility. Thus, if the firm does not price the products properly, then product cannibalization may arise and its revenue may be adversely impacted. In this paper, we study the pricing problem of a firm that sells both new and remanufactured products over a finite planning horizon. Customer demand processes for both new and remanufactured products are random and price‐sensitive, and product returns (also called cores) are random and remanufactured upon receipt. We characterize the optimal pricing and manufacturing policies that maximize the expected total discounted profit. If new products are made‐to‐order (MTO), we show that when the inventory level of remanufactured product increases, the optimal price of remanufactured product decreases while the price difference between new and remanufactured products increases; however, the optimal selling price of new product may increase or decrease. If new products are made to stock (MTS), then the optimal manufacturing policy is of a base‐stock policy with the base‐stock level decreasing in the remanufactured product inventory level. To understand the potential benefit in implementing an MTO system, we study the difference between the value functions of the MTO and MTS systems, and develop lower and upper bounds for it. Finally, we study several extensions of the base model and show that most of our results extend to those more general settings.