区间数与灰决策的作战效能评估模型

针对作战效能评估过程中评价指标值同时存在精确数、区间数和语言类模糊数的情况,引入区间数与灰决策原理,提出了一种基于区间数与灰决策的作战效能评估模型。结合案例分析,对模型合理性进行验证,结果表明,该模型能够真实地反映武器装备作战效能的综合评估值。     

Due-date assignment and early/tardy scheduling on identical parallel machines

This article examines the problem of simultaneously assigning a common due date to a set of independent jobs and scheduling them on identical parallel machines in such a way that the costs associated with the due date and with the earliness or tardiness of the jobs are minimized. We establish that, for certain values of the due-date cost, an optimal schedule for this problem is also optimal for an early/tardy scheduling problem studied by Emmons. We discuss the solution properties for the two problems, and show that both problems are NP-hard even for two machines. We further show that these problems become strongly NP-hard if the number of machines is allowed to be arbitrary. We provide a dynamic programming solution for the problems, the complexity of which indicates that the problems can be solved in pseudopolynomial time as long as the number of machines remains fixed. Finally, we present the results of a limited computational study. © 1994 John Wiley & Sons, Inc.     

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.     

A finite descent theory for linear programming,piecewise linear convex minimization,and the linear complementarity problem

A descent algorithm simultaneously capable of solving linear programming, piecewise linear convex minimization, and the linear complementarity problem is developed. Conditions are given under which a solution can be found in a finite number of iterations using the geometry of the problem. A computer algorithm is developed and test problems are solved by both this method and Lemke's algorithm. Current results indicate a decrease in the number of cells visited but an increase in the total number of pivots needed to solve the problem.     

一类高次多项式系统极限环讨论及其应用

本文讨论了一类高次多项式系统极限环的存在唯一性,分析了系统的分枝,解决了系统的极限环的个数和分布问题,应用所得的结果,推广并改进了前人的结果。     

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.     

Transformations of node‐balanced routing problems

This article describes a polynomial transformation for a class of unit‐demand vehicle routing problems, named node‐balanced routing problems (BRP), where the number of nodes on each route is restricted to be in an interval such that the workload across the routes is balanced. The transformation is general in that it can be applied to single or multiple depot, homogeneous or heterogeneous fleet BRPs, and any combination thereof. At the heart of the procedure lies transforming the BRP into a generalized traveling salesman problem (TSP), which can then be transformed into a TSP. The transformed graph exhibits special properties which can be exploited to significantly reduce the number of arcs, and used to construct a formulation for the resulting TSP that amounts to no more than that of a constrained assignment problem. Computational results on a number of instances are presented. © 2015 Wiley Periodicals, Inc. Naval Research Logistics 62: 370–387, 2015     

Using grasp to solve the component grouping problem

Component grouping problems, a type of set-partitioning problem, arise in a number of different manufacturing and material logistics application areas. For example, in circuit board assembly, robotic work cells can be used to insert components onto a number of different types of circuit boards. Each type of circuit board requires particular components, with some components appearing on more than one type. The problem is to decide which components should be assigned to each work cell in order to minimize the number of visits by circuit boards to work cells. We describe two new heuristics for this problem, based on so-called greedy random adaptive search procedures (GRASP). With GRASP, a local search technique is replicated many times with different starting points. The starting points are determined by a greedy procedure with a probabilistic aspect. The best result is then kept as the solution. Computational experiments on problems based on data from actual manufacturing processes indicate that these GRASP methods outperform, both in speed and in solution quality, an earlier, network-flow-based heuristic. We also describe techniques for generating lower bounds for the component grouping problem, based on the combinatorial structure of a problem instance. The lower bounds for our real-world test problems averaged within 7%-8% of the heuristic solutions. Similar results are obtained for larger, randomly generated problems. © 1994 John Wiley & Sons. Inc.     

Two‐machine flow shop scheduling with common due window to minimize weighted number of early and tardy jobs

This article studies two due window scheduling problems to minimize the weighted number of early and tardy jobs in a two‐machine flow shop, where the window size is externally determined. These new scheduling models have many practical applications in real life. However, results on these problems have rarely appeared in the literature because of a lack of structural and optimality properties for solving them. In this article, we derive several dominance properties and theorems, including elimination rules and sequencing rules based on Johnsos order, lower bounds on the penalty, and upper bounds on the window location, which help to significantly trim the search space for the problems. We further show that the problems are NP‐hard in the ordinary sense only. We finally develop efficient pseudopolynomial dynamic programming algorithms for solving the problems. © 2009 Wiley Periodicals, Inc. Naval Research Logistics, 2009     

Computational techniques for optimizing systems with standby redundancy

Three methods are used to solve the following problem: For P, a positive constant, maximize (P. Reliability-cost) of a system with standby redundancy. The results show that a method which rounds a noninteger solution to the nearest integer solution can lead to tremendous mistakes. However, neither a well known dynamic programming algorithm nor a previously developed branch and bound technique are able to solve large size problems. The solution of problems of large dimension thus requires the use of the noninteger solution of the first method to limit the number of possible solutions when using either the dynamic programming algorithm or a modified branch and bound technique. With this assistance, the branch and bound technique is able to solve large problems in a short amount of computational time.     

Numerical treatment of a class of semi-infinite programming problems

Many optimization problems occur in both theory and practice when one has to optimize an objective function while an infinite number of constraints must be satisfied. The aim of this paper in to describe methods of handling such problems numerically in an effective manner. We also indicate a number of applications.     

