Operations & Supply Chain Management

Heuristic solution methods for combinatorial optimization problems are often based on local neighborhood searches. These tend to get trapped in a local optimum and the final result is often heavily dependent on the starting solution. Simulated annealing methods attempt to avoid these problems by randomizing the procedure so as to allow for occasional changes that worsen the solution. In this paper we provide probabilistic analyses of different designs of these methods.

We consider a class of loss systems with exponential service times and a Poisson arrival process with a rate that varies periodically among N levels called seasons. For two special cases, we derive transient and steady-state solutions and provide simple proofs that losses are minimized when the arrival rates for all seasons are equal. In the general case, we describe a straightforward procedure to derive the steady-state probabilities. We also prove that when S=1, the server is generally busier during the high arrival rate seasons.

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.