An efficient cyclic coordinate method for optimizing penalty functions

In this study, a simple and efficient cyclic coordinate search procedure is used to optimize penalty functions. Since the contours of the penalty function are very ill-behaved, an accurate line search is very difficult to achieve. Due to accumulated errors in line search, this makes “simple-minded” search directions just as good as more sophisticated directions, and actually better since they require a smaller effort per iteration. Of course this is only true if the search procedure is able to “ride” along steep ridges, and meanwhile move an appreciable distance towards the optimal, if at all possible. Computational results on the cyclic coordinate method seems to support this point of view, and shows robustness, reliability, and efficiency of the method.     

Adjacent vertices on transportation polytopes

To solve linear fixed charge problems with Murty's vertex ranking algorithm, one uses a simplex algorithm and a procedure to determine the vertices adjacent to a given vertex. In solving fixed charge transportation problems, the simplex algorithm simplifies to the stepping-stone algorithm. To find adjacent vertices on transportation polytopes, we present a procedure which is a simplification of a more general procedure for arbitrary polytopes.     

A heuristic routine for solving large loading problems

The loading problem involves the optimal allocation of n objects, each having a specified weight and value, to m boxes, each of specified capacity. While special cases of these problems can be solved with relative ease, the general problem having variable item weights and box sizes can become very difficult to solve. This paper presents a heuristic procedure for solving large loading problems of the more general type. The procedure uses a surrogate procedure for reducing the original problem to a simpler knapsack problem, the solution of which is then employed in searching for feasible solutions to the original problem. The procedure is easy to apply, and is capable of identifying optimal solutions if they are found.     

Convex/stochastic programming and multilocation inventory problems

This paper examines a convex programming problem that arises in several contexts. In particular, the formulation was motivated by a generalization of the stochastic multilocation problem of inventory theory. The formulation also subsumes some “active” models of stochastic programming. A qualititative analysis of the problem is presented and it is shown that optimal policies have a certain geometric form. Properties of the optimal policy and of the optimal value function are described.     

The effect of correlated exponential service times on single server tandem queues

An investigation via simulation of system performance of two stage queues in series (single server, first-come, first-served) under the assumption of correlated exponential service times indicates that the system's behavior is quite sensitive to departures from the traditional assumption of mutually independent service times, especially at higher utilizations. That service times at the various stages of a tandem queueing system for a given customer should be correlated is intuitively appealing and apparently not at all atypical. Since tandem queues occur frequently, e.g. production lines and the logistics therewith associated, it is incumbent on both the practitioner and the theoretician that they be aware of the marked effects that may be induced by correlated service times. For the case of infinite interstage storage, system performance is improved by positive correlation and impaired by negative correlation. This change in system performance is reversed however for zero interstage storage and depends on the value of the utilization rate for the case where interstage storage equals unity. The effect due to correlation is shown to be statistically significant using spectral analytic techniques. For correlation equal unity and infinite interstage storage, results are provided for two through twenty-five stages in series to suggest how adding stages affects system performance for ρ>0. In this extreme case of correlation, adding stages has an effect on system performance which depends markedly on the utilization rate. Recursive formulae for the waiting time per customer for the cases of zero, one, and infinite interstage storage are derived.     

Optimal and suboptimal procedures in group sequential sampling

This paper investigates the problem of choosing between two simple hypothesis, H₀ and H₁, in terms of independent, identically distributed random variables, when observations can be taken in groups. At any stage in the decision process it must be decided whether to stop and take action now or to continue, in which case the size of the next group of observations must be decided upon. The problem is to find an optimal procedure incorporating a stopping, group size (batch) and terminal action rule. It is proven, in general, that the optimal stopping and terminal action rule is of the sequential probability ratio type (SPRT). Fixed stopping rules of the SPRT type are studied and an iterative procedure of the policy improvement type, both with and without a value determination step, is developed. It is shown, for the general situation, that both the average risk and scheduling rule converge to the optima. Also, six suboptimal scheduling rules are considered with respect to the average risks they achieve. Numerical results are presented to illustrate the effectiveness of the procedures.     

A general treatment of upper unbounded and bounded hitchcock problems

This paper is designed to treat (a) the problem of the determination of the absolute minimum cost, with the associated assignments, when there is no limit, N, on the number of parcels available for shipment in a modified Hitchcock problem. This is accomplished with the use of a transformed cost matrix. C*, to which the so-called transportation paradox does not apply. The general Hitchcock solution using C* gives the cost T*, which is the absolute minimum cost of the original problem, as well as sets of assignments which are readily transformed to give the general assignments of the original problem. The sum of these latter assignments gives the value of N_u, the unbounded N for minimum cost. In addition, this paper is designed to show (b) how the method of reduced matrices may be used, (c) how a particular Hitchcock solution can be used to determine a general solution so that one solution using C* can provide the general answer, (d) how the results may be modified to apply to problems with fixed N, and hence (e) to determine the function of the decreasing T as N approaches N_u, and finally (f) to provide a treatment when the supplies at origin i and/or the demands at destination j, are bounded.     

An efficient algorithm for the location-allocation problem with rectangular regions

The location-allocation problem for existing facilities uniformly distributed over rectangular regions is treated for the case where the rectilinear norm is used. The new facilities are to be located such that the expected total weighted distance is minimized. Properties of the problem are discussed. A branch and bound algorithm is developed for the exact solution of the problem. Computational results are given for different sized problems.     

Counterexamples to optimal permutation schedules for certain flow shop problems

It is well known that a minimal makespan permutation sequence exists for the n × 3 flow shop problem and for the n × m flow shop problem with no inprocess waiting when processing times for both types of problems are positive. It is shown in this paper that when the assumption of positive processing times is relaxed to include nonnegative processing times, optimality of permutation schedules cannot be guaranteed.     

Remarks on a univariate shock model with some bivariate generalizations

In a 1973 paper J. D. Esary, A. W. Marshall, and F. Proschan [5] considered a shock model giving rise to various nonparametric classes of life distributions of interest in reliability theory. A number of authors have extended these results in a variety of directions. In this paper, alternative proofs of the increasing failure rate (IFR) and decreasing mean residual life (DMRL) results are given which do not make use of the theory of total positivity. Some bivariate extensions are then obtained using a shock model similar to that originally used by H. W. Block, A. S. Paulson, and R. C. Kohberger [2] to unify various bivariate exponential distributions.