Solving multifacility location problems involving euclidean distances

This paper considers the problem of locating multiple new facilities in order to minimize a total cost function consisting of the sum of weighted Euclidean distances among the new facilities and between the new and existing facilities, the locations of which are known. A new procedure is derived from a set of results pertaining to necessary conditions for a minimum of the objective function. The results from a number of sample problems which have been executed on a programmed version of this algorithm are used to illustrate the effectiveness of the new technique.     

基于压力间断解析解对AUSM -up格式的修正*

AUSM -up格式是AUSM类系列格式中最完善的,通过在对流通量中引入压力耗散,同时在压力通量中引入速度耗散,使之在各种马赫数下均有良好的收敛性和稳定性。然而,通过对格式的分析,我们发现当马赫数为零时,在压力间断位置会出现质量通量无穷大的非物理现象。为了克服这一缺陷,采用特征线法获得了压力间断问题的解析解;以此为基础,对对流通量中的压力耗散项进行修正,发展出新的AUSM -up格式。以新的格式对不同速度驱动下的冲击波发展、不同强度压力间断问题和激波衍射问题进行了仿真,计算结果与理论解吻合得较好。     

应用压力间断解析解修正AUSM+-up格式

AUSM+-up格式是近年来发展的AUSM类格式,通过在对流通量中引入压力耗散,同时在压力通量中引入速度耗散,使之在各种马赫数下均有良好的收敛性和稳定性。然而,通过对格式的分析,我们发现当马赫数为零时,在压力间断位置会出现质量通量无穷大的非物理现象。为了克服这一缺陷,采用特征线法获得了压力间断问题的解析解;以此为基础,对对流通量中的压力耗散项进行修正,发展出新的AUSM+-up格式。以新的格式对不同速度驱动下的冲击波发展、不同强度压力间断问题和激波衍射问题进行了仿真,计算结果与理论解吻合得较好。     

基于模糊多属性决策的威胁度评估与排序研究

应用模糊多属性决策理论与方法,提出一种对多批目标威胁度大小综合评估和排序的方法。此方法用模糊集和模糊数来定义和表述问题,应用模糊多属性决策方法和模糊算法实现威胁度评估并排序,使结果更能逼近于真实的空中态势状态,有利于现代实战环境中实现作战指挥决策的科学化。     

A hard knapsack problem

In this article we develop a class of general knapsack problems which are hard for branch and bound algorithms. The number of alternate optimal solutions for these problems grows exponentially with problem parameters. In addition the LP bound is shown to be ineffective. Computational tests indicate that these problems are truly difficult for even very small problems. Implications for the testing of algorithms using randomly generated problems is discussed.     

Locating facilities in three-dimensional space by convex programming

We consider the problem of simultaneously locating any number of facilities in three-dimensional Euclidean space. The criterion to be satisfied is that of minimizing the total cost of some activity between the facilities to be located and any number of fixed locations. Any amount of activity may be present between any pair of the facilities themselves. The total cost is assumed to be a linear function of the inter-facility and facility-to-fixed locations distances. Since the total cost function for this problem is convex, a unique optimal solution exists. Certain discontinuities are shown to exist in the derivatives of the total cost function which previously has prevented the successful use of gradient computing methods for locating optimal solutions. This article demonstrates the use of a created function which possesses all the necessary properties for ensuring the convergence of first order gradient techniques and is itself uniformly convergent to the actual objective function. Use of the fitted function and the dual problem in the case of constrained problems enables solutions to be determined within any predetermined degree of accuracy. Some computation results are given for both constrained and unconstrained problems.     

进城农民工子女教育问题探析

当前,随着进城务工农民数量的不断增加,跟随其进城的子女也越来越多。农民在自己进城落脚的同时,却无力解决孩子进城就读将要面临的诸多现实问题,结果造成部分进城儿童无法得到足够和平等的教育机会,只能进入农民工子弟学校就学。总体来说,由于受教育体制、观念、教育经费等多种因素的制约,进城农民工子女的教育问题已成为一项重大社会问题。本文通过对进城农民工子女教育现状的描述找出问题,并对这些问题产生的原因以及解决的对策进行了初步探讨。     

多载荷识别频响函数矩阵求逆法的改进算法

分析了频响函数矩阵求逆法在多载荷识别中存在的问题 ,提出了两种改进算法 ,即算术平均法和条件数加权平均法。实验结果表明 ,这两种方法在识别精度和消除病态影响方面均优于传统的频域识别方法。     

Exploiting self‐canceling demand point aggregation error for some planar rectilinear median location problems

When solving location problems in practice it is quite common to aggregate demand points into centroids. Solving a location problem with aggregated demand data is computationally easier, but the aggregation process introduces error. We develop theory and algorithms for certain types of centroid aggregations for rectilinear 1‐median problems. The objective is to construct an aggregation that minimizes the maximum aggregation error. We focus on row‐column aggregations, and make use of aggregation results for 1‐median problems on the line to do aggregation for 1‐median problems in the plane. The aggregations developed for the 1‐median problem are then used to construct approximate n‐median problems. We test the theory computationally on n‐median problems (n ≥ 1) using both randomly generated, as well as real, data. Every error measure we consider can be well approximated by some power function in the number of aggregate demand points. Each such function exhibits decreasing returns to scale. © 2003 Wiley Periodicals, Inc. Naval Research Logistics 50: 614–637, 2003.