Bayes sequential strategies for crossing a field containing absorption points

A sequential decision problem is considered in which N particles have to cross a given field. Two alternative crossing paths are available. An unknown number of absorption points J₁ and J₂ are planted at each of the crossing paths. The bivariate prior distribution of (J₁,J₂) is given. If a particle passes close to an absorption point it may survive with probability s, 0 < s < 1. If a particle is absorbed, both the particle and the absorption point are ruined. There is no replacement of ruined absorption points. All absorption points act independently. The particles crciss the field in a consecutive order, and a crossing path can be chosen for each particle. The objective is to maximize the expected number of survivors. The Bayes sequential procedure is characterized. The csmditions under which the Bayes strategy is determined by the maximal posterior survival probabilities are specified.     

Estimating critical path and arc probabilities in stochastic activity networks

This article describes a new procedure for estimating parameters of a stochastic activity network of N arcs. The parameters include the probability that path m is the longest path, the probability that path m is the shortest path, the probability that arc i is on the longest path, and the probability that arc i is on the shortest path. The proposed procedure uses quasirandom points together with information on a cutset ? of the network to produce an upper bound of O[(log K)^N?|?|+1/K] on the absolute error of approximation, where K denotes the number of replications. This is a deterministic bound and is more favorable than the convergence rate of 1/K^1/2 that one obtains from the standard error for K independent replications using random sampling. It is also shown how series reduction can improve the convergence rate by reducing the exponent on log K. The technique is illustrated using a Monte Carlo sampling experiment for a network of 16 relevant arcs with a cutset of ? = 7 arcs. The illustration shows the superior performance of using quasirandom points with a cutset (plan A) and the even better performance of using quasirandom points with the cutset together with series reduction (plan B) with regard to mean square error. However, it also shows that computation time considerations favor plan A when K is small and plan B when K is large.     

On the optimal detection of an underwater intruder in a channel using unmanned underwater vehicles

Given a number of patrollers that are required to detect an intruder in a channel, the channel patrol problem consists of determining the periodic trajectories that the patrollers must trace out so as to maximized the probability of detection of the intruder. We formulate this problem as an optimal control problem. We assume that the patrollers' sensors are imperfect and that their motions are subject to turn‐rate constraints, and that the intruder travels straight down a channel with constant speed. Using discretization of time and space, we approximate the optimal control problem with a large‐scale nonlinear programming problem which we solve to obtain an approximately stationary solution and a corresponding optimized trajectory for each patroller. In numerical tests for one, two, and three underwater patrollers, an underwater intruder, different trajectory constraints, several intruder speeds and other specific parameter choices, we obtain new insight—not easily obtained using simply geometric calculations—into efficient patrol trajectory design under certain conditions for multiple patrollers in a narrow channel where interaction between the patrollers is unavoidable due to their limited turn rate.© 2011 Wiley Periodicals, Inc. Naval Research Logistics, 2011     

Minimizing the sum of absolute lateness in single-machine and multimachine scheduling

Kanet addressed the problem of scheduling n jobs on one machine so as to minimize the sum of absolute lateness under a restrictive assumption on their common due date. This article extends the results to the problem of scheduling n jobs on m parallel identical processors in order to minimize the sum of absolute lateness. Also, a heuristic algorithm for a more general version with no restriction on the common due date, for the problem of n-job single-machine scheduling is presented and its performance is reported.     

Some branch-and-bound procedures for fixed-cost transportation problems

In this article we present three properties that will improve the performance of branch-and-bound algorithms for fixed-cost transportation problems. By applying Lagrangian relaxation we show that one can develop stronger up and down penalties than those traditionally used and also develop a strengthened penalty for nonbasic variables. We also show that it is possible to “look ahead” of a particular node and determine the solution at the next node without actually calculating it. We present computational evidence by comparing our developments with existing procedures.     

Simulation of nonhomogeneous poisson processes by thinning

A simple and relatively efficient method for simulating one-dimensional and two-dimensional nonhomogeneous Poisson processes is presented The method is applicable for any rate function and is based on controlled deletion of points in a Poisson process whose rate function dominates the given rate function In its simplest implementation, the method obviates the need for numerical integration of the rate function, for ordering of points, and for generation of Poisson variates.