Optimal production growth for the machine loading problem

This paper investigates a production growth logistics system for the machine loading problem (generalized transportation model), with a linear cost structure and minimum levels on total machine hours (resources) and product types (demands). An algorithm is provided for tracing the production growth path of this system, viz. in determining the optimal machine loading schedule of machines for product types, when the volumes of (i) total machine hours, and (ii) the total amount of product types are increased either individually for each total or simultaneously for both. Extensions of this methodology, when (i) the costs of production are convex and piecewise linear, and (ii) when the costs are nonconvex due to quantity discounts, and (iii) when there are upper bounds for productions are also discussed. Finally, a “goal-programming” production growth model where the specified demands are treated as just goals and not as absolute quantities to be satisfied is also considered.     

A stock redistribution model

Multi-depot supply systems are subject to stock distribution imbalances; i. e., the fraction of total system stock located at a depot may be too small to support the fraction of system demand expected to be placed on it. In the supply system of concern, a cutomer is always satisfied if there is stock anywhere in the system. Stock redistributions to correct imbalances may reduce both transportation costs and customer waiting times. A model for determining optimum redistribution quantities is formulated, and a practical method of solution for the two depot case is described. Selected numerical illustrations are given.     

Finding equivalent transportation formulations for constrained transportation problems

This paper describes a procedure for determining if constrained transportation problems (i.e., transportation problems with additional linear constraints) can be transformed into equivalent pure transportation problems by a linear transformation involving the node constraints and the extra constraints. Our results extend procedures for problems in which the extra constraints consist of bounding certain partial sums of variables.     

The bottleneck transportation problem

The bottleneck transportation problem can be stated as follows: A set of supplies and a set of demands are specified such that the total supply is equal to the total demand. There is a transportation time associated between each supply point and each demand point. It is required to find a feasible distribution (of the supplies) which minimizes the maximum transportaton time associated between a supply point and a demand point such that the distribution between the two points is positive. In addition, one may wish to find from among all optimal solutions to the bottleneck transportation problem, a solution which minimizes the total distribution that requires the maximum time Two algorithms are given for solving the above problems. One of them is a primal approach in the sense that improving fcasible solutions are obtained at each iteration. The other is a “threshold” algorithm which is found to be far superior computationally.     

Transportation type problems with quantity discounts

It is known to be real that the per unit transportation cost from a specific supply source to a given demand sink is dependent on the quantity shipped, so that there exist finite intervals for quantities where price breaks are offered to customers. Thus, such a quantity discount results in a nonconvex, piecewise linear functional. In this paper, an algorithm is provided to solve this problem. This algorithm, with minor modifications, is shown to encompass the “incremental” quantity discount and the “fixed charge” transportation problems as well. It is based upon a branch-and-bound solution procedure. The branches lead to ordinary transportation problems, the results of which are obtained by utilizing the “cost operator” for one branch and “rim operator” for another branch. Suitable illustrations and extensions are also provided.     

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 incremental quantity discounted transportation problems by vertex ranking

Logistics managers often encounter incremental quantity discounts when choosing the best transportation mode to use. This could occur when there is a choice of road, rail, or water modes to move freight from a set of supply points to various destinations. The selection of mode depends upon the amount to be moved and the costs, both continuous and fixed, associated with each mode. This can be modeled as a transportation problem with a piecewise-linear objective function. In this paper, we present a vertex ranking algorithm to solve the incremental quantity discounted transportation problem. Computational results for various test problems are presented and discussed.     

A streamlined simplex approach to the singly constrained transportation problem

A primal simplex procedure is developed to solve transportation problems with an arbitrary additional linear constraint. The approach is a specialization of the Double Reverse Method of Charnes and Cooper. Efficient procedures for pricing-out the basis, determining representations, and implementing the change of basis are presented. These procedures exploit the pure transportation substructure in such a manner that full advantage may be taken of the computational schemes and list structures used to store and update the basis in codifying the MODI method. Furthermore, the pricing-out and change-of-basis procedures are organized in a manner that permits the calculations for one to be utilized in the other. Computational results are presented which indicate that this method is at least 50 times faster than the state-of-the-art LP code, APEX-III. Methods for obtaining basic primal “feasible” starts and “good” feasible integer solutions are also presented.     

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.     

Scheduling customer arrivals to a stochastic service system

An efficient algorithm for determining the optimal arrival schedule for customers in a stochastic service system is developed. All customers arrive exactly when scheduled, and service times are modeled as iid Erlang random variables. Costs are incurred at a fixed rate per unit of time each customer waits for service, and an additional cost is incurred for every unit of time the server operates beyond a scheduled closing time. The objective is to minimize total operating cost. This type of problem arises in many operational contexts including transportation, manufacturing, and appointment‐based services. © 1999 John Wiley & Sons, Inc. Naval Research Logistics 46: 549–559, 1999     

Determining adjacent vertices on assignment polytopes

To rank the solutions to the assignment problem using an extreme point method, it is necessary to be able to find all extreme points which are adjacent to a given extreme solution. Recent work has shown a procedure for determining adjacent vertices on transportation polytopes using a modification of the Chernikova Algorithm. We present here a procedure for assignment polytopes which is a simplification of the more general procedure for transportation polytopes and which also allows for implicit enumeration of adjacent vertices.     

An economic model for planning strategic mobility posture

This paper describes a linear programming model used to perform cost-effectiveness analysis to determine the requirements for military strategic mobility resources. Expenditures for three classes of economic alternatives are considered: purchase of transportation resources; prepositioning of material; and augmentation of port facilities. The mix of economic alternatives that maximizes the effectiveness of the resultant transportation system is determined for a given investment level. By repeating the analysis for several levels of investment, a cost-effectiveness tradeoff curve can be developed.     

