This paper establishes a simple existence proof for a solution to the optimality equations arising in finite undiscounted Markov Renewal Programs, by applying Brouwer's fixed point theorem to the so-called reduced value-iteration operator. Because of its simplicity, our approach lends itself to new existence results for more general models.
This paper presents a successive approximation method for solving systems of nested functional equations which arise, e.g., when considering Markov renewal programs in which policies that are maximal gain or optimal under more selective discount — and average overtaking optimality criteria are to be found. In particular, a successive approximation method is given to find the optimal bias vector and bias-optimal policies. Applications with respect to a number of additional stochastic control models are pointed out.
In many practical applications of multi-item inventory systems significant economies of scale can be exploited when coordinating replenishment orders for groups of items. This paper considers a continuous review multi-item inventory system with compound Poisson demand processes; excess demands are backlogged and each replenishment requires a lead time. There is a major setup cost associated with any replenishment of the family of items, and a minor (item dependent) setup cost when including a particular item in this replenishment. Moreover there are holding and penalty costs.
Consider a central depot (or plant) which supplies several locations experiencing random demands. Orders are placed (or production is initiated) periodically by the depot. The order arrives after a fixed lead time, and is then allocated among the several locations. (The depot itself does not hold inventory.) The allocations are finally received at the demand points after another lag. Unfilled demand at each location is backordered. Linear costs are incurred at each location for holding inventory and for backorders. Also, costs are assessed for orders placed by the depot.
Clark and Scarf [1960] characterize optimal policies in a two-echelon, two-location inventory model. We extend their result to the infinite-horizon case (for both discounted and average costs). The computations required are far easier than for the finite horizon problem. Further simplification is achieved for normal demands. We also consider the more interesting case of multiple locations at the lower echelon. We show that, under certain conditions, this problem can be closely approximated by a model with one such location.
This paper presents an algorithm to compute an optimal (s,S) policy under standard assumptions (stationary data, well-behaved one-period costs, discrete demand, full backlogging, and the average-cost criterion). The method is iterative, starting with an arbitrary, given (s,S) policy and converging to an optimal policy in a finite number of iterations. Any of the available approximations can thus be used as an initial solution. Each iteration requires only modest computations. Also, a lower bound on the true optimal cost can be computed and used in a termination test.
Consider a central depot that supplies several locations experiencing random demands. Periodically, the depot may place an order for exogenous supply. Orders arrive after a fixed leadtime, and are then allocated among the several locations. Each allocation reaches its destination after a further delay. We consider the special case where the penalty-cost/holding-cost ratio is constant over the locations. Several approaches are given to approximate the dynamic program describing the problem.
We address the combined problem of allocating a scarce resource among several locations, and planning deliveries using a fleet of vehicles. Demands are random, and holding and shortage costs must be considered in the decision along with transportation costs. We show how to extend some of the available methods for the deterministic vehicle routing problem to this case. Computational results using one such adaptation show that the algorithm is fast enough for practical work, and that substantial cost savings can be achieved with this approach.