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 algorithm for separable piecewise convex programming problems

We present a branch and bound algorithm to solve mathematical programming problems of the form: Find x =|(x₁,…x_n) to minimize Σ?_i0(x₁) subject to x?G, l≦x≦L and Σ?_i0(x₁)≦0, j=1,…,m. With l=(l₁,…,l_n) and L=(L₁,…,L_n), each ?_ij is assumed to be lower aemicontinuous and piecewise convex on the finite interval [l_i.L_i]. G is assumed to be a closed convex set. The algorithm solves a finite sequence of convex programming problems; these correspond to successive partitions of the set C={x|l ≦ x ≦L} on the bahis of the piecewise convexity of the problem functions ?_ij. Computational considerations are discussed, and an illustrative example is presented.     

Algorithms for the minimax transportation problem

In this paper, we consider a variant of the classical transportation problem as well as of the bottleneck transportation problem, which we call the minimax transportation problem. The problem considered is to determine a feasible flow x_ij from a set of origins I to a set of destinations J for which max_(i,j)εIxJ{c_ijx_ij} is minimum. In this paper, we develop a parametric algorithm and a primal-dual algorithm to solve this problem. The parametric algorithm solves a transportation problem with parametric upper bounds and the primal-dual algorithm solves a sequence of related maximum flow problems. The primal-dual algorithm is shown to be polynomially bounded. Numerical investigations with both the algorithms are described in detail. The primal-dual algorithm is found to be computationally superior to the parametric algorithm and it can solve problems up to 1000 origins, 1000 destinations and 10,000 arcs in less than 1 minute on a DEC 10 computer system. The optimum solution of the minimax transportation problem may be noninteger. We also suggest a polynomial algorithm to convert this solution into an integer optimum solution.     

A note on a stochastic production-maximizing transportation problem

A stochastic production-maximizing problem with transportation constraints is considered where the production rates, R_ij, of man i — job j combinations are random variables rather than constants. It is shown that for the family of Weibull distributions (of which the Exponential is a special case) with scale parameters λ_ij and shape parameter β, the plan that maximizes the expected rate of the entire line is obtained by solving a deterministic fixed charge transportation problem with no linear costs and with “set-up” cost matrix ‖λ_ij‖.     

Solution of minisum and minimax location–allocation problems with Euclidean distances

A new method for the solution of minimax and minisum location–allocation problems with Euclidean distances is suggested. The method is based on providing differentiable approximations to the objective functions. Thus, if we would like to locate m service facilities with respect to n given demand points, we have to minimize a nonlinear unconstrained function in the 2m variables x₁,y₁, ?,x_m,y_m. This has been done very efficiently using a quasi-Newton method. Since both the original problems and their approximations are neither convex nor concave, the solutions attained may be only local minima. Quite surprisingly, for small problems of locating two or three service points, the global minimum was reached even when the initial position was far from the final result. In both the minisum and minimax cases, large problems of locating 10 service facilities among 100 demand points have been solved. The minima reached in these problems are only local, which is seen by having different solutions for different initial guesses. For practical purposes, one can take different initial positions and choose the final result with best values of the objective function. The likelihood of the best results obtained for these large problems to be close to the global minimum is discussed. We also discuss the possibility of extending the method to cases in which the costs are not necessarily proportional to the Euclidean distances but may be more general functions of the demand and service points coordinates. The method also can be extended easily to similar three-dimensional problems.     

Use of completely reduced matrices in solving transportation problems with fixed charges

This paper shows how completely reduced matrices can be used in obtaining exact or approximate solutions to transportation problems with fixed charges. It does not treat methods for obtaining reduced matrices, which are available elsewhere, but it does discuss the problem of obtaining a completely reduced matrix, and then a general parametric solution to the primal problem, from any particular solution. Methods for obtaining particular solutions with determinacies of maximum order (solutions for the constant fixed charges problem) are then presented. The paper terminates with a discussion of methods which are useful in obtaining approximations to solutions of fixed charges problems with charges not constant.     

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.     

Adaptive competitive decision in repeated play of a matrix game with uncertain entries

This study is concerned with a game model involving repeated play of a matrix game with unknown entries; it is a two-person, zero-sum, infinite game of perfect recall. The entries of the matrix ((pij)) are selected according to a joint probability distribution known by both players and this unknown matrix is played repeatedly. If the pure strategy pair (i, j) is employed on day k, k = 1, 2, …, the maximizing player receives a discounted income of β^{k - 1} X_ij, where β is a constant, 0 ≤ β ? 1, and X_ij assumes the value one with probability p_ij or the value zero with probability 1 - p_ij. After each trial, the players are informed of the triple (i, j, X_ij) and retain this knowledge. The payoff to the maximizing player is the expected total discounted income. It is shown that a solution exists, the value being characterized as the unique solution of a functional equation and optimal strategies consisting of locally optimal play in an auxiliary matrix determined by the past history. A definition of an ?-learning strategy pair is formulated and a theorem obtained exhibiting ?-optimal strategies which are ?-learning. The asymptotic behavior of the value is obtained as the discount tends to one.     

Instant transportation solutions

This paper presents direct noniterative methods for solving such known problems as shoploading and aggregate scheduling. There is given a simple optimal rule for the shop-loading problem which is quite surprising. The crucial point in solving this problem is what not to assign rather than what to assign. The development of those methods was possible since the discussed problems can be converted into a special transportation model where the given cost coefficients c_ij assume a form cij = ui + uj.     

A solution for queues with instantaneous jockeying and other customer selection rules

