Base stock policies for production/inventory problems with uncertain capacity levels

In this paper we consider a single item, stochastic demand production/inventory problem where the maximum amount that can be produced (or ordered) in any given period is assumed to be uncertain. Inventory levels are reviewed periodically. The system operates under a stationary modified base stock policy. The intent of our paper is to present a procedure for computing the optimal base stocl level of this policy under expected average cost per period criterion. This procedure would provide guidance as to the appropriate amount of capacity to store in the form of inventory in the face of stochastic demand and uncertain capacity. In achieving this goal, our main contribution is to establish the analogy between the class of base stock production/inventory policies that operate under demand/capacity uncertainty, and the G/G/1 queues and their associated random walks. We also present example derivations for some important capacity distributions.     

Finding and identifying optimal inventory levels for systems with common components

In this article, we consider the problem of finding the optimal inventory level for components in an assembly system where multiple products share common components in the presence of random demand. Previously, solution procedures that identify the optimal inventory levels for components in a component commonality problem have been considered for two product or one common component systems. We will here extend this to a three products system considering any number of common components. The inventory problem considered is modeled as a two stage stochastic recourse problem where the first stage is to set the inventory levels to maximize expected profit while the second stage is to allocate components to products after observing demand. Our main contribution, and the main focus of this paper, is the outline of a procedure that finds the gradient for the stochastic problem, such that an optimal solution can be identified and a gradient based search method can be used to find the optimal solution.     

Two-resource stochastic capacity planning employing a Bayesian methodology

We examine a stochastic capacity-planning problem with two resources that can satisfy demand for two services. One of the resources can only satisfy demand for a specific service, whereas the other resource can provide both services. We formulate the problem of choosing the capacity levels of each resource to maximize expected profits. In addition, we provide analytic, easy-to-interpret optimal solutions, as well as perform a comparative statics analysis. As applying the optimal solutions effectively requires good estimates of the unknown demand parameters, we also examine Bayesian estimates of the demand parameters derived via a class of conjugate priors. We compare the optimal expected profits when demands for the two services follow independent distributions with informative and non-informative priors, and demonstrate that using good informative priors on demand can significantly improve performance.     

Capacity and Production Managment in a Single Product Manufacturing System

In planning and managing production systems, manufacturers have two main strategies for responding to uncertainty: they build inventory to hedge against periods in which the production capacity is not sufficient to satisfy demand, or they temporarily increase the production capacity by “purchasing” extra capacity. We consider the problem of minimizing the long-run average cost of holding inventory and/or purchasing extra capacity for a single facility producing a single part-type and assume that the driving uncertainty is demand fluctuation. We show that the optimal production policy is of a hedging point policy type where two hedging levels are associated with each discrete state of the system: a positive hedging level (inventory target) and a negative one (backlog level below which extra capacity should be purchased). We establish some ordering of the hedging levels, derive equations satisfied by the steady-state probability distribution of the inventory/backlog, and give a more detailed analysis of the optimal control policy in a two state (high and low demand rate) model.     

The stochastic economic lot sizing problem for non-stop multi-grade production with sequence-restricted setup changeovers

We study a variant of the stochastic economic lot scheduling problem (SELSP) encountered in process industries, in which a single production facility must produce several different grades of a family of products to meet random stationary demand for each grade from a common finished-goods (FG) inventory buffer that has limited storage capacity. When the facility is set up to produce a particular grade, the only allowable changeovers are from that grade to the next lower or higher grade. Raw material is always available, and the production facility produces continuously at a constant rate even during changeover transitions. All changeover times are constant and equal to each other, and demand that cannot be satisfied directly from inventory is lost. There is a changeover cost per changeover occasion, a spill-over cost per unit of product in excess whenever there is not enough space in the FG buffer to store the produced grade, and a lost-sales cost per unit short whenever there is not enough FG inventory to satisfy the demand. We model the SELSP as a discrete-time Markov decision process (MDP), where in each time period the decision is whether to initiate a changeover to a neighboring grade or keep the set up of the production facility unchanged, based on the current state of the system, which is defined by the current set up of the facility and the FG inventory levels of all the grades. The goal is to minimize the (long-run) expected average cost per period. For problems with more than three grades, we develop a heuristic solution procedure which is based on decomposing the original multi-grade problem into several 3-grade MDP sub-problems, numerically solving each sub-problem using value iteration, and constructing the final policy for the original problem by combining parts of the optimal policies of the sub-problems. We present numerical results for problem examples with 2–5 grades. For the 2- and 3-grade examples, we numerically solve the exact MDP problem using value iteration to obtain insights into the structure of the optimal changeover policy. For the 4- and 5-grade examples, we compare the performance of the decomposition-based heuristic (DBH) solution procedure against that obtained by numerically solving the exact problem. We also compare the performance of the DBH method against the performance of three simpler parameterized heuristics. Finally, we compare the performance of the DBH and the exact solution procedures for the case where the FG inventory storage consists of a number of separate general-purpose silos capable of storing any grade as long as it is not mixed with any other grade.     

