An operator theory of parametric programming for the transportation problem-II

This paper investigates the effect on the optimum solution of a (capacitated) transportation problem when the data of the problem (the rim conditions-i. e., the warehouse supplies and market demands-, the per unit transportation costs and the upper bounds) are continuously varied as a (linear) function of a single parameter. Operators that effect the transformation of optimum solution associated with such data changes, are shown to be a product of basis preserving operators (described in the earlier paper) that operate on a sequence of adjacent basis structures. Algorithms are provided for both rim and cost operators. The paper concludes with a discussion of the economic and managerial interpretations of the operators.     

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)

     

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.     

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.     

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.     

Techniques for establishing ergodic and recurrence properties of continuous-valued markov chains

We present techniques for classifying Markov chains with a continuous state space as either ergodic or recurrent. These methods are analogous to those of Foster for countable space chains. The theory is presented in the first half of the paper, while the second half consists of examples illustrating these techniques. The technique for proving ergodicity involves, in practice, three steps: showing that the chain is irreducible in a suitable sense; verifying that the mean hitting times on certain (usually bounded) sets are bounded, by using a “mean drift” criterion analogous to that of Foster; and finally, checking that the chain is such that bounded mean hitting times for these sets does actually imply ergodicity. The examples comprise a number of known and new results: using our techniques we investigate random walks, queues with waiting-time-dependent service times, dams with general and random-release rules, the s-S inventory model, and feedback models.     

The distribution of recoverable inventory items from a repair center when the number of consumption centers is large

This paper considers real-time decision rules for an inventory system where items are repaired than “used up.” The problem is to decide which user in the system has the greatest need for the newly available inventory items coming out of repair. The main result shows that two published approahes, the Transportation Time Look Ahead policy and METRIC, are optimal when the number of users gets large. A useful byproduct of the proof is a lower bound on the average backorder rate for a repair-inventory system of any size.     

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.     

Surrogate duality in a branch-and-bound procedure

Recent research has led to several surrogate multiplier search procedures for use in a primal branch-and-bound procedure. As single constrained integer programming problems, the surrogate subproblems are also solved via branch-and-bound. This paper develops the inner play between the surrogate subproblem and the primal branch-and-bound trees which can be exploited to produce a number of computational efficiencies. Most important is a restarting procedure which precludes the need to solve numerous surrogate subproblems at each node of a primal branch-and-bound tree. Empirical evidence suggests that this procedure greatly reduces total computation time.