A backward recursive technique for optimal sequential sampling plans

This paper presents a procedure akin to dynamic programming for designing optimal acceptance sampling plans for item-by-item inspection. Using a Bayesian procedure, a prior distribution is specified, and a suitable cost model is employed depicting the cost of sampling, accepting or rejecting the lot. An algorithm is supplied which is digital computer oriented.     

Stock control in a many depot system

The chief problems considered are: (1) In a parallel set of warehouses, how should stocks be allocated? (2) In a system consisting of a central warehouse and several subsidiary warehouses, how much stock should be carried in each? The demands may have known, or unknown, distribution functions. For problem (1), the i-th stock n_i should usually be allocated in proportion to the i-th demand m_i; in special cases, a significant improvement is embodied in the formula (N = total allocable stock)

     

The discrete max-min problem

The historic max-min problem is examined as a discrete process rather than in its more usual continuous mode. Since the practical application of the max-min model usually involves discrete objects such as ballistic missiles, the discrete formulation of the problem seems quite appropriate. This paper uses an illegal modification to the dynamic programming process to obtain an upper bound to the max-min value. Then a second but legal application of dynamic programming to the minimization part of the problem for a fixed maximizing vector will give a lower bound to the max-min value. Concepts of optimal stopping rules may be applied to indicate when sufficiently near optimal solutions have been obtained.     

Cyclical job sequencing on multiple sets of identical machines

The problem posed in this paper is to sequence or route n jobs, each originating at a particular location or machine, undergoing r?1 operations or repairs, and terminating at the location or machine from which it originated. The problem is formulated as a 0-1 integer program, with block diagonal structure, comprised of r assignment subproblems; and a joint set of constraints to insure cyclical squences. To obtain integer results the solutions to each subproblem are ranked as required and combinations thereof are implicitly enumerated. The procedure may be terminated at any step to obtain an approximate solution. Some limited computational results are presented.     

Probabilistic priorities in the M/G/1 queue

A simple method is presented for deriving the mean and variance of the queueing time distribution in an M/G/1 queue when the priorities assigned to customers have an assignment probability distribution. Several examples illustrate the results. The mean and variance of the queueing time distribution for the longest service time discipline are derived, and its disadvantages are discussed.     

A finiteness proof for modified dantzig cuts in integer programming

Let be a basic solution to the linear programming problem subject to: where R is the index set associated with the nonbasic variables. If all of the variables are constrained to be nonnegative integers and x_u is not an integer in the basic solution, the linear constraint is implied. We prove that including these “cuts” in a specified way yields a finite dual simplex algorithm for the pure integer programming problem. The relation of these modified Dantzig cuts to Gomory cuts is discussed.     

Computing equilibria via nonconvex programming

The problem of determining a vector that places a system in a state of equilibrium is studied with the aid of mathematical programming. The approach derives from the logical equivalence between the general equilibrium problem and the complementarity problem, the latter being explicitly concerned with finding a point in the set S = {x: < x, g(x)> = 0, g(x) ≦ 0, x ≧ 0}. An associated nonconvex program, min{? < x, g(x) > : g(x) ≦ 0, x ≧ 0}, is proposed whose solution set coincides with S. When the excess demand function g(x) meets certain separability conditions, equilibrium solutions are obtained by using an established branch and bound algorithm. Because the best upper bound is known at the outset, an independent check for convergence can be made at each iteration of the algorithm, thereby greatly increasing its efficiency. A number of examples drawn from economic and network theory are presented in order to demonstrate the computational aspects of the approach. The results appear promising for a wide range of problem sizes and types, with solutions occurring in a relatively small number of iterations.     

Sequencing independent jobs with a single resource

This paper examines problems of sequencing n jobs for processing by a single resource to minimize a function of job completion times, when the availability of the resource varies over time. A number of well-known results for single-machine problems which can be applied with little or no modification to the corresponding variable-resource problems are given. However, it is shown that the problem of minimizing the weighted sum of completion times provides an exception.     

Spike swapping in basis reinversion

During basis reinversion of either a product form or elimination form linear programming system, it may become necessary to swap spike columns to effect the reinversion and maintain the desired sparsity characteristics. This note shows that the only spikes which need be examined when an interchange is required are those not yet processed in the current external bump.