The stochastic transportation problem with single sourcing

We propose a branch-and-price algorithm for solving a class of stochastic transportation problems with single-sourcing constraints. Our approach allows for general demand distributions, nonlinear cost structures, and capacity expansion opportunities. The pricing problem is a knapsack problem with variable item sizes and concave costs that is interesting in its own right. We perform an extensive set of computational experiments illustrating the efficacy of our approach. In addition, we study the cost of the single-sourcing constraints.     

Inverse optimization: towards the optimal parameter set of inverse LP with interval coefficients

We study the inverse optimization problem in the following formulation: given a family of parametrized optimization problems and a real number called demand, determine for which values of parameters the optimal value of the objective function equals to the demand. We formulate general questions and problems about the optimal parameter set and the optimal value function. Then we turn our attention to the case of linear programming, when parameters can be selected from given intervals (“inverse interval LP”). We prove that the problem is NP-hard not only in general, but even in a very special case. We inspect three special cases—the case when parameters appear in the right-hand sides, the case when parameters appear in the objective function, and the case when parameters appear in both the right-hand sides and the objective function. We design a technique based on parametric programming, which allows us to inspect the optimal parameter set. We illustrate the theory by examples.     

Analysis of seat allocation and overbooking decisions with hybrid information

We investigate a single-leg airline revenue management problem where an airline has limited demand information and uncensored no-show information. To use such hybrid information for simultaneous overbooking and booking control decisions, we combine expected overbooking cost with revenue. Then we take a robust optimization approach with a regret-based criterion. While the criterion is defined on a myriad of possible demand scenarios, we show that only a small number of them are necessary to compute the objective. We also prove that nested booking control policies are optimal among all deterministic ones. We further develop an effective computational method to find the optimal policy and compare our policy to others proposed in the literature.     

Production-inventory control policy under warm/cold state-dependent fixed costs and stochastic demand: partial characterization and heuristics

The motivation for our study comes from some production and inventory systems in which ordering/producing quantities that exceed certain thresholds in a given period might eliminate some setup activities in the next period. Many examples of such systems have been discussed in prior research but the analysis has been limited to production settings under deterministic demand. In this paper, we consider a periodic-review production-inventory model under stochastic demand and incorporate the following fixed-cost structure into our analysis. When the order quantity in a given period exceeds a specified threshold value, the system is assumed to be in a “warm” state and no fixed cost is incurred in the next period regardless of the order quantity; otherwise the system state is considered “cold” and a positive fixed cost is required to place an order. Assuming that the unsatisfied demand is lost, we develop a dynamic programming formulation of the problem and utilize the concepts of quasi-K-convexity and non-K-decreasing to show some structural results on the optimal cost-to-go functions. This analysis enables us to derive a partial characterization of the optimal policy under the assumption that the demands follow a Pólya or uniform distribution. The optimal policy is defined over multiple decision regions for each system state. We develop heuristic policies that are aimed to address the partially characterized decisions, simplify the ordering policy, and save computational efforts in implementation. The numerical experiments conducted on a large set of test instances including uniform, normal and Poisson demand distributions show that a heuristic policy that is inspired by the optimal policy is able to find the optimal solution in almost all instances, and that a so-called generalized base-stock policy provides quite satisfactory results under reasonable computational efforts. We use our numerical examples to generate insights on the impact of problem parameters. Finally, we extend our analysis into the infinite horizon setting and show that the structure of the optimal policy remains similar.     

Managing manufacturing risks by using capacity options

