Algorithms for minimizing total cost,bottleneck time and bottleneck shipment in transportation problems

We consider the transportation problem of determining nonnegative shipments from a set of m warehouses with given availabilities to a set of n markets with given requirements. Three objectives are defined for each solution: (i) total cost, TC, (ii) bottleneck time, BT (i.e., maximum transportation time for a positive shipment), and (iii) bottleneck shipment, SB (i.e., total shipment over routes with bottleneck time). An algorithm is given for determining all efficient (pareto-optimal or nondominated) (TC, BT) solution pairs. The special case of this algorithm when all the unit cost coefficients are zero is shown to be the same as the algorithms for minimizing BT. provided by Szwarc and Hammer. This algorithm for minimizing BT is shown to be computationally superior. Transportation or assignment problems with m=n=100 average about a second on the UNIVAC 1108 computer (FORTRAN V)) to the threshold algorithm for minimizing BT. The algorithm is then extended to provide not only all the efficient (TC, BT) solution pairs but also, for each such BT, all the efficient (TC, SB) solution pairs. The algorithms are based on the cost operator theory of parametric programming for the transportation problem developed by the authors.     

An M/M/1 queue with delayed feedback

We present some results for M/M/1 queues with finite capacities with delayed feedback. The delay in the feedback to an M/M/1 queue is modelled as another M-server queue with a finite capacity. The steady state probabilities for the two dimensional Markov process {N(t), M(t)} are solved when N(t) = queue length at server 1 at t and M(t) = queue length at server 2 at t. It is shown that a matrix operation can be performed to obtain the steady state probabilities. The eigenvalues of the operator and its eigenvectors are found. The problem is solved by fitting boundary conditions to the general solution and by normalizing. A sample problem is run to show that the solution methods can be programmed and meaningful results obtained numerically.     

The divisionalized firm revisited—A comment on Enzer's “the static theory of transfer pricing”

Three different solutions to a very simple transfer pricing problem are outlined and contrasted. These are labeled by their authors: Hirshleifer, Enzer, and Ronen and McKinney. Weaknesses associated with each solution are pointed out.     

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.     

Solving a (0, 1) hyperbolic program by branch and bound

A problem in (0, 1) hyperbolic programming is formulated and solved by the use of branch and bound methods. Computational results are presented including a comparison among several branching rules. Heuristic methods for quickly finding relatively good feasible solutions are presented and tested. The problem finds application in the scheduling of common carriers. In the solution of the main problem, a subproblem is identified and solved. A geometric analogue is presented, which allows an interesting interpretation of the subproblem. The subproblem itself finds application in the design of gambles.     

Simulating stable stochastic systems,V: Comparison of ratio estimators

The regenerative method for estimating parameters in a simulation requires the simulator to estimate the ratio of two means. Five point estimates and four confidence intervals for this ratio have been computed for three stochastic simulations. The jackknife method appears to be the most promising for both point and interval estimation.     

Least-absolute-value estimators for one-way and two-way tables

This paper concerns itself with the problem of estimating the parameters of one-way and two-way classification models by minimization of the sum of the absolute deviations of the regression function from the observed points. The one-way model reduces to obtaining a set of medians from which optimal parameters can be obtained by simple arithmetic manipulations. The two-way model is transformed into a specially structured linear programming problem, and two algorithms are presented to solve this problem. The occurrence of alternative optimal solutions in both models is discussed, and numerical examples are presented.     

Multiproduct lot-size scheduling with proportional product demands

In this paper we consider the multiproduct, multiperiod production-scheduling model of Manne under the assumption that, across products, demands are interrelated over time. When demand requirements are proportional we show that the solution has a specific structure determined by the ratio of setup to production-run time of each product. This structure holds for any length horizon and may permit a substantial (time) savings for column generation solution procedures.     

The continuous multiple-modular design problem

In this article we extend our previous work on the continuous single-module design problem to the multiple-module case. It is assumed that there is a fixed cost associated with each additional module used. The Kuhn–Tucker conditions characterize local optima among which there is a global optimum. Modules are associated with partitions and a special class, guillotine partitions, are characterized. Branch-and-bound, partial enumeration, and heuristic procedures for finding optimum or good guillotine partitions are discussed and illustrated with examples.     

An approximate solution method for the fixed charge problem

In the absence, to date, of an exact method for solving the linear programming problem with fixed charges, two heuristic methods have been proposed and extensively investigated, computationally, for moderate sized problems. The results indicate that the heuristic methods produce optimal solutions in well over 90 percent of the several hundred problems investigated and very close to optimal (a few percent) in the remaining cases. Hence it should be of practical significance to practitioners in the field.