Solution of minisum and minimax location–allocation problems with Euclidean distances

A new method for the solution of minimax and minisum location–allocation problems with Euclidean distances is suggested. The method is based on providing differentiable approximations to the objective functions. Thus, if we would like to locate m service facilities with respect to n given demand points, we have to minimize a nonlinear unconstrained function in the 2m variables x₁,y₁, ?,x_m,y_m. This has been done very efficiently using a quasi-Newton method. Since both the original problems and their approximations are neither convex nor concave, the solutions attained may be only local minima. Quite surprisingly, for small problems of locating two or three service points, the global minimum was reached even when the initial position was far from the final result. In both the minisum and minimax cases, large problems of locating 10 service facilities among 100 demand points have been solved. The minima reached in these problems are only local, which is seen by having different solutions for different initial guesses. For practical purposes, one can take different initial positions and choose the final result with best values of the objective function. The likelihood of the best results obtained for these large problems to be close to the global minimum is discussed. We also discuss the possibility of extending the method to cases in which the costs are not necessarily proportional to the Euclidean distances but may be more general functions of the demand and service points coordinates. The method also can be extended easily to similar three-dimensional problems.     

A note on sojourn times in M/G/1 queues with instantaneous,bernoulli feedback

Queueing systems which include the possibility for a customer to return to the same server for additional service are called queueing systems with feedback. Such systems occur in computer networks for example. In these systems a chosen customer will wait in the queue, be serviced and then, with probability p, return to wait again, be serviced again and continue this process until, with probability (1 – p) = q, it departs the system never to return. The time of waiting plus service time, the nth time the customer goes through, we will call his nth sojourn time. The (random) sum of these sojourn times we will call the total sojourn time (abbreviated, sojourn time when there is no confusion which sojourn time we are talking about). In this paper we study the total sojourn time in a queueing system with feedback. We give the details for M/G/1 queues in which the decision to feedback or not is a Bernoulli process. While the details of the computations can be more difficult, the structure of the sojourn time process is unchanged for the M/G/1 queue with a more general decision process as will be shown. We assume the reader is familiar with Disney, McNickle and Simon [1].     

基于攻击图的计算机网络攻击建模方法

随着计算机网络入侵技术的不断发展,网络攻击行为表现出不确定性、复杂性和多样性等特点,攻击向大规模、协同化和多层次方向发展,计算机网络攻击建模已成为当前研究的热点.综合论述计算机网络攻击建模的研究概况,剖析网络攻击图的定义,讨论现有的典型网络攻击图的主要生成方法并对其进行复杂性分析,在此基础上归纳总结目前网络攻击图的应用.给出网络攻击图研究的若干热点问题与展望.     

油-水旋流器流场数值模拟研究

采用改进后的双方程湍流模型和SIMPLE计算方法,对切流式单入口油-水旋流器内部流场进行了模拟研究。结果表明:旋流器内部三维流场各向异性,即同一位置流体在不同方向的流动参数变化很大,流体质点在不同条件下的运动轨迹、速度、分离特性等方面都有较大差别;圆柱段与圆锥段的流场在柱锥结合面发生变化,旋流器的主要分离过程在圆锥段完成;单入口旋流器的流场中心与几何中心有偏差,对流场的稳定和分离会产生影响。该模拟结果与他人所做实验结果比较接近,说明该模型和算法是可靠的,为旋流器的实际应用提供了参考。     

单像自标定的迭代优化方法

针对基于灭点的单像自标定方法精度不高的局限性,利用影像中的灭点和椭圆几何约束信息,提出一种迭代优化的单像自标定方法。根据极点-极线关系及其表示的正交性,由影像中的椭圆曲线及其所在平面的灭线确定一组正交共轭灭点对。利用这些正交共轭灭点对建立关于主距和主点的非线性模型,以主距的方差最小作为优化准则,并选用多个位置作为主点的初始值进行多次迭代优化估计,获得主距和主点的最优结果。仿真影像和真实影像实验结果表明,该方法能够有效地实现单像自标定。与基于灭点的摄像机标定方法相比,该方法能够获得更为满意的标定结果。     

A queueing system with multiple service time distributions

This paper explores a modification of the output discipline for the Poisson input, exponential output, single channel, first-come, first-served queueing system. Instead, the service time distribution of customers beginning service when alone in the system is considered different from that governing service times of all other customers. More specifically, the service times of lone customers are governed by a one parameter gamma distribution, while the service times of all other customers are exponentially ajstributed. The generating function for the steady-state probsbilities, n_j = Pr { j customers in system at an arbitrary point of departure}, of the imbedded chain, {X_n/X_n = number in system after nth customer is serviced}, is obtained, and the steady-state probabilities, themselves, are found in closed form.     

