A note on allocating jobs to two machines

A recent article in this journal by Mehta, Chandrasekaran, and Emmons [1] described a dynamic programming algorithm for assigning jobs to two identical parallel processors in a way that minimizes the average delay of these jobs. Their problem has a constraint on the sequence of the jobs such that any group of jobs assigned to a processor must be processed in the order of the sequence. This note has two purposes. First, we wish to point out a relationship between this work and some prior work [2]. Second, we wish to point out that Mehta, Chandrasekaran, and Emmons formulation, slightly generalized, can be used to find the optimum assignment of jobs to two machines in a more general class of problems than they considered including a subclass in which the jobs are not constrained to be processed in a given sequence.     

Project scheduling: The effects of problem structure on heuristic performance

Individual characteristics of multiple-constrained resource, project scheduling problems are examined in an attempt to predict the solution obtainable with heuristic methods. Difficulties encountered in performing this type of research are described, and several multiple regression models are developed for predicting heuristic performance. Both single and multiple project data are examined, and results reported demonstrate the efficacy of determining beforehand the method used for problem solution.     

A survey of maintenance models: The control and surveillance of deteriorating systems

The literature on maintenance models is surveyed. The focus is on work appearing since the 1965 survey, “Maintenance Policies for Stochastically Failing Equipment: A Survey” by John McCall and the 1965 book, The Mathematical Theory of Reliability, by Richard Barlow and Frank Proschan. The survey includes models which involve an optimal decision to procure, inspect, and repair and/or replace a unit subject to deterioration in service.     

Optimal inventory policy when stockouts alter demand

An inventory model in which future demand is affected by stockouts has been considered recently by B. L. Schwartz. Some generalizations of Schwartz's model are presented in this paper and properties of the optimal policies are determined. In the case of deterministic demand, a set-up cost is included and a mixture of backlogged and nonbacklogged orders is allowed during stockout. It is proved that the optimal policy entails either no stockout or continual stockout, depending on the values of three parameters. For stochastic demand, the effect of stockouts on demand density is postulated, the resulting optimal inventory policy is discussed, and an example involving an exponential density function is then analyzed in detail.     

Linearly constrained pseudo-Newton method

Must Newton-type methods for linearly constrained optimization be either of the modified Newton or quasi-Newton variety? The contention of this paper is that explicity recomputing part of the projected Hessian may be superior to both approaches. A computational comparison with MINOS is presented.     

On the reliability,availability and bayes confidence intervals for multicomponent systems

The problem of computing reliability and availability and their associated confidence limits for multi-component systems has appeared often in the literature. This problem arises where some or all of the component reliabilities and availabilities are statistical estimates (random variables) from test and other data. The problem of computing confidence limits has generally been considered difficult and treated only on a case-by-case basis. This paper deals with Bayes confidence limits on reliability and availability for a more general class of systems than previously considered including, as special cases, series-parallel and standby systems applications. The posterior distributions obtained are exact in theory and their numerical evaluation is limited only by computing resources, data representation and round-off in calculations. This paper collects and generalizes previous results of the authors and others. The methods presented in this paper apply both to reliability and availability analysis. The conceptual development requires only that system reliability or availability be probabilities defined in terms acceptable for a particular application. The emphasis is on Bayes Analysis and the determination of the posterior distribution functions. Having these, the calculation of point estimates and confidence limits is routine. This paper includes several examples of estimating system reliability and confidence limits based on observed component test data. Also included is an example of the numerical procedure for computing Bayes confidence limits for the reliability of a system consisting of N failure independent components connected in series. Both an exact and a new approximate numerical procedure for computing point and interval estimates of reliability are presented. A comparison is made of the results obtained from the two procedures. It is shown that the approximation is entirely sufficient for most reliability engineering analysis.     

Optimal spares for stochastically failing equipment

A mathematical model is formulated for determining the number of spare components to purchase when components stochastically fail according to a known life distribution function and there is a cost incurred when a component is replaced. Bounds are determined for the optimal inventory which indicate that the inclusion of the replacement cost lowers the optimal inventory. Since these bounds are no easier to calculate than the optimal spares level, the theory is specialized to components with exponentially distributed time to failure. Procedures are given for calculating the optimal spares level, and numerical examples are provided.     

An extension of the (szwarc) truck assignment problem

In this journal in 1967. Szware presented an algorithm for the optimal routing of a common vehicle fleet between m sources and n sinks with p different types of commodities. The main premise of the formulation is that a truck may carry only one commodity at a time and must deliver the entire load to one demand area. This eliminates the problem of routing vehicles between sources or between sinks and limits the problem to the routing of loaded trucks between sources and sinks and empty trucks making the return trip. Szwarc considered only the transportation aspect of the problem (i. e., no intermediate points) and presented a very efficient algorithm for solution of the case he described. If the total supply is greater than the total demand, Szwarc shows that the problem is equivalent to a (mp + n) by (np + m) Hitchcock transportation problem. Digital computer codes for this algorithm require rapid access storage for a matrix of size (mp + n) by (np + m); therefore, computer storage required grows proportionally to p². This paper offers an extension of his work to a more general form: a transshipment network with capacity constraints on all arcs and facilities. The problem is shown to be solvable directly by Fulkerson's out-of-kilter algorithm. Digital computer codes for this formulation require rapid access storage proportional to p instead of p². Computational results indicate that, in addition to handling the extensions, the out-of-kilter algorithm is more efficient in the solution of the original problem when there is a mad, rate number of commodities and a computer of limited storage capacity.