Minimization of expected variance of completion times on single machine for stochastic jobs

This article deals with the problem of scheduling jobs with random processing times on single machine in order to minimize the expected variance of job completion times. Sufficient conditions for the existence of V-shaped optimal sequences are derived separately for general and ordered job processing times. It is shown that when coefficient of variation of random processing times are bounded by a certain value, an optimal sequence is V-shaped. © 1997 John Wiley & Sons, Inc.     

A fast infiltration game on n arcs

Starting from a safe base, an Infiltrator tries to reach a sensitive zone within a given time limit without being detected by a Guard. The Infiltrator can move with speed at most u, while the Guard can only perform a restricted number of searches. A discrete variant of this zero-sum game played on a graph consisting of two vertices joined by n nonintersecting arcs is investigated. Optimal strategies and an explicit expression for its value are obtained. © 1996 John Wiley & Sons, Inc.     

A one-dimensional helicopter-submarine game

The article considers a two-person zero-sum game in which a searcher with b bombs wishes to destroy a mobile hider. The players are restricted to move on a straight line with maximum speeds v and u satisfying v > u > 0; neither player can see the other but each knows the other's initial position. The bombs all have destructive radius R and there is a time lag T between the release of a bomb and the bomb exploding. The searcher gets 1 unit if the hider is destroyed and 0 if he survives. A solution is given for b = 1, and extended to b > 1 when the time lag is small. Various applications of the game are discussed.     

Some two-on-two homogeneous stochastic combats

In this article we consider two versions of two-on-two homogeneous stochastic combat and develop expressions, in each case, for the state probabilities. The models are natural generalizations of the exponential Lanchester square law model. In the first version, a marksman whose target is killed resumes afresh the killing process on a surviving target; in the second version, the marksman whose target is killed merely uses up his remaining time to a kill on a surviving target. Using the state probabilities we then compute such important combat measures as (1) the mean and variance of the number of survivors as they vary with time for each of the sides, (2) the win probabilities for each of the sides, and (3) the mean and variance of the battle duration time. As an application, computations were made for the specific case of a gamma (2) interfiring time random variable for each side and the above combat measures were compared with the appropriate exponential and deterministic Lanchester square law approximations. The latter two are shown to be very poor approximations in this case.     

Transportation type problems with quantity discounts

It is known to be real that the per unit transportation cost from a specific supply source to a given demand sink is dependent on the quantity shipped, so that there exist finite intervals for quantities where price breaks are offered to customers. Thus, such a quantity discount results in a nonconvex, piecewise linear functional. In this paper, an algorithm is provided to solve this problem. This algorithm, with minor modifications, is shown to encompass the “incremental” quantity discount and the “fixed charge” transportation problems as well. It is based upon a branch-and-bound solution procedure. The branches lead to ordinary transportation problems, the results of which are obtained by utilizing the “cost operator” for one branch and “rim operator” for another branch. Suitable illustrations and extensions are also provided.     

Armor configurations via dynamic programming

The problem of selecting materials, their thicknesses and order for armor designed for the defeat of shaped charge threats, has been formulated as a constrained optimization problem. The mathematical model provides an optimal order and thickness of each layer of material such that the resulting armor configuration will be of minimum mass per unit area subject to constraints on total thickness and shaped charge jet tip exit velocity.     

The two-on-one stochastic duel

The one-on-one stochastic duel is extended to the general two-on-one duel for the first time. The state equations, win probabilities, mean value, and variance functions are derived. The case where one side has Erlang (2) firing times and the other is negative exponential is compared with the corresponding “Stochastic Lanchester” and Lanchester models to demonstrate their nonequivalence.