舰用锅炉胀接结构可靠性与后退式胀管器的应用

针对舰用锅炉换热管与管板胀接结构可靠性,分析了影响胀接的主要因素,运用弹性理论对胀接结构进行了理论分析,并首次对舰用锅炉应用双轴承后退式胀管器进行管子与管板试件的胀接试验研究,推导出适合机械式胀接的胀管率近似理论计算方法.     

Stochastic call center staffing with uncertain arrival,service and abandonment rates: A Bayesian perspective

In this article, we introduce staffing strategies for the Erlang‐A queuing system in call center operations with uncertain arrival, service, and abandonment rates. In doing so, we model the system rates using gamma distributions that create randomness in operating characteristics used in the optimization formulation. We divide the day into discrete time intervals where a simulation based stochastic programming method is used to determine staffing levels. More specifically, we develop a model to select the optimal number of agents required for a given time interval by minimizing an expected cost function, which consists of agent and abandonment (opportunity) costs, while considering the service quality requirements such as the delay probability. The objective function as well as the constraints in our formulation are random variables. The novelty of our approach is to introduce a solution method for the staffing of an operation where all three system rates (arrival, service, and abandonment) are random variables. We illustrate the use of the proposed model using both real and simulated call center data. In addition, we provide solution comparisons across different formulations, consider a dynamic extension, and discuss sensitivity implications of changing constraint upper bounds as well as prior hyper‐parameters. © 2016 Wiley Periodicals, Inc. Naval Research Logistics 63: 460–478, 2016     

Note: Facility location with closest rectangular distances

This paper considers the problem of locating one or more new facilities on a continuous plane, where the destinations or customers, and even the facilities, may be represented by areas and not points. The objective is to locate the facilities in order to minimize a sum of transportation costs. What is new in this study is that the relevant distances are the distances from the closest point in the facility to the closest point in the demand areas. © 2000 John Wiley & Sons, Inc. Naval Research Logistics 47: 77–84, 2000     

用动网格法计算理想平板的颤振导数

提出了一种数值模拟振动的理想平板绕流场 ,并提取其气动导数的方法。时间相关的不可压N S方程采用Projetion 2格式解耦 ,关于中间速度的动量方程的时间和空间离散采用二阶半隐格式 ,压力Possion方程迭代用多层网格法加速收敛。分别计算平板作竖向强迫振动或扭转强迫振动的气动力 ,用动网格法考虑平板和气流的耦合作用。由计算得到的气动力用最小二乘法确定 8个气动导数。计算结果和理想平板的Theodorsen理论值有较好的一致性     

A note on equity across groups in facility location

An equity model between groups of demand points is proposed. The set of demand points is divided into two or more groups. For example, rich and poor neighborhoods and urban and rural neighborhoods. We wish to provide equal service to the different groups by minimizing the deviation from equality among groups. The distance to the closest facility is a measure of the quality of service. Once the facilities are located, each demand point has a service distance. The objective function, to be minimized, is the sum of squares of differences between all pairs of service distances between demand points in different groups. The problem is analyzed and solution techniques are proposed for the location of a single facility in the plane. Computational experiments for problems with up to 10,000 demand points and rectilinear, Euclidean, or general ?_p distances illustrate the efficiency of the proposed algorithm. © 2011 Wiley Periodicals, Inc. Naval Research Logistics, 2011     

Approximating the nondominated frontiers of multi‐objective combinatorial optimization problems

Finding all nondominated vectors for multi‐objective combinatorial optimization (MOCO) problems is computationally very hard in general. We approximate the nondominated frontiers of MOCO problems by fitting smooth hypersurfaces. For a given problem, we fit the hypersurface using a single nondominated reference vector. We experiment with different types of MOCO problems and demonstrate that in all cases the fitted hypersurfaces approximate all nondominated vectors well. We discuss that such an approximation is useful to find the neighborhood of preferred regions of the nondominated vectors with very little computational effort. Further computational effort can then be spent in the identified region to find the actual nondominated vectors the decision maker will prefer. © 2009 Wiley Periodicals, Inc. Naval Research Logistics, 2009     

One-facility location with rectilinear tour distances

This article concerns the location of a facility among n points where the points are serviced by “tours” taken from the facility. Tours include m points at a time and each group of m points may become active (may need a tour) with some known probability. Distances are assumed to be rectilinear. For m ≤ 3, it is proved that the objective function is separable in each dimension and an exact solution method is given that involves finding the median of numbers appropriately generated from the problem data. It is shown that the objective function becomes multimodal when some tours pass through four or more points. A bounded heuristic procedure is suggested for this latter case. This heuristic involves solving an auxiliary three-point tour location problem.     

