An operator theory of parametric programming for the generalized transportation problem: II Rim,cost and bound operators

This paper investigates the effect on the optimum solution of a capacitated generalized transportation problem when certain data of the problem are continuously varied as a linear function of a single parameter. First the rim conditions, then the cost coefficients, and finally the cell upper bounds are varied parametrically and the effect on the optimal solution, the associated change in costs and the dual changes are derived. Finally the effect of simultaneous changes in both cost coefficients and rim conditions are investigated. Bound operators that effect changes in upper bounds are shown to be equivalent to rim operators. The discussion in this paper is limited to basis preserving operators for which the changes in the data are such that the optimum bases are preserved.     

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

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. An operator theory is developed and algorithms provided for applying rim and cost operators that effect the transformation of optimum solution associated with changes in rim conditions and unit costs. Bound operators that effect changes in upper bounds are shown to be equivalent to rim operators. The discussion in this paper is limited to basis preserving operators for which the changes in the data are such that the optimum basis structures are preserved.     

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.     

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.     

On some sequencing problems

The (mxn) sequencing problem may be characterized as follows: There are m machines which can produce a piece consisting of n parts. Each part has a determined order in which it is processed through the machines. It is assumed that each machine cannot deal with more than one part at a time and that the processing required for each part can be accomplished only on one machine. That is, the machines are all specialized so that alternate machines for the same processing on a part is not possible. The problem is to find the best production plan consisting in sequencing the different parts so as to make the whole amount of time from the beginning of work till the piece is completed the shortest possible. Such a plan is called an optimum one. In the first 4 sections of this paper, the problem (2xn) is solved for the (2xn) case in which the order in which parts come on the machine is not constrained by further assumptions. The remainder of the paper then takes up: 1) the (3xn) problem of Bellman-Johnson (viz. the technological processing order through the machine is the same for all parts) for several new special cases; 2) the 2xn problem of sequencing when delay times must also be considered; and, 3) some properties of an approximating method for solving (mxn) problems, including a delineation of cases when the approximating method will yield optimal solutions.     

Optimization in mixed-integer space with a single linear bound

The search for an optimal point in a mixed-integer space with a single linear bound may be significantly reduced by a procedure resembling the Lagrangian technique. This procedure uses the coefficients of the linear bound to generate a set of necessary conditions that may eliminate most of the space from further consideration. Enumerative or other techniques can then locate the optimum with greater efficiency. Several methods are presented for applying this theory to separable and quadratic objectives. In the maximization of a separable concave function, the resulting average range of the variables is approximately equal to the maximum (integer) coefficient of the constraint equation.     

An operator theory of parametric programming for the generalized transportation problem—IV—global operators

This paper investigates the effect of the optimal solution of a (capacitated) generalized transportation problem when the data of the problem (the rim conditions—i.e., the available time of machine types and demands of product types, the per unit production costs, the per unit production time and the upper bounds) are continuously varied as a linear function of a single parameter. Operators that effect the transformation of optimal solution associated with such data changes, are shown to be a product of basis preserving operators (described in our earlier papers) that operate on a sequence of adjacent basis structures. Algorithms are furnished for the three types of operators—rim, cost, and weight. The paper concludes with a discussion of the production and managerial interpretations of the operators and a comment on the “production paradox”.     

Values for optimum reject allowances

Industrial situations exist where it is necessary to estimate the optimum number of parts to start through a manufacturing process in order to obtain a given number of completed good items. The solution to this problem is not straightforward when the expected number of rejects from the process is a random variable and when there are alternative penalties associated with producing too many or too few items. This paper discusses various aspects of this problem as well as some of the proposed solutions to it. In addition, tables of optimum reject allowances based on a comprehensive model are presented.     

Solving generalized transportation problems via pure transportation problems

