The many-product cargo loading problem

An algorithm, based upon dynamic programming, is developed for a class of fixed-cost cargo loading problems. The problems can be formulated as integer programming problems, but cannot be efficiently solved as such because of computational difficulties. The algorithm developed has proved to be very efficient in an actual operations research study involving over 500 different cargo items, more than 40 possible stops and several types of transportation vehicles. A numerical illustration is provided.     

Determination of efficient points in multiple-objective location problems

This article is devoted to an MCDM problem connected with locational analysis. The MCDM problem can be formulated so as to minimize the distance between a facility and a given set of points. The efficient points of this problem are candidates for optimal solutions to many location problems. We propose an algorithm to find all efficient points when distance is measured by any polyhedral norm.     

Optimal location of public facilities

Location of both public and private facilities has become an important consideration in today's society. Progress in solution of location problems has been impeded by difficulty of the fixed charge problem and the lack of an efficient algorithm for large problems. In this paper a method is developed for solving large-scale public location problems. An implicit enumeration scheme with an imbedded transportation algorithm forms the basis of the solution technique.     

Auxiliary procedures for solving long transportation problems

An efficient auxiliary algorithm for solving transportation problems, based on a necessary but not sufficient condition for optimum, is presented.     

Flowshop sequencing problem with ordered processing time matrices: A general case

The ordered matrix flow shop problem with no passing of jobs is considered. In an earlier paper, the authors have considered a special case of the problem and have proposed a simple and efficient algorithm that finds a sequence with minimum makespan for a special problem. This paper considers a more general case. This technique is shown to be considerably more efficient than are existing methods for the conventional flow shop problems.     

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.     

防空导弹反TBM作战指挥中目标分配关键问题研究

依据防空反导作战理论和目标分配的要求,对防空导弹反TBM作战指挥中目标分配的关键问题进行了研究。分别对威胁排序方法、拦截可行性条件、目标分配原则和目标分配算法进行了分析,提出了一种反TBM作战指挥中目标分配问题的算法,最后讨论了目标分配的评价问题。通过实际应用表明此方法是切实可行的。     

An algorithm for a class of loading problems

The loading problem we consinder is to assign a set of discrete objects, each having a weight, to a set of boxes, each of which has a capacity limit, in such a way that every object is assigned to a box and the number of boxes used is minimized. A characterization of the assignments is offered and used to develop a set of rules for generating nonredundant assignments. The rules are incorporated into an implicit enumeration algorithm. The algorithm is tested against a very good heuristic. Computational experience shows that the algorithm is highly efficient, solving problems of up to 3600 0-1 variables in a CPU second.     

The conditional p-center problem in the plane

An algorithm is given for the conditional p-center problem, namely, the optimal location of one or more additional facilities in a region with given demand points and one or more preexisting facilities. The solution dealt with here involves the minimax criterion and Euclidean distances in two-dimensional space. The method used is a generalization to the present conditional case of a relaxation method previously developed for the unconditional p-center problems. Interestingly, its worst-case complexity is identical to that of the unconditional version, and in practice, the conditional algorithm is more efficient. Some test problems with up to 200 demand points have been solved. © 1993 John Wiley & Sons, Inc.     

Detection of minimal forecast horizons in dynamic programs with multiple indicators of the future

Many sequential planning problems can be represented as a shortest path problem in an acyclic network. This includes all deterministic dynamic programs as well as certain stochastic sequential decision problems. In this article, we identify a large class of shortest path problems for which a general efficient algorithm for the simultaneous solution and detection of minimal forecast horizons is developed. Detection of a such minimal forecast horizons is essential when accurate information regarding various relevant parameters is obtained progressively, i.e., when the initial information is restricted to a limited horizon of “future” stages only. We describe five classes of planning problems which can be efficiently addressed by the general algorithm. These classes deal with multi-item joint replenishment systems, combined inventory and routing problems, machine scheduling issues, single item stochastic inventory settings and routing problems in the plane and in space. © 1996 John Wiley & Sons, Inc.     

两种选址问题的算法及有关结论

本文提出两种选址问题,对其局部最优性建立了充要条件,并在此基础上提出了该类问题的有效算法。     

A convex property of an ordered flow shop sequencing problem

A flow shop sequencing problem with ordered processing time matrices is considered. A convex property for the makespan sequences of such problems is discussed. On the basis of this property an efficient optimizing algorithm is presented. Although the proof of optimality has not been developed, several hundred problems were solved optimally with this procedure.     

Adjacency‐based local top‐down search method for finding maximal efficient faces in multiple objective linear programming