作战文书自动生成系统中内容规划的设计

作战文书拟制是 C3I系统中的重要工作 ,利用自然语言生成理论实现作战文书的自动生成可大大提高文书拟制的效率。通过对大量作战文书文本的仔细分析 ,构造出各类作战文书的 Schem a库 ,并以扩充转移网络图表示。遍历该网络图 ,利用 Schema上的修辞谓词从知识抽取相应的知识 ,便可构造出文书内容。     

直接瞄准射击提前量实测法的理论跟踪误差

本文分析了直接瞄准射击中用实测法确定提前量产生理论跟踪误差的原因,推导了一个计算此项误差的近似公式,利用此公式讨论了理论跟踪误差的变化规律及影响因素,并讨论了减小此项误差的措施.本文也提出了精确计算理论跟踪误差的方法,并实际计算了装有火控系统对运动目标射击时的理论跟踪误差,从而讨论了装有火控系统的坦克是否需要修正此项误差.     

Approximate decision rules for continuous review inventory systems

Constrained multi-item inventory models have long presented signifcant computational problems. This article presents a general algorithm to obtain simultaneous solutions for order quantities and safety stocks for each line item in an inventory, while satisfying constraints on average inventory investment and reordering workload. Computational experience is presented that demonstrates the algorithm's efficiency in handling large-scale applications. Decision rules for several customer service objectives are developed, with a discussion of the characteristics of the inventory systems in which each objective would be most appropriate. The decision rules are approximations, based on the assumptions commonly used in practice.     

Geometric programming with multiplicative slack variables

A posynomial geometric programming problem formulated so that the number of objective function terms is equal to the number of primal variables will have a zero degree of difficulty when augmented by multiplying each constraint term by a slack variable and including a surrogate constraint composed of the product of the slack variables, each raised to an undetermined negative exponent or surrogate multiplier. It is assumed that the original problem is canonical. The exponents in the constraint on the product of the slack variables must be estimated so that the associated solution to the augmented problem, obtained immediately, also solves the original problem. An iterative search procedure for finding the required exponents, thus solving the original problem, is described. The search procedure has proven quite efficient, often requiring only two or three iterations per degree of difficulty of the original problem. At each iteration the well-known procedure for solving a geometric programming problem with a zero degree of difficulty is used and so computations are simple. The solution generated at each iteration is optimal for a problem which differs from the original problem only in the values of some of the constraint coefficients, so intermediate solutions provide useful information.     

Optimal control of entry to an M/Ek/1 queue serving several classes of customers

The individual and social optimum control policies for entry to an M/M//1 queue serving several classes of customers have been shown to be control-limit policies. The technique of policy iteration provides the social optimum policy for such a queue in a straightforward manner. In this article, the problem of finding the optimal control policy for the M/E_k/1 system is solved, thereby expanding the potential applicability of the solutions developed. The Markovian nature of the queueing system is preserved by considering the service as having k sequential phases, each with independent, identically distributed, exponential service times, through which a customer must pass to be serviced. The optimal policy derived by policy iteration for such a system is likely to be difficult to use because it requires knowledge of the number of phases rather than customers in the system when an arrival occurs. To circumvent this difficulty, a heuristic is used to find a good usable (implementable) solution. In addition, a mixed-integer program is developed which yields the optimal implementable solution when solved.     

实时位置反馈的多机器人主从式编队控制

提出了一种基于反馈控制的多机器人的编队控制方法,能够使主从机器人在相对运动时保持期望的角度和距离,并且形成稳定的编队结构。然后运用数学图论将单一主从式编队控制扩展到多机器人的编队控制,能够更加简易的实现编队控制和几何形状的变换,最后通过仿真验证了该方法的有效性。     

提高近场精度的海洋声学快速场改进模型

为了提高海洋声学快速场模型在近场区域的计算精度,分析了影响经典快速场模型精度的因素,主要包括Bessel函数近似、忽略内行波项以及在水平距离最远处波数采样率过低,这些因素导致快速场模型近场误差较大、远场水平距离最远处结果不正确(计算结束后需要去除水平距离后段的声场)。提出能够提高经典快速场模型近场计算精度的改进模型,改进部分主要是采用保留内行波项的近似Bessel函数,再将近场上下两个基于声源点与对称轴的三角形区域用波数积分解(使用精确Bessel函数)覆盖。算例测试结果表明:与经典快速场模型相比,改进模型可在绝对时间增加较少的情况下,显著提高近场计算精度,综合性能更优;与波数积分法相比,改进模型在误差为同量级的情况下,积分时间大幅降低,实际应用价值更高。