Approximation algorithms for capacitated stochastic inventory systems with setup costs

We develop the first approximation algorithm with worst‐case performance guarantee for capacitated stochastic periodic‐review inventory systems with setup costs. The structure of the optimal control policy for such systems is extremely complicated, and indeed, only some partial characterization is available. Thus, finding provably near‐optimal control policies has been an open challenge. In this article, we construct computationally efficient approximate optimal policies for these systems whose demands can be nonstationary and/or correlated over time, and show that these policies have a worst‐case performance guarantee of 4. We demonstrate through extensive numerical studies that the policies empirically perform well, and they are significantly better than the theoretical worst‐case guarantees. We also extend the analyses and results to the case with batch ordering constraints, where the order size has to be an integer multiple of a base load. © 2014 Wiley Periodicals, Inc. Naval Research Logistics 61: 304–319, 2014     

A balancing problem for mixed model assembly lines with a paced moving conveyor

We state a balancing problem for mixed model assembly lines with a paced moving conveyor as: Given the daily assembling sequence of the models, the tasks of each model, the precedence relations among the tasks, and the operations parameters of the assembly line, assign the tasks of the models to the workstations so as to minimize the total overload time. Several characteristics of the problem are investigated. A line‐balancing heuristic is proposed based on a lower bound of the total overload time. A practical procedure is provided for estimating the deviation of any given line‐balance solution from the theoretical optimum. Numerical examples are given to illustrate the methodology. © 2004 Wiley Periodicals, Inc. Naval Research Logistics, 2004.     

Steady-state analysis of load balancing with Coxian-2 distributed service times

This paper studies load balancing for many-server (N servers) systems. Each server has a buffer of size b ? 1, and can have at most one job in service and b ? 1 jobs in the buffer. The service time of a job follows the Coxian-2 distribution. We focus on steady-state performance of load balancing policies in the heavy traffic regime such that the normalized load of system is λ = 1 ? N^?α for 0 < α < 0.5. We identify a set of policies that achieve asymptotic zero waiting. The set of policies include several classical policies such as join-the-shortest-queue (JSQ), join-the-idle-queue (JIQ), idle-one-first (I1F) and power-of-d-choices (Po d) with d = O(N^α log N). The proof of the main result is based on Stein's method and state space collapse. A key technical contribution of this paper is the iterative state space collapse approach that leads to a simple generator approximation when applying Stein's method.     

矢量多边形并行栅格化数据划分方法

针对多边形并行栅格化中的负载不均衡问题提出一种新的数据划分方法,主要包括:迭代计算划分线的位置,在每次迭代中保证分块间的计算量大致均衡,完成数据划分、实现负载均衡;提出基于二叉树的划分结果融合策略,以解决跨边界多边形的融合问题。在多核CPU环境下实现并行算法,选用多个典型土地利用现状数据集进行测试。结果表明:针对不同类型多边形数据集,所提方法较传统方法可获得更高的并行加速比和更好的负载均衡;针对大数据量数据集,以多边形节点数为度量标准可更精确地估算分块计算量,从而更好地实现负载均衡。     

基于流量均衡和跨层技术的星群路由算法

针对分布式星群网络业务通信QoS不高的问题,提出了一种基于流量均衡和跨层技术的分布式星群网络路由算法(TACA)。该算法首先通过跨层技术将物理层、MAC层的相关信息搜集起来,作为判断链路负载状况的依据;然后对不同类型的业务进行分类,根据链路负载状况和业务QoS级别选择不同的路由层次,从而均衡流量以提高QoS。仿真表明,该路由算法在一定程度上降低了星群的呼叫阻塞率和切换阻塞率,平衡了网络的负载,提高了网络吞吐量。     

一种航天侦察任务-资源匹配的负载均衡方法

当前航天侦察任务预处理方法一般仅从任务需求的角度考虑资源分配问题,容易导致负载不均衡,对此提出了一种综合考虑任务需求与资源负载的任务-资源匹配方法.分析了资源负载均衡需要考虑的任务要素以及相应的描述方法,提出用任务执行概率度量卫星资源负载状况,基于任务流模型给出了单任务执行概率的估算公式,并给出了一种简易的多任务执行概...     

一种基于HLA分布式仿真系统的动态负载平衡算法

基于兴趣域的"快递式"动态负载平衡算法从HLA/RTI提供的服务出发,当节点成为重载节点时,将节点部分负载转移到兴趣域内的轻载节点上,同时采用两次"握手"方式解决了负载迁移过程中出现的问题.通过使用两个评价参数--CPU占有率和内存使用率进行实验证明,负载平衡前后重载节点的CPU利用率和内存使用率有明显差别,结果表明该方法能有效地平衡系统各节点之间的负载,保证系统的实时性,提高系统的服务质量.     

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     

装备分布式虚拟维修训练仿真负载平衡研究

基于HLA的装备分布式虚拟维修训练过程极易产生仿真节点负载失衡,以往的负载平衡研究多关注资源利用率,仿真运行过程中可能会因节点负载的不均衡进行频繁的负载调度,影响仿真运行效率.针对此问题,以保证仿真节点的高效运行为首要目的,将负载平衡定义为不存在超载节点即为平衡,提出了一种动静结合的复合式负载平衡调度方法.研究了复合式负载平衡系统的体系结构,采用最小连接调度法实现了节点静态负载的粗粒度平衡,引入仿真运行比率分量参数表征负载量值,进而设计了动态负载平衡算法对仿真运行过程进行实时监控和调度.实验结果表明,改进后仿真平衡调度频率明显下降,实现了资源利用率和仿真效率的平衡兼顾,取得了良好的效果.     

用于动平衡测试的MDAC窄带跟踪滤波器

为了从强干扰噪声中提取出与转速同频的振动分量,且适应转速波动时的情形,利用互相关原理导出了跟踪滤波方法,并采用乘法数模转换器(MDAC)设计并实现了窄带跟踪滤波器。实验结果表明,其增益相对误差优于0.2%,相位绝对误差优于0.4°,当转速变化率不超过9000r/min2时,滤波器的输出能够跟踪转速的变化。该滤波器能较好地满足动平衡测试的需要。