The dynamic transportation problem: A survey

The dynamic transportation problem is a transportation problem over time. That is, a problem of selecting at each instant of time t, the optimal flow of commodities from various sources to various sinks in a given network so as to minimize the total cost of transportation subject to some supply and demand constraints. While the earliest formulation of the problem dates back to 1958 as a problem of finding the maximal flow through a dynamic network in a given time, the problem has received wider attention only in the last ten years. During these years, the problem has been tackled by network techniques, linear programming, dynamic programming, combinational methods, nonlinear programming and finally, the optimal control theory. This paper is an up-to-date survey of the various analyses of the problem along with a critical discussion, comparison, and extensions of various formulations and techniques used. The survey concludes with a number of important suggestions for future work.     

A dynamic inventory system with recycling

This paper deals with a periodic review inventory system in which a constant proportion of stock issued to meet demand each period feeds back into the inventory after a fixed number of periods. Various applications of the model are discussed, including blood bank management and the control of reparable item inventories. We assume that on hand inventory is subject to proportional decay. Demands in successive periods are assumed to be independent identically distributed random variables. The functional equation defining an optimal policy is formulated and a myopic base stock approximation is developed. This myopic policy is shown to be optimal for the case where the feedback delay is equal to one period. Both cost and ordering decision comparisons for optimal and myopic policies are carried out numerically for a delay time of two periods over a wide range of input parameter values.     

Storage problems when demand is “all or nothing”

An inventory of physical goods or storage space (in a communications system buffer, for instance) often experiences “all or nothing” demand: if a demand of random size D can be immediately and entirely filled from stock it is satisfied, but otherwise it vanishes. Probabilistic properties of the resulting inventory level are discussed analytically, both for the single buffer and for multiple buffer problems. Numerical results are presented.     

Test selection for a mass screeening program

Periodic mass screening is the scheduled application of a test to all members of a population to provide early detection of a randomly occurring defect or disease. This paper considers periodic mass screening with particular reference to the imperfect capacity of the test to detect an existing defect and the associated problem of selecting the kind of test to use. Alternative kinds of tests differ with respect to their reliability characteristics and their cost per application. Two kinds of imperfect test reliability are considered. In the first case, the probability that the test will detect an existing defect is constant over all values of elapsed time since the incidence of the defect. In the second case, the test will detect the defect if, and only if, the lapsed time since incidence exceeds a critical threshold T which characterizes the test. The cost of delayed detection is an arbitrary increasing function (the “disutility function”) of the duration of the delay. Expressions for the long-run expected disutility per unit time are derived for the above two cases along with results concerning the best choice of type of test (where the decision rules make reference to characteristics of the disutility function).     

Techniques for establishing ergodic and recurrence properties of continuous-valued markov chains

We present techniques for classifying Markov chains with a continuous state space as either ergodic or recurrent. These methods are analogous to those of Foster for countable space chains. The theory is presented in the first half of the paper, while the second half consists of examples illustrating these techniques. The technique for proving ergodicity involves, in practice, three steps: showing that the chain is irreducible in a suitable sense; verifying that the mean hitting times on certain (usually bounded) sets are bounded, by using a “mean drift” criterion analogous to that of Foster; and finally, checking that the chain is such that bounded mean hitting times for these sets does actually imply ergodicity. The examples comprise a number of known and new results: using our techniques we investigate random walks, queues with waiting-time-dependent service times, dams with general and random-release rules, the s-S inventory model, and feedback models.     

The estimation of P(x < Y) for distributions useful in life testing

In this paper the reliability function K = P(X < Y) has been estimated when X and Y follow gamma, exponential or bivariate exponential distributions. The paper is partly expository.     

Estimation in single server queues

Moment and maximum likelihood estimates (m.l.e.'s) arc investigated for nonparametric and parametric models for a single server queue observed over a random time horizon, namely, up to the nth departure epoch. Also. m.l.e's of the mean interarrival time and mean service time in anM/M/1 queue observed over a fixed time-interval are studied Limit distributions of these estimates are obtained Without imposing steady state assumptions on the queue-size or waiting time processes.     

The search for an intelligent evader concealed in one of an arbitrary number of regions

This paper considers the search for an evader concealed in one of an arbitrary number of regions, each of which is characterized by its detection probability. We shall be concerned here with the double-sided problem in which the evader chooses this probability secretly, although he may not subsequently move; his aim is to maximize the expected time to detection, while the searcher attempts to minimize it. The situation where two regions are involved has been studied previously and reported on recently. This paper represents a continuation of this analysis. It is normally true that as the number of regions increases, optimal strategies for both searcher and evader are progressively more difficult to determine precisely. However it will be shown that, generally, satisfactory approximations to each are almost as easily derived as in the two region problem, and that the accuracy of such approximations is essentially independent of the number of regions. This means that so far as the evader is concerned, characteristics of the two-region problem may be used to assess the accuracy of such approximate strategies for problems of more than two regions.     

Optimal state-dependent pricing policies for a class of stochastic multiunit service systems

This paper models a k-unit service system (e.g., a repair, maintenance, or rental facility) with Poisson arrivals, exponential service times, and no queue. If we denote the number of units that are busy as the state of the system, the state-dependent pricing model formalizes the intuitive notion that when most units are idle, the price (i.e., the service charge per unit time) should be low, and when most units are busy, the price should be higher than the average. A computationally efficient algorithm based on a nonlinear programming formulation of the problem is provided for determination of the optimal state-dependent prices. The procedure ultimately reduces to the search on a single variable in an interval to determine the unique intersection point of a concave increasing function and a linear decreasing function. The algorithm takes, on the average, only about 1/2 second per problem on the IBM 360/65 (FORTRAN G Compiler). A discrete optimal-control approach to the problem is shown to result in essentially the same procedure as the nonlinear-programming formulation. Several properties of the optimal state-dependent prices are given. Comparisons of the optimal values of the objective function for the state-dependent and state-independent pricing policies show that the former is on the average, only about 0.7% better than the latter, which may explain partly why state-dependent pricing is not prevalent in many service systems. Potential generalizations of the model are discussed.