Search

In today's business environment, unpredictable economic and noneconomic forces can affect firms' operational costs and discount factors, as well as demand. In this paper, we incorporate these uncertainties into a single-product, periodic-review, finite-horizon stochastic inventory system by modeling operational costs, discount factors, and demands as stochastic processes that evolve over time. We study three stockout protocols and establish conditions under which (s, S) inventory policies are optimal when discount factors, operational costs, and demands are stochastic and correlated both to one another and over time. Examples are provided to demonstrate nontrivial optimal policies in the absence of these sufficient conditions. [ABSTRACT FROM AUTHOR]

We develop multidimensional balancing algorithms to compute provably near-optimal capacity-expansion policies. Our approach is computationally efficient and guaranteed to produce a policy with total expected cost of no more than twice that of an optimal policy. We overcome the curse of dimensionality by introducing novel cost-separation schemes to separate the lost-sales cost of the system into exact monotonic subparts. This is the first approximation technique for multimachine, multiproduct systems facing stochastic, nonstationary, and correlated demands. To show the generality of this separation technique, we apply it to the capacity-expansion problem under two different production planning models: monotone production and revenue-maximizing production. We make the assumptions of minimal inventory and lost sales. [ABSTRACT FROM AUTHOR]

We develop the first algorithmic approach to compute provably good ordering policies for a multiperiod, capacitated, stochastic inventory system facing stochastic nonstationary and correlated demands that evolve over time. Our approach is computationally efficient and guaranteed to produce a policy with total expected cost no more than twice that of an optimal policy. As part of our computational approach, we propose a novel scheme to account for backlogging costs in a capacitated, multiperiod environment. Our cost-accounting scheme, called the forced marginal backlogging cost-accounting scheme, is significantly different from the period-by-period accounting approach to backlogging costs used in dynamic programming; it captures the long-term impact of a decision on system performance in the presence of capacity constraints. In the likely event that the per-unit order costs are large compared to the holding and backlogging costs, a transformation of cost parameters yields a significantly improved guarantee. We also introduce new semi myopic policies based on our new cost-accounting scheme to derive bounds on the optimal base-stock levels. We show that these bounds can be used to effectively improve any policy. Finally, empirical evidence is presented that indicates that the typical performance of this approach is significantly stronger than these worst-case guarantees. [ABSTRACT FROM AUTHOR]

In this paper, we consider two fundamental inventory models, the single-period newsvendor problem and its multiperiod extension, but under the assumption that the explicit demand distributions are not known and that the only information available is a set of independent samples drawn from the true distributions. Under the assumption that the demand distributions are given explicitly, these models are well studied and relatively straightforward to solve. However, in most real-life scenarios, the true demand distributions are not available, or they are too complex to work with. Thus, a sampling-driven algorithmic framework is very attractive, both in practice and in theory. We shall describe how to compute sampling-based policies, that is, policies that are computed based only on observed samples of the demands without any access to, or assumptions on, the true demand distributions. Moreover, we establish bounds on the number of samples required to guarantee that, with high probability, the expected cost of the sampling-based policies is arbitrarily close (i.e., with arbitrarily small relative error) compared to the expected cost of the optimal policies, which have full access to the demand distributions. The bounds that we develop are general, easy to compute, and do not depend at all on the specific demand distributions. [ABSTRACT FROM AUTHOR]

We consider two classical stochastic inventory control models, the periodic-review stochastic inventory control problem and the stochastic lot-sizing problem. The goal is to coordinate a sequence of orders of a single commodity, aiming to supply stochastic demands over a discrete, finite horizon with minimum expected overall ordering, holding, and backlogging costs. In this paper, we address the important problem of finding computationally efficient and provably good inventory control policies for these models in the presence of correlated, nonstationary (time-dependent), and evolving stochastic demands. This problem arises in many domains and has many practical applications in supply chain management. Our approach is based on a new marginal cost accounting scheme for stochastic inventory control models combined with novel cost-balancing techniques. Specifically, in each period, we balance the expected cost of overordering (i.e., costs incurred by excess inventory) against the expected cost of underordering (i.e., costs incurred by not satisfying demand on time). This leads to what we believe to be the first computationally efficient policies with constant worst-case performance guarantees for a general class of important stochastic inventory control models. That is, there exists a constant C such that, for any instance of the problem, the expected cost of the policy is at most C times the expected cost of an optimal policy. In particular, we provide a worst-case guarantee of two for the periodic-review stochastic inventory control problem and a worst-case guarantee of three for the stochastic lot-sizing problem. Our results are valid for all of the currently known approaches in the literature to model correlation and nonstationarity of demands over time. [ABSTRACT FROM AUTHOR]

