Operations & Supply Chain Management

In the classical maximal flow problem, the objective is to maximize the supply to a single sink in a capacitated network. In this paper we consider general capacitated networks with multiple sinks: the objective is to optimize a general "concave" preference relation on the set of feasible supply vectors. We show that an optimal solution can be obtained by a marginal allocation procedure. An efficient implementation results in an adaptation of the augmenting path algorithm. We also discuss an application of the procedure for an investment company that deals in oil and gas ventures.

Rational restrictions are derived for the values of American options on futures contracts. For these options, the optimal policy, in general, involves premature exercise. A model is developed for valuing options on futures contracts in a constant interest rate setting. Despite the fact that premature exercise may be optimal, the value of this American feature appears to be small and a European formula due to Black serves as a useful approximation. Finally, a model is developed to value these options in a world with stochastic interest rates.

Special algorithms have been developed to compute an optimal (s,S) policy for an inventory model with discrete demand and under standard assumptions (stationary data, a well-behaved one-period cost function, full backlogging and the average cost criterion). We present here an iterative algorithm for continuous demand distributions which avoids any form of prior discretization. The method can be viewed as a modified form of policy iteration applied to a Markov decision process with continuous state space. For phase-type distributions, the calculations can be done in closed form.

We consider a queueing system with two types of servers and two types of customers. General-use servers can provide service to either customer type while limited-use servers can be used only for one of the two. Though the apparent Markovian state space of this system is five-dimensional, we show that an aggregation results in an exact two-dimensional representation that is also Markovian. Matrix geometric theory is used to obtain approximations for the mean delay times and other measures of interest for each customer type.

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.

We examine a queueing system with multiple primary servers and a fewer number of auxiliary servers. There are two classes of customers—those who require service from a primary server working alone and those who require service from a primary server who is assisted by an auxiliary server. Though the apparent Markovian state space is five-dimensional, we show that an aggregation results in an exact two-dimensional representation which is Markovian. Matrix geometric theory is used to obtain approximations for the mean delay and blocking probability of each customer type.

Many queueing situations such as computer, communications and emergency systems have the feature that customers may require service from several servers at the same time. They may thus be delayed until the required number of servers is avialable and servers may be idle when customers are waiting. We consider general server-completion-time distributions and derive approximation methods for the computation of the steady-state distribution of the number of customers in queue as well as the moments of the waiting-time distribution. Extensive computational results are reported.

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.