This paper investigates certain issues of coefficient sensitivity in generalized network problems when such problems have small gains or losses. In these instances, it might be computationally advantageous to temporarily ignore these gains or losses and solve the resultant “pure” network problem. Subsequently, the optimal solution to the pure problem could be used to derive the optimal solution to the original generalized network problem. In this paper we focus on generalized transportation problems and consider the following question: Given an optimal solution to the pure transportation problem, under what conditions will the optimal solution to the original generalized transportation problem have the same basic variables? We study special cases of the generalized transportation problem in terms of convexity with respect to a basis. For the special case when all gains or losses are identical, we show that convexity holds. We use this result to determine conditions on the magnitude of the gains or losses such that the optimal solutions to both the generalized transportation problem and the associated pure transportation problem have the same basic variables. For more general cases, we establish sufficient conditions for convexity and feasibility. © 2002 Wiley Periodicals, Inc. Naval Research Logistics 49: 666–685, 2002; Published online in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/nav.10034     

Selection of the optimal setup policy

A model is developed taking into consideration all the costs (namely cost of sampling, cost of not detecting a change in the process, cost of a false indication of change, and the cost of readjusting detected changes) incurred when a production process, using an unscheduled setup policy, utilizes fraction-defective control charts to control current production. The model is based on the concept of the expected time between detection of changes calling for setups. It is shown that the combination of unscheduled setups and control charts can be utilized in an optimal way if those combinations of sample size, sampling interval, and extent of control limits from process average are used that provide the minimum expected total cost per unit of time. The costs of a production process that uses unscheduled setups in conjunction with the appropriate optimal control charts are compared to the costs of a production process that uses scheduled setups at optimum intervals in conjunction with its appropriate control charts. This comparison indicates the criteria for selecting production processes with scheduled setups using optimal setup intervals over unscheduled setups. Suggestions are made to evaluate the optimal process setup strategy and the accompanying optimal decision parameters, for any specific cost data, by use of computer enumeration. A numerical example for assumed cost and process data is provided.     

装甲装备周转备件需求最优组合预测

针对单项统计预测模型存在的不足,提出采用组合预测方法进行周转备件需求预测的观点,并建立了周转备件需求最优组合预测模型。首先,介绍了组合预测的基本原理和常用的周转备件单项预测方法。在综合权衡预测结果精度和稳健性的前提下,建立了基于预测误差绝对值和最小的周转备件最优组合预测模型,并给出了确定各加权系数和预测评价效果的方法。最后,结合案例验证了该组合预测方法的有效性和优越性。     

An optimal procedure for the coordinated replenishment dynamic lot‐sizing problem with quantity discounts

We consider in this paper the coordinated replenishment dynamic lot‐sizing problem when quantity discounts are offered. In addition to the coordination required due to the presence of major and minor setup costs, a separate element of coordination made possible by the offer of quantity discounts needs to be considered as well. The mathematical programming formulation for the incremental discount version of the extended problem and a tighter reformulation of the problem based on variable redefinition are provided. These then serve as the basis for the development of a primal‐dual based approach that yields a strong lower bound for our problem. This lower bound is then used in a branch and bound scheme to find an optimal solution to the problem. Computational results for this optimal solution procedure are reported in the paper. © 2000 John Wiley & Sons, Inc. Naval Research Logistics 47: 686–695, 2000     

The fractional fixed-charge problem

Fractional fixed-charge problems arise in numerous applications, where the measure of economic performance is the time rate of earnings or profit (equivalent to an interest rate on capital investment). This paper treats the fractional objective function, after suitable transformation, as a linear parametric fixed-charge problem. It is proved, with wider generality than in the case of Hirsch and Dantzig, that some optimal solution to the generalized linear fixed-charge problem is an extreme point of the polyhedral set defined by the constraints. Furthermore, it is shown that the optimum of the generalized fractional fixed-charge problem is also a vertex of this set. The proof utilizes a suitable penalty function yielding an upper bound on the optimal value of the objective function; this is particularly useful when considering combinations of independent transportation-type networks. Finally, it is shown that the solution of a fractional fixed-charge problem is obtainable through that of a certain linear fixed-charge one.     

A dynamic allocation heuristic for centralized safety stock