The dynamic transportation problem: A survey

The dynamic transportation problem is a transportation problem over time. That is, a problem of selecting at each instant of time t, the optimal flow of commodities from various sources to various sinks in a given network so as to minimize the total cost of transportation subject to some supply and demand constraints. While the earliest formulation of the problem dates back to 1958 as a problem of finding the maximal flow through a dynamic network in a given time, the problem has received wider attention only in the last ten years. During these years, the problem has been tackled by network techniques, linear programming, dynamic programming, combinational methods, nonlinear programming and finally, the optimal control theory. This paper is an up-to-date survey of the various analyses of the problem along with a critical discussion, comparison, and extensions of various formulations and techniques used. The survey concludes with a number of important suggestions for future work.     

An efficient primal approach to bottleneck transportation problems

This article addresses bottleneck linear programming problems and in particular capacitated and constrained bottleneck transportation problems. A pseudopricing procedure based on the poly-ω procedure is used to facilitate the primal simplex procedure. This process allows the recent computational developments such as the Extended Threaded Index Method to be applied to bottleneck transportation problems. The impact on problem solution times is illustrated by computational testing and comparison with other current methods.     

Optimal policy for a dynamic multi-echelon inventory model

A general multiperiod multi-echelon supply system consisting of n facilities each stocking a single product is studied. At the beginning of a period each facility may order stock from an exogenous source with no delivery lag and proportional ordering costs. During the period the (random) demands at the facilities are satisfied according to a given supply policy that determines to what extent stock may be redistributed from facilities with excess stock to those experiencing shortages. There are storage, shortage, and transportation costs. An ordering policy that minimizes expected costs is sought. If the initial stock is sufficiently small and certain other conditions are fulfilled, it is optimal to order up to a certain base stock level at each facility. The special supply policy in which each facility except facility 1 passes its shortages on to a given lower numbered facility called its direct supplier is examined in some detail. Bounds on the base stock levels are obtained. It is also shown that if the demand distribution at facility j is stochastically smaller (“spread” less) than that at another facility k having the same direct supplier and if certain other conditions are fulfilled, then the optimal base stock level (“virtual” stock out probability) at j is less than (greater than) or equal to that at facility k.     

A simulated port facility in a theatre of operations

A hypothetical port facility in a theatre of operations is modeled and coded in a special purpose simulation language, for the purpose of conducting simulation experiments on a digital computer. The experiments are conducted to investigate the resource requirements necessary for the reception, discharge, and clearance of supplies at the port. Queue lengths, waiting times, facility utilizations, temporary storage levels, and ship turn-around times are analyzed as functions of transportation and cargo handling resources, using response surface methodology. The resulting response surfaces are revealing in regard to the sensitivity of port operations to transportation resource levels and the characteristics of the port facility's load factor. Two specific conclusions of significant value are derived. First, the simulation experiments clearly show that the standard procedures for determining discharge and clearance capacities take insufficient account of the effects of variability. Second, the response surfaces for ship turn-around times and temporary storage levels indicate that an extremely steep gradient exists as a function of troop levels.     

A branch and bound algorithm for allocation problems in which constraint coefficients depend upon decision variables

A branch and bound algorithm is developed for a class of allocation problems in which some constraint coefficients depend on the values of certain of the decision variables. Were it not for these dependencies, the problems could be solved by linear programming. The algorithm is developed in terms of a strategic deployment problem in which it is desired to find a least-cost transportation fleet, subject to constraints on men/materiel requirements in the event of certain hypothesized contingencies. Among the transportation vehicles available for selection are aircraft which exhibit the characteristic that the amount of goods deliverable by an aircraft on a particular route in a given time period (called aircraft productivity and measured in kilotons/aircraft/month) depends on the ratio of type 1 to type 2 aircraft used on that particular route. A model is formulated in which these relationships are first approximated by piecewise linear functions. A branch and bound algorithm for solving the resultant nonlinear problem is then presented; the algorithm solves a sequence of linear programming problems. The algorithm is illustrated by a sample problem and comments concerning its practicality are made.     

The continuous‐time single‐sourcing problem with capacity expansion opportunities

This paper develops a new model for allocating demand from retailers (or customers) to a set of production/storage facilities. A producer manufactures a product in multiple production facilities, and faces demand from a set of retailers. The objective is to decide which of the production facilities should satisfy each retailer's demand, in order minimize total production, inventory holding, and assignment costs (where the latter may include, for instance, variable production costs and transportation costs). Demand occurs continuously in time at a deterministic rate at each retailer, while each production facility faces fixed‐charge production costs and linear holding costs. We first consider an uncapacitated model, which we generalize to allow for production or storage capacities. We then explore situations with capacity expansion opportunities. Our solution approach employs a column generation procedure, as well as greedy and local improvement heuristic approaches. A broad class of randomly generated test problems demonstrates that these heuristics find high quality solutions for this large‐scale cross‐facility planning problem using a modest amount of computation time. © 2005 Wiley Periodicals, Inc. Naval Research Logistics, 2005.     

光电探测系统电源通用化设计与实现

为应对全天候、全天时实时使用要求,光电探测系统逐渐从功能单一的光电探测系统演变为多功能、多传感器的综合光电系统。因此,具体进行工程设计时,系统电源组件的技术指标要合理,满足系统使用要求。同时,组件维修、故障诊断、部件互换也要容易。针对此问题,基于描述的光电探测系统电源通用化设计原则,提出了一种可工程化设计方案。该方案对电源硬件结构设置、电源控制管理和电源功能扩展设计等进行了讨论,并给出具体设计方法。通过实际应用验证表明,该方案能够满足系统对电源组件的要求。