Note: Dual sourcing with nonidentical suppliers

We analyze a dual-sourcing inventory model with exponential lead times and constant unit demand in which the order quantity is split in some proportion between two sources of supply. Unlike earlier studies, we do not require that the two sources be identical in terms of the lead-time parameters or the supply prices. We compare the expected total annual costs for the two-source and the traditional single-source models over a wide range of parameter values. We confirm the findings of earlier studies that, under stochastic lead times, dual sourcing yields savings in holding and shortage costs that could outweigh the incremental ordering costs. With this more general model, we demonstrate that savings from dual sourcing are possible even where the mean or the variability of the second source is higher. © 1993 John Wiley & Sons, Inc.     

Note: A geometrical method of solving certain games

One of the diagrammatic methods for solving two-person 2 × n matrix games can be extended to solve m × n games where each column of the matrix is a concave function of the row number. This gives a simple proof of a theorem of Benjamin and Goldman that such games have solutions involving no more than two consecutive strategies for the row player, and no more than two strategies for the column player. Two extensions are discussed. © 1994 John Wiley & Sons, Inc.     

An exact solution approach for the time-dependent traveling-salesman problem

We present an algorithm for solving the time-dependent traveling-salesman problem (TDTSP), a generalization of the classical traveling salesman problem in which the cost of travel between two cities depends on the distance between the cities and the position of the transition in the tour. The algorithm is derived by applying Benders decomposition to a mixed-integer linear programming formulation for the problem. We identify trivial TDTSPs for which a standard implementation of the algorithm requires an exponential number of iterations to converge. This motivates the development of an efficient, network-flow-based method for finding Pareto-optimal dual solutions of a highly degenerate subproblem. Preliminary computational experience demonstrates that the use of these Pareto-optimal solutions has a dramatic impact on the performance of the algorithm. © 1996 John Wiley & Sons, Inc.     

Multiperiod capacity expansion and shipment planning with linear costs

In this paper we consider a multiperiod deterministic capacity expansion and shipment planning problem for a single product. The product can be manufactured in several producing regions and is required in a number of markets. The demands for each of the markets are non-decreasing over time and must be met exactly during each time period (i.e., no backlogging or inventorying for future periods is permitted). Each region is assumed to have an initial production capacity, which may be increased at a given cost in any period. The demand in a market can be satisfied by production and shipment from any of the regions. The problem is to find a schedule of capacity expansions for the regions and a schedule of shipments from the regions to the markets so as to minimize the discounted capacity expansion and shipment costs. The problem is formulated as a linear programming model, and solved by an efficient algorithm using the operator theory of parametric programming for the transporation problem. Extensions to the infinite horizon case are also provided.     

Longitudinal manpower planning models

A manpower planning model is presented that exploits the longitudinal stability of manpower cohorts. The manpower planning process is described. An infinite horizon linear program for calculating minimum cost manpower input plans is presented and found to have a straightforward solution in a great many cases and to yield an easily implemented approximation technique in other cases.     

OPTIMAL FACILITY LOCATION UNDER RANDOM DEMAND WITH GENERAL COST STRUCTURE

This paper investigates the problem of determining the optimal location of plants, and their respective production and distribution levels, in order to meet demand at a finite number of centers. The possible locations of plants are restricted to a finite set of sites, and the demands are allowed to be random. The cost structure of operating a plant is dependent on its location and is assumed to be a piecewise linear function of the production level, though not necessarily concave or convex. The paper is organized in three parts. In the first part, a branch and bound procedure for the general piecewise linear cost problem is presented, assuming that the demand is known. In the second part, a solution procedure is presented for the case when the demand is random, assuming a linear cost of production. Finally, in the third part, a solution procedure is presented for the general problem utilizing the results of the earlier parts. Certain extensions, such as capacity expansion or reduction at existing plants, and geopolitical configuration constraints can be easily incorporated within this framework.     

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.     

Decision rules for attacking targets of opportunity

Frequently in warfare, a force is required to attack a perishable enemy target system - a target system where the targets are detected seemingly at random, and if not immediately attacked, will shortly escape from detection. A conflicting situation arises when an attack element detects a target of relatively low value and has to decide whether to expend his resources on that particular target or to wait for a more lucrative one, hoping one will be found. This paper provides a decision rule giving the least valued target that should be attacked as well as the resources that should be expended as a function of the attack element's remaining mission time.     

On scheduling with ready-times,due-dates and vacations

A single machine sequencing problem is considered in which there are ready-time and due-date constraints on jobs and vacation constraints on the machine. Each vacation has fixed starting and finish time and no preemption is allowed for the jobs. The objective is to minimize maximum lateness. An intriguing feature of this formulation is that it allows sequencing in disconnected time windows. A relaxation of the problem is obtained by modeling the vacations as a set of jobs with flexible ready-times and artificial due-dates and a branch and bound algorithm is developed for the problem. In the algorithm, the search is not only guided by the bounds but also by a careful manipulation of the artificial due-dates. Consequently; while searching in the relaxed solution space, solutions of the original problem are implicitly enumerated. Computational results indicate that the algorithm can satisfactorily solve problems with multiple vacations.     

Inventory control of a multiproduct system with a limited production resource

Optimal control of the production of several products subject to restricted production resources is considered. Linear production, holding and penalty costs are assumed although this is crucial only for production costs. Excess demand results in lost sales. A single point plays an important role in the definition of the optimal policy.