On mixed integer quadratic programs

This paper provides a method for solving mixed integer quadratic programs with the help of cutting-plane technique.     

Order-preserving allocation of jobs to two machines

In this paper, we consider the problem of minimizing the mean flow time of jobs to be processed on two machines. The jobs have a predetermined order, perhaps reflecting the order of arrival, and each job has a known processing time. We wish to assign the jobs to machines so as to minimize the mean flow time, with the constraint that the original order must be preserved within the subset of jobs assigned to each machine. An efficient algorithm based on dynamic programming is developed.     

A note on the costly surveillance of a stochastic system

We consider the costly surveillance of a stochastic system with a finite state space and a finite number of actions in each state. There is a positive cost of observing the system and the system earns at a rate depending on the state of the system and the action taken. A policy for controlling such a system specifies the action to be taken and the time to the next observation, both possibly random and depending on the past history of the system. A form of the long range average income is the criterion for comparing different policies. If R ^Δ denotes the class of policies for which the times between successive observations of the system are random variables with cumulative distribution functions on [0, Δ], Δ < ∞, we show that there exists a nonrandomized stationary policy that is optimal in R ^Δ. Furthermore, for sufficiently large Δ, this optimal policy is independent of Δ.     

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.     

Sequential determination of inspection epochs for reliability systems with general lifetime distributions

The problem of determining the optimal inspection epoch is studied for reliability systems in which N components operate in parallel. Lifetime distribution is arbitrary, but known. The optimization is carried with respect to two cost factors: the cost of inspecting a component and the cost of failure. The inspection epochs are determined so that the expected cost of the whole system per time unit per cycle will be minimized. The optimization process depends in the general case on the whole failure history of the system. This dependence is characterized. The cases of Weibull lifetime distributions are elaborated and illustrated numerically. The characteristics of the optimal inspection intervals are studied theoretically.     

The multicommodity network flow model revised to include vehicle per time period and node constraints

The minimum-cost formulation of the problem of determining multicommodity flows over a capacitated network subject to resource constraints has been treated in previobs papers. In those treatments only capacitated arcs were assumed and a uniform unit of measure like short tons was used for all commodities. This paper treats the effect of constraints on the nodes of the network, allows the commodities to be measured in their “natural” units and allows the network capacities to be expressed in vehicles per time period-in some cases giving a more accurate representation of the capacities of the network. This paper describes the solution procedure which uses the column generation technique; it also discusses computational experience.     

A convex property of an ordered flow shop sequencing problem

A flow shop sequencing problem with ordered processing time matrices is considered. A convex property for the makespan sequences of such problems is discussed. On the basis of this property an efficient optimizing algorithm is presented. Although the proof of optimality has not been developed, several hundred problems were solved optimally with this procedure.     

Adaptive forecasting of the size of a work force subject to random withdrawals

Adaptive forecasting procedures are developed for predicting the size of a work force which is subject to random withdrawals. The procedures are illustrated using Marine Corps data in which four stages of service for incoming cohorts are distinguished. Using these data, three forecasting procedures—conditional maximum likelihood estimation of prediction intervals; tolerance intervals; and Bayes prediction intervals—are compared.     

A note on a paper by W. Szwarc

In this note the authors call for a change of the optimality criteria given by Theorem 3 in section 5 of the paper of W. Szwarc “On Some Sequencing Problems” in NRLQ Vol. 15, No. 2 [2]. Further, two cases of the three machine problem, namely, (i) ≦ and (ii) ≦ are considered, and procedures for obtaining optimal sequences in these cases are given. In these cases the three-machine problem is solved by solving n (the number of jobs) two-machine problems.     

Determining the most vital link in a flow network

The most vital link in a single commodity flow network is that are whose removal results in the greatest reduction in the value of the maximal flow in the network between a source node and a sink node. This paper develops an iterative labeling algorithm to determine the most vital link in the network. A necessary condition for an are to be the most vital link is established and is employed to decrease the number of ares which must be considered.