The Markov decision problem of locating a policy to maximize the long-run average reward subject to K long-run average cost constraints is considered. It is assumed that the state and action spaces are finite and the law of motion is unichain, that is, every pure policy gives rise to a Markov chain with one recurrent class. It is first proved that there exists an optimal stationary policy with a degree of randomization no greater than K; consequently, it is never necessary to randomize in more than K states. A linear program produces the optimal policy with limited randomization. For the special case of a single constraint, we also address the problem of finding optimal nonrandomized, but nonstationary, policies. We show that a round-robin type policy is optimal, and conjecture the same for a steering policy that depends on the entire past history of the process, but whose implementation requires essentially no more storage than that of a pure policy.

A general approach to testing for initialization bias in the mean of a simulation output series is presented. The output is transformed into a standardized test sequence that can be contrasted with a known limiting stochastic process. This transformation requires very little computation and the asymptotic theory is applicable to a wide variety of simulations. An initialization bias test is developed and several examples of its application are presented.

This note shows that the assignment and sequencing of single-operation jobs in a parallel-machine environment can be formulated as an assignment problem. Means for reducing the size and computational difficulty of this problem are identified.

We develop a family of rollout policies based on fixed routes to obtain dynamic solutions to the vehicle routing problem with stochastic demand and duration limits (VRPSDL). In addition to a traditional one-step rollout policy, we leverage the notions of the pre- and post-decision state to distinguish two additional rollout variants. We tailor our rollout policies by developing a dynamic decomposition scheme that achieves high quality solutions to large problem instances with reasonable computational effort. Computational experiments demonstrate that our rollout policies improve upon the performance of a rolling horizon procedure and commonly employed fixed-route policies, with improvement over the latter being more substantial.

This paper considers the problem of determining the mean and distribution of the length of a minimal spanning tree (MST) on an undirected graph whose arc lengths are independently distributed random variables. We obtain bounds and approximations for the MST length and show that our upper bound is much tighter than the naive bound obtained by computing the MST length of the deterministic graph with the respective means as arc lengths. We analyze the asymptotic properties of our approximations and establish conditions under which our bounds are asymptotically optimal. We apply these results to a network provisioning problem and show that the relative error induced by using our approximations tends to zero as the graph grows large.

This paper discusses a highly effective heuristic procedure for generating optimum and near-optimum solutions for the symmetric traveling-salesman problem. The procedure is based on a general approach to heuristics that is believed to have wide applicability in combinatorial optimization problems. The procedure produces optimum solutions for all problems tested, “classical” problems appearing in the literature, as well as randomly generated test problems, up to 110 cities. Run times grow approximately as n2; in absolute terms, a typical 100-city problem requires less than 25 seconds for one case (GE635), and about three minutes to obtain the optimum with above 95 per cent confidence.

The optimum routing of a fleet of trucks of varying capacities from a central depot to a number of delivery points may require a selection from a very large number of possible routes, if the number of delivery points is also large. This paper, after considering certain theoretical aspects of the problem, develops an iterative procedure that enables the rapid selection of an optimum or near-optimum route. It has been programmed for a digital computer but is also suitable for hand computation.

The multiple vehicle routing problem with time windows (VRPTW) is a hard and extensively studied combinatorial optimization problem. This paper considers a dynamic VRPTW with stochastic customers, where the goal is to maximize the number of serviced customers. It presents a multiple scenario approach (MSA) that continuously generates routing plans for scenarios including known and future requests. Decisions during execution use a distinguished plan chosen, at each decision, by a consensus function. The approach was evaluated on vehicle routing problems adapted from the Solomon benchmarks with a degree of dynamism varying between 30% and 80%. They indicate that MSA exhibits dramatic improvements over approaches not exploiting stochastic information, that the use of consensus function improves the quality of the solutions significantly, and that the benefits of MSA increase with the (effective) degree of dynamism.

A method is presented for ranking multiattributed alternatives using a weighted-additive evaluation function with partial information about the weighting (scaling) constants, the method is applied to evaluate materials for use in nuclear waste containment. The paper derives conditions to determine whether a pair of alternatives can be ranked given the partial information about weighting constants, and presents an algorithm that partially rank-orders the complete set of alternatives based on the pairwise ranking information.

Quantitative decision analysis techniques are applied to a particular problem of bargaining and negotiation: How should a negotiating team representing the United States prepare for an international conference on tanker safety and pollution prevention? The negotiating team had a short time to prepare for the Conference, which was to consider a number of complex and difficult measures on which there were considerable differences of opinion. The analytic approach used focused on a multiattribute value model that incorporated the views of many of the negotiating countries. This model was refined over the preparation period by both analysts and negotiators. The U.S. negotiators found that the model was useful for evaluating alternative proposals, anticipating and understanding the negotiating positions of other countries, generating promising compromise proposals, and communicating with other U.S. interest groups. The modeling effort helped the negotiators to identify a compromise proposal very similar to the one finally adopted by the Conference. As a result of the Conference important new international measures to improve the safety of oil tankers and help prevent pollution of the seas from ships were adopted.