An inventory system that consists of a depot (central warehouse) and retailers (regional warehouses) is considered. The system is replenished regularly on a fixed cycle by an outside supplier. Most of the stock is direct shipped to the retailer locations but some stock is sent to the central warehouse. At the beginning of any one of the periods during the cycle, the central stock can then be completely allocated out to the retailers. In this paper we propose a heuristic method to dynamically (as retailer inventory levels change with time) determine the appropriate period in which to do the allocation. As the optimal method is not tractable, the heuristic's performance is compared against two other approaches. One presets the allocation period, while the other provides a lower bound on the expected shortages of the optimal solution, obtained by assuming that we know ahead of time all of the demands, period by period, in the cycle. The results from extensive simulation experiments show that the dynamic heuristic significantly outperforms the “preset” approach and its performance is reasonably close to the lower bound. Moreover, the logic of the heuristic is appealing and the calculations, associated with using it, are easy to carry out. Sensitivities to various system parameters (such as the safety factor, coefficient of variation of demand, number of regional warehouses, external lead time, and the cycle length) are presented. © 2005 Wiley Periodicals, Inc. Naval Research Logistics, 2005.     

Computation of constrained optimum quantities and reorder points for time-weighted backorder penalties

The purpose of this paper and the accompanying tables is to facilitate the calculation of constrained optimum order quantities and reorder points for an inventory control system where the criterion of optimality is the minimization of expected inventory holding, ordering, and time-weighted backorder costs. The tables provided in the paper allow the identification of the optimal solution when order quantities and/or reorder points are restricted to a set of values which do not include the unconstrained optimal solution.     

The fixed charge problem

The fixed charge problem is a nonlinear programming problem of practical interest in business and industry. Yet, until now no computationally feasible exact method of solution for large problems had been developed. In this paper an exact algorithm is presented which is computationally feasible for large problems. The algorithm is based upon a branch and bound approach, with the additional feature that the amount of computer storage required remains constant throughout (for a problem of any given size). Also presented are three suboptimal heuristic algorithms which are of interest because, although they do not guarantee that the true optimal solution will be found, they usually yield very good solutions and are extremely rapid techniques. Computational results are described for several of the heuristic methods and for the branch and bound algorithm.     

Makespan minimization in the two‐machine flowshop batch scheduling problem

In this paper we consider a practical scheduling problem commonly arising from batch production in a flexible manufacturing environment. Different part‐types are to be produced in a flexible manufacturing cell organized into a two‐stage production line. The jobs are processed in batches on the first machine, and the completion time of a job is defined as the completion time of the batch containing it. When processing of all jobs in a batch is completed on the first machine, the whole batch of jobs is transferred intact to the second machine. A constant setup time is incurred whenever a batch is formed on any machine. The tradeoff between the setup times and batch processing times gives rise to the batch composition decision. The problem is to find the optimal batch composition and the optimal schedule of the batches so that the makespan is minimized. The problem is shown to be strongly NP‐hard. We identify some special cases by introducing their corresponding solution methods. Heuristic algorithms are also proposed to derive approximate solutions. We conduct computational experiments to study the effectiveness of the proposed heuristics. © 2000 John Wiley & Sons, Inc. Naval Research Logistics 47: 128–144, 2000     

Termination policies for a two-state stochastic process

The purpose of this paper is to investigate and optimize policies which can be used to terminate a two-state stochastic process with a random lifetime. Such a policy consists of a schedule of times at which termination attempts should be made. Conditions are given which reduce the difficulty of finding the optimal policy by eliminating constraints and some boundary points from consideration. Finally, a bound for the optimal policy is derived for a case where some restrictions are imposed on the model.     

A recursive branch and bound algorithm for the multidimensional knapsack problem

This paper presents an efficient branch and bound algorithm for the solution of certain multiconstrained knapsack problems. The key to this algorithm is a rigidly defined tree structure in which branching and bounding may be performed through recursive relationships. The algorithm is particularly useful when only limited amounts of core storage are available as only the current and one previous solution is saved at any one time. Execution speeds compare favorably with other algorithms. A numerical example and computational experience is given.     

正反向量子斯特林循环有限时间热力学性能界限和优化准则

研究了正反向量子斯特林循环的最优性能.在经典极限下,导出了循环的有限时间热力学性能界限和优化准则.得到了斯特林热机、制冷机和热泵特性参数之间的优化关系.