In this study, we investigate the strategy of increasing production capacity temporarily through contingent contractual agreements with short-cycle manufacturers to manage the risks associated with demand volatility. We view all these agreements as capacity options. More specifically, we consider a manufacturing company that produces a replenishment product that is sold at a retailer. The demand for the product switches randomly between a high level and a low level. The production system has enough capacity to meet the demand in the long run. However, when the demand is high, it does not have enough capacity to meet the instantaneous demand and thus has to produce to stock in advance. Alternatively, a contractual agreement with a short-cycle manufacturer can be made. This option gives the right to receive additional production capacity when needed. There is a fixed cost to purchase this option for a period of time and, if the option is exercised, there is an additional per unit exercise price which corresponds to the cost of the goods produced at the short-cycle manufacturer. We formulate the problem as a stochastic optimal control problem and analyse it analytically. By comparing the costs between two cases where the contract with the short-cycle manufacturer is used or not, the value of this option is evaluated. Furthermore, the effect of demand variability on this contract is investigated.     

Managing variances in manufacturing system design

The goal of this paper is to investigate how uncertainties in demand and production should be incorporated into manufacturing system design problems. We examine two problems in manufacturing system design: the resource allocation problem and the product grouping problem. In the resource allocation problem, we consider the issue of how to cope with uncertainties when we utilize two types of resources: actual processing capacity and stored capacity (inventory). A closed form solution of the optimal allocation scheme for each type of capacity is developed, and its performance is compared to that of the conventional scheme where capacity allocation and inventory control decisions are made sequentially. In the product grouping problem, we consider the issue of how we design production lines when each line is dedicated to a certain set of products. We formulate a mathematical program in which we simultaneously determine the number of production lines and the composition of each line. Two heuristics are developed for the problem.     

Asymptotic Analysis of a Greedy Heuristic for the Multi-Period Single-Sourcing Problem: The Acyclic Case

The multi-period single-sourcing problem that we address in this paper can be used as a tactical tool for evaluating logistics network designs in a dynamic environment. In particular, our objective is to find an assignment of customers to facilities, as well as the location, timing and size of production and inventory levels, that minimizes total assignment, production, and inventory costs. We propose a greedy heuristic, and prove that this greedy heuristic is asymptotically optimal in a probabilistic sense for the subclass of problems where the assignment of customers to facilities is allowed to vary over time. In addition, we prove a similar result for the subclass of problems where each customer needs to be assigned to the same facility over the planning horizon, and where the demand for each customer exhibits the same seasonality pattern. We illustrate the behavior of the greedy heuristic, as well as some improvements where the greedy heuristic is used as the starting point of a local interchange procedure, on a set of randomly generated test problems. These results suggest that the greedy heuristic may be asymptotically optimal even for the cases that we were unable to analyze theoretically.     

Newsvendor models with dependent random supply and demand

The newsvendor model is perhaps the most widely analyzed model in inventory management. In this single-period model, the only source of randomness is the demand during the period and one tries to determine the optimal order quantity in view of various cost factors. We consider an extention where supply is also random so that the quantity ordered is not necessarily received in full at the beginning of the period. Such models have been well-received in the literature with the assumption of independence between demand and supply. In this setting, we suppose that the random demand and supply are not necessarily independent. We focus on the resulting optimization problem and provide interesting characterizations on the optimal order quantity.     

A modification of the stochastic ruler method for discrete stochastic optimization

We propose a modified stochastic ruler method for finding a global optimal solution to a discrete optimization problem in which the objective function cannot be evaluated analytically but has to be estimated or measured. Our method generates a Markov chain sequence taking values in the feasible set of the underlying discrete optimization problem; it uses the number of visits this sequence makes to the different states to estimate the optimal solution. We show that our method is guaranteed to converge almost surely (a.s.) to the set of global optimal solutions. Then, we show how our method can be used for solving discrete optimization problems where the objective function values are estimated using either transient or steady-state simulation. Finally, we provide some numerical results to check the validity of our method and compare its performance with that of the original stochastic ruler method.     

Optimal policies for inventory systems with discretionary sales, random yield and lost sales

We determine replenishment and sales decisions jointly for an inventory system with random demand, lost sales and random yield. Demands in consecutive periods are independent random variables and their distributions are known. We incorporate discretionary sales, when inventory may be set aside to satisfy future demand even if some present demand may be lost. Our objective is to minimize the total discounted cost over the problem horizon by choosing an optimal replenishment and discretionary sales policy. We obtain the structure of the optimal replenishment and discretionary sales policy and show that the optimal policy for finite horizon problem converges to that of the infinite horizon problem. Moreover, we compare the optimal policy under random yield with that under certain yield, and show that the optimal order quantity （sales quantity） under random yield is more （less） than that under certain yield.     

Evaluating shortfall distributions in periodic inventory systems with stochastic endogenous demands and lead-times