We consider several classical models in deterministic inventory theory: the single-item lot-sizing problem, the joint replenishment problem, and the multistage assembly problem. These inventory models have been studied extensively, and play a fundamental role in broader planning issues, such as the management of supply chains. For each of these problems, we wish to balance the cost of maintaining surplus inventory for future demand against the cost of replenishing inventory more frequently. For example, in the joint replenishment problem, demand for several commodities is specified over a discrete finite planning horizon, the cost of maintaining inventory is linear in the number of units held, but the cost incurred for ordering a commodity is independent of the size of the order; furthermore, there is an additional fixed cost incurred each time a nonempty subset of commodities is ordered. The goal is to find a policy that satisfies all demands on time and minimizes the overall holding and ordering cost. We shall give a novel primal-dual framework for designing algorithms for these models that significantly improve known results in several ways: the performance guarantees for the quality of the solutions improve on or match previously known results; the performance guarantees hold under much more general assumptions about the structure of the costs, and the algorithms and their analysis are significantly simpler than previous known results. Finally, our primal-dual framework departs from the structure of previously studied primal-dual approximation algorithms in significant ways, and we believe that our approach may find applications in other settings. More specifically, we provide 2-approximation algorithms for the joint replenishment problem and for the assembly problem, and solve the single-item lot-sizing problem to optimality. The results for the joint replenishment and the lot-sizing problems also hold for their generalizations with back orders allowed. As a byproduct of our work, we prove known and new upper bounds on the integrality gap of some linear-programming (LP) relaxations of the abovementioned problems. [ABSTRACT FROM AUTHOR]

We consider multiunit Vickrey auctions for procurement in supply chain settings. This is the first paper that incorporates transportation costs into auctions in a complex supply network. We first introduce an auction mechanism that makes simultaneous production and transportation decisions so that the total supply chain cost is minimized and induces truth telling from the suppliers. Numerical study shows that considerable supply chain cost savings can be achieved if production and transportation costs are considered simultaneously. However, the buyer's payments in such auctions can be high. We then develop a new Vickrey-type auction that incorporates the buyer's reservation price function into quantity allocation and payment decision. As a result, the buyer has some control over his payments at the expense of introducing uncertainty in the quantity acquired in the auction. [ABSTRACT FROM AUTHOR]

We consider a single-location inventory system with periodic review and stochastic demand. It places replenishment orders to raise the inventory position--that is, inventory on hand plus inventory in transit--to exactly S at the beginning of every period. The lead time associated with each of these orders is random. However, the lead-time process is such that these orders do not cross. Demand that cannot be met with inventory available on hand is lost permanently. We state and prove some sample-path properties of lost sales, inventory on hand at the end of a period, and inventory position at the end of a period as functions of S. The main result is the convexity of the expected discounted sum of holding and lost-sales costs as a function of S. This result justifies the use of common search procedures or linear programming methods to determine optimal base-stock levels for inventory systems with lost sales and stochastic lead times. It should be noted that the class of base-stock policies is suboptimal for such systems, and we are primarily interested in them because of their widespread use. [ABSTRACT FROM AUTHOR]

Proposes a model for multiple resource types used for multiple product families. Mathematical formulation of the strategic capacity planning problem; Discussion on demand modeling; Calculation of the expected value of the instantaneous lost sales cost; Outline of an efficient divide-and-conquer algorithm.

Evaluates the capacity planning practices of the semiconductor industry using an optimal capacity planning technique. Cost effects for capacity expansion; Cost implications of capacity planning heuristics; Sensitivity of costs to the frequency of forecasting and planning.

In the semiconductor industry many critical decisions are basal on demand forecasts. However, these forecasts are subject to random error. In this paper we lay out a scheme estimating the variance and correlation of forecast errors (without altering given forecasts) and modeling the evolution of forecasts over time. Our scheme allows correlations across time, products and technologies. It also addresses the case of nonstationary errors due to ramps (technology migrations). It can he used to simulate chip demands for production planning capacity expansion studies. [ABSTRACT FROM AUTHOR]

We study the problem of determining production quantities in each period of an infinite horizon for a single item produced in a capacity-limited facility. The demand for the product is random, and it is independent and identically distributed from period to period. The demand is observed at the beginning of a time period, but it need not be filled until the end of the period. Unfilled demand is backordered. A base stock or order-up-to policy is used. The shortfall is the order-up-to level minus the inventory position. The inventory system is easily understood and managed if we know the distribution of the shortfall. We develop a new approximation for this distribution, and perform extensive computational tests of existing approximations. Our new approximation works extremely well as long as the coefficient of variation of the demand is less than two. For practical applications this is by far the most interesting case. No known approximations work well consistently when the coefficient of variation of the demand is greater than two. [ABSTRACT FROM AUTHOR]

