An algorithm and new penalties for concave integer minimization over a polyhedron

We present a branch-and-bound algorithm for globally minimizing a concave function over linear constraints and integer variables. Concave cost functions and integer variables arise in many applications, such as production planning, engineering design, and capacity expansion. To reduce the number of subproblems solved during the branch-and-bound search, we also develop a framework for computing new and existing penalties. Computational testing indicates that penalties based on the Tuy cutting plane provide large decreases in solution time for some problems. A combination of Driebeek-Tomlin and Tuy penalties can provide further decreases in solution time. © 1994 John Wiley & Sons, Inc.     

The survival probability function of a target moving along a straight line in a random field of obscuring elements

A target is moving along a straight-line path. Random portions of the path might be invisible to the hunter (in shadow). Shooting trials are conducted only along the visible segments of the path. An algorithm for the numerical determination of the survival probability of the target is developed. This algorithm is based on the distribution of shadow length, which is also developed. © 1994 John Wiley & Sons, Inc.     

Combination setwise-Bonferroni-type bounds

We consider three classes of lower bounds to P(c) = P (X₁ ≤ c₁,…, X_n ≤ c); Bonferroni-type bounds, product-type bounds and setwise bounds. Setwise probability inequalities are shown to be a compromise between product-type and Bonferroni-type probability inequalities. Bonferroni-type inequalities always hold. Product-type inequalities require positive dependence conditions, but are superior to the Bonferroni-type and setwise bounds when these conditions are satisfied. Setwise inequalities require less stringent positive dependence bound conditions than the product-type bounds. Neither setwise nor Bonferroni-type bounds dominate the other. Optimized setwise bounds are developed. Results pertaining to the nesting of setwise bounds are obtained. Combination setwise-Bonferroni-type bounds are developed in which high dimensional setwise bounds are applied and second and third order Bonferroni-type bounds are applied within each subvector of the setwise bounds. These new combination bounds, which are applicable for associated random variables, are shown to be superior to Bonferroni-type and setwise bounds for moving averages and runs probabilities. Recently proposed upper bounds to P(c) are reviewed. The lower and upper bounds are tabulated for various classes of multivariate normal distributions with banded covariance matrices. The bounds are shown to be surprisingly accurate and are much easier to compute than the inclusion-exclusion bounds. A strategy for employing the bounds is developed. © 1996 John Wiley & Sons, Inc.     

Longitudinal manpower planning models

A manpower planning model is presented that exploits the longitudinal stability of manpower cohorts. The manpower planning process is described. An infinite horizon linear program for calculating minimum cost manpower input plans is presented and found to have a straightforward solution in a great many cases and to yield an easily implemented approximation technique in other cases.     

Inventory models with a mixture of backorders and lost sales

This article presents several single-echelon, single-item, static demand inventory models for situations in which, during the stockout period, a fraction b of the demand is backordered and the remaining fraction 1 - b is lost forever. Both deterministic and stochastic demand are considered. although the case of stochastic demand is treated heuristically. In each situation, a mathematical model representing the average annual cost of operating the inventory system is developed. and an optimum operating policy derived. At the extremes b=1 and b=0 the models presented reduce to the usual backorders and lost sales cases, respectively.     

Parametric studies in transportation-type problems

In this paper we present some results in parametric studies on several transportation-type problems. Specifically, a characterization is obtained for the optimal values of the variables in the problem of determining an optimal growth path in a logistics system. We also derive an upper bound beyond which the optimal growth path remains the same. The results are then extended to the goal programming model and the prespecified market growth rate problem.     

Optimal maintenance models for systems subject to failure–A Review

This paper is a state-of-the-art review of the literature related to optimal maintenance models of systems subject to failure. The emphasis is on work appearing since the 1976 survey, “A Survey of Maintenance Models: The Control and Surveillance of Deteriorating Systems,” by W.P. Pierskalla and J.A. Voelker, published in this journal.     

A decomposable transshipment algorithm for a multiperiod transportation problem

A dynamic version of the transportation (Hitchcock) problem occurs when there are demands at each of n sinks for T periods which can be fulfilled by shipments from m sources. A requirement in period t₂ can be satisfied by a shipment in the same period (a linear shipping cost is incurred) or by a shipment in period t₁ < t₂ (in addition to the linear shipping cost a linear inventory cost is incurred for every period in which the commodity is stored). A well known method for solving this problem is to transform it into an equivalent single period transportation problem with mT sources and nT sinks. Our approach treats the model as a transshipment problem consisting of T, m source — n sink transportation problems linked together by inventory variables. Storage requirements are proportional to T² for the single period equivalent transportation algorithm, proportional to T, for our algorithm without decomposition, and independent of T for our algorithm with decomposition. This storage saving feature enables much larger problems to be solved than were previously possible. Futhermore, we can easily incorporate upper bounds on inventories. This is not possible in the single period transportation equivalent.     

A time series analysis of some interrelated logistics performance variables

This paper is a case study. We show how the powerful methods of time series analysis can be used to investigate the interrelationships between Alert Availability, a logistics performance variable, and Flying Hours, an operational requirement, in the presence of a major change in operating procedures and using contaminated data. The system considered is the fleet of C-141 aircraft of the U.S. Air Force. The major change in operating procedures was brought about by what is known as Reliability Centered Maintenance, and the contaminated data were due to anomalies in reporting procedures. The technique used is a combination of transfer function modeling and intervention analysis.     

Application of level crossing analysis to discrete state processes in queueing systems

In this paper we introduce a discrete state level crossing analysis and present some basic results and a key theorem of level crossings. We illustrate the fertility of the discrete state level crossing analysis by applying it to queueing systems with (i) bulk arrival, (ii) instantaneous feedback, (iii) limited waiting space, and (iv) to machine interference problems.