This paper addresses a multi-period production/inventory problem with two suppliers, where demand sizes and supplier lead time are stochastic and correlated. A discrete time, single item inventory system is considered, where inventory levels are reviewed periodically and managed using a base-stock policy. At the end of each period, a replenishment order is placed, which enters a queue at the buffer stage and is consequently forwarded to the first available supplier. We present a mathematical model of this inventory system and determine optimal safety stock levels for it, in closed form, using matrix analytic techniques and the properties of phase type distributions. To account for the effect of order crossovers, which occur whenever replenishment orders do not arrive in the sequence in which they were placed, the inventory shortfall distribution is analyzed. Finally, a set of numerical experiments with a system with two suppliers is presented, where the proposed model is compared to other existing models.     

Likelihood robust optimization for data-driven problems

We consider optimal decision-making problems in an uncertain environment. In particular, we consider the case in which the distribution of the input is unknown, yet there is some historical data drawn from the distribution. In this paper, we propose a new type of distributionally robust optimization model called the likelihood robust optimization (LRO) model for this class of problems. In contrast to previous work on distributionally robust optimization that focuses on certain parameters (e.g., mean, variance, etc.) of the input distribution, we exploit the historical data and define the accessible distribution set to contain only those distributions that make the observed data achieve a certain level of likelihood. Then we formulate the targeting problem as one of optimizing the expected value of the objective function under the worst-case distribution in that set. Our model avoids the over-conservativeness of some prior robust approaches by ruling out unrealistic distributions while maintaining robustness of the solution for any statistically likely outcomes. We present statistical analyses of our model using Bayesian statistics and empirical likelihood theory. Specifically, we prove the asymptotic behavior of our distribution set and establish the relationship between our model and other distributionally robust models. To test the performance of our model, we apply it to the newsvendor problem and the portfolio selection problem. The test results show that the solutions of our model indeed have desirable performance.     

A stochastic programming approach for planning horizons of infinite horizon capacity planning problems

Planning horizon is a key issue in production planning. Different from previous approaches based on Markov Decision Processes, we study the planning horizon of capacity planning problems within the framework of stochastic programming. We first consider an infinite horizon stochastic capacity planning model involving a single resource, linear cost structure, and discrete distributions for general stochastic cost and demand data (non-Markovian and non-stationary). We give sufficient conditions for the existence of an optimal solution. Furthermore, we study the monotonicity property of the finite horizon approximation of the original problem. We show that, the optimal objective value and solution of the finite horizon approximation problem will converge to the optimal objective value and solution of the infinite horizon problem, when the time horizon goes to infinity. These convergence results, together with the integrality of decision variables, imply the existence of a planning horizon. We also develop a useful formula to calculate an upper bound on the planning horizon. Then by decomposition, we show the existence of a planning horizon for a class of very general stochastic capacity planning problems, which have complicated decision structure.     

A new distributionally robust p-hub median problem with uncertain carbon emissions and its tractable approximation method

The p-hub median problem is to determine the optimal location for p hubs and assign the remaining nodes to hubs so as to minimize the total transportation costs. Under the carbon cap-and-trade policy, we study this problem by addressing the uncertain carbon emissions from the transportation, where the probability distributions of the uncertain carbon emissions are only partially available. A novel distributionally robust optimization model with the ambiguous chance constraint is developed for the uncapacitated single allocation p-hub median problem. The proposed distributionally robust optimization problem is a semi-infinite chance-constrained optimization model, which is computationally intractable for general ambiguity sets. To solve this hard optimization model, we discuss the safe approximation to the ambiguous chance constraint in the following two types of ambiguity sets. The first ambiguity set includes the probability distributions with the bounded perturbations with zero means. In this case, we can turn the ambiguous chance constraint into its computable form based on tractable approximation method. The second ambiguity set is the family of Gaussian perturbations with partial knowledge of expectations and variances. Under this situation, we obtain the deterministic equivalent form of the ambiguous chance constraint. Finally, we validate the proposed optimization model via a case study from Southeast Asia and CAB data set. The numerical experiments indicate that the optimal solutions depend heavily on the distribution information of carbon emissions. In addition, the comparison with the classical robust optimization method shows that the proposed distributionally robust optimization method can avoid over-conservative solutions by incorporating partial probability distribution information. Compared with the stochastic optimization method, the proposed method pays a small price to depict the uncertainty of probability distribution. Compared with the deterministic model, the proposed method generates the new robust optimal solution under uncertain carbon emissions.