Operations & Supply Chain Management

A nonstationary Markov chain is weakly ergodic if the dependence on the state distribution on the starting state vanishes as time tends to infinity. A chain is strongly ergodic if it is weakly ergodic and converges in distribution. In this paper we show that the two ergodicity concepts are equivalent for finite chains under rather general (and widely verifiable) conditions. We discuss applications to probabalistic analyses of general search methods for combinatorial optimization problems (simulated annealing).

Based on observations made during an extensive study of police patrol operations in New York City, we examine the issues of the validity and utility of queueing models of service systems in which adaptive behavior by the (human) customers or servers is likely. We find that in addition to depending on the technical accuracy of its assumptions, the accuracy of such a model will also depend upon the level of managerial control of the system and adequacy of resources.

Most quantities of interest in discounted and undiscounted (semi-) Markov decision processes can be obtained by solving a system of functional equations. This paper derives bounds and variational characterizations for the solutions of such systems.

This paper considers a single-item, periodic-review inventory model with uncertain demands. In contrast to prior treatments of this problem we assume a finite production capacity per period. Assuming stationary data, a convex one-period cost function and a discrete demand distribution, we show (under a few additional unrestrictive assumptions) that a modified base-stock policy is optimal under the average-cost criterion; in addition, we characterize the optimal base-stock level.

This paper considers a single-item, periodic review inventory model with uncertain demands. We assume a finite production capacity in each period. With stationary data, a convex one-period cost function and a continuous demand distribution, we show (under a few additional unrestrictive assumptions) that a modified basic-stock policy is optimal under the discounted cost criterion, both for finite and infinite planning horizons. In addition we characterize the optimal base-stock levels in several ways.

We consider the problem of scheduling n jobs, each with a specific processing requirement, release time and due date on m uniform parallel machines. It is shown that a feasible schedule can be obtained by determining the maximum flow in a network, thus permitting the use of standard network flow codes. Using a specialized maximum flow procedure, the complexity reduces to O(tn3) operations when t is the number of distinct machine types.

This paper presents an allocation model for a perishable product, distributed from a regional center to a given set of locations with random demands. We consider the combined problem of allocating the available inventory at the center while deciding how these deliveries should be performed. Two types of delivery patterns are analyzed: the first pattern assumes that all demand points receive individual deliveries; the second pattern subsumes the frequently occuring case in which deliveries in multistop routes traveled by a fleet of vehicles. Computational experience is reported.

In many resource allocation problems, the objective is to allocate discrete resource units to a set of activities so as to maximize a concave objective function subject to upper bounds on the total amounts allotted to certain groups of activities. If the constraints determine a polymatroid and the objective is linear, it is well known that the greedy procedure results in an optimal solution. In this paper we extend this result to objectives that are "weakly concave," a property generalizing separable concavity.