We show that an O(n³ log n) algorithm can find optimal power-of-two lot size policies for finite production rate assembly systems. This improves an O(n5) algorithm proposed in D. Atkins, M. Queyranne and D. Sun's 1992 paper. [ABSTRACT FROM AUTHOR]

We consider a multistage, multiproduct production/inventory system in discrete time. When an order is placed for a component it is instantly delivered, and the required amounts of the components consumed in producing the given component are simultaneously withdrawn from their respective inventories. External demand occurs for a single component. We assume that the external demand for the component is nonconstant, deterministic, and must be met without backlogging. We propose two new cluster-based heuristics for this problem. We will show that the first of these heuristics has a wont-case relative cost that is between 1.44 and 2, and the second of these heuristics has a worst-case relative cost of 2. Computational tests indicate that, on the avenge, these heuristics are within 0.7% and 1.3% of optimal, respectively, and that their performance is very insensitive to the size of the system and to other input parameters. [ABSTRACT FROM AUTHOR]

In this paper, we address the problem of scheduling a number of jobs on a bank of parallel machines to minimize the total weighted tardiness, under the assumption that the weight of each job is proportional to its processing time. The version of the problem that has general weights has been shown to be strongly NP-complete. We prove this version of the problem to be NP-complete, and give a pseudopolynomial time algorithm for solving it. We study a family of simple sequencing rules in which the jobs are sequenced in increasing order of gamma[sub l] = d[sub l] - theta p[sub l], where d, is the due date of job i, p[sub l] its processing time, w[sub l] its weight, and 0 less than or equal to theta less than or equal to 1. This family of sequencing rules generalizes the earliest due date sequencing rule. We obtain bounds on the ratio [C[sub gamma] x C[sup *]]/[SIGMA[sub i]w[sub i]p[sub l]], where C[sub gamma] and C[sup *] are the costs of the heuristic and optimal schedules, respectively. The denominator is the cost of having each job be late by its own processing time. It is intended to measure what is or is not a large deviation from optimality, in absolute rather than relative terms, for the problem at hand. We also report on the results of computational experiments. [ABSTRACT FROM AUTHOR]

In this paper we study the problem of coordinating the purchase and shipment of I items in a one-warehouse, N-retailer inventory system. The model includes positive echelon holding costs, fixed costs for ordering and shipping each item, and a fixed joint item order cost at each retailer. Demand for each item at each retailer is assumed to occur at a constant and continuous rate. A mathematical model is developed based on these assumptions and the assumption that a stationary nested policy is followed. An efficient algorithm is presented based on the problem's structure that involves only sorting and runs in O(NI log NI) time. The cost of the policy computed is proven to be within 6% of the cost of an optimal nested policy. An example is presented to illustrate the problem structure and the proposed algorithm. [ABSTRACT FROM AUTHOR]

An extension of the Economic Order Quantity (EOQ) model to multi-stage production-distribution systems and the isotonic regression problem are known to be equivalent and to be solvable in O(N4) time. The following specializations of the model are solvable in O(N log N) time: joint replenishment systems, pure assembly systems, nested policies in pure distribution systems, nonnested policies in one-warehouse multi-retailer systems, nested policies in multi-item, one-warehouse, multi-retailer systems, and systems in which the underlying network is a series-parallel digraph. We show here that a generalization of this problem is solvable in O(N log N) time whenever the undirected version of the underlying network is a tree. The algorithm we propose is used as a subroutine in an algorithm solving the EOQ problem on general circuitless directed graphs, the subject of a companion paper. [ABSTRACT FROM AUTHOR]

Most past approaches to job shop scheduling are either highly myopic, or they are unable to adapt effectively to the stream of unforeseen disruptions that characterizes almost all manufacturing systems. We propose a two-module scheduling system that is both robust and non-myopic. Periodically a Planning Module develops a global view of what is likely to happen in the facility over the next one to four weeks. It then passes information down to the Dispatching Module. The Dispatching Module is based on microprocessors that are located on the factory floor. Whenever a machine is about to become idle, a fast optimization algorithm is run on the closest microprocessor to decide which job should be done next. The data provided by the Planning Module allows this decision to be made in a non-myopic manner. [ABSTRACT FROM AUTHOR]