It is well‐known that the efficient set of a multiobjective linear programming (MOLP) problem can be represented as a union of the maximal efficient faces of the feasible region. In this paper, we propose a method for finding all maximal efficient faces for an MOLP. The new method is based on a condition that all efficient vertices (short for the efficient extreme points and rays) for the MOLP have been found and it relies on the adjacency, affine independence and convexity results of efficient sets. The method uses a local top‐down search strategy to determine maximal efficient faces incident to every efficient vertex for finding maximal efficient faces of an MOLP problem. To our knowledge, the proposed method is the first top‐down search method that uses the adjacency property of the efficient set to find all maximal efficient faces. We discuss this and other advantages and disadvantages of the algorithm. We also discuss some computational experience we have had with our computer code for implementing the algorithm. This computational experience involved solving several MOLP problems with the code.     

具有模糊系数约束的多目标线性规划

研究了一类具有模糊系数约束的多目标线性规划问题.根据各目标函数的梯度方向来量化目标之间的冲突程度,以此提出了一种确定目标权重的新方法,然后基于惩罚函数运用梯度上升算法求问题的有效解.最后给出了一个数值例子.     

Minimizing sums and products of linear fractional functions over a polytope

In this paper, we develop efficient deterministic algorithms for globally minimizing the sum and the product of several linear fractional functions over a polytope. We will show that an elaborate implementation of an outer approximation algorithm applied to the master problem generated by a parametric transformation of the objective function serves as an efficient method for calculating global minima of these nonconvex minimization problems if the number of linear fractional terms in the objective function is less than four or five. It will be shown that the Charnes–Cooper transformation plays an essential role in solving these problems. Also a simple bounding technique using linear multiplicative programming techniques has remarkable effects on structured problems. © 1999 John Wiley & Sons, Inc. Naval Research Logistics 46: 583–596, 1999     

A forward network simplex algorithm for solving multiperiod network flow problems

An optimization model which is frequently used to assist decision makers in the areas of resource scheduling, planning, and distribution is the minimum cost multiperiod network flow problem. This model describes network structure decision-making problems over time. Such problems arise in the areas of production/distribution systems, economic planning, communication systems, material handling systems, traffic systems, railway systems, building evacuation systems, energy systems, as well as in many others. Although existing network solution techniques are efficient, there are still limitations to the size of problems that can be solved. To date, only a few researchers have taken the multiperiod structure into consideration in devising efficient solution methods. Standard network codes are usually used because of their availability and perceived efficiency. In this paper we discuss the development, implementation, and computational testing of a new technique, the forward network simplex method, for solving linear, minimum cost, multiperiod network flow problems. The forward network simplex method is a forward algorithm which exploits the natural decomposition of multiperiod network problems by limiting its pivoting activity. A forward algorithm is an approach to solving dynamic problems by solving successively longer finite subproblems, terminating when a stopping rule can be invoked or a decision horizon found. Such procedures are available for a large number of special structure models. Here we describe the specialization of the forward simplex method of Aronson, Morton, and Thompson to solving multiperiod network network flow problems. Computational results indicate that both the solution time and pivot count are linear in the number of periods. For standard network optimization codes, which do not exploit the multiperiod structure, the pivot count is linear in the number of periods; however, the solution time is quadratic.     

用紧支径向基函数传递固体域耦合数据的方法

针对热-电场耦合仿真计算中非匹配网格之间的数据插值问题,提出了一种基于紧支径向基函数点插值的数据传递方法。推导了数据传递矩阵,根据所提出的数据传递方法编制了非匹配网格之间数据传递计算程序,以若干组非匹配网格之间的温度插值为例进行了验证,并分析了不同参数对计算时间及精度的影响,结果表明,算法效率较高,计算误差较小,适用于以热-电场耦合为代表的固体域耦合非匹配网格间的数据传递计算。     

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.     

The enumeration of all efficient solutions for a linear multiple-objective transportation problem

An algorithm is presented by which the set of all efficient solutions for a linear multiple-objective transportation problem can be enumerated. First the algorithm determines an initial efficient basic solution. In a second step all efficient basic solutions are enumerated. Finally, the set of all efficient solutions is constructed as a union of a minimal number of convex sets of efficient solutions. The algorithm is illustrated by a numerical example.     

被动式寻的导弹的目标自适应制导算法

主要解决以下两个问题 :一是在仅有角度信息的被动制导中如何获得距离信息 ;二是对攻击点的选择问题作了初步的探索 ,在获得距离信息的基础上 ,利用交战双方几何关系实现目标自适应制导算法 ,解决在红外被动制导中跟踪点和攻击点不同的问题。文末给出实验仿真结果及分析