This paper presents a general solution for the M/M/r queue with instantaneous jockeying and r > 1 servers. The solution is obtained in matrices in closed form without recourse to the generating function arguments usually used. The solution requires the inversion of two (Z^r?1) × (2^r?1) matrices. The method proposed is extended to allow different queue selection preferences of arriving customers, balking of arrivals, jockeying preference rules, and queue dependent selection along with jockeying. To illustrate the results, a problem previously published is studied to show how known results are obtained from the proposed general solution.     

On convexity proofs in location theory

It is often assumed in the facility location literature that functions of the type ø_i(x_i, y) = β_i[(x_i-x)²+(y_i-y)²]^K/2 are twice differentiable. Here we point out that this is true only for certain values of K. Convexity proofs that are independent of the value of K are given.     

Approximation schemes for ordered vector packing problems

In this paper we deal with the d‐dimensional vector packing problem, which is a generalization of the classical bin packing problem in which each item has d distinct weights and each bin has d corresponding capacities. We address the case in which the vectors of weights associated with the items are totally ordered, i.e., given any two weight vectors a_i, a_j, either a_i is componentwise not smaller than a_j or a_j is componentwise not smaller than a_i. An asymptotic polynomial‐time approximation scheme is constructed for this case. As a corollary, we also obtain such a scheme for the bin packing problem with cardinality constraint, whose existence was an open question to the best of our knowledge. We also extend the result to instances with constant Dilworth number, i.e., instances where the set of items can be partitioned into a constant number of totally ordered subsets. We use ideas from classical and recent approximation schemes for related problems, as well as a nontrivial procedure to round an LP solution associated with the packing of the small items. © 2002 Wiley Periodicals, Inc. Naval Research Logistics, 2003     

On sequencing with earliest starts and due dates with application to computing bounds for the (n/m/G/Fmax) problem

Recent efforts to improve lower bounds in implicit enumeration algorithms for the general (n/m/G/F_max) sequencing problem have been directed to the solution of an auxiliary single machine problem that results from the relaxation of some of the interference constraints. We develop an algorithm that obtains optimal and near optimal solutions for this relaxed problem with relatively little computational effort. We report on computational results achieved when this method is used to obtain lower bounds for the general problem. Finally, we show the equivalence of this problem to a single machine sequencing problem with earliest start and due date constraints where the objective is to minimize the maximum lateness.     

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.     

On computing the expected discounted return in a markov chain

The discounted return associated with a finite state Markov chain X₁, X₂… is given by g(X₁)+ αg(X₂) + α²g(X₃) + …, where g(x) represents the immediate return from state x. Knowing the transition matrix of the chain, it is desired to compute the expected discounted return (present worth) given the initial state. This type of problem arises in inventory theory, dynamic programming, and elsewhere. Usually the solution is approximated by solving the system of linear equations characterizing the expected return. These equations can be solved by a variety of well-known methods. This paper describes yet another method, which is a slight modification of the classical iterative scheme. The method gives sequences of upper and lower bounds which converge mono-tonely to the solution. Hence, the method is relatively free of error control problems. Computational experiments were conducted which suggest that for problems with a large number of states, the method is quite efficient. The amount of computation required to obtain the solution increases much slower with an increase in the number of states, N, than with the conventional methods. In fact, computational time is more nearly proportional to N², than to N³.     

Analysis of the greedy approach in problems of maximum k-coverage

In this paper, we consider a general covering problem in which k subsets are to be selected such that their union covers as large a weight of objects from a universal set of elements as possible. Each subset selected must satisfy some structural constraints. We analyze the quality of a k-stage covering algorithm that relies, at each stage, on greedily selecting a subset that gives maximum improvement in terms of overall coverage. We show that such greedily constructed solutions are guaranteed to be within a factor of 1 − 1/e of the optimal solution. In some cases, selecting a best solution at each stage may itself be difficult; we show that if a β-approximate best solution is chosen at each stage, then the overall solution constructed is guaranteed to be within a factor of 1 − 1/e^β of the optimal. Our results also yield a simple proof that the number of subsets used by the greedy approach to achieve entire coverage of the universal set is within a logarithmic factor of the optimal number of subsets. Examples of problems that fall into the family of general covering problems considered, and for which the algorithmic results apply, are discussed. © 1998 John Wiley & Sons, Inc. Naval Research Logistics 45: 615–627, 1998     

Testing fit with nuisance location and scale parameters

For each n, X₁(n),…, X_n(n) are independent and identically distributed random variables, each with cumulative distribution function F(x) which is known to be absolutely continuous but is otherwise unknown. The problem is to test the hypothesis that \documentclass{article}\pagestyle{empty}\begin{document}$ F(x) = G\left( {{\textstyle{{x - \theta _1 } \over {\theta _2 }}}} \right) $\end{document}, where the cumulative distribution function G_x is completely specified and satisfies certain regularity conditions, and the parameters θ₁, θ₂ are unknown and unspecified, except that the scale parameter θ₂, is positive. Y₁ (n) ≦ Y₂ (n) ≦ … ≦ Y_n (n)are the ordered values of X₁(n),…, X_n(n). A test based on a certain subset of {Y_i(n)} is proposed, is shown to have asymptotically a normal distribution when the hypothesis is true, and is shown to be consistent against all alternatives satisfying a mild regularity condition.     

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.     

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.     

Mathematical aspects of the 3 × n job-shop sequencing problem

The paper discusses mathematical properties of the well-known Bellman-Johnson 3 × n sequencing problem. Optimal rules for some special cases are developed. For the case min B_i ≥ maxA_j we find an optimal sequence of the 2 × n problem for machines B and C and move one item to the front of the sequence to minimize (7); when min B_i ≥ max C_j we solve a 2 × n problem for machines A and B and move one item to the end of the optimal sequence so as to minimize (9). There is also given a sufficient optimality condition for a solution obtained by Johnson's approximate method. This explains why this method so often produces an optimal solution.