|
Article Excerpt
We show the optimality of state-dependent echelon base-stock policies in uncapacitated serial inventory systems with Markov-modulated demand and Markov-modulated stochastic lead times in the absence of order crossing. Our results cover finite-time horizon problems as well as infinite-time horizon formulations, with either a discounted or an average cost criterion. We employ a novel approach, based on a decomposition of the problem into a series of single-unit single-customer problems that are essentially decoupled. Besides providing a simple proof technique, this approach also gives rise to efficient algorithms for the calculation of the base-stock levels.
Subject classifications: inventory/production: multiechelon; inventory/production: policies: review/lead times.
Area of review: Manufacturing, Service, and Supply Chain Operations.
History: Received August 2001; revisions received March 2003, July 2006, September 2007, accepted October 2007.
1. Introduction
This paper deals with serial (multiechelon) inventory systems of the following type. There are M stages. Stage 1 receives stock from stage 2, stage 2 from stage 3, etc., and stage M receives stock from an outside supplier with ample stock. Demands originate at stage 1, unfilled demand is backlogged. There are holding, ordering, and backorder costs, and a central controller has the objective of minimizing these costs in the appropriate time frame.
In their seminal paper, Clark and Scraf (1960) characterize optimal policies for an uncapacitated serial inventory system. They consider finite-horizon problems and prove that echelon base-stock policies are optimal when the demands are independent identically distributed (i.i.d.) and the lead times between stages are deterministic. Their proof technique involves a decomposition of the multiechelon problem into a series of single-stage problems. This general approach guided much of the subsequent literature, and many extensions were obtained using the same stage-by-stage decomposition. In particular, Federgruen and Zipkin (1984) extend the results to the stationary infinite-horizon setting, and Chen and Zheng (1994) provide and alternative proof that is also valid in continuous time. Rosling (1989) shows that a general assembly system can be converted to an equivalent serial system. All of these papers assume i.i.d. demands and deterministic lead times.
In this paper, we study a system with Markov-modulated demands and stochastic a lead times. We assume that demands and lead times are stochastic and are affected (modulated) by an exogeneous Markov process. Such a model can capture many phenomena such as seasonalities, exchange rate variations, fluctuating market conditions, demand forecasts, etc. This type of demand model, where the distribution of demand depends on the state of a modulating Markov chain, is certainly not new to the inventory control literature. Song and Zipkin (1993), Beyer and Sethi (1997), Sethi and Cheng (1997), and Cheng and Sethi (1999) all investigate a single-stage system with such a demand model and prove the optimality of state-dependent (s, S) policies under different time horizon assumptions, with and without backlogging assumptions. Song and Zipkin (1992) and (1996a) evaluate the performance of base-stock policies in serial inventory systems, with state-independent and state-dependent policies, respectively. More recently, Chen and Song (2001) show the optimality of state-dependent echelon base-stock policies for serial systems with Markov-modulated demand and deterministic lead times, under an infinite-horizon average cost criterion. Markov-modulated demand is also considered by Parker and Kapuscinski (2004) in a capacitated setting.
The study of stochastic lead times in inventory control dates back to the early days of the literature. Hadley and Within (1963) investigate the subject for a single-stage problem, and suggest that two seemingly contradictory assumptions are needed-namely, that orders do not cross each other and that they are independent. Kaplan (1970) provides a simple model of stochastic lead times that prevents order crossing, while keeping the probability that an outstanding order arrives in the next time period independent of the current status of other outstanding order. He shows that the deterministic lead-time results carry over to his model of stochastic lead times. Nahmias (1979) and Ehrhardt (1984) streamlined Kaplan's results. Zipkin (1986) investigated stochastic lead times in continuous-time single-stage inventory models. Song and Zipkin (1996b) study a single-stage system with Markov modulated lead times. Svoronos and Zipkin (1991) evaluate one-for-one replenishment policies in the serial system setting. However, ever, we are not aware of any optimality results for serial systems under any type of stochastic lead times. Our stochastic lead-time model incorporates the same two important features of Kaplan's stochastic lead-time model, i.e., the absence of order crossing and the independence from the current status of other outstanding orders. In our model, just like in Kalpan's an exogeneous random variable determines which outstanding orders are going to arrive at a given stage. However, we additionally allow the stochastic lead time to depend on the state of a modulating Markov chain, and we also allow for dependencies between the lead-time random variables corresponding to different stages in the system.
The standard approach in multiechelon inventory theory is a decomposition into a series of single-stage problems. This approach, and especially the simplified and streamlined proof technique introduced by Veinott (1966), indeed does lead to many of the results and extensions discussed above. Nevertheless, our approach relies on a decomposition into a series of unit-customer pairs. Consider a single unit and a single customer. Assume that the distribution of time until the customer arrives to the system is known and that the goal is to move the unit through the system in a way that optimizes the holding versus backorder cost trade-off. Because only a single unit and a single customer are present, this problem is much simpler than the original one. We show that under the assumptions of this paper, the original problem is equivalent to a series of decoupled single-unit single-customer problems. This approach allows us to handle several extensions to the standard model in an intuitive manner, and provides an alternative to inductive arguments based on dynamic programming equations. The primary contribution of this paper is the formal proof of the decomposition of the serial inventory problem into essentially decoupled subproblems, each consisting of a single unit and a single customer.
A decomposition of the type employed here has been introduced in a series of paper by Axsater, although without bringing it to bear on the full-fledged dynamic programming formulation of the inventory control problem. Axsater (1990) observes that in a distribution system with a single depot and multiple retailers that follow base-stock policies, any particular unit ordered by retailer i is used to fill a particular future demand. He than matches this unit with that demand and evaluates the expected cost for this unit and "its demand." Using this approach, he develops an efficient method to evaluate the cost of a given base-stock policy for a two-echelon distribution system in continuous time with Poisson demand under the infinite-horizon average cost criterion. In Axsater (1993a), he extends this result to batch-ordering policies and in Axsater (1993b), he investigates. the system with periodic review, using the virtual allocation rule suggested by Graves (1996) and base-stock policy. As we show in this paper, Axsater's insight, when used properly, leads to the decomposition of the problem into single-unit single-customer problems, and provides a powerful technique for developing optimality results and algorithms for multiechelon systems.
A related work is the master thesis by Achy-Brou (2001) (supervised by the second author, concurrently with this work), who studies the single-unit single-customer subproblem for the case i.i.d. demands and deterministic lead times and a discounted cost criterion. This work formulates the subproblem as a dynamic programming algorithm, analyzes structural properties of the solutions, and discusses the relationship between the subproblem and base-stock policies in the overall inventory system.
We finally note that besides providing a simple proof technique, the decomposition into single-unit single customer subproblems leads to simple and efficient algorithms for calculating the base-stock levels. Even for several special cases of our model for which computational methods are already available, our algorithms are at least as efficient and provide an alternative method with potential advantages. These are listed at the end of [section]6, where the algorithms are presented.
The rest of the paper has six sections. Section 2 provides some background results on generic discrete-time decomposable dynamical systems. Section 3 provides a mathematical formulation of the problem and the necessary notation. Sections 4 and 5 contain the results for finite and infinite-horizon versions of the problem, respectively. Section 6 discusses the resulting algorithms for computing the optimal base-stock levels. Section 7 concludes the paper.
2. Preliminaries: Decomposable Systems
In this section we introduce the problem of optimal control of a decomposable system and point out the decoupled nature of the resulting optimal policies. The result we provide is rather obvious, but we find it useful to state it explicitly, both for ease of exposition and also because it is a key building block for our subsequent analysis.
Following the notation in Bertsekas (1995), w consider a generic stationary discrete-time dynamical system of the form
[x.sub.[t + 1]] = f([x.sub.t], [u.sub.t,], [w.sub.t]), t = 0,1...., T - 1 (1)
Here, [x.sub.t] is the state of the system at time t, [u.sub.t] a control to be applied at time t, [w.sub.t] a stochastic disturbance, and T is the time horizon. We assume that [x.sub.t], [u.sub.t], and [w.sub.t] are elements of give sets X, U, and W, respectively, and that f: X x U x W [right arrow] X is a given mapping. Finally, we assume that, given [x.sub.t] and [u.sub.t], the random variable [w.sub.t] is conditionally independent from the past and has a given conditional distribution.
We define a policy [pi] as a sequence of functions, [pi] = [[mu].sub.0], [[mu].sub.1],..., [[micro].sub.[T - 1]]), where each [[micro].sub.t]: X [right arrow] U maps the state x into a control u = [[micro].sub.t] (x). Let II be the set of all policies.
Given an initial state [x.sub.0] and a policy [pi], the sequence [x.sub.t] becomes a Markov chain with a well-defined probability distribution. For any time t < T and any state x [member of] X, we define the cost-to-go [J.sub.[t, T].sup.[pi]] (x) from time t until the end of the horizon by
[J.sub.[t, T].sup.[pi]](x) = E{[[T - 1].summation over ([tau] = 1)][[alpha].sup.[[tau] - t].g([x.sub.[tau]],[[mu].sub.[tau]]([x.sub.[tau]]))|[x.sub.t] = x},
where g: X x U [right arrow] [0,[infinity] is a given cost-per-stage function and [alpha] [member of] [0.1] is a discount factor. The optimal cost-to-go function [J*.sub.[t, T]] is defined by
[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]
(Note that [J.sub.[t, T].sup.[pi]] (x) and [J*.sub.[t, T]] can be infinite at certain states.) A policy [pi]* is said to be optimal if
[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]
When t = 0, we will use the simpler notation [J.sub.T.sup.[pi] (x) and [J*.sub.T] (x) instead of [J.sub.0,T.sup.[pi]] (x) [J*.sub.0.T] (x), respectively.
We now introduce the notion of a decomposable system. Loosely speaking, this is a system consisting of multiple by a common source of uncertainty, which evolves independently of the subsystems and is modulated by a Markov process [S.sub.t].
DEFINITION 2.1. A discrete-time dynamic programming problem of the form described above is said to be decomposable if it admits a representation with the following properties:
A1. The state space is a Cartesian product of the form X = S x [
.X] x [
.X], so that any x [member of] X can be represented as x = (s, [x.sup.1], [x.sup.2],...) with s [member of] S and [x.sup.i] [member of] [
.X], for every i [greater than or equal to] 1.
A2. There is a set [
.U] so that the control space U is the Cartesian product of countably many copies of [
.U], that is, any u [member of] U can be represented as u = [u.sup.1], [u.sup.2],...) with [u.sup.i] [member of] [
.U], for all i [greater than or equal to] 1.
A3....
|
